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

agc = power of rng_58

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.

ok .

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).

kilotaras thanks

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

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

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 :((

what is simplex ?

+++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... :((((

The solution is non-integral (some variables won't be 0-1)You have to take the items that simplex discardedYou 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.

red coders knows a lot of things , but rng_58 is super red .. coming up with counter solutions of lgm

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).

is rated ))