### Coding Contest-14 Editorial

Posted:

**Mon Apr 10, 2017 2:39 pm**Problem A: Boshir Mishtanno

Link: https://devskill.com/CodingProblems/ViewProblem/277

Problem Setter: Jayed Al Hasan

In this problem, you have to iterate over R and C values to calculate sweets in each layer.

In first layer, there will be R*C sweets.

In second layer, there will be ((R-1)*(C-1)) sweets.

and so on...

So, Just iterate over R and C untill one of them become zeros. Then multiply total counter with price of sweet-15 taka.

Problem B: Again Binary

Link: http://devskill.com/CodingProblems/ViewProblem/262

Problem Setter: Md. Nazmul H Pranto

After simplification of the equation given in the problem statement, your task is to calculate the

binary value of 2^N -2 .

As N is very large, we can not simply convert the equation to binary string and print last 3 digits.

What you can do is: Observe that if N becomes larger then 2 then answer will always be equal to "110".

If N is 2: answer will be "010".

If N is 1 : answer will be "000".

Problem C: Binary Game

Link: http://devskill.com/CodingProblems/ViewProblem/282

Problem Setter: Bishal Gautam

Here, you are given a binary string of length 33. We can reduce problem statement as:

You have to determine the total number of sub-string reversal operations which makes it a binary string in which all 0s are on

left side and all the 1s are on right side( as one can not make lexicographically minimum string by doing same reversal operation on this ).

After finding this number, we can easily say who will win the game.

If this number is odd, "Alice" will win the game, as Alice is a first player. Otherwise, Bob will win the game.

Now, Lets see how to find this total number:

When making a lexicographically minimum string in every step, the chooses pair should always comes from

leftmost index as leftmost 1 position and rightmost should come from one of the 0s block.

Let us consider we have total K zeros blocks after leftmost 1.

But, here we are not sure, which 0s block's rightmost index we should choose.

Lets assume, we find that one also. Then after reversing the sub-string generated by left and right index ,

we again encounter same situation but total options of 0s block will be K-1 at this time..and so on.

So, overall total number of game playing will be equivalent to total numbers of 0s block in given string.

Here, we can easily loop over string to find that number.

So, overall complexity of the problem is O( TC*33 ).

Considering problem-C, We also allowed O(TC*33*Constant) solution to pass also.

So, Selecting two leftmost 1 and rightmost 0 and reversing them will also get Accepted.

Problem D: Bitwise Recursion

Link: http://devskill.com/CodingProblems/ViewProblem/1299

Problem Setter: Suman Bhadra

First of all, the given expression ((n OR m) AND (n XOR m)) is same as the expression (n XOR m). We can check it by truth table.

Secondly, if we observe the recursion , it is easy to understand that we have to calculate the value of summation of (i XOR j)

where 1<=i<=n && 1<=j<=n.

Now we can calculate all the answer offline preprocessing by sorting the given inputs. We can count the number of bits in

each position up to n. then if in position x number of zero and one are p and q.

then we add to the answer p*q*(1<<x).

Complexity of the preprocessing is O(n*16).

Problem D: Motku2

Link: http://devskill.com/CodingProblems/ViewProblem/176

Problem Setter: Bir Bahadur Khatri

For each query (given u and k), need to find a node v such that distance from u to v is exactly k and sum of values at that path is minimum.

Naive Solution:

We can run a DFS keeping root u and Keep the array which stores sum of values in the path from root to node v. For the same distance node form u, this array will keep the minimum sum among many if possible. Now for each query which starts from u and having various distances can be answered by looking the stored array value. Of course complexity is O (n*n), where n is number of nodes in tree.

Expected Solution:

For each query, actually the problem need to find a pair of noses (u, v) whose starting node is u and ending at v such that Dist (u, v) =k. So we can solve this problem using Centroid Decomposition in offline.

If you are unknown about this please learn from [ https://threads-iiith.quora.com/Centroi ... -of-a-Tree ] and solve the some basic problems from the provided link.

We pick the centroid as the root r and find the number of paths passing through r. Then, the other paths won't pass through r, so we can remove r and split the tree into more sub trees, and recursively solve for each sub tree as well. While processing, for particular centroid r, we keep the array table like above which stores sum from centroid node r to particular nodes. Among many same distance nodes from centroid to nodes we stores only minimum sum of values at that path. While processing query such that which starts from node u (let) which have following properties.

Distance between centroid to this node= L.

Sum of values of node from centroid to this node =S.

For some length k from this node we have to find the node at a distance k-L from Centroid.

So answer is S + Sum [K-L]; here Sum is array which stores sum from centroid to particular node.

Make sure that K-L is positive always.

Complexity:

Since each subtree is at most half the size of the original tree, and the time taken to solve the problem where the path must pass through the root for a single tree takes time proportional to the size of the tree, this solution works in O(nlogn)

Link: https://devskill.com/CodingProblems/ViewProblem/277

Problem Setter: Jayed Al Hasan

In this problem, you have to iterate over R and C values to calculate sweets in each layer.

In first layer, there will be R*C sweets.

In second layer, there will be ((R-1)*(C-1)) sweets.

and so on...

So, Just iterate over R and C untill one of them become zeros. Then multiply total counter with price of sweet-15 taka.

Problem B: Again Binary

Link: http://devskill.com/CodingProblems/ViewProblem/262

Problem Setter: Md. Nazmul H Pranto

After simplification of the equation given in the problem statement, your task is to calculate the

binary value of 2^N -2 .

As N is very large, we can not simply convert the equation to binary string and print last 3 digits.

What you can do is: Observe that if N becomes larger then 2 then answer will always be equal to "110".

If N is 2: answer will be "010".

If N is 1 : answer will be "000".

Problem C: Binary Game

Link: http://devskill.com/CodingProblems/ViewProblem/282

Problem Setter: Bishal Gautam

Here, you are given a binary string of length 33. We can reduce problem statement as:

You have to determine the total number of sub-string reversal operations which makes it a binary string in which all 0s are on

left side and all the 1s are on right side( as one can not make lexicographically minimum string by doing same reversal operation on this ).

After finding this number, we can easily say who will win the game.

If this number is odd, "Alice" will win the game, as Alice is a first player. Otherwise, Bob will win the game.

Now, Lets see how to find this total number:

When making a lexicographically minimum string in every step, the chooses pair should always comes from

leftmost index as leftmost 1 position and rightmost should come from one of the 0s block.

Let us consider we have total K zeros blocks after leftmost 1.

But, here we are not sure, which 0s block's rightmost index we should choose.

Lets assume, we find that one also. Then after reversing the sub-string generated by left and right index ,

we again encounter same situation but total options of 0s block will be K-1 at this time..and so on.

So, overall total number of game playing will be equivalent to total numbers of 0s block in given string.

Here, we can easily loop over string to find that number.

So, overall complexity of the problem is O( TC*33 ).

Considering problem-C, We also allowed O(TC*33*Constant) solution to pass also.

So, Selecting two leftmost 1 and rightmost 0 and reversing them will also get Accepted.

Problem D: Bitwise Recursion

Link: http://devskill.com/CodingProblems/ViewProblem/1299

Problem Setter: Suman Bhadra

First of all, the given expression ((n OR m) AND (n XOR m)) is same as the expression (n XOR m). We can check it by truth table.

Secondly, if we observe the recursion , it is easy to understand that we have to calculate the value of summation of (i XOR j)

where 1<=i<=n && 1<=j<=n.

Now we can calculate all the answer offline preprocessing by sorting the given inputs. We can count the number of bits in

each position up to n. then if in position x number of zero and one are p and q.

then we add to the answer p*q*(1<<x).

Complexity of the preprocessing is O(n*16).

Problem D: Motku2

Link: http://devskill.com/CodingProblems/ViewProblem/176

Problem Setter: Bir Bahadur Khatri

For each query (given u and k), need to find a node v such that distance from u to v is exactly k and sum of values at that path is minimum.

Naive Solution:

We can run a DFS keeping root u and Keep the array which stores sum of values in the path from root to node v. For the same distance node form u, this array will keep the minimum sum among many if possible. Now for each query which starts from u and having various distances can be answered by looking the stored array value. Of course complexity is O (n*n), where n is number of nodes in tree.

Expected Solution:

For each query, actually the problem need to find a pair of noses (u, v) whose starting node is u and ending at v such that Dist (u, v) =k. So we can solve this problem using Centroid Decomposition in offline.

If you are unknown about this please learn from [ https://threads-iiith.quora.com/Centroi ... -of-a-Tree ] and solve the some basic problems from the provided link.

We pick the centroid as the root r and find the number of paths passing through r. Then, the other paths won't pass through r, so we can remove r and split the tree into more sub trees, and recursively solve for each sub tree as well. While processing, for particular centroid r, we keep the array table like above which stores sum from centroid node r to particular nodes. Among many same distance nodes from centroid to nodes we stores only minimum sum of values at that path. While processing query such that which starts from node u (let) which have following properties.

Distance between centroid to this node= L.

Sum of values of node from centroid to this node =S.

For some length k from this node we have to find the node at a distance k-L from Centroid.

So answer is S + Sum [K-L]; here Sum is array which stores sum from centroid to particular node.

Make sure that K-L is positive always.

Complexity:

Since each subtree is at most half the size of the original tree, and the time taken to solve the problem where the path must pass through the root for a single tree takes time proportional to the size of the tree, this solution works in O(nlogn)