[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/bbcode.php on line 488: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4756: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3891)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4758: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3891)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4759: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3891)
[phpBB Debug] PHP Warning: in file [ROOT]/includes/functions.php on line 4760: Cannot modify header information - headers already sent by (output started at [ROOT]/includes/functions.php:3891)
Dev Skill Forum • View topic - Coding Contest -20 Editorial
Page 1 of 1

Coding Contest -20 Editorial

PostPosted: Mon Apr 02, 2018 10:49 am
by BishalG
Contest Link: https://www.devskill.com/ContestArchive ... d58fa46501
Contest Ranklist: https://www.devskill.com/home/contestra ... d58fa46501


Link: https://devskill.com/CodingProblems/ViewProblem/496
Problem Setter: Bishal Gautam
Alternate Writer: Mahmud Allahverdiyev, Bir Bahadur Khatri

In this problem, you are given a binary string which contains only character '0' or '1'. Your task is to find total sub-strings in given string which consists of only '1'.
As the limit is small, this can be solved fixing starting index of every substring and looping over the remaining part of string till '1' occurs there.

Time Complexity: O( T*N^2 )




Link: https://devskill.com/CodingProblems/ViewProblem/512
Problem Setter: Feodor Volonter
Alternate Writer: Mortadha Touzi, Bishal Gautam

In this problem you have to find the number of closed regions into which three circles divide the plane.
The initial problem can be reduced to the number of intersection points. If this number is zero, then the answer is 3. If this number is 2 then the answer is 4. For four intersection point we have five closed regions and finally for six intersection points we have the answer 7.

Time Complexity: O(1)




Link: https://devskill.com/CodingProblems/ViewProblem/514
Problem Setter: Feodor Volonter
Alternate Writer: Mortadha Touzi, Bishal Gautam

In this problem you have to find the number of possible balanced strings with given beginning.
If L is odd or K > L/2 then the answer is zero. For even value for L we can apply stright DP solution.
Let denote "open" as the number of symbols '(' we can use for constructing balances string and "close" is for possible numbers of symbols ')'.
Then the DP recurrence is:
(1) if( open ) dp[open][close] += rec( open-1, close); // use '('
(2) if( open < close ) dp[open][close] += rec( open, close-1); // use ')'

Time Complexity: O( L^2 )




Link: https://devskill.com/CodingProblems/ViewProblem/502
Problem Setter: Fahim Shahriar Shakkhor
Alternate Writer: MD Musfiqur Rahman Sanim, Mahmud Allahverdiyev , Bir Bahadur Khatri

In this problem, there are 2*N nodes in a graph aligned in 2 rows , each row having N nodes. The nodes of the first row are sequentially numbered from 1 to N. The nodes of the second row are sequentially numbered from N + 1 to 2*N. Each node is connected to the node to its left , right , up and down.The distance between any two adjacent node is 1. We have to compute the all pair shortest path sum !!

At first consider only one row. We will fix a node by coloring it as red and compute all the distances to its right.
Image

Let us denote the total sum as S. S can be written as:
Image

As D(i,j) and D(j,i) is same , we get total sum of distances in a row 2 * S. Now for every (i,j) pair, if we shift the j to the bottom row, all the distances get increased by 1. It means if we choose one node from top row and one node from bottom row, sum for all there pairs will be 2 * S + N2.

So for choosing i from top row and j from any row our total sum becomes 4 * S + N2. We have to do the same for the bottom row. Hence our final answer is 8 * S + 2 * N2.

Time Complexity: O(T * log N)




Link: https://devskill.com/CodingProblems/ViewProblem/513
Problem Setter: Feodor Volonter
Alternate Writer: Mortadha Touzi

In this problem you have to find a full list of charming numbers and perform a binary search on it.

We can generate full list of charming numbers on interval [1...200000000]. In order to exclude the list sorting (about 27M numbers) we can use compact bitset for marking a number as charming. Then on each query we can find the indexes of nearest charming numbers to L-1 and R, the answer is the difference of this two indexes.

Time Complexity: O( 200000000 * log log(200000000) + T * log( 27000000 ) )




Link: https://devskill.com/CodingProblems/ViewProblem/511
Problem Setter: Feodor Volonter
Alternate Writer: Mortadha Touzi

In this problem you have to find the number of positive integer solutions to the specific equation with six variables on very limited interval.

Firstly we should reduce A and B by the general multiplier. Then we can check A and B on the prime factor greater then M. Then we can iterate over all possible values A*x1*x2*x3, counting the number of ways to reach this value. Finally, we can iterate over all possible values B*x4*x5*x6, calculating the answer. We can use hash to speed up solution.

Time Complexity: O( M^3 )

Re: Coding Contest -20 Editorial

PostPosted: Mon Apr 02, 2018 9:05 pm
by feodorv
I beg your pardon, the correct link on "Three Circles" problem is https://devskill.com/CodingProblems/ViewProblem/512.

Re: Coding Contest -20 Editorial

PostPosted: Mon Apr 09, 2018 9:21 am
by BishalG
Thanks @Feodorv, Link is corrected !!