Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя rng_58

AtCoder Grand Contest 023
Автор rng_58, история, 6 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +100
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Unfortunately, it overlaps with google hashcode.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

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.)

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

reminder: 5 mins

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Problem F is similar to this

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Is this contest popular among Chinese?

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      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.

      → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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) ?

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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).

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +95 Проголосовать: не нравится

Quality of problems on Atcoder never make me disappointed.

→ Ответить
»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится +7 Проголосовать: не нравится

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.net/blog/entry/43696 ?

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
6 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

→ Ответить