maroonrk's blog

By maroonrk, history, 3 years ago, In English

We will hold AtCoder Regular Contest 119.

The point values will be 300-500-500-700-800-800.

We are looking forward to your participation!

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +29 Vote: I do not like it

E was quite similar to 1513F - Swapping Problem.

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

    Is the solution similar? Cause in the CF problem two diff arrays are used.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yes, you just have to pay attention to the fact that you mustn't overlap an interval with itself, which isn't too hard to take care of.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You can assume $$$b_i = a_{i+1}$$$.
      Then, you have to maximize $$$|a_i - a_j| + |b_i - b_j| - |a_i - b_i| - |a_j - b_j|$$$ instead of $$$|a_i - b_j| + |b_i - a_j| - |a_i - b_i| - |a_j - b_j|$$$.
      Hence, the two segments should be both in $$$X$$$ or both in $$$Y$$$ instead of one of them in $$$X$$$ and the other one in $$$Y$$$. The rest of the solution is identical.

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

A was a complete search on $$$b$$$.

C was really neat, a subarray can be chosen if the alternating sum of heights is 0.

What was the approach for B?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +62 Vote: I do not like it

    If you visualize the 1s as empty cells and 0s as people/pieces on the array, the problem becomes: move each person to the correct spot in the final string, one person cannot walk past another. Answer is number of people that need to move. img

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

      That's pretty neat, thanks!

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

      Oh! So instead of working with "people" you work with "empty chairs" and that makes the solution straight-forward! Thats fantastic!

      I did some complicated counting and moving according to the rules and keeping track of how much people have been pushed and I needed to iterate forwards once and backwards once: Submission

      But this is so much simpler!

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

      How does this work?

      Consider the beginning of s and t in Sample 4, these are

      s=110011110111010...
      t=111111111111111...
      

      Here, the first '0' (in position 2) can and must be swapped with the 1 in position 4. After that first swap s looks like:

      s=111001110111010...
      

      And same pattern repeats until we have.

      s=111111111100000...
      

      But for that we needed more than 4 operations (it is 13 I think).

      Where am I wrong?

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

        You can move a $$$0$$$ to any position between the $$$0$$$ on its left and the $$$0$$$ on its right, using only $$$1$$$ move.

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

        Well, it isn't optimal to make that first swap between position 2 and 4 in the first place. For sample 4, if you go backwards instead it'll work.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +19 Vote: I do not like it

        There always has to be a corresponding pair of 0s on positions from in $$$S$$$ and position to in $$$T$$$ such that in $$$S$$$ the elements (from, to] only contain ones. Then we can apply the operation to move the zero from from to to in $$$S$$$. Repeat until all zeroes are sorted.

        Why does such a pair of zeroes always exist?
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How is this true? Any proof?

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

      It's useful in this problem to find an invariant. If we add a $$$1$$$ to two adjacent elements, notice that the alternating sum of the entire array does not change. The same if we subtract $$$1$$$. Thus, the alternating sum is an invariant. And we want all zeros, so the alternating sum of our array must be the same as all zeros, which is zero.

      In-contest though, I just did a few examples and it reminded me of multiples of $$$11$$$, like $$$352$$$, and one easy way to check for divisibility by $$$11$$$ is to take the alternating sum mod $$$11$$$ and check that it's $$$0$$$.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Yes I agree! This was a very fantastic problem! The idea was to consider the sum $$$\sum_{i=1}^n (-1)^i a_i$$$ which is invariant under any such move(this is essentially the alternating sum) Originally I thought of $$$\left( \sum_{i=1}^n a_i \right) \pmod 2$$$ which unfortunately didn't work. You play around with it more and you realize the above invariant. By the way to those who are unclear how a solution after this would work, here are a couple of ideas:(I consider $$$1$$$-based indexing, just to be clear)

        Hint 1
        Hint 2
        Bonus 1
        Bonus 2
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Bonus 1 was almost what I did in-contest, although I didn't need to store $$$x$$$

          Bonus 2
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Umm I did say you don't have to store $$$pref$$$ or $$$x$$$

            Yes! For bonus $$$2$$$ your idea is exactly like mine, but I guess these ideas will be implementation heavy. I think a simpler solution would exist if you made use of the fact that

            $$$\sum_{i=1}^p a_i z^i = 0$$$

            where the $a_i$ are all integers(actually even rational is fine, but not needed here) and $$$z$$$ is a primitive root of order $$$p$$$(which is pretty much any root because $$$p$$$ is prime) iff all the $$$a_i$$$'s are equal. This thing works only if $$$p$$$ is prime. I am aware of a solution of the case $$$p = 3$$$ but I don't know a very clean way of generalising it to arbitrary primes.

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

              In my solution, I didn't store $$$pref$$$. I meant that it's trivial to remove $$$x$$$.

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I am getting +ve deltas in ABCs and CF D2s, I must be improving.
ARC/SRM div 1-You what?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    a[i] means the distance between i-th 0 and (i+1)-th 0.

    And a operation is a[i]+=x and a[i+1]-=x (x is not necessary be positive), and s equal to t iff (a[i] of s) = (a[i] of t).

    This can be done by greedy.

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

      Can you elaborate on the greedy part?

      How do you prove that you can always find a zero that you can move without hitting another zero. Implementation-wise, is this problem harder if you also have to output the moves?

      For example S=00111100 and T=11000011, the innermost zeroes have to move first so you can't just do left to right.

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

        A[i] need to be modified if and only if :

        1. $$$\sum_{j\leq i} A[j]=\sum_{j\leq i} B[j]$$$

        2. $$$A[i]=B[i]$$$

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve C?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    The intuition I had was the following: any operation will either increase or decrease the sum of odd-indexed values and even-indexed values by exactly 1. This means that the sum of odd-indexed and even-indexed values being equal is a necessary condition for (L, R) to be valid. One can notice that this is also sufficient (to see why, imagine doing operations to set values to 0 from the left to the right). This means that if you multiply all odd-indexed values by -1, the answer is simply the number of non-empty subarrays with a sum of 0.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Wow. That's really nice! Thanks!

»
3 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

The gap between C and {D, E} is too large :(

»
3 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

During the contest, TL (link):

REP(i, 0, w + h) {
	REP(i, 0, h + w) {
		...
	}
}

After the contest, AC (link):

REP(i, 0, w + h) {
	...
}

Nice problems anyway :) Thanks for the contest!

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Did a problem similar to C appear on codeforces before?

I can't remember where I remember the parity trick from.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Someone have AC on E with $$$O(nlog^2n)$$$?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial still not available? Currently I only see problem A's solution.

»
3 years ago, # |
Rev. 3   Vote: I like it +32 Vote: I do not like it

Editorial for D.

Spoiler
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In A why the possible values of b is 0 to 59?

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

    Once A becomes 0 increasing B would just increase sum since C remains N.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone share a hint for Problem D? I've tried playing with bipartite graph constructions, but am not able to progress beyond that.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Spoiler
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      Almost There
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        Done :)
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

My approach to D is slightly different — I also make a bipartite graph but one partition has red cells and the other has rows/columns. If we pick the last row/column (w.l.o.g. column), then we know that all red cells in this column can only be used with their rows, and we don't need to pick any other cells for these rows; this frees up all other red cells in these rows to be used with their columns, and so on. Notice that this way, we traverse the whole connected component of this row/column and find an ordering for all rows/columns in it except one. For every component with $$$r$$$ rows and $$$c$$$ columns, we can thus use $$$(r-1, c)$$$ or $$$(r, c-1)$$$. To combine it over components, a simple DP tells us the maximum number of columns we can use for each number of rows, and then we pick the pair ($$$r$$$ used rows, $$$c$$$ used columns) that gives the maximum answer. The rest is implementation of construction.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it
My solution to D
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve F?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +30 Vote: I do not like it

    Dp of Dp

    dp[i][j][k] : consider the first i stations, the ways of "The distance to the last A is j,and the distance to the last B is k".

    And answer is $$$\sum_{\min(j,k)<K} dp_{n,j,k}$$$.

    You can do this dp in $$$O(N^3)$$$ .

    But you can find that if $$$j>k+2$$$, you can go to the next B and back to the previous A in 2 steps , so you can think j = k+2.

    This also works for $$$k>j+2$$$.

    So it is $$$O(N^2)$$$.

    my solution: https://atcoder.jp/contests/arc119/submissions/22690514

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Editorial to Problem D:

The problem is quite similar to the following template.

Bombs in the Grid

Problem Statement: Given a grid $$$G[n][m]$$$, $$$1<=n, m<=10^3$$$, some cells have a bomb that can destroy either the row containing the cell or the column. Find an order in which to use the bomb to maximize the number of destroyed cells.

Tutorial: This genre of problems can be solved by building a bipartite graph with $$$n+m$$$ nodes. Node $$$i$$$ and $$$j+n$$$ are connected by an edge if a bomb exists in the cell $$$G[i][j]$$$. Suppose, we choose to destroy $$$r$$$ rows and $$$c$$$ columns. Then, the number of cells not destroyed is given as $$$(n-r)(m-c)$$$. So, we have to minimize this objective function. Find the number of connected components in the constructed bipartite graph. Let there be $$$p$$$ components of size $$$1$$$ comprising of row nodes only and $$$q$$$ components of size $$$1$$$ comprising of column nodes only. Let there be $$$k$$$ components with a size greater than $$$1$$$. We know that we will not be able to use $$$p$$$ rows and $$$q$$$ columns (as they don’t have any cell with the bomb). How to deal with the components of size greater than $$$1$$$? Consider one such component. Pick any node arbitrarily, (it may be a row node or a column node, without loss of generality, let’s assume we pick a column node), then we know that all bomb cells in this column can only be used with their rows, and we don't need to pick any other cells for these rows; this frees up all other bomb cells in these rows to be used with their columns, and so on. Notice that this way, we traverse the whole connected component of this row/column and find an ordering for all rows/columns in it except one. Now, for each of the $$$k$$$ components, we need to decide whether to root that component with a row node or a column node. Suppose we choose $$$x$$$ components that are to be rooted with row node, and for other components, column node is chosen to be the root. Then, the number of cells not destroyed will be $$$F(x)=(p+x)(q+k-x)$$$ where $$$p, q$$$ are fixed and $$$x$$$ can be varied. From mathematical analysis, if $$$p>q$$$, choose $$$x=k$$$ else $$$x=0$$$ for optimal value.

Implementation: Construct a graph with $$$n+m$$$ nodes, representing rows and columns, with node $$$i$$$ and $$$j+n$$$ having an edge if a bomb exists in cell $$$G[i][j]$$$. Let $$$p$$$ be the number of row nodes having no edge and $$$q$$$ be the number of column nodes having no edge. Let the number of connected components of size greater than 1 be $$$k$$$. If we only want to know the maximum number of cells destroyed, it is given as $$$nm-pq-k*max(p, q)$$$. If $$$p>q$$$, run multi-dfs considering row nodes only as root, else consider the column nodes as root. In the dfs call, suppose you are at vertex $$$u$$$, after calling dfs from its child $$$v$$$, add pair $$$<v, u>$$$ to the result. This will provide the ordering of using bombs. While processing the pairs in answer, let the current pair be $$$<v, u>$$$, if $$$v<n$$$, this means bomb in the cell $$$G[v][u-n]$$$ is used to destroy row $$$v$$$, otherwise bomb in the cell $$$G[u][v-n]$$$ is used to destroy column $$$v-n$$$.

Submission: https://atcoder.jp/contests/arc119/submissions/22699042