CODEFT05 : BRIGHTEST BRAIN
As both the players play optimally and Misha moves first,:
-
if N is odd then she can pick all the stones and Reet will left with no move and loses.
-
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 : hiYzqO - Online Python3 Interpreter & Debugging Tool - Ideone.com
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 : 9pDqfY - Online C++0x Compiler & Debugging Tool - Ideone.com
CODE : g82nua - Online C++0x Compiler & Debugging Tool - Ideone.com
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 :
-
right or down moves, if point (x1, y1) is to the right or right down to point (x, y).
-
right or up moves, if point (x1, y1) is to the right or right up to point (x, y).
-
left or up moves, if point (x1, y1) is to the left or left up to point (x, y).
-
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 : CY6qYJ - Online C++0x Compiler & Debugging Tool - Ideone.com
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 : KFJUZJ - Online C++0x Compiler & Debugging Tool - Ideone.com (Binary Indexed Tree (Offline))
CODE : ryxyNf - Online C++0x Compiler & Debugging Tool - Ideone.com (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 : Easiest HLD with subtree queries - Codeforces
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 : aiU4wS - Online C++0x Compiler & Debugging Tool - Ideone.com
CODE : I2VdJq - Online C++0x Compiler & Debugging Tool - Ideone.com
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) : Closest Pair of Points using Divide and Conquer algorithm - GeeksforGeeks
CODE : dVACdi - Online Python3 Interpreter & Debugging Tool - Ideone.com
