N-Special cards:
Question link: https://www.codechef.com/CODE2021?itm_campaign=contest_listing
Quick Approach:
First of all you need to find uncovered positions in s (because rest of them will determine uniquely). If there is no parados in covered positions (a position should have more than one value), then the answer will be 0, otherwise it’s 26uncovered. To check this, you just need to check that no two consecutive matches in s have parados. So, for this purpose, you need to check if a prefix of t is equal to one of its suffixes in O(1). You can easily check this with prefix function (or Z function).
Ashsport
Question link:https://www.codechef.com/CODE2021/problems/CCH4
Quick Approach
Note that if r_i or b_i >= n, we need to collect tokens no matter what since those costs can’t be offset. So, we can assume that r_i, b_i <= n.
Let’s only buy tokens when we need them. Note that after buying a card, you will have either 0 red tokens or 0 blue tokens, so our dp state can be described by [mask][which one is zero][how many of the other] The dimensions of this dp table are 2^n * 2 * (n^2) (n^2 because the costs to buy cards is at most n).
Subham, Alisha and the tree
Question link:https://www.codechef.com/CODE2021/problems/CCH6
Quick Approach
The first observation is that to make vertex x a centroid we need to choose some subtree not containing x with size not exceeding n/2 (assume its root is w ), remove an edge uw between its subtree and the remaining tree, and add an edge between x and w , in such a way that subtrees of all children of x have size not exceeding .
Consider v — the centroid of the tree, let’s make it a root. Assume u_1 , u_2, …, u_k are the neighbours of v , and T_1, …, T_k are the subtrees of these vertices. Then it is easy to prove, that if some vertex x belongs to T_i can be made a centroid after replacing one edge of the tree, then it can be done using one of the following options:
Remove some edge vu_j for j ≠ i and add an edge xu_j .
Remove the edge u_iv and add edge xv . It is possible, if the size of T_i is exactly n-n/2 .
This is true, because if the root w of the subtree which we disconnect from the part of the tree containing x is in some T_j , i ≠ j, then we can move up w to v and disconnect the whole subtree T_j , since its size does not exceed n/2 . If w belong to T_i then the size of the disconnected subtree is more than n/2 , since the sum of sizes of T_j for i ≠ j plus vertex u_i is already n-size(T_i)+1>n/2 . So, the only remaining option is w = v, and the only possible edge to erase is u_iv , otherwise x will be in the disconnected subtree.
So we need to calculate the sizes of all subtrees (array cnt ) and then run dfs from u_1 , …, u_k . Vertex x belong to T_i can be made a centroid if ether |T_i|=n-n/2 , or cnt[x]+*max_i ≠ j|T_j|>=n-n/2 (since we add edge xu_j to maximize |T_j |, if the last condition holds, then the number of vertices in the connected component of x , if x is deleted from the tree, will not exceed n/2 — so all the condition for x being centroid will hold). To check the second condition, we need to find two maximums in the set |T_1|, |T_2|, …, |T_k |.