### rng_58's blog

By rng_58, history, 15 months ago,

We will hold AtCoder Grand Contest 035. This contest counts for GP30 scores.

The point values will be announced later.

We are looking forward to your participation!

UPD: We are very sorry, due to an urgent trouble we delay the round by 30 minutes. UPD2: We fixed the trouble and the round will start from 21:30 JST. Again we are very sorry for the inconvenience.

• +109

 » 15 months ago, # |   -36 i am sofa.
•  » » 15 months ago, # ^ |   0 this ??
•  » » » 15 months ago, # ^ |   -13 Why so many people do not like my comment.
•  » » » » 15 months ago, # ^ |   +14 According to the (virtual) rules of codeforces you need to be at least orange to get upvotes on such a shitty comment
•  » » » » » 15 months ago, # ^ |   +3 OK, i know it now.
•  » » » » » » 15 months ago, # ^ |   0 BTW do you know what does that mean, your first comment?
•  » » » » » » » 15 months ago, # ^ |   +69 In China, It means the first comment of all.
•  » » » » » » » » 15 months ago, # ^ |   +29 So it's like the usual Youtube comment "first"?
•  » » » » » » » » » 15 months ago, # ^ |   +20 Yup :>
•  » » » » » » » » » 15 months ago, # ^ |   +2 Ok, yeah, these kinds of comments always deserve downvotes.
•  » » » » » 15 months ago, # ^ |   +13 Probably you need people who understand what "Sofa" means and knows you too to give you upvotes before other people follows.
•  » » 15 months ago, # ^ |   +26 What's the meaning of 'sofa'? I can't understand
•  » » » 15 months ago, # ^ |   0 me2
•  » » » 15 months ago, # ^ |   0 It means "I am the first one to leave a comment." I hope it's helpful to you. :D
 » 15 months ago, # | ← Rev. 2 →   +13 Falls on the same date as Educational Codeforces Round #68 so I can take part in both contests.
•  » » 15 months ago, # ^ |   +13 and also no time conflict
•  » » » 15 months ago, # ^ |   +15 Both contests conflict with Wimbledon and Cricket World cup final though. :(
•  » » » 15 months ago, # ^ |   +23 well now it has :D
 » 15 months ago, # |   0 Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
 » 15 months ago, # |   +61 Does the delay have to be 30 minutes? In that case it will clash with the next Codeforces round.
•  » » 15 months ago, # ^ |   +11 The overlap is like 5 minutes and there's usually nothing to do in the last x minutes of the contest, so it's not that bad.
 » 15 months ago, # | ← Rev. 2 →   -7 And now I don't wanna give this contest anymore.
•  » » 15 months ago, # ^ |   +18 You can still take it instead.
 » 15 months ago, # |   -11 The contest was delayed by 30 minutes?
 » 15 months ago, # |   +81 First and last time I will ever write this, butPlease delay Educational by 10 mins)))
•  » » 15 months ago, # ^ |   0 Done. :p
 » 15 months ago, # |   0 And now it's clashing with Educational round 68 ;_;
 » 15 months ago, # |   +3 It seems that I have to stay up a little late.
 » 15 months ago, # | ← Rev. 2 →   -27 i deleted my response
•  » » 15 months ago, # ^ |   +30 I believe you have plenty of time to eat during the contest.
•  » » » 15 months ago, # ^ | ← Rev. 2 →   -17 i deleted my response
•  » » » » 15 months ago, # ^ |   -8 Maybe you can find inspiration by going to dinner when you have difficulty in solving problem a.
 » 15 months ago, # | ← Rev. 3 →   -55 The answer for First question for test case43 3 3 3should be NO. But my code gives answer as Yes and it is accepted. There exist no permutation of given input which will satisfy the given constraint but it is passing my solution which basically does this: Compute xor of all input and print YES if it 0 else print NO.the test cases are certainly weak or the tester/setter code is incorrect.
•  » » 15 months ago, # ^ |   -95 It is also giving tle for just insert and erase in multiset. The submission which is correct gives tle and submission which is logically incorrect is accepted. This makes no sense.
•  » » » 15 months ago, # ^ |   +58 Next time, don't discuss problems during the contest.
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   -155 Next time set better quality contest and don't give chance to anyone to discuss.
•  » » » » » 15 months ago, # ^ |   +36 Next time and also this time, follow the rules.
•  » » » » » » 15 months ago, # ^ |   -118 First of all you start following the rule of uploading correct test cases, then automatically all the rules will followed.
•  » » » » » » » 15 months ago, # ^ |   +28 Why should I upload test cases for a contest I'm competing in? That doesn't make any sense.
 » 15 months ago, # |   -47 The writers confirmed for bad test cases in first question. A simple test case was also not handled and people are busy thinking their solution is incorrect. This should be enough to make this round unrated. Please see into this. People have high hopes for their good ratings.
 » 15 months ago, # |   +1 Why is problem C named after Skolem?
•  » » 15 months ago, # ^ |   0
 » 15 months ago, # |   +39 Problem B is https://www.codechef.com/DEC18B/problems/EDGEDIR.
•  » » 15 months ago, # ^ |   0 I think B appears at least yearly in one contest (it's been part of the Romanian folklore for at least 12 years). In mathematics it's even better known. I find it very odd that atcoder would use such a problem. Also, B was significantly easier than C, I find it strange they had the same score
•  » » » 15 months ago, # ^ |   +13 Well, for me C was much easier than B. I haven't seen B before, it was an interesting problem for me.
 » 15 months ago, # |   0 How to solve B
 » 15 months ago, # |   +20 How to solve C?
•  » » 15 months ago, # ^ | ← Rev. 6 →   0 Here's a simple way to solve the problem:Let's first say Vertex $N+i$ as $i$ for simplicity, and all we need to do is place 2 vertexes with value $i$ such that it forms the required tree, where the weight of each vertex is its value.Now, take the first case when $N$ is odd, Place $1$ as the root of the tree, and for each $i$ where $i$ is even, connect with $1$ the following $2$ branches, $(i+1)-i-$ and $i-(i+1)-$. This would complete the requirement for all $i$ and $i+1$ such that $i$ is even. Next, we are only left to satisfy $1$ which could be simply done by connecting it to the leaf of any of the branches connected to $1$.Next case, when $N$ is even, We can do the above process to satisfy each vertex up to value $N-1$. Now, we just need to satisfy the criterion for vertex $N$ as well. We could show that these two vertexes must not be on the same branches, otherwise we wouldn't be able to satisfy vertex $N$, let's say they are on different branches, then, 1 must lie on the path between them, So, $1 \oplus x = N$ where $x$ is the weight of other vertexes on path, so, $x = N+1$. Another observation would be the following, that $N$ must be connected to the direct children of $1$. So, All we need to do is find two vertexes $j$ and $k$ $(1 \lt j,k \lt N)$. such that $j \oplus k = N+1$.
•  » » 15 months ago, # ^ |   +18 Good question. It took me probably over an hour to figure it out.If $N$ is a power of $2$, there's obviously no solution. Otherwise, there is a solution. For $N$ odd, it's easy, just make paths $(2k+1)-(2k)-1-(2k+1+N)-(2k+N)$ and add $N+1$ somewhere to the bottom.For $N$ even, we have to do something with the $(N, 2N)$ pair. For example, a path $(N)-(N+1-2^k)-(1)-(2^k)-(N+N)-(N+N+1-2^k)-(N+1)-(N+2^k)$ can do it, where the $k$-th bit in $N$ is $1$ ($k > 0$). This means we can't add all the remaining pairs $(2k, 2k+1)$ just like for $N$ odd, since we broke the pairs $(2^k, 2^k+1)$ and $(N-2^k, N+1-2^k)$. Fortunately, we can add $(2^k+1, N+2^k+1)$ from the first pair as $(2^k+1)-(1)-(2^k)-(N+2^k+1)$ and $(N-2^k, N+N-2^k)$ from the second pair as $(N-2^k)-(N+1-2^k)-1-(N+N-2^k)$, and the rest can be handled like for $N$ odd.
•  » » » 15 months ago, # ^ |   0 Got it.Thanks for the great explanation.
 » 15 months ago, # |   +21 D: Is this solution intended to pass? Because it runs like a beast, in <= 4 ms:Contiguous sequences of eaten cards are independent, so for each of them, let's find out all pairs of costs it can send to its (left, right).Let's take a sequence from card $l$ to card $r$. We're assuming that cards $l-1$ and $r-1$ haven't been eaten yet and the last of the cards $l$ through $r$ that's eaten is card $c$. Let's denote the set of pairs of costs added to cards $l-1$ and $r-1$ by eating these cards by $P_{l, r}$. For each pair $(x, y)$ in $P_{l, c-1}$ and $(z, w)$ in $P_{c+1, r}$, eating card $c$ (with cost $A_c + y + z$) afterwards means that we get a pair $(x+A_c+y+z, w+A_c+y+z)$ in $P_{l, r}$. We can try all possible $c$ and compute $P_{l, r}$ for each $l, r$.This is easy and it's slow, probably $O(N!)$. However, here comes a heuristic. Whenever there's a pair $(a, b)$ in $P_{l, r}$ such that there is a pair $(c, d)$ in $P_{l, r}$ with $c \le a, d \le b$, we can discard $(a, b)$. Discarding all such pairs is just sorting and one pass. That's it.
•  » » 15 months ago, # ^ |   -38 sir, can u plz explain in detail(easier version) , i'm new in cp... thanks!!
•  » » » 15 months ago, # ^ |   +10 It's a question for the organisers.
 » 15 months ago, # |   0 I tried B by simply iterating over the vertices and setting edge directions to make degree even but i am getting WA on some testcases. can someone please explain where this logic fails? https://atcoder.jp/contests/agc035/submissions/6375813
 » 15 months ago, # |   +23 I think for people like me who don't use prewritten code it would be nicer if you give some substantial amount of points for $O(n \log n \log m)$ in F (calculating power of polynomial via binary exponentiation, not $\log$ and $\exp$).
•  » » 15 months ago, # ^ |   0 From the editorial, it seems to me like this wasn't intended to pass, with or without prewritten code.
•  » » 15 months ago, # ^ |   0 Wow, checked tourist's solution and it was apparently possible to squeeze NTT in.You probably already checked the editorial, but the intended solution is just one loop in linear time, and the NTT solution misses a key idea, so maybe the opposite should've been done and constraints raised further to disallow all kinds of NTT?
•  » » » 15 months ago, # ^ |   +91 Wow, checked tourist's solution and it was apparently possible to squeeze NTT in. Sure, but it is a well known fact that when a CPU encounters tourist's code, it gets scared and runs twice as fast.
•  » » » 15 months ago, # ^ |   0 OK, intended solution is cooler :)Funny that if I didn't think that I have any chances to get AC with $O(n \log n \log m)$, I could probably find a way to simplify the polynomial on paper.
•  » » 15 months ago, # ^ |   +14 Sorry we didn't know the existence of such solutions. Our intended solution is simple $O(n log n)$.
•  » » 15 months ago, # ^ | ← Rev. 2 →   +8 Simple reduce to $O((N + M)log(N + M))$ by Taylor: $(\sum(\frac{n - i + 1}{i!}x^i)^m = (\sum(\frac{n + 1}{i!})x^i-\sum(\frac{1}{i!})x^i)^m=(n + 1 - x)^me^{mx}$.Easily to apply NTT here.
•  » » » 15 months ago, # ^ |   +7 And then we can multiply it by $n! e^{x}$, take coefficient before $x^{n}$ and get exactly the formula from editorial. Yes, I can do math too, but not when I have 18 minutes left and I'm writing FFT.
 » 15 months ago, # | ← Rev. 2 →   +5 My approach to F, which sadly didn't work out. Make a grid $(N+1) \times (M+1)$. In each row except the first one place a red token in some cell, similarly place blue token in some cell in each column except first. Blue and red token can share a cell. This token represents the number selected in row and column, respectively.A forbidden configuration is one that has a blue token directly below red one. In that case, we can move the tokens around to achieve a configuration without this pair, but one that generates the same grid. Now we have the following DP:$DP[i][j]$ = number of ways of placing red and blue tokens in columns $(1..i)$, such that $j$ red tokens have been used. The transition is $DP[i][j+k] = DP[i][j] * (M+1-k) * {M-j \choose k}$. Naively, this is $\mathcal O(NM^2)$.This is equivalent to $DP[N][j] = \sum \frac{M!}{\prod_{i=1}^N x_i! \cdot (M+1-x_i)}$ where $\sum x_i \leq M$, from which we can compute the answer. This can be computed by NTT and binary exponentiation in $\mathcal O(N \log N \log M)$. However, this is where I got stuck (or more precisely, the time ran out) — the input is too big to allow two logarithms, let alone the big constant of NTT, it runs for more than $20$ seconds even for $N=M=10^5$.EDIT: I read Um_nik's comment above and agree.
 » 15 months ago, # | ← Rev. 2 →   -8 .........................................
 » 15 months ago, # |   +60 AtCoder doesn't stop to amaze with their insane quality of problems. I absolutely loved E and F seemed to be great as well, but I didn't have time for it.
•  » » 15 months ago, # ^ |   +40 If I had to be really picky, I would object to B and C being constructive graph problems. But you're right, I enjoyed every single one that I solved and also loved revealing the secrets of F.
•  » » 15 months ago, # ^ |   +8 I can't comment on E or F and I liked C and (in principle) D, but B shouldn't have been used, since it's too standard. Also, A and maybe D allowed me to get an unfairly high place.
 » 15 months ago, # |   -38 There's some issues with the problem A. Consider this test case:41 2 5 6The answer should be 'No'. But many solutions output 'Yes', like #6386417, while some solutions output 'No', like #6386376, and they're both AC. This round should be unrated!
•  » » 15 months ago, # ^ |   -24 That's the limitation of system test format. Unless we expect such solutions in advance, we can't prepare counter-tests for them.
•  » » » 15 months ago, # ^ |   +20 In general, yeah, but in a problem where the answer is obviously No if the xor is non-zero, you can always expect a solution that outputs Yes if the xor is 0. I read the problem, immediately wrote and submitted that, thinking "well it's such a stupid simple solution that if it's wrong, you surely prepared countertests!".Also, it fails even on simple tests like "$N$ even, all $A_i$ identical".
•  » » » » 15 months ago, # ^ |   +65 Frankly speaking, when testers are strong, they miss too stupid solutions.
•  » » » » » 15 months ago, # ^ |   +16 They won't miss simple stupid solutions if they try to come up with them. The issue is they usually don't try.
•  » » » » » » 15 months ago, # ^ |   +15 We try hard to avoid wrong solutions, for example this time in problem D marathon specialist chokudai wrote a marathon-like solution for D and we tried hard to break it.Still, sometimes solutions we never imagine can appear. Here's a quiz for you. What wrong solutions passed in this problem? SpoilerN%K
•  » » » » » » » 15 months ago, # ^ |   +8 You can't make too many tests, because judging will be slow. The only way to fix it is multitest. If you give 10000 test cases, such wrong solutions wouldn't pass.
•  » » » » » » » » 15 months ago, # ^ |   0 That can be broken using "if small test then bruteforce" in solutions, but in general, yeah, +10000 small random tests are a good idea.
•  » » » » » » » » 15 months ago, # ^ | ← Rev. 2 →   0 Something that absurd is indeed impossible to predict but then usually it's hard to create tests that will let it pass. For example, 100 1 looks like a very important test in this problem (max/edge-test). Does it work iff K > N/2? That's really hard to avoid in 10-20 tests ;pBtw. the point touched by Xellos that "if small then bruteforce" is very important. Having this hack shouldn't give you AC so I don't like problems with multiple test cases and condition like "the sum of N doesn't exceed 1e6".
•  » » » » » » » » » 15 months ago, # ^ |   +10 Having this hack shouldn't give you AC so I don't like problems with multiple test cases and condition like "the sum of N doesn't exceed 1e6" But you can do the same in problems with single test case.
•  » » » » » » » » » 15 months ago, # ^ |   0 Nah, problems with single test case don't have thousands of small random tests.I'm saying the most important tests are smart big tests. The strength of tests is roughly equal to the number of types of big tests you will create.
 » 15 months ago, # |   +9 When will the testcases be uploaded?Link
•  » » 15 months ago, # ^ |   +23 Uploaded.
 » 15 months ago, # |   +10 Secret History: The idea of problem E is from the card game, Dominion (although the setting changed so much from original). Does someone enjoy this game and notice that?
•  » » 15 months ago, # ^ |   +15 I haven't played for so long... it seems like a card effect, which one?
•  » » » 15 months ago, # ^ |   +10 Original one is trashing a card from hand and gain (and topdeck) the cards whose costs are exactly -1 and +1 of the cost of the trashed card. In this problem it became -2 and +K.
 » 15 months ago, # |   +20 One of the many many instances of problem B.
•  » » 15 months ago, # ^ |   +11 And another one
 » 15 months ago, # | ← Rev. 2 →   +5 Can someone explain how Tourist's solution for D works in time? To me it looks like it will do 16! operations??
•  » » 15 months ago, # ^ |   +15 Let $f(k)$ be the number of recursive calls of Go when you call Go once with $to - from = k$.Then $f(k) = 1 + 2(f(1) + ... + f(k-1))$ and $f(k) = 3^{k-1}$.
 » 15 months ago, # |   0 From the editorial, for problem A, how do you observe that quickly?
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 May be slightly easier solution. Consider two cases: (a) the sequence begins with 2 equal numbers, (b) the sequence begins with 2 different numbers. In first case the sequence will look like: "x x 0 x x 0 ..." and in the second case it looks like "a b c a b c ...". Now the only thing is to handle the "last number = first number". But instead of that, you can observe that, "if you pick two unequal numbers from the given numbers, they will always be adjacent". So pick the largest number X and the smallest number Y (if all the numbers are equal, following solution still works). Consider them as first two numbers, and try to find all the next N — 2 numbers. Now just check if the count of the numbers in this sequence matches with the input. Also check if the last two numbers yield the first number.
 » 15 months ago, # |   +1 For task A, the solution given by the editorial is $O(n\log n)$. But I solved it in only $O(n)$. And I just judged whether the XOR of all numbers is ZERO. So how to prove the sufficiency?
•  » » 15 months ago, # ^ |   +1 Oh, I found it was wrong. Here is a hack data: 4 1 1 2 2 Obviously it is impossible.
•  » » » 15 months ago, # ^ |   +1 yes, problem a test case is weak.
•  » » 15 months ago, # ^ |   +13 It can be solved in $\mathcal O(n)$ though. You can simply answer No once the map has $4$ elements.
 » 15 months ago, # |   0 Please help with this solution for problem B, could someone provide some testcase when this code wont work? Here is my submission (just one wrong answer): https://atcoder.jp/contests/agc035/submissions/6383471
•  » » 15 months ago, # ^ |   0 i visited the vertices in the order of their new degrees, pls some testcase for which my algorithm fails?
•  » » » 15 months ago, # ^ |   +3 9 10 1 2 2 3 3 4 4 5 5 2 1 6 6 7 7 8 8 9 6 9 
•  » » » » 15 months ago, # ^ |   0 Thanks a lot :D .
 » 15 months ago, # | ← Rev. 2 →   0 where I can find the editorials in english for the AtCoder Grand Contest 035?
•  » » 15 months ago, # ^ |   +3 The same place as the Japanese oneProtip: Read the sentence in red.
 » 15 months ago, # |   +32 I am not able to understand dp in editorial of E for several days. Could please anyone help me?
•  » » 15 months ago, # ^ |   +14 Me neither, couldn't figure out how to do transition concerning the last dimension of the dp state in the tutorial.
•  » » 15 months ago, # ^ | ← Rev. 2 →   +8 This is pretty tricky to get right. Think of this that way. Every cycle of desired shape has some start and end which are of the same parity. It contains all elements with the same parity that are between them and moreover some more consecutive elements of the other parity which are symmetrical with respect to the middle of the cycle. We will "detect" such cycle just after the end of the other parity part.We are at some position $p$. Assume that x is the number of last positions with the same parity as $p$ that were deleted. That is $p, p-2, p-4, \ldots, p-2x+2$ were deleted, but $p-2x$ wasn't. Assume that y denotes the same but for the other parity, that is $p-1, p-3, \ldots, p-2y+$1 were deleted, but $p-2y-1$ wasn't. Assume x>y. This is the moment where we want to bound number of consecutive appearances of deleted positions for the future in order to omit the forbidden cycle. If $y=0$ then we won't get here any hypothetical cycle, so we don't have to do anything. If $y \ge 1$ and $2x \ge k+3$ then we know that if we delete next $\frac{k - 2y + 1}{2}$ elements with the same parity as $p$ then we get this forbidden cycle, so we keep $x + \frac{k - 2y + 1}{2}$ as the bound on the length of current length of consecutive deleted elements with the same parity as $p$.One more thing to note is that this is one bound for one parity, but what about the other parity? Maybe it has some bound on its length as well, so we should keep two bounds in state? Actually it is not necessary since we can keep the bound just for the parity that currently has longer suffix of deleted elements.Maybe my code can help: https://atcoder.jp/contests/agc035/submissions/6384104 but I used a bit different naming there. $b$ corresponds to $x$, $c$ to $y$, $d$ to that bound, prefix $prv_$ means it is from previous state, prefix $n$ stands for $\texttt{new}$ and stands for new value of that variable. $\texttt{dp[i][b][c][d]}$ stands for the number of states so that I considered $i$ positions, $x=b$, $y=c$ and the bound on the length of longer sequence of deleted elements is $d$ (meaning that, if it reaches $d$ then the cycle is completed, so $dp[i][d][c][d]=0$). I did this dp in "forward" manner instead of more popular "backward" manner. Ignore any ifs regarding debugs because they are successfully polluting this.Hope I helped.
 » 15 months ago, # |   0 I write a brute force for D and find out that the number of distinct ways is the $(n-2)^{th}$ Catalan number, which means it can actually be solved by brute force if we can avoid redundant states. The idea is basically if you have a b c d e, you will never eat b after d because it would yield the same result as eat b before d. My code
•  » » 15 months ago, # ^ |   0 Ok, that explains why my heuristic solution is fast enough, this is the worst case for it. It deals with much fewer states, but at least it's "much fewer than Catalan numbers" instead of "much fewer than factorial".
•  » » 15 months ago, # ^ |   0 Nonisomorphic ways of doing this process indeed correspond to binary trees with n-1 leaves, so it indeed is some Catalan number. It can be seen by marking spaces between elements and when we are removing some element we are merging two consecutive spaces.I noted this during competition, but somehow didn't realize that this is only 35 mlns...
 » 15 months ago, # |   -27 rng_58 Is the data of problem A weak? I found that if you just judge if the xor of all the numbers is 0,you will get AC,but the data 1 2 4 7 is No even 1^2^4^7 is 0 :).
 » 15 months ago, # |   0 I can't understand the editorial of problem E. In the situation where we cannot add $a$ to $S$, why $b$ must be less than $a$? And why a \not= b (mod 2)?