We will hold AtCoder Grand Contest 035. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc035
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20190714T2100&p1=248
- Duration: TBD (around 2 hours)
- Number of Tasks: 6
- Writer: DEGwer, camypaper, chokudai
- Rated range: All
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.
i am sofa.
this ??
Why so many people do not like my comment.
According to the (virtual) rules of codeforces you need to be at least orange to get upvotes on such a shitty comment
OK, i know it now.
BTW do you know what does that mean, your first comment?
In China, It means the first comment of all.
So it's like the usual Youtube comment "first"?
Yup :>
Ok, yeah, these kinds of comments always deserve downvotes.
Probably you need people who understand what "Sofa" means and knows you too to give you upvotes before other people follows.
What's the meaning of 'sofa'? I can't understand
me2
It means "I am the first one to leave a comment." I hope it's helpful to you. :D
Falls on the same date as Educational Codeforces Round #68 so I can take part in both contests.
and also no time conflict
Both contests conflict with Wimbledon and Cricket World cup final though. :(
well now it has :D
Auto comment: topic has been updated by rng_58 (previous revision, new revision, compare).
Does the delay have to be 30 minutes? In that case it will clash with the next Codeforces round.
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.
And now I don't wanna give this contest anymore.
You can still take it instead.
First and last time I will ever write this, but
Please delay Educational by 10 mins)))
Done. :p
And now it's clashing with Educational round 68 ;_;
It seems that I have to stay up a little late.
i deleted my response
I believe you have plenty of time to eat during the contest.
i deleted my response
Maybe you can find inspiration by going to dinner when you have difficulty in solving problem a.
The answer for First question for test case
4
3 3 3 3
should 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.
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.
Next time, don't discuss problems during the contest.
Next time set better quality contest and don't give chance to anyone to discuss.
Next time and also this time, follow the rules.
First of all you start following the rule of uploading correct test cases, then automatically all the rules will followed.
Why should I upload test cases for a contest I'm competing in? That doesn't make any sense.
Why is problem C named after Skolem?
See this https://en.wikipedia.org/wiki/Langford_pairing
Problem B is https://www.codechef.com/DEC18B/problems/EDGEDIR.
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
Well, for me C was much easier than B. I haven't seen B before, it was an interesting problem for me.
How to solve B
How to solve C?
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$$$.
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.
Got it.Thanks for the great explanation.
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.
sir, can u plz explain in detail(easier version) , i'm new in cp... thanks!!
It's a question for the organisers.
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
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$$$).
From the editorial, it seems to me like this wasn't intended to pass, with or without prewritten code.
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?
Sure, but it is a well known fact that when a CPU encounters tourist's code, it gets scared and runs twice as fast.
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.
Sorry we didn't know the existence of such solutions. Our intended solution is simple $$$O(n log n)$$$.
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.
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.
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.
.........................................
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.
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.
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.
There's some issues with the problem A. Consider this test case:
4
1 2 5 6
The 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!
That's the limitation of system test format. Unless we expect such solutions in advance, we can't prepare counter-tests for them.
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".
Frankly speaking, when testers are strong, they miss too stupid solutions.
They won't miss simple stupid solutions if they try to come up with them. The issue is they usually don't try.
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?
N%K
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.
That can be broken using "if small test then bruteforce" in solutions, but in general, yeah, +10000 small random tests are a good idea.
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 iffK > 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".
But you can do the same in problems with single test case.
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.
When will the testcases be uploaded?
Link
Uploaded.
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?
I haven't played for so long... it seems like a card effect, which one?
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.
One of the many many instances of problem B.
And another one
Can someone explain how Tourist's solution for D works in time? To me it looks like it will do 16! operations??
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}$$$.
From the editorial, for problem A, how do you observe that quickly?
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.
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?
Oh, I found it was wrong. Here is a hack data:
Obviously it is impossible.
yes, problem a test case is weak.
It can be solved in $$$\mathcal O(n)$$$ though. You can simply answer
No
once the map has $$$4$$$ elements.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
i visited the vertices in the order of their new degrees, pls some testcase for which my algorithm fails?
Thanks a lot :D .
where I can find the editorials in english for the AtCoder Grand Contest 035?
The same place as the Japanese one
Protip: Read the sentence in red.
I am not able to understand dp in editorial of E for several days. Could please anyone help me?
Me neither, couldn't figure out how to do transition concerning the last dimension of the dp state in the tutorial.
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.
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 eatb
afterd
because it would yield the same result as eatb
befored
. My codeOk, 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".
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...
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 even1^2^4^7
is 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)?