CoDeft Editorial

CONTEST LINK

CODEFT05 : BRIGHTEST BRAIN

As both the players play optimally and Misha moves first,:

  1. if N is odd then she can pick all the stones and Reet will left with no move and loses.

  2. If N is even Misha can pick N-1 number of stones (as it is odd) and Reet will left with one stone and and cannot pick that stone being odd and loses.

So in both cases Misha can always win if she moves optimally.

So simply print 1 irrespective of N.

CODE : https://ideone.com/hiYzqO

CODEFT02 : Hash it, Cash it!

We need to choose a subset from given N strings such that we can form all the strings of the chosen subset from the given string S. Firstly we can maintain an array which contains frequency of all the characters in string S (Let’s call it array h). Also we can maintain a frequency array of Nx26 (let’s call it Freq array) which contains frequency of every character of i th string . As N is quite low we can generate all the subsets and check that the frequency of all the characters in the chosen subset is less that or equal to the characters frequency in S(i.e. in array h).

CODE : https://ideone.com/9pDqfY

CODE : https://ideone.com/g82nua

CODEFT11 : Ding Ding Ding Ding…

If you observe the problem a bit, it is similiar to finding the number of ways to reach from (0, 0) to (n, m) in a grid. So we can use one of the following below moves :

  1. right or down moves, if point (x1, y1) is to the right or right down to point (x, y).

  2. right or up moves, if point (x1, y1) is to the right or right up to point (x, y).

  3. left or up moves, if point (x1, y1) is to the left or left up to point (x, y).

  4. left or down moves, if point (x1, y1) is to the left or left down to point (x, y).

We can see that all above four types of above described moves are symmetric for this problem and we can simply find the number of ways to make n moves (where n = abs(x-x1) + abs(y-y1)) from the given point (x, y) to reach (x1,y1) using exactly one type of the four moves described above, which is (n! / (abs(x-x1)! * abs(y-y1)!)) (NCR).

CODE : https://ideone.com/CY6qYJ

CODEFT07 : Subtree Summation

Problem : For every node x we need to find the summation of all the elements which are less than A[x] in the subtree of x.

We can convert the tree into array using dfs and maintain an index array (let’s call it idx) and subtree size array which contains the number of nodes in the subtree of node x(let’s call it sz). So the left and right indexes of subarray which contains elements of the subtree of node x is l = idx[x] + 1, r = idx[x] + sz[x] – 1 (If l > r, then x is a leaf node so it will not add anything to our answer). Now the problem reduces to finding the number of elements that are less than a specific value Y in the subarray l to r, which can be done using Merge sort tree. A bit easier solution is using Binary Indexed Tree.

CODE : https://ideone.com/KFJUZJ (Binary Indexed Tree (Offline))

CODE : https://ideone.com/ryxyNf (Merge Sort Tree)

CODEFT13 : HOUSE OF QUERIES :

Use the DFS traversal of tree to convert the tree into an array; for every node: store it’s distance from the root, size of the subtree, and the in-time for each node.

Blog : https://codeforces.com/blog/entry/53170

We will store the new position( array equivalent of the tree) of node at a distance ‘i’ from root node, in a 2D Vector at index i. We will use N-BIT(Fenwick) each corresponding to distance i from the root, to store prefix sum of the values.

Now the nodes at a distance ‘K’ from a node X will be at a distance of ‘K+dist[X]’ from the root node.

But the queries we need to consider the nodes only in the subtree of X. These nodes in the array equivalent will lie in the index range : [in-time of node X, ( in-time of node X ) + (Size of subtree X ]

We will binary-search to find how many nodes at distance ‘K+dist[X] ‘

lie in the range [in-time of node X, ( in-time of node X ) + (Size of subtree X ] and use BIT to get the prefix sum.

CLEAN CODE : https://ideone.com/aiU4wS
CODE : https://ideone.com/I2VdJq

CODEFT17 : Space Tourism

The sadness due to prefix sum(Distance) between the two planets can be represented as X and the sadness due to prefix sum(Tax paid) can be represented as Y.

Thus, each planet can be uniquely represented as a point on a 2D plane with co-ordinates (X,Y).

Now mimimum dis(i,j)2 + tax(i,j)2 can be found by finding the square of the minimum distance between 2 points on the plane.

This can be done in O(N(logN)^2) : https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/

CODE : https://ideone.com/dVACdi

7 Likes

I couldnt even see the contest
can someone pls send me the link
thanks

2 Likes

The editorial of the last problem seems wrong. Each planet is not to be represented as a point of (distance, tax) but rather as a point of (prefix sum of distance, prefix sum of tax). And also in the code, you are using the O(N log N) method of finding the closest pair of points.

1 Like

Hi, O(N(logN)^2) is also an acceptable solution.
I have added the prefix sums in the editorial to make it more clear.

I solved the question: [House of Queries] using sparse table. Have a look at my code:

code

1 Like

Nice ProblemSet!
When can we submit the problems as currently Codechef is not allowing any submissions…

2 Likes

For anyone interested, here’s a problem similar to the last problem: https://codeforces.com/problemset/problem/429/D

3 Likes

Thankyou @roll_no_1 :slight_smile: