The problems can be solved in Practice section as well. ROBOGAME:The main observation was that if the ranges of any two robots had even a single cell in common, then they could coordinate their starting times so that they both collide. Hence, you just had to check if any of the ranges intersect or not. REDCGAME:At the end, there will only be one integer whose value is $> K$. The rest will all be exactly $K$ , or if they had initially itself been $< K$, then they won't change ever. Let the sum of all elements $\leq K$ be $SumLess$. Now take only the elements > $K$. Suppose there are $m$ such elements. Subtract $K$ from each of them (because these can never go below $K$), and add $m*K$ to the final answer. Sort those integers: $0 < a_1 \leq a_2 \leq \ldots a_m$. We will try and keep $a_m$ intact, and have that as the last remaining value. But to do so, we should be able to reduce all the others to 0. So now, we look at two cases: Case 1: $(a_1 + a_2 + \ldots + a_{m2}) < a_{m1}$. In this case, the best we can do is to take each of the $m2$ elements and pair them up with $a_{m1}$ repeatedly until they all become $0$. Then we take $a_{m1}$ (which would by now have become $a_{m1}  a_1  a_2  \ldots  a_{m2}$ ) and make pairs with $a_m$. In this case, the final answer will be $SumLess + m*K + [a_m  (a_{m1}  a_1  a_2  \ldots  a_{m2})]$, which is just (sum of all elements  $2*a_{m1}$). Case 2: $(a_1 + a_2 + \ldots + a_{m2}) \ge a_{m1}$. In this case, we will first keep pairing up some two elements from the first $m2$ elements, till their total sum becomes equal to $a_{m1}$. Then we'll pair them up with $a_{m1}$, and then pair them up with $a_{m1}$ repeatedly, as in last case. But the only catch here is when we are not able to get the sum of the first $m2$ elements equal to $a_{m1}$. This happens when the parity of $(a_1 + a_2 + \ldots + a_{m2})$ and $a_{m1}$ is different. In which case, we'll end up with extra number which should be reduced with $a_m$. Therefore, in this case, when the two parities are same, the final answer will be $SumLess + m*K + a_m$. When the two parities are different, the final answer will be $SumLess + m*K + a_m  1$. WORDGRID:Among the 32 words, remove duplicates. Also check if any word is a reverse of any other word, and remove one of them. Because one of them appears in the grid if and only if the other appears. Now, after doing the cleanup, let $n$ be the number of words remaining. If $n$ is more than 8 words, we claim that the answer is Not Possible. Why? Because each of these words has to be in a different row or column, and there are only 4 rows and 4 columns. After this, the intuition is that because there will be a lot of constraints imposed by previously set words, just doing a bruteforce recursion should work. But let us formally prove that it does work. First let us get an approximate idea of the number of possible outcomes for various values of $n$. Let $f(n)$ denote the maximum number of valid outcomes possible when we have $n$ words. Suppose $n$ = 8 or 7: In this case, either all four rows are filled with 4 words (or their reverses), or four columns are filled with some 4 words. Once these are filled, there is no other choice left for us. So the total number of outcomes is at most $2$ (either rows or columns) $* {8 \choose 4}$ (choosing which 4 words will be used to fill, say, the rows) $* 4!$ (those 4 words can be arranged in so many ways) $* 2^4$ (each of those 4 words can be reversed or not). In the case of $n = 7$, the ${8 \choose 4}$ will be replaced by the smaller ${7 \choose 4}$. This amounts to $f(8), f(7) \leq 53760 \leq 6 * 10^4$. Suppose $n$ = 6: There are two cases in this. Either the 6 words are split as 4 in rows (or columns) and the other 2 in columns (or rows), or they are split as 3 and 3. In the first case, we do the same calculation as the previous case, and we get something less than $6 * 10^4$. The other case is $6 = 3+3$. Now, let's first fix the 3 words in the rows. This can be done in ${6 \choose 3} * {4 \choose 3} * 3! * 2^3$. Once these three rows are fixed, now look at each column. Each column can be used by at most one of the remaining three words. Because there are no duplicates or reverses among the words. So, at most one of the three remaining words has 2 columns in which it can appear. And this is the only choice that we can make after fixing the three rows. So the total number of outcomes in this case is just ${6 \choose 3} * {4 \choose 3} * 3! * 2^3 * 2 = 7680 \leq 10^4$. So, $f(6) \leq 6 * 10^4$. Suppose $n \leq 5$: Take the first word. It has 16 possibilities of appearing in the grid: in either of the 8 rows and columns, and in 2 directions in each of them. Try each possibility. After fixing one of these 16 possibilities for the first word, the second word will now have only 14 choices, because one of the rows or columns has been taken up. And the third word will have 12 choices, and so on. So $f(5) \leq 16 * 14 * 12 * 10 * 8 = 215040 \approx 2 * 10^5$. $f(4) \leq 16 * 14 * 12 * 10 \leq 3 * 10^4$. $f(3) \leq 16 * 14 * 12 \leq 3 * 10^3$. $f(2) = 16*14 \leq 10^3$. And $f(1) = 16$. Now lets see what happens when we do a bruteforce recursion. In the recursion, while looking at the possibilities for the next word, you just make sure that there are no mismatches being created. And at the end, you fill the remaining cells, if any, with 'A' and you output the lexicographically smallest valid grid. Let's take the worst case when $n=8$. This recursion tree will have depth 8. At the first layer, we have $16$ nodes, then $16 * 14$ nodes, and so on. But in the ith layer, each node corresponds to some valid outcome when we look at just the first $i$ words. Hence the number of nodes in that layer must be $\leq f(i)$. So the total number of states in the recursion is $\leq \sum_{i=1}^{i=8} f(i) = 16 + 10^3 + 3*10^3 + 3*10^4 + 2*10^5 + 6*10^4 + 6*10^4 + 6*10^4 \leq 5*10^5$. In each state, we spend at most 16 time, and there are 50 testcases. So the total time taken is $O(5 * 10^5 * 16 * 50) \leq 4 * 10^8$. BIPFAMILLet $dp[n][m]$ be the number of connected Range Graphs with $n$ vertices on left and $m$ vertices on right. We will precompute these DP values, and then use these to answer the testcases in constant time. We first observe that the total number of Range Graphs on $n$ and $m$ vertices is $(\frac{m*(m+1)}{2})^n$. Now, to compute $dp[n][m]$, what we want to do, is take all the Range Graphs, and then subtract the disconnected graphs from it. To do this, we will look at the connected component that one particular vertex (say $v_{n+m}$) is part of, and use dp to find this. So now, the connected component in question will contain say the vertices {$v_{n+mr}, v_{n+mr+1}, \ldots, v_{n+m}$}, and some l vertices from the left partition. The number of ways that this can be done is ${n \choose l} * dp[l][r+1]$. Once $l$ and $r$ are fixed, the rest of the graph (ie, the remaining $nl$ vertices on the left and the $r' = m(r+1)$ vertices on the right can be filled up in any way amongst themselves, as long as they form a Range Graph. That is, connectivity is not enforced there. So for a fixed $l$ and $r$, the total number of disconnected Range Graphs is ${n \choose l} * dp[l][r+1] * (\frac{r'*(r'+1)}{2})^{nl}$. So we loop over all l and r, and subtract all of these from the total number of Range Graphs. There are two catches in this: First is that, we should be careful not to let $l$ and $r$ span the entire graph. In that case, we'll just get a connected Range Graph (and it will lead to cyclic dependencies, as it will depend on $dp[n][m]$). So make sure that $l + (r+1) < n + m$. So once $l$ is fixed, we'll run $r$ from 0 to $m1$. But if $l$ is $n$, then we need to only run till $m2$. So, in general $r$ will run from 0 to $m  1 (l==n))$. The second catch is that the vertex $v_{n+m}$ might not have been used at all. That is, there are Range Graphs in which $v_{n+m}$ will be an isolate vertex. These graphs have not been subtracted out. But the number of such graphs is just $(\frac{(m1)*(m)}{2})^n$. So we subtract this as well, and get our final formula: $dp[n][m] = (\frac{m*(m+1)}{2})^n  (\frac{(m1)*(m)}{2})^n  \sum_{l=1}^{l=n} \sum_{r=0}^{r=m1(l==n)} { {n \choose l} * dp[l][r+1] * (\frac{r'*(r'+1)}{2})^{nl}}$ PRESTIGEThe first observation in this problem is that the upper faces of the first deck will always be 1s followed by 1s. Suppose the updates of Type 2 are $K_1 \leq K_2 \leq \ldots \leq K_s$. After the first update, the first $K_1$ cards will be 1 and rest will be 1. Now when $K_2$ comes, the first $K_2  K_1$ cards will be 1 and rest will be +1. And so on. So, this can be kept track of, with just one variable, $K$, which denotes that currently the first $K$ cards are 1. Once you have this, the problem can be solved with treaps, which support reverse. But here, we overload the usual reverse with also reversing the face of the cards. So when the reverse variable is true in a node of the treap, it denotes that the sequence is reversed, as well as that the lower faces are now actually on top. This takes care of updates of Type 2. When a Type 3 query $A$ $B$ $C$ $D$ comes, we get the sum of the cards in indices $A$ to $B$ of the second deck using the treap, and then we find how many 1s are there in the first deck between $C$ and $D$ (using the variable $K$ that we are maintaining). If there are $X$ of them, we take the sum of the cards in indices $A$ to $A+X1$ of the second deck (again using the treap) and subtract twice of this from the previous computed sum. PS: Inspiration for the problem: Video asked 25 Oct, 13:11

An extra feasibility precheck for WORDGRID (which you would use after eliminating duplicates and reverses): Total up the occurrence of each different letter in the word set. Then halve these counts, rounding up (e.g. Justification: every letter in the grid can only belong to at most two words. Note that any list of more than 8 words will fail this test. answered 26 Oct, 02:26

A proof for Case 2 in REDCGAME. answered 26 Oct, 01:28

Please Add these problems to practice. answered 25 Oct, 13:39
3
They have already been added. You can either go to the contest problem page (https://www.codechef.com/ACMIND18/problems/ROBOGAME) and click on the "Submit(Practice)" button, or you can directly go to the Practice link (https://www.codechef.com/problems/ROBOGAME)
(25 Oct, 13:42)

Prestige(Python 2.7) def become(x,y,z):
def a():
a() how to solve the TLE error in this problem(if possible)? answered 25 Oct, 21:12

In REDCGAME Case 2: Shouldn't it be SumLess+(m1)∗K+am in case of same parity and in different parity SumLess+(m1)∗K+am1 answered 26 Oct, 09:00
We are subtracting K from each of those elements which are > K at the beginning. So a_m in the final formula actually refers to (a_m  K), which I believe is what you're referring to.
(26 Oct, 13:08)
Can you tell me What is wrong with my solution https://www.codechef.com/viewsolution/21209663
(27 Oct, 13:23)

for Robogame what editorial stated im doing exactly, still getting WA. Editorial is missing any corner case? link link text answered 30 Oct, 00:29
Check this
Hint: ASCII value of 0 is 48 and that position needs to be marked as well.
(30 Oct, 00:56)
earlier i considered zero but still not working.
(30 Oct, 01:04)
Line number 52.
Why? What will low and high be for 0?
(30 Oct, 01:07)
ok i removed that , bcoz earlier i didnt marked for zero movement robot, but getting wrong answer still after marking zero move for above code(21337330).I will not sleep untill i get AC
(30 Oct, 01:14)
Array size is 50. Len is upto 50. $\implies$ high upto 50. 0 based indexing. Max possible index allowed is 49. Still used $\leq high$. Try fixing that.
(30 Oct, 01:34)
By making size of visited array 51 > AC , but any ways earlier the size was 50 (1 less), how an visited array of size 1 less can give WA, can u think of such test case Any ways thanks legend!!
(30 Oct, 01:43)
showing 5 of 6
show all

In WORDGRID, there are 50 test cases. So, won't the complexity increase to around 8e9 (16x14x12x10x8x6x4x2 x 16 x 50)? Am I missing something?
Apologies. I totally missed the 50 testcases, and posted it without getting it verified by the setter or tester. It's been fixed now. Still not sure if this is the analysis which the setter had in mind, but this should work. A better analysis will probably come up in the actual editorial.