atcoder_official's blog

AtCoder Beginner Contest 419 Announcement
By atcoder_official, history, 13 months ago, In English

We will hold AtCoder Beginner Contest 419.

We are looking forward to your participation!

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

Comments Comments (24)
| Write comment?
»
13 months ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

I like 100-200-300-425-475.....

→ Reply
»
13 months ago, hide # |
← Rev. 2  
Vote: I like it +18 Vote: I do not like it

First comment after CF became alive!

Good contest, but big gap between F and G. Also, problem F is bad. It requires no thinking but AC automaton, a advanced data structure used to solve problems about strings.

→ Reply
»
13 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

someone explain E in the easiest possible way please :sob:

→ Reply
  • »
    »
    13 months ago, hide # ^ |
    ← Rev. 5  
    Vote: I like it 0 Vote: I do not like it

    It's DP. first of all, a[ i ], a[ i + L ], a[ i + 2 * L ],... should have the same reminder divided by M. Now for i to L and for j to M, b[ i ] [ j ] is the total number of operations needed to make all a[ i ], a[ i + L ], a[ i + 2 * L ],... have a reminder of j divided by M. Now , for i to L and for j to M and for k to M, update dp [ i ] [ ( j + k ) % M ] with dp [ i -1 ] [ k ] + b [ i ][ j ]. The answer would be dp [ L — 1 ] [ 0 ]. p.s: dp [ i ] [ j ] means the minimum number of operations needed to make the sum of first i+1 elements of the array has a reminder of j, divided by M. here is my submission: https://atcoder.jp/contests/abc419/submissions/68572396

    → Reply
»
13 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

C>=D. And D good but esay.

→ Reply
»
13 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I wonder who that person is who spent ages trying to make an inclusion-exclusion solution work for F, only to fail... couldn't be me, right?

→ Reply
»
13 months ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

Hi, I think the test data for G is weak, and the sample solution is slightly wrong. For the input


7 10
1 2
2 7
1 3
3 7
1 4
4 7
1 5
5 7
1 6
6 7

the answer should be 0 5 0 0 0 0, but the sample solution gives 0 1 0 0 0 0 (and passes).

Thank you!

(Also I tested some of the top submissions, and they correctly output 0 5 0 0 0 0, so I don't think that this will change the rankings significantly)

→ Reply
»
13 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone please explain why in problem C, median of row and column values does not work? I guessed that mid point might work after median approach failed, but I cannot understand why it fails.

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

    Let $$$x$$$ be the average of all the points' coordinates along a certain direction, then $$$x$$$ minimizes the sum of the squared differences, i.e. $$$x = minarg_{a \in \mathbb{Z}} \sum{(a - x_i)^2}$$$, which is not what we want.

    Let $$$x$$$ be the median of all the points' coordinates along a certain direction, then $$$x$$$ minimizes the sum of the absolute value of the differences, i.e. $$$x = minarg_{a \in \mathbb{Z}} \sum{|a - x_i|}$$$, which is not what we want.

    What we want here is to minimize the maximum distance, therefore $$$x$$$ should be the average between the 2 extremal values in that direction.

    → Reply
»
13 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

From C to E, the topics are [binary search + math], [segment covering trick], [dp + math + periodicity].

To my surprise, problem F is dp based on Aho-Corasick automaton !! This is crazy :D

→ Reply
  • »
    »
    13 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Binary search in C? C is just like

            int dist = Math.Max(maxc - minc, maxr - minr);

        if (dist % 2 == 0)
            Console.WriteLine(dist / 2);
        else
            Console.WriteLine(dist / 2 + 1);
    → Reply
    • »
      »
      »
      13 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      I didn't realize that problem C can be solved based on pure math. Thank you so much for sharing your solution, which I think is quite neat and clear, and has linear complexity.

      → Reply
      • »
        »
        »
        »
        13 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        hey how to do E?

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

          Here is my solution.

          The problem requests that a[1]+a[2]+...+a[L] = a[2]+a[3]+...+a[L+1] (mod M), and then we can get that a[1] = a[L+1] (mod M). Applying this to all the other contiguous subarrays, and we can find that a[x] = a[x+L] (mod M) must hold. This observation is quite important, and this is where periodicity comes from.

          Now, consider a[1]=a[1+L]=a[1+2L]=... (mod M), and we can compute the minimum number of operations to make all of them equal to some x, where x =0,1,2,...,M-1, based on some math. The total complexity is O(L*N*M), which is fast enough. We use cost[i][r] to denote the minimum number of operations that we need to make a[i]=a[i+L]=a[i+2L]=...=r (mod M)

          Next, we use dp[i][r], defined as follows:

          • i denotes that we have done with the previous i positions, where i=1,2,...,L
          • r denotes that now the remainder after mod M is r, i.e., a[1]+a[2]+...+a[i] = r (mod M)
          • dp[i][r] denotes the minimum number of operations that we need

          The transition is as follow: dp[i][r] = min(dp[i][r], dp[i — 1][r1] + cost[i][r2]) and we can brute-force r1 and r2, where both r1 and r2 take values from 0,1,2,...,M-1, and r = (r1+r2) % M. The complexity of this step is O(L*M*M), which is fast as well.

          → Reply
»
13 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

How to E in $$$O(NM)$$$ ?

→ Reply
»
13 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It was my first time being able to solve D, but I still only made it to the top 4000. Maybe D was easier than in previous contests, and even easier than C this time.

→ Reply