rng_58's blog

AtCoder Grand Contest 003
By rng_58, history, 8 years ago, In English

AtCoder Grand Contest 003 will be held on Sunday (time). The writer is DEGwer.

Contest Link

Contest Announcement

Let's discuss problems after the contest.

Also, we've just announced Code Festival 2016!

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

I'm new to your site where to register in the contest?

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

Thanks for holding those contests!

Would it be possible for you to maintain an official Google Calendar with contests, like TopCoder does, so that one can import it and never miss a round?

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

I'm looking forward to seeing you in the contest!

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

I solved last time's F (when upsolving) in around 10 minutes and had much more trouble with D/E, so I intended to start from the hardest problem now, but after reading it... no way.

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

    Actually F is not hard if you notice that you don't have to deal with the complicated case(connected in both side)... But I didn't even notice that black cells are connected Orz

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

What is the intended solution for E?

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

    Please check "Editorial" tab for intended solutions.

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

      I can't find editorial in english, can u please provide me with the appropriate link , Thanks in advance :)

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

    I solved it by expressing the array after each query as previous arrays and some prefixes of the initial array, then as just prefixes of the initial array. I maintain a prefix of some array, find the first time this prefix was formed (the latest array before it that has length less than this prefix), then split it into a prefix of this smaller array plus its  ≥ 1 whole copies. This can only be repeated times, since the length of this current prefix always decreases at least twice; the total time complexity is using good RMQ to find the last smaller element.

    And I just noticed after looking for you in the scoreboard, sorting by name shouldn't be case sensitive...

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

http://pastebin.com/dr4fzuLT For B , any Test Case where greedy strategy of making pairs in increasing order fails?

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

I missed the "all black cells are connected" condition in problem F and marvelled at the number of AC solutions while having exactly zero ideas how to solve it.

Does anyone have any clue how to solve this problem in general case?

And by the way, the problems were awesome, thanks a lot!

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

    At least I couldn't find the solution in general case when I made this problem.

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

Can D be solved using some sort of inclusion-exclusion?

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

Testdata for problem D is too weak, my code takes more than 10 seconds in this case: generator.

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

    Sorry, that's my fault. Generator contained some bug so there are no case that consists of around 100000 distinct primes, although I tried.

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

I am wondering whether this solution to E is correct:

Let's define B sequence as in editorial(increasing suffix minimums). Build a segment tree with min(N, B[0]) ones. Next, let's process B sequence.

In i-th step multiply whole array by max(1, B[i + 1]/B[i]) and then add 1 to range [1, B[i + 1] % B[i]]. We can then restore the answer by querying the tree : Sum[1,1], Sum[2,2] etc. In this solution time complexity is O(N log N + Q log N), so I think it's better than editorial one.

Tree can be build like in this editorial : https://discuss.codechef.com/questions/72277/addmul-editorial

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

In C, I used two priority queues. I stored all even indexed elements in one and odd indexed in the other. The I alternatively started popping the first queue, if q1.top() <= q2.top(), I just pop it else I popped q2 and pushed q1.top() to q2 and incremented a counter variable.

I then printed the counter variable. This gave me WA in last 7 test cases. Although the intended solution is much easier, I just want to know what is wrong with my approach. Thank you.

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

begin sob story During contest, I submitted correct solution to problem E but with unneccesary cout statements. The grader gave me verdict TLE because I printed too many of these, but I assumed my program was too slow and went to problem F.

After contest commenting out 3 lines of cout gives AC.

(http://agc003.contest.atcoder.jp/submissions/847933,

http://agc003.contest.atcoder.jp/submissions/848807)

end sob story

But I personally think that the grader should give feedback on sample inputs.

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

    Did you see the details during the contest? There are some WA in it.

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

    Mmm, there are sample tests at the bottom. Weren't them there during the contest too? Btw, my condolences :|

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

    You have no idea how many times this (or leaving a bruteforce/generator from debugging in the code) has happened to me. That's why I check all couts in my code before submitting and test it on samples. Sometimes, I still forget and get a WA, but it's been happening much less often lately.

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

      Ok, looks like I am not yet experienced with these contests or AtCoder interface yet, I did forget to click details.

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

Did everyone who solved D used same approach as editorial?

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

How to solve D? I am not able to understand editorial.

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

    In which part do you have a trouble? Computing Pair(t)? Something else?

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

      What exactly are we doing after calculating pairs and norms ?

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

        Consider a graph where each vertex corresponds to a number and there is an edge between two vertices if the product is cubic. This graph will be a set of complete bipartite graphs, so the size of max independent set is (total number of vertices) — (max matching). Max matching can be computed greedily by eliminating edges one by one.

        → Reply