rng_58's blog

AtCoder Grand Contest 031 Announcement
By rng_58, history, 6 years ago, In English

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.

  • Vote: I like it
  • +159
  • Vote: I do not like it

Comments Comments (31)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited for my first AtCoder contest

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did the contest duration finalized?
In the top page of contest website, we can see that the duration is 160 minutes, in "Contest Information".

→ Reply
»
6 years ago, # |
  Vote: I like it +52 Vote: I do not like it

If I had to pick two things that are lowering my self-esteem then these are definitely sudoku competitions and AGCs.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it -6 Vote: I do not like it

the more easy to understand atcoder problems are ,the more hard to solve it .

How to solve C ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Some editorials are ready (including C) and uploaded. Others will be uploaded when they are ready.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 6   Vote: I like it +18 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ;_;

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +29 Vote: I do not like it

C http://acm.timus.ru/problem.aspx?space=1&num=1972

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I think Problem C is related to Gray Code and Hamiltonian path in Hypercube graph.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I also immediately googled "hypercube hamilton path", but Wikipedia said it's just easy, and skipped the proof, so I was disappointed :(((

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      You can delete a lot of edges and get a 2*2^(N-1) rectangle, so its pretty easy :)

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Wow, this sentence helped me more in understanding the problem than the whole editorial :)

        → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Tasks on AtCoder are good and interesting, but there is always some random constructive problem where I spent $$$\frac{2}{3}$$$ of time.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    coming up with such problems is also hard .

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is too sad that simplex in E does not working :((

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    +++
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      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

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it 
    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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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 discarded

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      LP-guided branching — nice, your FPT teachers would be happy to see you use it xD. Too bad it doesn't work (ಥ﹏ಥ)

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +208 Vote: I do not like it

      I use about the 4, 5 days for the testcases of this problem. Thanks for giving the role to my efforts:)

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply