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.
reminder(3days)
reminder(1day)
reminder(2hours)?
What's the expected difficulty on a scale of Beginner to Grand contest? Also
Yes, rated for everyone. The difficulty/quality of problems is similar to AGC.
and what is difficulty of AGC? I registered at atcoder 10 minutes ago, so I don't know anything.
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.
AtCoder Points: 900(500) — 1300(300) — 1300 — 1800 → TopCoder Points: 450(250) — 650(150) — 650 — 900
I don't know the points of Codeforces.
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.
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.)
Does it mean "we don't want to, it's too late" or "there is some other contest before the Mujin"?
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?
Yes :D
Solution for problem A 900 points?
Just uploaded the editorial (click "editorial" tab).
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. "
Our choice for the first frog doesn't affect which of the other frogs can be 2nd, 3rd, 4th, etc.
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:
So our answer is 2 * 2 = 4.
Nice problems! Too bad I couldn't optimize Oriented Tree solution below O(N3) :(
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].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.
I don't understand how the tree is built. How would it look like for yzzyz?
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).
Is there going to be an editorial? Answered
Awesome problems, awesome editorials.
A short tutorial on being the first to solve the "Oriented Tree" problem:
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.
I also had O(n * d^2) solution and it worked without any special case handling in 1238 ms
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
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?
There are two more assignments: all arrows pointing towards 1, and all arrows pointing away from 1.
Brilliant contest! I was really pleased to participate in it.
EDIT : Nvm found the error