rng_58's blog

AtCoder Grand Contest 017
By rng_58, history, 7 years ago, In English

AtCoder Grand Contest 017 will be held on Sunday (time). The writer is semiexp.

Contest Link

Contest Announcement

The point values will be 200 — 400 — 1000 (500) — 1100 — 1200 — 1600.

Let's discuss problems after the contest.

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

»
7 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

[reminder] The contest starts in 2 hours.

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

Your contests are serious hit on my self-esteem, guys.. It took me an hour to solve B and I totally don't know how to prove my solution to D, not to mention I couldn't come up with C or E at all. And something like that happens all the time I try to solve AtCoder. It seems I just can't into solving your problems :'(

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

    That's what you get for problems which require you to utilize your brain ;) If you participate for fun, not for self-esteem, such problems are much nicer than yet-another-standard-technical-problem from (put almost any other contest platform name here).

    That said, this time problem D wasn't very original :( It is called "Hackenbush", and it probably appeared before on dozens of different contests.

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

Have you seen D before? I was surprised to see that it was solved in 3 minutes.

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

    It came in our ICPC regionals and i have seen it at cf gym before as well.

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

    It's a well-known game called Green Hackenbush.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it -28 Vote: I do not like it

    Will the contest be unrated because of this ?

    UPD: It's rated

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

    khsoo01 didn't seen it before but he solved it in 3min. He said it was trivial grundy number question.

    I'm not familiar with grundy number, but I thought there will be simillar problem somewhere. So I started to google and found a nice editorial in HackerRank

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

    Yes,when practising for OI about 3 months ago,I was told the exactly same problem and its solution.And since the only difficulty lies in the way of calculating Sprague-Grundy function,the problem seemed to be easier than Problem A for me. (And I'm sure that many Chinese contestants,especailly who participated in OI,have seen this problem before.)

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

    Yes, I did: https://www.codechef.com/AMR16MOS/problems/AMR16J

    When I was solving problems from that Amritapuri contest I was pretty surprised, because I solved all harder problems without big effort (only painting one demanded more work for me), but I couldn't solve this one for a really long time. I was pretty frustrated that problem without any ACs was no-brainer for me, but I was stuck for few hours at something that so many teams have solved :p (results here: http://results.cloudcontest.org/amrita2016/ACMICPCRC.html, problem J). I finally solved it, but after long time. I wouldn't call it "trivial grundy question", it depends on some details in definitions you make whether solution becomes intuitive or not. Still, after I shared this with my teammates Marek told me it is well-known game called green hackenbush, as already mentioned here.

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

Never been waiting so eagerly for the testcases (of E) to be uploaded...

So to me seems like...
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Uploaded.

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

      Thanks ^ ^

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

      Typo in solution for E: replace

      if Di ≠ 0, r =  + Bi

      by

      if Di ≠ 0, r =  + Di

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

C was much harder than D and E IMO.

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

    Initially there were no queries in C. The writer's intended solution works in the same way even with queries (and it's described in the editorial), but I solved the original vertion with standard DP + segment tree, and we decided to add queries to avoid that. It seems it became much harder.

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

My F passes (after contest) in 3796 ms and 221568 KB, but during the contest it gave MLE with 275 KB. Did anyone else have this problem?

The limits seems very tight for this problem, even if you are trying to fail O(2^n n^3) solutions.

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

    Sorry this time the limit had to be very tight because we have to separate O(2nn2) and O(2nn3). Still our Java solution works in 2s.

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

      Before submission, it is strongly recommended to measure the execution time of your code using "Custom Test".

      This line tricked me into optimizing my O(mn22n) until it passed.

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

      Remember that Codeforces somehow shitty parses powers in Latex :p

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

Exact same question:

Link

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

O(1) solution for problem B:

    int start = a - (n - 1) * d;
    int len = (n - 1) * (d - c);
    int space = 2 * c + (n - 2) * (c - d);
    int end = a + (n - 1) * d;
    if(!(start <= b && b <= end))
    {
        cout << "NO" << endl;
        return 0;
    }
    if(space <= 0)
        cout << "YES" << endl;
    else
        cout << ((b - start) % (space + len) <= len ? "YES" : "NO") << endl;
→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

" On the other hand, when this inequality holds, we can find an example of Yi. We can first set the values of Yi to −D or C, and while the sum is smaller than B − A, we can increase integers one by one in the order Y1, Y2, Y3, . . . , YN−1, Y1, Y2, . . . ." . I am not getting these lines from editorial of B .Can someone please help !!!!

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

I have a solution using flow with upper and lower bound capcity and I wonder whether it is right.

For a piece i we make two new nodes : i and i + n, and we add an edge (i + n, i) with capacity [1, 1].

If piece i on the left of piece j, then we have:

Cj = 0 and Aj = Di

or

Di = 0 and Bi = Cj

then we add an edge (j, i + n) with capacity [0, 1].

Add twos edges (S, SS) and (TT, T) with capacity [1, 1], and if i can be put at the leftmost place, we add an edge (SS, i + n) with capacity [0, 1], similar for the rightmost one.

It's easy to make 2 * h new nodes to reduce the number of edges to O(n).

I wonder whether it's right. Anyone help me, please?

Sorry for poor English.

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

    My bad.

    I just want to find whether there's a Hamilton path in polynomial time.

    The solution above will find some circles instead of a Hamilton path.

    → Reply