**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 26*uncovered*. 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*|.