rng_58's blog

Mujin Programming Challenge 2017
By rng_58, history, 8 years ago, In English

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.

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

»
8 years ago, # |
← Rev. 3   Vote: I like it +13 Vote: I do not like it

reminder(3days)

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

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

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

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

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

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

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

        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.

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

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

        I don't know the points of Codeforces.

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

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.

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

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

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

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

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

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?

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

Solution for problem A 900 points?

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

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

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

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

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

        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.

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

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

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

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

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

    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.

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

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

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

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

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

Is there going to be an editorial? Answered

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

Awesome problems, awesome editorials.

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

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.

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

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

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

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

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

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?

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

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

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

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

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

EDIT : Nvm found the error

→ Reply