# Coding Contest -20 Editorial

All contest related discussion goes here. Both Dev Skill and Non Dev Skill contest related discussion is allowed. (But please keep the forum clean)

### Coding Contest -20 Editorial

Contest Ranklist: https://www.devskill.com/home/contestra ... d58fa46501

Problem A: Only '1' Substrings !!
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 )

Problem B: Three Circles
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)

Problem C: Parenthesis
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 )

Problem D: Simple Graph
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. Let us denote the total sum as S. S can be written as: 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)

Problem E: Charming Numbers
Problem Setter: Feodor Volonter

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 ) )

Problem E: Strange Equation
Problem Setter: Feodor Volonter

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 ) Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

### Re: Coding Contest -20 Editorial

I beg your pardon, the correct link on "Three Circles" problem is https://devskill.com/CodingProblems/ViewProblem/512.

Posts: 11
Joined: Thu Jun 15, 2017 3:37 pm

### Re: Coding Contest -20 Editorial

Thanks @Feodorv, Link is corrected !! Posts: 43
Joined: Tue Jan 17, 2017 10:10 pm

Who is online
Users browsing this forum: No registered users and 1 guest 