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

Автор -emli-, 7 лет назад, По-английски

Two contests AtCoder Regular Contest 078 and AtCoder Beginner Contest 067 will be held at the same time.

You can participate in whichever contest you want. (However, you can't register to both competitions.) The last two tasks in ABC are the same as the first two tasks in ARC.

Time: July 15th (Saturday), 21:00 JST

Duration: 100 minutes

Number of Tasks: 4

writer: camypaper

Rating: 0-2799 for ARC, 0-1199 for ABC

The point values will be announced later.

We are looking forward to your participation!

UPD:

The point values are announced.

It is 100 — 200 — 300 — 400 — 800 — 900.

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

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

The point values are announced. (Link)
It is 100 — 200 — 300 — 400 — 800 — 900.

UPD: Thank you for updating blog.

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

I decided first time to participe on AtCoder contests and registered for Regular round. Than I decided that I want to do Beginner contest ( I think I am not ready for such big jump in competetive programming ), so I wanted to unregister and register again to different round, but there is not such option ( or I can not see it )...

If anyone know way, it would be nice to help me :)

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

    If I try little hard I can solve all problems in beginner contest, Your rating is high from mine. So it's easy to you.

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

    I think you should participate in regular round, because beginner rounds are easier than div2.

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

      @-emli-, Len

      I believe you are right about participation. But after exam at university, unrated CS Academy contest and two bad CF rounds for me, I wanted to feel as genious who can solve everything at some round :D Normally it is possible to fail again, but than I would fail on regular contest too.

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

      In addition, AtCoder Beginner Contest's maximum performance is 1600, even if you get 1st place. But AtCoder Regular Contest's maximum performance is 3200, so I think you should participate in regular round. (Rating approaches performance asymptotically)

      allllekssssa You are purple. Have confidence!!!



      Sorry for my poor English.

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

How did you solve Fennec VS. Snuke?

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

    Look at the path from 1 to n. First they will color whole path ( half one color half other). Than erase path you will get forest ( several trees ) . In each tree you will have one color and that whole tree will be colored on that way. So just count amount of nodes in "black root" trees and "white root" trees and see what is bigger.

    I really hate interactive problems, I came up with solution very fast, but I didn't get AC :(

    Is the last task some bitmask + max flow min cost algorithm ?

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

    Root the tree at vertex 1, now in optimal game snuke goes up some vertices up and paints the whole subtree white. So, just check the vertices the snuke can go and take the maximum subtree.

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

    I used a BFS maintaining 2 queues (black and white) and a distance array maintaining layers from nodes 1 and n. if a node from black has color black (let's call it t1), the distance of all it's adjacent nodes is d(t1)+1. if d(t1)+1 <= d(adjacent node) i will color it black and add it to queue. Similar thing can be done with white queue but one difference: add to white only if d(t2)+1 < d(adjacent node).

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

    I solved by this algorithm.

    1. Calculate dist(1, 1), dist(1, 2), ..., dist(1, N) and dist(N, 1), dist(N, 2), ..., dist(N, N).
    2. Define two integer a, b. Initially these two are 0.
    3. For each i: if dist(1, i) ≥ dist(N, i) a++, otherwise b++.

    4. a means the number of vertex which can get Fennec, and b means the number of vertex which can get Snuke.
    5. So if a > b, Fennec wins. Otherwise, Snuke wins.

    This algorithm is correct because there is no more than one vertex which is dist(1, i) = dist(N, i).

    My code is here. Sorry for my poor English.

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

    What I did was

    First maintain two array level1 and level2

    Bfs from 1 and store all the values of level of all the nodes in level1

    Bfs from N and store all the values of level of all the nodes in level2

    Then

        for(i=1;i<=n;i++)
        {
           if(level1[i]<=level2[i])
             ans1++;
           else
             ans2++;
        }
        if(ans1>ans2)
        {
           cout<<"Fennec"<<endl;
           return 0;
        }
        cout<<"Snuke"<<endl;
    
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Consider some vertex is painted in black at any stage of the game. Consider many components you will get when you remove current black vertex. One of that components will initially contain white vertices. White will never paint a vertex in any other component during the rest of the game. So black will paint them when the time comes in any case.

    So an optimal strategy for both players will be to paint next vertex on the shortest path from vertices 1 to n. In that way, they will potentially increase the number of vertices to paint in future for themselves.

    When the path is painted, you can simulate the process to see who will win. Or you can say that 1 is a root, calculate the size of the subtree for every vertex, compare the number of vertices in the subtree of the highest vertex the black player can get to with the remaining number of vertices in the whole tree.

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

    There is no need to find path from 1 to N or to compute any distances; one queue for bfs is enough. First vertex in queue is 1, it's colored black; second vertex is N, it's colored white; problem is solved with usual bfs — in one step just color all adjusting uncolored vertices the same color current vertex has, and add those to queue. And then compare sizes of two components (if black > white Fennec wins, otherwise wins Snuke).

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

Any Hint for Awkward Response?

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +22 Проголосовать: не нравится
    1. Calculate the number of digits.
    Detail


    2. Use binary search to get number. Since to be always n > N, the question number n should be multiple by 10. (This means if the number of digits of N is 2, the number of digit of n should be 3.

    Detail


    The code is here. Sorry for my poor English.

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

How did you solve Mole and Abandoned Mine?

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

For Problem E Awkward Response, is it possible to know the value of N for test cases 2,5,7,14,30?