tourist's blog

AtCoder Grand Contest 041
By tourist, history, 4 years ago, In English

We will hold AtCoder Grand Contest 041. This is the last contest of 2019 that counts for AtCoder Race Ranking.

The point values will be 300 — 700 — 900 — 1200 — 1600 (800 + 800) — 2000.

We are looking forward to your participation!

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

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

its great!!

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

orz tourist

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

    So it proves that Codeforces is ratist.

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

tourist can we discuss the problems after the contest here ?

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

What is the current race ranking?

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

will we get editorial for this?

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

difficute

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

Hope everyone high rating

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

How to solve C? What all I could deduce is that $$$n = 2k$$$ is possible, $$$n=3$$$ is possible, but I could not fill with $$$n=5$$$.

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

Is there a nice solution to C? Mine just has hard-coded solutions for $$$n = 4, 5, 6, 7$$$ with 3 unique dominoes on every row and column, and puts rectangles of those sizes on the diagonal for cases $$$n \geq 4$$$. Case $$$n = 3$$$ is trivial, and case $$$n = 2$$$ is impossible.

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

    For n = 4 pretty easy to construct this answer

    Spoiler

    And for n = 6

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

      What are you trying to say?

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

        no need to use bruteforce for n = 4 and n = 6

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

          he has to bruteforce 6, for row/col has 3 dominoes, then he can combine with other form.

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

            There also easy answer for n = 6 and 3 dominos in each row/column:

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

          My bad, didn't notice he edited his comment.

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

    Can you please share your code for the bruteforce you did?

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

      My brute-force was just backtracking with some break conditions:

      brute-force
      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    My solution involves finding solution for primes and then duplicating that matrix. And finding solution for a prime involves padding a solution for a multiple of 3 with either a line and a column or two lines and two columns. Solving for a multiple of 3 required combining solution for a 3x3 matrix with 1 piece per line or 2 pieces per line.

    So I would guess your solution is actually nice.

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

    Model solution isn't nice either :) I found $$$n = 7$$$ case with brute force.

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

    Am I only one "brute-force" by DRAWING?

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

      I got 5 and 7 in one attempt each. Not sure if I'm lucky or there are actually a lot of possible solutions.

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

    You probably always need to hardcode patterns for n=5,7 (3 and 4 are trivial). Solutions that use patterns for $$$n=3k$$$ can be tricky because you need the diagonal blocks to have the same number of dominoes and the easiest patterns there have 2, while all other $$$n$$$ need to have 3.

    Here is a solution that avoids it: while $$$n \ge 6$$$ is even, divide it by 2, which gives you $$$2^k \times 2^k$$$ square blocks. All these blocks have sizes either 4 or an odd number greater than 1. If it's 3 or 4, just use the pattern. Otherwise, use many diagonal blocks 4x4 and one 5x5 or 7x7. We don't use any 3x3 block, so the number of dominoes in each block and therefore in each row/column is the same.

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

Very sad, that the only wrong answer of my solution for C is n=5 :(

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

When will the editorials be out?

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

Editorial is out

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

Thanks for participating! The editorial is out indeed.

I was not sure whether the uniforming or the non-uniforming subtask of E will be solved by more people. According to my calculations, 40 people solved the uniforming one, and 28 people solved the non-uniforming one. Well done!

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

Problem C is also Problem 4 from the 2018 European Girls Mathematical Olympiad xd

See https://artofproblemsolving.com/community/c6h1625929p10191585 for discussion

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

Damn, I wasted half an hour to squeeze D into TL and lacked <2 mins to get C accepted :<. I got O(n^2 log n) tho (log n and solution in editorial is in O(n^2), but all my friends got O(n^2 log n) as well if I'm not mistaken.

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

Final GP30 standings: https://img.atcoder.jp/file/GP30.html

Congratulations tourist, ecnerwala, Um_nik, ksun48, Petr, jqdai0815, LHiC, and mnbvmar!

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

    It is stupid from the position of trying to get the best place in finals, but can you allow maroonrk to participate in the finals, if he is not one of the problemsetters? He gave us some of the best problems this year, and today he did solve F very fast, and it seems that he just left the contest in the middle, so he could easily get at least 3rd place, which would be enough for him to overcome both mnbvmar and eatmore. Also it shouldn't be too expensive since he is already in Japan :)

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

      Thanks for the comment, but I didn't leave the contest.

      I was trying to improve my N^2logN solution to D and ended up with the 39th place instead of the 3rd. I wish I knew N^2logN was enough...(and E1 was really easy with bitset!)

      Though I couldn't make it to the finals, I would like to help the organizers in some way. So, maybe I can see you in Japan next year.

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

      I like your idea, but still it feels a bit unfair to change the rule after the contest ends.

      How about allowing maroonrk (or a few more) onsite participation unofficially? i.e., he participates in the same contest from the same room, but the official ranks and medals are given to the 8 official finalists. Something like JPN2 team in IOI2019.

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

Why the output of following sample case is 8 in problem B ?

10 4 8 5

7 2 3 6 1 6 5 4 6 5

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

    Total votes to add = 8*4 = 32

    Steps:

    (first sort the sequence)

    1. Add these votes: 1(+4),2(+4),3(+4),4, 5, 5, 6(+4),6(+4),6(+4),7(+4) (max 4 can be added) -- 28 votes done, 4 remains.

    2. Add these votes to above: ._,_,_,4(+2),5(+1),5(+1),_,_,_,_

    Now the 8th element will jump to 5th place.

    Since 8th smallest element can jump to 5th place, any element greater than the 8th smallest can be made to jump to 5th place. So, 8 is the answer.

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

Another piece of stats: 40 people solved D, and 10 of them did it in $$$O(N^2)$$$.

In any case, be sure to check the $$$O(N^2)$$$ solution in the editorial, I like it a lot.

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

    can you tell this stat for all problems ? It will help in improving a lot .

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

      You can check yourself how many people solved a given problem. As for "solved problem with a certain complexity", come on, no one will take the time to manually analyze thousands of solutions just for you.

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

      If you are looking for complexity for each problem then you can kind of guess them from constraints, for example, for problem B, $$$N$$$ $$$<= 1e5$$$ . That means $$$O(N^2)$$$ is not going to cut it rather $$$O(N log N)$$$ will.

      You can safely assume $$$10^8$$$ operations can be done in 1 sec and deduce rest from there.

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

    Did you expect $$$O(N^2 \log N)$$$ to pass?

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

      Not really. The only $$$O(N^2 \log N)$$$ we had during testing had a very large constant, and I couldn't squeeze it into the time limit. Turns out that simpler $$$O(N^2 \log N)$$$ approaches also exist.

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

I'm happy to see that tourist set problem D with the same background of the problem I set before (Score Distribution 3).

But I'm unhappy that I get AC 40 mins after contest end. :(

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

$$$O(n^2)$$$ solution to F:

First, dissect the histogram into a tree of size $$$O(n^2)$$$ where each node describes a part of the histogram and is of one of the following types:

  • Init: a leaf denoting an empty column.
  • Join(A, B): merge two nodes (A is on the left, B is on the right), assuming that no rook from A can see any cell from B and vice versa.
  • Add(A): append a bottom row to the histogram.

Note that there are $$$O(n)$$$ Init and Join nodes.

We'll do inclusion-exclusion on the columns which contain at least one non-covered cell. What happens if we set a subset $$$X$$$ of columns and we want to count the configurations of rooks which leave none of these columns fully covered? This can be solved by an easy DP/DFS on the tree we just constructed. This DP will return for each node:

  • The number of columns which must be left uncovered,
  • The number of rook configurations in the part of the histogram such that no rook is within any forbidden column, and there is a fully covered forbidden column,
  • The number of rook configurations in the part of the histogram such that no rook is within any forbidden column, and there is no fully covered forbidden column.

Init and Join are very simple here. When Adding the row, we can either leave the row empty (there's no fully covered forbidden column now) or we can put some rook (if there was a fully covered column, there will still be one). It's very simple to write all the transitions in $$$O(1)$$$ time by preprocessing the powers of 2.

How to continue from here? We'll compute this DP for all subsets of columns at once. Each node will now return:

  • need[], where need[k] denotes the sum over all k-element forbidden subsets of columns within this part of histogram of (the number of rook configurations such that there is a fully covered forbidden column),
  • noneed[], defined analogously, only that we count the configurations with no fully covered forbidden column.

DP will work in the same way as above, only that we also need to track the number of forbidden columns within the part of the histogram.

Init is very simple (and $$$O(1)$$$). Join can be easily done in the time proportional to the product of the widths of the histograms, and therefore all Joins will take $$$O(n^2)$$$ time. Add can be easily done in time proportional to the width of the histogram, and we can also prove that all Adds will take at most $$$O(n^2)$$$ time in total (we can bound the time by the area of the histogram).

My code is here, but it was kinda written in rush. Enjoy.

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

When you are using the late-submit strategy and shit suddenly got real

(https://atcoder.jp/contests/agc041/submissions?f.User=jonathanirvings)

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

In question A, when the parity is different. Why not we can simply take the minimum of n — a and b — 1

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

    You are assuming parity can't be changed but it can in change in two possible cases.

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

      Can you please tell me a test case where this logic will fail, as I am unable to think of any.

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

        When one of them reaches the end, in the next step parity will change.

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

        It is given that a<b, so a-1 will always be minimum than n-a. Similarly, n-b will be minimum than b-1. Hence u will always take min(a-1,n-b).

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

          a — 1 will always be minimum than n — a. But the point is b will also have to reach table 1, so it will take at least b — 1 matches to reach to table 1.

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

            For example, for the test case: 10 2 7. A will go to table 1 but B will also have to go to table 1. So the answer would be B — 1, i.e. 7 — 1 = 6.

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

              After two rounds, A will be at table 1 and B will be at table 5. Instead of waiting at table 1, A can move towards B. In this case, they will meet after two more rounds at table 3. Thus, the answer is 4.

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

                Thank you very much, sir. I did not figured out that A also can move towards B. I feel overwhelmed to see your reply.

                → Reply