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

Автор rng_58, история, 7 лет назад, По-английски

Mujin Programming Challenge 2017 will be held on February 25th, 21:00 — 23:00 JST.

This is an online contest, and the top 30 people will be awarded prizes. The prize for the first place is $2000.

Please check the official site for details.

You will be asked to fill a questionnaire when you register, so please register at least several minutes before the contest.

UPD: Point values are 900(500) — 1300(300) — 1300 — 1800. The full scores correspond to C, D, E, F in AGC, and partial scores correspond to B, A.

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

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

reminder(3days)

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

What's the expected difficulty on a scale of Beginner to Grand contest? Also

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

    Yes, rated for everyone. The difficulty/quality of problems is similar to AGC.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      and what is difficulty of AGC? I registered at atcoder 10 minutes ago, so I don't know anything.

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

        CF div1, more or less. You can just read past AGC problems, but with these external contests, past problems aren't always an indicator of how hard they'll be this year.

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

        AtCoder Points: 900(500) — 1300(300) — 1300 — 1800 → TopCoder Points: 450(250) — 650(150) — 650 — 900

        I don't know the points of Codeforces.

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

The Mujin contest ends exactly when The CodeChef Lunchtime (authored by me) starts. Is it possible to move your contest to be 5 or 30 minutes earlier? Our starting time was announced first — Codechef times are the same every month, fixed from a long time.

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

    There are lots of contests especially in weekends, and it's difficult to avoid collisions with all contests. (Though I check dates of TC, CF, GCJ, FHC, Open Cup, etc.)

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится -9 Проголосовать: не нравится

      Does it mean "we don't want to, it's too late" or "there is some other contest before the Mujin"?

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

I just registered at AtCoder and didn't find a FAQ, so I guess I'll ask here. What are the point values in brackets? Are they for the same problems but with reduced constraints?

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

Solution for problem A 900 points?

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

    Just uploaded the editorial (click "editorial" tab).

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      In the editorial solution of the problem, Can anyone explain this line?

      " Notice that the number of valid orderings of the remaining frogs doesn’t depend on the choice of this first frog. "

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

        Our choice for the first frog doesn't affect which of the other frogs can be 2nd, 3rd, 4th, etc.

        3
        1 2 3
        

        In this sample case, frogs 1 and 2 can both be first place, but no matter which one we choose, frog 3 can always be second place.

        We have:

        • 2 options for which frog will be first place (either frog 1 or frog 2)
        • 2 options for second place (frog 3 and whichever we didn't choose last time)
        • The remaining frog will get third place.

        So our answer is 2 * 2 = 4.

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

Nice problems! Too bad I couldn't optimize Oriented Tree solution below O(N3) :(

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

In Robot and String queries can be answered in O(1). We basically need to check if one node is an ancestor of the other in a tree. Just run dfs and compute time when we enter and exit the node, then the answer is Yes if tin[r] <= tin[l-1] && tout[l-1] <= tout[r].

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Could you elaborate a bit on this approach? I got AC using the intended solution, but I'm not sure how to use a tree for this problem? Thanks!

    Edit: I see, it's a dfs with i being a child of j if f(i, j) is empty.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I don't understand how the tree is built. How would it look like for yzzyz?

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

        For each index i (1<=i<=n) and character ch ('a'<=ch<='z'), let next(i, ch) be the leftmost index j to the right of i such that the final state of the substring [i, j) after all reductions is the character ch.

        For ch1 < ch2 (eg. 'x' < 'y'), next(i, ch1) < next(i, ch2). This can be seen as follows. Suppose the final state of the string is y. That is possible only from xx. Consider the first x, due to which next(i, 'x') will be always be less than next(i, 'y'). So, for all ch such that ch>str[i], we can calculate next(i, ch) recursively as next(i, ch) = next(next(i, ch-1), ch-1) because we will always create ch from (ch-1)(ch-1).

        Apart from this, we calculate next_null(i) as the minimum j to the right of i such that the substring [i, j) is the empty string which is done using next(next(i, 'z'), 'z') as we can get that by deleting zz.

        For all ch such that ch<str[i], we have to first get the empty string and then only can be obtain that character (think about it). So next(i, ch) = next(next_null(i), ch).

        The tree mentioned in the editorial consists of only the edges i->next_null(i).

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Is there going to be an editorial? Answered

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

Awesome problems, awesome editorials.

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

A short tutorial on being the first to solve the "Oriented Tree" problem:

  1. Implement an O(n·diameter2) solution
  2. Get a half of AC's, a half of WA's and a single TLE on the system test data
  3. Fix the cause of WA's and add a special "if" to solve the bamboo-shaped tree case efficiently
  4. You're awesome!

That being said, I'm not sure about the n ≤ 1000 constraint when the intended solution works in O(n2). It was actually very easy to fix my solution so that it worked in O(n2) too, but I hadn't realized it before getting accepted.

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

    I also had O(n * d^2) solution and it worked without any special case handling in 1238 ms

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

As regards A. Here is my O(1) memory solution. It is very simple, so no need to explain it too much. You only construct as long sequence of frogs that can be jumped over by the last frog. When you can't do this, put the last frog right behind the last one. It can jump previously constructed sequence, but the next one would not be able to do that, so remove that frog from the sequence, reduce the multiplier and continue.

http://mujin-pc-2017.contest.atcoder.jp/submissions/1133610

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

I have a question to problem D.

The input is:

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

Why the output is not 8 but 10?

Shouldn't it be assigning different directions in each set: {(1, 2), (2, 3)}, {(1, 4), (4, 5)}, {(1, 6), (6, 7)}, which is 2 * 2 * 2 = 8 in total?

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

    There are two more assignments: all arrows pointing towards 1, and all arrows pointing away from 1.

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

Brilliant contest! I was really pleased to participate in it.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -21 Проголосовать: не нравится

EDIT : Nvm found the error