AtCoder Grand Contest 031 will be held on Saturday (time). There are unusually many writers: yutaka1999, yosupo, DEGwer, maroonrk, hogloid, HIR180. All of them are participating in Oman camp now, and they formed a problemset together.
This is the first GP30-rated contest in this season — see this post for details.
Contest duration: TBD
The point values will be announced later.
Let's discuss problems after the contest.
Excited for my first AtCoder contest
Did the contest duration finalized?
In the top page of contest website, we can see that the duration is 160 minutes, in "Contest Information".
If I had to pick two things that are lowering my self-esteem then these are definitely sudoku competitions and AGCs.
why ?
Surprise, because I suck at them XD
r/humblebrag
the more easy to understand atcoder problems are ,the more hard to solve it .
How to solve C ?
Some editorials are ready (including C) and uploaded. Others will be uploaded when they are ready.
Lets mark
f(A,B,n)answer to the problem.Note that we can solve problem for $$$0, A \oplus B $$$ and then just xor everything with A. So lets solve the problem with A = 0.
If B has even number of bits — answer is trivially NO (you have odd number of moves, each move adds or removes one bit).
Otherwise lets find any set bit in B and if it's not the highest swap it with highest (again we can do the reverse for every number before outputing). Lets write B as $$$\overline{1C}$$$, where C are rest of the bits. . We'll build the answer so that the first $$$2^{n-2}$$$ numbers have 0 in highest bit, and the last one have 1.
$$$0, ... ,\overline{0M}, \overline{1M},....,\overline{1C}$$$
Lets select M such that we can calculate f(0,M,n-1) and f(M,C,n-1), e.g by selecting $$$M=C \oplus 1$$$ . Solve recursively on left and right half. Merge results (while adding $$$2^{n-1}$$$ to the right half). Reverse your operations (swap bits, and xor everything with A).
Used 80min on D and failed, and after looking at the solution I was like meh... Isn't it normal to admit that you got no observation, and give up if you didn't found anything till n = 6 ;_;
I also had this feeling but i wanted to check if the number of terms that makes up a_k grows linearly so i computed more.
C http://acm.timus.ru/problem.aspx?space=1&num=1972
I think Problem C is related to Gray Code and Hamiltonian path in Hypercube graph.
I also immediately googled "hypercube hamilton path", but Wikipedia said it's just easy, and skipped the proof, so I was disappointed :(((
You can delete a lot of edges and get a 2*2^(N-1) rectangle, so its pretty easy :)
Wow, this sentence helped me more in understanding the problem than the whole editorial :)
Tasks on AtCoder are good and interesting, but there is always some random constructive problem where I spent $$$\frac{2}{3}$$$ of time.
coming up with such problems is also hard .
It is too sad that simplex in E does not working :((
so now we can compete against each other by the number of tests we can pass with simplex, izban told me that he passed 65/75 tests with some heuristics
47 is my current maximum
The answer is 1, not 1.5
It seems to me that
I missed, thanks!
Yeah, nothing simplex-related works in E... :((((
You also sometimes have to discard the items the simplex decided to take fully...
In the end, I was trying to squeeze in some LP-guided branching (but it was severely limited by the problems above). Still, I didn't manage to pass 9 tests out of 70-some.
Nice strong tests, though.
LP-guided branching — nice, your FPT teachers would be happy to see you use it xD. Too bad it doesn't work (ಥ﹏ಥ)
I use about the 4, 5 days for the testcases of this problem. Thanks for giving the role to my efforts:)
Wow, two characters away from the correct solution in D. Wrote n instead of k and the small samples had k==n, so sad. But at least the problems were fun :)
can someone elaborate on solution for problem B please? I can't understand the editorial..
UPD: Thanks to P___ comment, i can get accepted on the problem :)
It basically means, that when you consider stone i-th, take the stone j-th with the same colour. Make sure that stone j-th has a different color then stone (j-1)'th. Then you have 2 choices: you just add stone i-th and do nothing or you add that stone and change all the stones from j-th to i-th (so the arrangements made up to j-1 stone can be counted twice with different suffixes).
That's why you add dp[i-1] + dp[j1-1] + dp[j2-1]+.. -> Assuming j1, j2 have the same color as i and different than j1-1, j2-1 etc.
The second requirement is necessary to avoid duplication in counting. When you add stone i, which has the same color as stone i-1, you can't change anything (all the changes will result in the same configuration as doing nothing).