ACMIND18 - ICPC Online Round - Solution Outlines

general
,
1

Contest Link

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

13 Likes
2

Please Add these problems to practice.

1 Like
3

In REDCGAME: “Case 2: (a_1+a_2+…+a_{m−2})≥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}.”

What if there’s no way to pair any two elements such that their sum is reducible to a_{m-1}? Consider the case when m = 5 and the elements are 2, 3, 4, 8, 10. Here, the sum of the first 5-2=3 elements is 9 which is greater than the second last element, 8. But, no two elements out of the first three have sum greater than or equal to 8. So how will you pair elements here "till their total sum becomes equal to a_{m−1}"?

1 Like
4

In REDCGAME : “Case 2: (a1+a2+…+am−2)≥am−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 am−1.”

What if the m=5 and the numbers were 2,3,5,8,10.The parity of sum of m-2 elements is same as that of am-1 but how can it be reduced to zero ??

After 1st step (The sequence would look like this)

0,1,5,8,10

After 2nd step

0,0,3,8,10

After 3rd step

0,0,0,5,10

And that would not result into the optimum answer. I thought of some other choices like first pair 5 and 8 which will reduce 8 to 3 and after that we pair two remaining 3s but this will result into answer = 8

How can I pair these m-2 elements such that we get correct answer ??

Can you please explain with a case of 2,3,4,6,39,40 (m=6) because in this case even though the parity of sum of m-2 elements is same as that of (m-1)th element but we won’t be able to keep mth element untouched.

5

Prestige(Python 2.7)
def become(x,y,z):

k=0
m=[]
m.extend(x)
for j in range(int(y)-1,int(z)):
    l=int(z)-1-k
    m[l][0],m[l][1]=m[l][1],m[l][0]
    x[j]=m[l]
    k+=1
return x

def a():

a,b=raw_input().split(" ")
a=int(a)
b=int(b)
c=raw_input().split(" ")
d=raw_input().split(" ")
f=[]
g=[]
for e in range(a):
    f.append([int(c[e]),int(d[e])])
    g.append([1,-1])
for h in range(b):
    i=raw_input().split(" ")
    if len(i)==3:
        f=become(f,i[1],i[2])
    if len(i)==2:
        g=become(g,1,i[1])
    if len(i)==5:
        on=int(i[1])
        tw=int(i[2])
        th=int(i[3])
        fo=int(i[4])
        count=0
        sums=0
        while (th-1+count)<=(fo-1):
            sums+=g[th-1+count][0]*f[on-1+count][0]
            count+=1
        print sums

a()

how to solve the TLE error in this problem(if possible)?

1 Like
6

A proof for Case 2 in REDCGAME.
Suppose the sum of the first g-2 elements is greater than/equal to g-1’st element. Therefore, there have to be at least 2 elements, both smaller than g-1’st element in the g-2 elements(If this was not the case and we only had one element, it would be the g-1’st element instead). Let the element at g-1 be x and the sum of the first g-2 elements be y. Since there are at least two elements in the first g-2, we can pair some of them up (y-x)/2 times to make the sum of them just smaller than x. Then we can conveniently pair all the remaining elements with the g-1’st element. If in turn, the sum was originally less than x, the optimal way is to pair everything with g-1’st element, as not utilizing the g-1’st element for pairing would lead to it being used to decrease the largest element in a non-optimal way.

1 Like
7

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. (count+1)//2). The minimum number of squares required will be the sum of these values - if it’s more than 16, the word set is not feasible.

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.

2 Likes
8

In REDCGAME
Case 2:
Shouldn’t it be SumLess+**(m-1)**∗K+am in case of same parity

and in different parity SumLess+**(m-1)**∗K+am-1

9

for Robogame what editorial stated im doing exactly, still getting WA. Editorial is missing any corner case?

link- link text

10

They have already been added. You can either go to the contest problem page (CodeChef: Practical coding for everyone) and click on the “Submit(Practice)” button, or you can directly go to the Practice link (ROBOGAME Problem - CodeChef)

3 Likes
11

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?

7 Likes
12

In this case it is not possible to pair up the elements fully due to different parity of 9 and 8. One element will always be left, which in turn will be paired up with a_m. It is written how to deal with this case a bit ahead in the paragraph.

13

Yes I had read that earlier. I had mistaken the “their” in the statement I have quoted above for the pair of elements instead of the first m - 2 elements.

1 Like
14

The m = 5 case: The sum of the first three elements is 10, which is greater than the second largest element, 8. So we have to first reduce the sum of the first 3 elements to 8. That can be done by subtracting 1 from both 2 and 3. The sequence now is 1, 2, 5, 8, 10.

Now, we’ve to pair the first three elements with the 4th one, one by one. So the sequence changes like this:

0 2 5 7 10
0 0 5 5 10
0 0 0 0 10
1 Like
15

For the m = 6 case, the sum of the first four elements is 15, which is less than the fifth element. So you’re right, we’ll have to reduce the last element also.

Read Case 1 in the solution outline.

1 Like
16

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.

2 Likes
17

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.

18

Can you tell me What is wrong with my solution
https://www.codechef.com/viewsolution/21209663

19

Check this-

1
.0.2

Hint: ASCII value of 0 is 48 and that position needs to be marked as well.

20

earlier i considered zero but still not working.

link- CodeChef: Practical coding for everyone