rng_58's blog

AtCoder Grand Contest 023
By rng_58, history, 6 years ago, In English

AtCoder Grand Contest 023 will be held on Saturday (time). The writer is maroonrk. This contest counts for GP30 scores.

Contest Link

Contest Announcement

The point values (and duration) will be announced later.

Let's discuss problems after the contest.

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

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

Minor quibble: it overlaps with tomorrow's BOI mirror, you could consider moving it slightly later. Of course, the overlap is just 30 minutes out of the 5-hour BOI, so it's not a big deal.

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

Unfortunately, it overlaps with google hashcode.

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

There are lots of contests in weekends and it's difficult to avoid all of them. Also, I think it's not a very good idea to move contests too frequently.

Thank you for the information, but we won't move it this time, sorry. Of course we will care more important contests (like CF, TC, major tournaments, etc.)

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

reminder: 5 mins

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

Problem F is similar to this

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

    Is this contest popular among Chinese?

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

      This problem is for the provincal OI team selection contest several days ago. It may be popular among the high school students.

      And it is similar to a very old problem.

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

On C, how to get the formula for number of ways to fill the first K positions of our permutation such that all squares are black (the C(K - 1, N - K - 1) part) ?

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

    You need a set {a1, a2, ..., aK} with a1 = 1, aK = N - 1.

    Let di = ai + 1 - ai. Thus, this is equivalent to choosing d1 + d2 + ... + dK - 1 = N - 2. Since di is either 1 or 2, we find that we must have N - K - 1 2s and the rest are 1s. This immediately gives C(K - 1, N - K - 1).

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

      In case someone's wondering (like me), why exactly, N - K - 1 2s. Here is the explanation:

      If all were 1, the sum would be K - 1, which is not equal to N - 2. Hence we need some 2s. Lets say we need 'x' number of 2s. So,

      2 * x + 1 * (K - 1 - x) = N - 2

      x + K - 1 = N - 2

      x = N - 1 - K

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

    You have k numbers 1 = a1 < a2, ... < ak = n - 1 such that ai - ai + 1 = 1 or 2. We have to have 2 as a difference n - 1 - k times. Because N - 2 = ak - a1 = (a2 - a1) + (a3 - a2) + ... + (ak - ak - 1) = k - 1 +  #(of twos). We want to have a sequence of differences of length k - 1 with n - 1 - k — twos, hence the formula.

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

Quality of problems on Atcoder never make me disappointed.

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

Thanks a lot for a great contest!

I have a question with regard to how Java is judged at AtCoder. After the contest I've submitted a solution to problem E that is slighly more complicated than in editorial (multiplies O(nlogn) 3x3 matrices), and I keep getting MLE. 4nlogn 3x3 matrices don't indeed fit into memory (they would take ~600M), but at any moment of time there should not be more than ~4n matrices in memory. So it seems that garbage collection does not happen or something like that.

Could it be that you're passing -Xmx<big number>? Could you maybe adopt the approach from http://codeforces.com/blog/entry/43696 ?

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

In problem E, can anyone explain the part "the number we want compute is exactly a half of the number of valid permutaions (after the replacement)."? Why it is true?

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

    I assume because when Ai==Aj, positions i and j are completely symmetric, and thus in exactly half of all cases there will be an inversion.

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

There is a typo in the editorial for F: "Let p be its children". It should be "Let p be its father".

→ Reply