### rng_58's blog

By rng_58, history, 5 years ago,

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

 » 5 years ago, # | ← Rev. 3 →   +13 reminder(3days)
•  » » 5 years ago, # ^ |   +6 reminder(1day)
•  » » » 5 years ago, # ^ |   +3 reminder(2hours)?
 » 5 years ago, # |   +33 What's the expected difficulty on a scale of Beginner to Grand contest? Also
•  » » 5 years ago, # ^ |   +26 Yes, rated for everyone. The difficulty/quality of problems is similar to AGC.
•  » » » 5 years ago, # ^ |   0 and what is difficulty of AGC? I registered at atcoder 10 minutes ago, so I don't know anything.
•  » » » » 5 years ago, # ^ |   +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.
•  » » » » 5 years ago, # ^ | ← 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.
 » 5 years ago, # | ← 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.
•  » » 5 years ago, # ^ |   +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.)
•  » » » 5 years ago, # ^ |   -9 Does it mean "we don't want to, it's too late" or "there is some other contest before the Mujin"?
 » 5 years ago, # |   +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?
•  » » 5 years ago, # ^ |   +18 Yes :D
 » 5 years ago, # |   0 Solution for problem A 900 points?
•  » » 5 years ago, # ^ |   +8 Just uploaded the editorial (click "editorial" tab).
•  » » » 5 years ago, # ^ |   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. "
•  » » » » 5 years ago, # ^ | ← 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.
 » 5 years ago, # |   +3 Nice problems! Too bad I couldn't optimize Oriented Tree solution below O(N 3) :(
 » 5 years ago, # |   +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].
•  » » 5 years ago, # ^ | ← 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.
•  » » » 5 years ago, # ^ |   0 I don't understand how the tree is built. How would it look like for yzzyz?
•  » » » » 5 years ago, # ^ |   +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 chnext_null(i).
 » 5 years ago, # | ← Rev. 2 →   0 Is there going to be an editorial? Answered
 » 5 years ago, # |   +9 Awesome problems, awesome editorials.
 » 5 years ago, # |   +223 A short tutorial on being the first to solve the "Oriented Tree" problem: Implement an O(n·diameter 2) solution Get a half of AC's, a half of WA's and a single TLE on the system test data Fix the cause of WA's and add a special "if" to solve the bamboo-shaped tree case efficiently You're awesome! That being said, I'm not sure about the n ≤ 1000 constraint when the intended solution works in O(n 2). It was actually very easy to fix my solution so that it worked in O(n 2) too, but I hadn't realized it before getting accepted.
•  » » 5 years ago, # ^ |   +30 I also had O(n * d^2) solution and it worked without any special case handling in 1238 ms
 » 5 years ago, # |   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.
 » 5 years ago, # |   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?
•  » » 5 years ago, # ^ |   +13 There are two more assignments: all arrows pointing towards 1, and all arrows pointing away from 1.
 » 5 years ago, # |   +10 Brilliant contest! I was really pleased to participate in it.
 » 3 years ago, # | ← Rev. 2 →   -21 EDIT : Nvm found the error