Блог пользователя rng_58

AtCoder Grand Contest 017
Автор rng_58, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +102
  • Проголосовать: не нравится

»
7 лет назад, # |
← Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

[reminder] The contest starts in 2 hours.

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +74 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +66 Проголосовать: не нравится

    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.

    → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +65 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится -28 Проголосовать: не нравится

    Will the contest be unrated because of this ?

    UPD: It's rated

    → Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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

    → Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

So to me seems like...
→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

C was much harder than D and E IMO.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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.

    → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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.

      → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Remember that Codeforces somehow shitty parses powers in Latex :p

      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Exact same question:

Link

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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;
→ Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

" 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 !!!!

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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.

    → Ответить