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_{m-2}) < a_{m-1}. In this case, the best we can do is to take each of the m-2 elements and pair them up with a_{m-1} repeatedly until they all become 0. Then we take a_{m-1} (which would by now have become a_{m-1} - a_1 - a_2 - \ldots - a_{m-2} ) and make pairs with a_m. In this case, the final answer will be SumLess + m*K + [a_m - (a_{m-1} - a_1 - a_2 - \ldots - a_{m-2})], which is just (sum of all elements - 2*a_{m-1}).
Case 2: (a_1 + a_2 + \ldots + a_{m-2}) \ge a_{m-1}. In this case, we will first keep pairing up some two elements from the first m-2 elements, till their total sum becomes equal to a_{m-1}. Then we’ll pair them up with a_{m-1}, and then pair them up with a_{m-1} repeatedly, as in last case. But the only catch here is when we are not able to get the sum of the first m-2 elements equal to a_{m-1}. This happens when the parity of (a_1 + a_2 + \ldots + a_{m-2}) and a_{m-1} 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 clean-up, 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 i-th 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.
BIPFAMIL
Let dp[n][m] be the number of connected Range Graphs with n vertices on left and m vertices on right. We will pre-compute 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+m-r}, v_{n+m-r+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 n-l 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})^{n-l}.
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 m-1. But if l is n, then we need to only run till m-2. 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{(m-1)*(m)}{2})^n. So we subtract this as well, and get our final formula:
dp[n][m] = (\frac{m*(m+1)}{2})^n - (\frac{(m-1)*(m)}{2})^n - \sum_{l=1}^{l=n} \sum_{r=0}^{r=m-1-(l==n)} { {n \choose l} * dp[l][r+1] * (\frac{r'*(r'+1)}{2})^{n-l}}
PRESTIGE
The 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+X-1 of the second deck (again using the treap) and subtract twice of this from the previous computed sum.
PS: Inspiration for the problem: Video