rng_58's blog

AtCoder Grand Contest 046 Announcement
By rng_58, history, 4 years ago, In English

We will hold AtCoder Grand Contest 046. This contest counts for GP30 scores.

The point values will be 200-600-800-1100-1500-2000.

We are looking forward to your participation!

  • Vote: I like it
  • +129
  • Vote: I do not like it

Comments Comments (36)
| Write comment?
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I decribed my solution below. It has a lot of steps.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    DP. State is (position in the string, how many times you can delete a 1 from the string, how many times you can add a 1 to the string, whether you are allowed to delete a 1, whether you are allowed to add a 1). The transition is picking whether the next character will be a 0 or a 1.

    The two booleans in the state are to avoid double-counting. Once you decide not to delete a 1 in the current block you can't delete 1s any more (since that would give two paths to the same string). Once you delete a 1 in a block of ones you can't add a 1 anymore (since that would give two paths to the same string).

    Brute force over how many moves (adds+deletes) you will ultimately make. Note that this is at most the number of 1s in the original string ($$$K<=10^9$$$ is misleading).

    My code ("nadd" starts as the number of moves you will ultimately make):

    ll dp(ll i, ll nadd, ll ndel, bool just_deleted, bool deleted) {
  // If S[i]==1, can accept or delete this character. Can delete if we already dropped a 1 somewhere earlier, and either the previous character was a 0 or we just deleted.
  // If S[i]==0, can accept this character or airlift a 1 here. Can airlift if we have 1s left and we didn't delete within this block.
  if(i==S.size()) { return nadd==0 && ndel==0 ? 1LL : 0LL; }
  ll key = i*S.size()*S.size()*2*2 +nadd*S.size()*2*2 + ndel*2*2 + (just_deleted?1:0)*2 + (deleted?1:0);
  if(DP[key]>=0) { return DP[key]; }
  ll ans = 0;
  if(S[i]=='1') {
    ans = ADD(dp(i+1, nadd, ndel,false,deleted), ndel>=1 && just_deleted ? dp(i+1, nadd, ndel-1,true,true) : 0);
  } else {
    ans = ADD(dp(i+1, nadd, ndel,true,false), nadd>=1 && !deleted ? dp(i, nadd-1, ndel+1,true,deleted) : 0);
  }
  DP[key] = ans;
  return ans;
}
    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Assume there n number 0,we get n+1 pit,use 1 throw in these pit.Set dp[i][j][k] represent the to i-th pit,use j number 1 total,move k step.We can get a O(n^4) Dp,but for 0 and 1 need balance,the number of pit expected is n/2,so time complex is O(n/2^4),and we also need meet j>=sum[i] anytime,sum[i] is the first i pit include 1's number.So with the condition,we actually time complex is expected O(n^3).

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

A — Either brute force, or use the formula lcm(360, x) / x.

B — Use dynamic programming. Let f[i][j] denote the number of different configurations starting from a rectangle of size a x b to a rectangle of size i x j. The transitions are the following:

  • (i, j) is filled: in this case, it is always possible to uniquely determine whether a row or a column was added last. Therefore, f[i][j] += f[i-1][j] + f[i][j-1].

  • (i, j) is not filled: We count the number of cases where we could have added a row last (that is, the top row contains exactly 1 black square), which is (j — 1) * f[i-1][j]. Similarly, we count the number of cases where we could have added a column last, which is (i — 1) * f[i][j-1]. Finally, we subtract the number of cases where both are possible, which is (i — 1) * (j — 1) * f[i-1][j-1].

C — Consider the zeros of the string as separators dividing the string up into blocks. Also consider the sequence, consisting of (NumOfZerosInString + 1) elements, which represent the number of 1's in each block. For example, the string 0111001 is represented by the sequence [0, 3, 0, 1] (Note that there is a size 0 block at the very beginning, before the first 0).

Whenever we perform an operation, we decrement an element of the sequence by 1 and increment an element to the left of it.

We find that a sequence can be achieved using some number of operations if and only if each element in the new sequence's prefix sum sequence is not less than the corresponding element in the original sequence's prefix sum sequence. In addition, if the new sequence can be formed, the minimum number of operations needed to change the original sequence, orig_i, to the new sequence, new_i, is the sum of all max(new_i — orig_i, 0).

Using these facts, we can do dynamic programming. Let f[i][j][k] be the number of ways to choose the first i elements of the sequence such that the current prefix sum is j and the current minimum number of operations needed is k. To make transitions, enumerate the next element of the sequence.

The time complexity is currently O(n^4). To speed it up to O(n^3) we use prefix sums (turns out two prefix sums are needed, with one of them being a diagonal prefix sum).

By the way, the forbidden configuration in problem F is identical to that of 1338E - JYPnation. Even the labeling used in the statement (A, B, C, and D) is unchanged.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is the proof of A?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We keep rotating until the total angle we rotate by is a multiple of 360. Clearly, the first multiple of 360 that we will reach is lcm(x, 360). Dividing this number by x yields the number of rotations that we will perform.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but each time we are moving by one meter, why we will regain our first position after the first multiple of 360 ?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For the angles divisible by $$$360$$$, If we consider the angles as the exterior angles of a regular polygon of $$$1$$$m side. It is known that it's sum is equal to $$$360$$$. We can extend this for angles not divisible by $$$360$$$ by taking the lcm.

          For a more detailed proof we can consider the equation in vector plane:

          $$$\sum_{k = 1}^{n}1 \angle (k x) = 0$$$

          $$$\sum_{k = 1}^{n}e ^{ik x} = 0$$$ where you can assume real part as x axis and imaginary as y axis.

          The second answer from this link shows that this is equal to :

          $$$\frac{sin\frac{nx}{2}}{\frac{x}{2}}e^{\frac{i(n+1)x}{2}}$$$

          So, $$$nx$$$ = multiple of $$$360$$$ for the above term to be $$$0$$$.

          → Reply
»
4 years ago, # |
  Vote: I like it +96 Vote: I do not like it

It was a great DP contest

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Solving A by guessing :)

→ Reply
»
4 years ago, # |
  Vote: I like it +56 Vote: I do not like it

Lucky for reading this problem :D

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same here.

    I did upsolve the problem but my solution was different from the author's, so I had to read the editorial during the contest.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      On the opposite, Radewoosh solved it in a different way than editorial and that insight he had during cf contest gave him a lot advantage here, while me and mnbvmar read editorial of this problem and got nothing. Could you describe how to solve it based on observations from editorial?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        https://codeforces.com/blog/entry/75913?#comment-602145

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yep, I was thinking more about a Hamiltonian cycle of the graph instead of partitioning it into two parts while still I cut this cycle into two to calculate the result.

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +18 Vote: I do not like it

        When I read that the vertices can be split into two parts (say, P and Q), I was almost sure that the table[i][j]=(there is an edge from P_i -> Q_j ?) has a nice structure, because otherwise, it's impossible to count them!.

        I then wrote down some graphs, found a likely pattern, gave reasoning to satisfy myself, and got AC!

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, I considered such tables for a long time, but got pretty lame results. One nice condition is that when I look at a vertex then its outneighbours on second path form an interval which says that 0s in each row form an interval and that 1s in each column form an interval and moreover that is equivalent condition for a table to have no forbidden structures. However such tables can be pretty wild and I had no idea how to count them (with even some more conditions on indegrees and caring that such partition is unique in some way). mnbvmar told me that if we still remember that terminal vertex of one part has maximum indegree then these tables look nicer, bit I didn't use that when analyzing them — is that something you used?

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Well, I used that fact, but not explicitly. Rather, I just sorted the vertices of each part, then the table looked really simple.

            → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +167 Vote: I do not like it

    I am author of that problem and I cannot solve in time.......

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve B?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    dp[i][j]=number of ways to color a grid of size i*j. The given grid is always fully white. So, dp[a][b]=1.

    Transitions are quite simple,

    dp[i][j] = dp[i][j-1]*i + dp[i-1][j]*j-dp[i-1][j-1]*(i-1)*(j-1)

    First term corresponds to adding a column where we can color any 1 of the i cells. Second term corresponds to adding a row where we can color any 1 of the j cells. We have counted some colorings twice, so we'll remove them. This part corresponds to the 3rd term.

    Final answer is dp[c][d].

    → Reply
»
4 years ago, # |
  Vote: I like it +55 Vote: I do not like it

Soooo my solution to D, which was to me the most interesting problem out of ABCD because of this unusual approach:

  • Suppose that we performed operations and kept a suffix $$$X$$$ we haven't touched yet and a set $$$S$$$ of characters we should reinsert, since we don't need to reinsert characters immediately, only before operations that use them. We have the following options (most of them are only important as edge cases):
    • Erase the first character from $$$X$$$, move the next character of $$$X$$$ into $$$S$$$.
    • Erase the second character from $$$X$$$, move the first character of $$$X$$$ into $$$S$$$.
    • Erase a character from $$$S$$$, move the first character of $$$X$$$ into $$$S$$$.
    • Erase a character from $$$S$$$.
    • Erase the first character from $$$X$$$, if $$$|S| \ge 1$$$.
  • This way, we describe reachable states (suffix $$$X$$$, number of '0' in $$$S$$$, number of '1' in $$$S$$$).
  • Let's fix the numbers of '0'-s and '1'-s in the resulting string. For each choice of $$$X$$$, the state is uniquely given.
  • There's no benefit in choosing larger $$$X$$$, so we find the shortest suffix $$$X$$$ for each pair $$$(n_0, n_1)$$$.
  • These cases are independent; for each of them, we only need to find the number of strings that can be made by arbitrarily adding $$$n_0$$$ '0'-s and $$$n_1$$$ '1'-s to a given suffix.
  • We could find that number using DP with states (suffix used so far, number of added '0'-s, number of added '1'-s). If the character we're adding can come from extending the suffix used so far, we choose that instead of making it one of the added characters. This ensures that each string is counted once.
  • Calculating that independently would be kinda inefficient since the states have a lot in common. We can do the DP described above and use its states — they're almost correct, the only difference is that we don't have maximum suffix length.
  • Let's add one thing to the states: whether the last character came from the suffix or was an extra character. When we're dealing with a suffix with length $$$k$$$, we want to take only states where the last thing we did was add the first character of this suffix (watch out for $$$k=0$$$), and repeat the same DP except without the case/option of extending the suffix. Again, this can be computed once.
  • Time complexity: $$$O(N^3)$$$. See my code for further details.
→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

My code to "F — Forbidden Tournament". Time complexity $$$\mathcal O (N^4)$$$.

mayaohua2003 had said CF1338E has a worth studying Graph structure. As expected, just modifying a little, creates a new problem.

Use the lemmas in CF1338E's official editorial, it turns out we need to calculate the number of sequences $$$a_{1 \ldots |P|}$$$ satisfying $$$a_1 = 0$$$, $$$a_{|P|} = |Q|$$$ and $$$a_{i - 1} \le a_i$$$, furthermore, because the editorial demands node $$$x$$$ has the maximum in-degree, condition $$$(i - (|P| - |Q|)) \le a_i \le (i - 1)$$$ must be satisfied. But in this way some graphs may be counted multiple times, this is because if more than one vertices have the maximum in-degree as $$$x$$$ does, each of them will be chosen as $$$x$$$ exactly once. So if the number of these vertices is $$$c$$$, this sequence contributes $$$\frac{N!}{c}$$$ to the answer.

For all values of $$$|P|$$$ and $$$|Q|$$$, use DP to calculate the contributions, naive approach gives $$$\mathcal O (N^6)$$$. Use prefix-sums to handel transitions, and process the $$$P, Q$$$ pairs together if they have the same $$$|P| - |Q|$$$ value. So the final complexity is $$$\mathcal O (N^4)$$$.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    detailed explanations.

    $$$a_i$$$ is actually $$$|\mathrm{in}Q(P_i)|$$$ in CF1338E's official editorial, the editorial didn't give out all the properties. let $$$b_i = |\mathrm{in}P(Q_i)|$$$, we have $$$b_i = \min ( \{ j \mid a_j \ge i \} ) - 1$$$. considering the in-degrees of vertices in $$$Q$$$ should be less than $$$|P|$$$ too, it's not hard to get $$$(i - (|P| - |Q|)) \le a_i$$$.

    when counting those $$$c$$$ vertices, note that $$$\displaystyle c = \sum_{i = 1}^{|P|} [a_i = i - 1] + \sum_{j = 0}^{|Q| - 1} [a_{j + |P| - |Q|} = j]$$$. so add it to DP states, it's an 1 dimension stages($$$i$$$) 2 dimension states DP($$$a_i$$$ and $$$c$$$).

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

$$$O(n^3)$$$ solution of F: As in all other solutions, notice that in strongly connected graph we can arrange vertices on cycle in such a way that for every vertex $$$v$$$ all vertices $$$u$$$ such that there is an edge $$$v->u$$$ form a segment after $$$v$$$ (let's call its end $$$C(v)$$$). Ok, let's multiply all at $$$(n-1)!$$$, now just the lengths of segment matters. Lets fix also $$$a=C(1)$$$. Now let's go from 1 to $$$a$$$ and draw some sequence of $$$+$$$ and $$$-$$$ in the following way — in $$$i$$$-th step draw firstly $$$+$$$, then $$$C(i+1)-C(i)$$$ minuses. If we look at condition about degree, we can notice that correct sequences are the followings: if we start from $$$a-1$$$ and make steps $$$+1$$$ and $$$-1$$$ according the sequence, we will be in $$$[max(n-k-1,1), k+1]$$$ all the time, and it is equivalent. Now we can calculate number of such paths using reflection principle in $$$O(n)$$$ (and in total there is just formula with $$$O(n^3)$$$ summands).

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    In fact all summands are binomial coefficients, and there are only $$$O(n^2)$$$ different of them, so with some care we will obtain $$$O(n^2)$$$ solution, or maybe even faster.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

When solving the problem D, I noticed the following.

Let X be the number of different binary strings that can be obtained by inserting exactly $$$n$$$ 1s and $$$m$$$ 0s into a binary string S.

The X only depends on the number of 1s and 0s in S. In other words, if to shuffle digits in S, X won't change.

How to prove it?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +31 Vote: I do not like it

    Consider the greedy algorithm deciding if string $$$t$$$ is a subsequence of another string $$$s$$$. In case of success this algorithm gives $$$|t|$$$ positions $$$a_1, a_2, \ldots, a_{|t|}$$$ such that $$$t_i = s_{a_i}$$$. Notice that for each $$$i < |t|$$$ letters $$$s_{a_i+1}, \ldots s_{a_{i+1}-1}$$$ must not be equal to $$$s_{a_{i+1}}$$$. The letters after $$$a_{|t|}$$$ don't matter.

    So you just take string $$$t$$$ and before each letter $$$t_i$$$ you insert some non-negative number of letters not equal to $$$t_i$$$. After the last letter you can insert anything. In this way you can uniquely generate all possible strings $$$s$$$ which have $$$t$$$ as a subsequence. Simple binomial coefficients finish the argument.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

What was the reason for introducing a lower bound for participation in AGC? You can take a look at grass_strawberry, who took the 20'th place and gets nothing. This decision seems a bit unfortunate, especially that most of the stats show that the contests for everyone provide the best rating (the closest to the real skill).

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Sometimes A is nontrivial and for very low rated people it's possible to get + by not getting any ACs.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give a bound for tourist's solution to C

It seems O(n^4) but it passes all the tests.

https://atcoder.jp/contests/agc046/submissions/14500508

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it +11 Vote: I do not like it

    I believe a lot of optimized $$$O(n^4)$$$ passes for $$$n \le 300$$$ especially when a lot of states aren't actually visited so the constant is small. I had a $$$O(n^4)$$$ in C and D during contest but tried to get them to $$$n^3$$$ and failed :(

    UPD: It turns out I misread C >_<

    → Reply