rng_58's blog

By rng_58, history, 7 days 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  
  • +156
  • Vote: I do not like it  

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited for my first AtCoder contest

»
7 days ago, # |
  Vote: I like it -19 Vote: I do not like it

agc = power of rng_58

»
7 days 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".

»
7 days 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.

»
7 days 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 ?

  • »
    »
    7 days 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.

  • »
    »
    6 days 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).

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

  • »
    »
    7 days 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.

»
7 days ago, # |
  Vote: I like it +29 Vote: I do not like it
  • »
    »
    7 days ago, # ^ |
      Vote: I like it -50 Vote: I do not like it

    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

»
7 days 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.

  • »
    »
    7 days 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 :(((

    • »
      »
      »
      7 days 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 :)

      • »
        »
        »
        »
        6 days 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 :)

»
7 days 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.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 days ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    what is simplex ?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    +++
    • »
      »
      »
      7 days 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

  • »
    »
    7 days 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

  • »
    »
    7 days 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.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it -61 Vote: I do not like it

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

    • »
      »
      »
      7 days 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 (ಥ﹏ಥ)

    • »
      »
      »
      7 days 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:)

»
6 days 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 :)

»
6 days 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 :)

  • »
    »
    6 days 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).

»
21 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

is rated ))