You are not logged in. Please login at www.codechef.com to post your questions!

×

ACMIND18 - ICPC Online Round - Solution Outlines

10
6

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

asked 25 Oct, 13:11

admin's gravatar image

0★admin ♦♦
19.6k349497539
accept rate: 35%

edited 25 Oct, 20:49

6

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?

(25 Oct, 16:21) sarthakmanna6★
2

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.

(25 Oct, 20:54) admin ♦♦0★

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.

link

answered 26 Oct, 02:26

joffan's gravatar image

5★joffan
9148
accept rate: 12%

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.

link

answered 26 Oct, 01:28

prakhar17252's gravatar image

5★prakhar17252
23618
accept rate: 6%

Please Add these problems to practice.

link

answered 25 Oct, 13:39

babangain's gravatar image

3★babangain
423213
accept rate: 4%

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) admin ♦♦0★

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}$"?

link

answered 25 Oct, 17:23

the_extractor's gravatar image

4★the_extractor
1277
accept rate: 8%

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.

(25 Oct, 18:20) prakhar172525★
1

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.

(25 Oct, 19:28) the_extractor4★

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.

link

answered 25 Oct, 19:54

iluvpriyanshi's gravatar image

0★iluvpriyanshi
1
accept rate: 0%

1

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

(25 Oct, 20:08) the_extractor4★
1

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.

(25 Oct, 20:14) the_extractor4★

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)?

link

answered 25 Oct, 21:12

pratham31's gravatar image

2★pratham31
9
accept rate: 0%

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

link

answered 26 Oct, 09:00

deermen001's gravatar image

3★deermen001
484
accept rate: 9%

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) admin ♦♦0★

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

(27 Oct, 13:23) deermen0013★

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

link- link text

link

answered 30 Oct, 00:29

code_man's gravatar image

3★code_man
46
accept rate: 8%

Check this-

1 .0.2

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

(30 Oct, 00:56) vijju123 ♦♦5★

earlier i considered zero but still not working.

link- https://www.codechef.com/viewsolution/21337330

(30 Oct, 01:04) code_man3★

Line number 52.

if(low!=high)

Why? What will low and high be for 0?

(30 Oct, 01:07) vijju123 ♦♦5★

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) code_man3★

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) vijju123 ♦♦5★

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) code_man3★
showing 5 of 6 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,035
×22

question asked: 25 Oct, 13:11

question was seen: 5,618 times

last updated: 30 Oct, 01:43