### rng_58's blog

By rng_58, history, 11 days ago, ,

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 Announcement

Contest duration: TBD

The point values will be announced later.

Let's discuss problems after the contest.

•
• +156
•

 » 10 days ago, # |   0 Excited for my first AtCoder contest
 » 10 days ago, # |   -19 agc = power of rng_58
 » 10 days ago, # |   0 Did the contest duration finalized? In the top page of contest website, we can see that the duration is 160 minutes, in "Contest Information".
 » 10 days ago, # |   +52 If I had to pick two things that are lowering my self-esteem then these are definitely sudoku competitions and AGCs.
•  » » 10 days ago, # ^ |   -15 why ?
•  » » » 10 days ago, # ^ |   +12 Surprise, because I suck at them XD
•  » » 4 days ago, # ^ |   +6 r/humblebrag
 » 10 days ago, # | ← Rev. 3 →   -6 the more easy to understand atcoder problems are ,the more hard to solve it . How to solve C ?
•  » » 10 days ago, # ^ |   +4 Some editorials are ready (including C) and uploaded. Others will be uploaded when they are ready.
•  » » » 10 days ago, # ^ | ← Rev. 3 →   -10 ok .
•  » » 10 days ago, # ^ | ← Rev. 6 →   +18 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).
•  » » » 10 days ago, # ^ |   0 kilotaras thanks
 » 10 days ago, # |   0 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 ;_;
•  » » 10 days ago, # ^ |   0 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.
 » 10 days ago, # |   +29
•  » » 10 days ago, # ^ |   -50 no issue , as not everyone solves acm timus or if use , its not necessary he has solved that problem . c was a nice problem and it should be put on the common platform
 » 10 days ago, # |   +8 I think Problem C is related to Gray Code and Hamiltonian path in Hypercube graph.
•  » » 10 days ago, # ^ |   +12 I also immediately googled "hypercube hamilton path", but Wikipedia said it's just easy, and skipped the proof, so I was disappointed :(((
•  » » » 10 days ago, # ^ |   +29 You can delete a lot of edges and get a 2*2^(N-1) rectangle, so its pretty easy :)
•  » » » » 10 days ago, # ^ |   +16 Wow, this sentence helped me more in understanding the problem than the whole editorial :)
 » 10 days ago, # |   +5 Tasks on AtCoder are good and interesting, but there is always some random constructive problem where I spent $\frac{2}{3}$ of time.
•  » » 10 days ago, # ^ |   +6 coming up with such problems is also hard .
 » 10 days ago, # |   0 It is too sad that simplex in E does not working :((
•  » » 10 days ago, # ^ |   -9 what is simplex ?
•  » » 10 days ago, # ^ |   +5 +++
•  » » » 10 days ago, # ^ |   +20 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
•  » » » » 10 days ago, # ^ |   0 47 is my current maximum
•  » » 10 days ago, # ^ |   +13 3 1 1 1 3 2 1 2 3 1 3 L 2 2 R 2 2 D 2 2 The answer is 1, not 1.5
•  » » » 10 days ago, # ^ |   0 It seems to me that L 2 1 R 2 1 D 2 1 
•  » » » » 10 days ago, # ^ |   0 I missed, thanks!
•  » » 10 days ago, # ^ |   +28 Yeah, nothing simplex-related works in E... :(((( The solution is non-integral (some variables won't be 0-1)3 5 5 10 12 12 10 5 22 10 3 U 10 1 D 20 1 L 10 1  You have to take the items that simplex discarded4 5 5 10 12 12 10 5 22 10 5 12 11 3 U 10 1 D 20 1 L 10 1 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.
•  » » » 10 days ago, # ^ |   -61 red coders knows a lot of things , but rng_58 is super red .. coming up with counter solutions of lgm
•  » » » 10 days ago, # ^ |   +30 LP-guided branching — nice, your FPT teachers would be happy to see you use it xD. Too bad it doesn't work (ಥ﹏ಥ)
•  » » » 10 days ago, # ^ | ← Rev. 2 →   +208 I use about the 4, 5 days for the testcases of this problem. Thanks for giving the role to my efforts:)
 » 10 days ago, # |   0 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 :)
 » 10 days ago, # | ← Rev. 4 →   +8 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 :)
•  » » 10 days ago, # ^ |   +3 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).
 » 4 days ago, # |   0 is rated ))