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

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

The writer is wo_

Time

Scoring Distribution

ABC: 100 — 200 — 300 — 400

ARC: 300 — 400 — 700 — 900

https://arc090.contest.atcoder.jp/

https://abc087.contest.atcoder.jp/

Let's discuss the problems after the contest :)

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

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

    The opposite happened to me. I registered for the Regular contest and couldn't go to the Beginner contest anymore. xD. But, I was able to solve problem C. Was this an easier C than usual AtCoder contests ?

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

      The problem was very straightforward. I think it was the same difficulty as most C problems.

      Also I thought of O(N) dp and couldn't even think of the bruteforce.

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

        Normally, I can't solve C problems so I was feeling happy that I am improving.

        I did it with DP too.

        Do you mean O(MN) ? Where M is the number of rows and N the columns ? (M happens to be fixed in this question).

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

          Yeah M = 2 so I just said O(N).

          I meant straightforward as a DP problem, I didn't even think of the bruteforce xD.

          And good job on solving the problem! I hope you try your best in up solving to continue improving.

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

For problem D wouldn't the graph have to be a DAG to print "YES"? Editorial doesn't state that, not sure if this is correct observation.

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

    Idea: use BFS and push nodes with indegree 0 first. Then, update distances for each node reachable from source (like multi source shortest path). Check while updating data for any contradiction.

    My AC Submission: https://abc087.contest.atcoder.jp/submissions/2034615

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

      Check this case out:

      3 2
      1 2 100
      3 2 1
      

      Is this test valid? Your program outputs "No", yet top rated participant's program outputs "Yes"

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

        Yes, I too think answer would be "yes". Thank you for pointing out mistake, There is an implementation mistake, I should have used -ve edges too. This approach works with your test case. Weak test cases.

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

    no. You could have something like this:

    A->B 5 B->C 3 A->C 100

    which contradicts itself. (distance between AC != AC + BC)

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

    If the graph is not a DAG, answer is definitely "NO". If the graph is a DAG, it is NOT guaranteed that the answer is "YES".

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

    Thanks for the response guys. I have one more question: how could it be optimal to bfs/dfs from arbitrary vertices in each component(s)?

    I thought of everything else but got stuck on this in contest. Maybe I misunderstood something?

    Something like this:

    Wouldn't you have to start your traversal at A, and not B or C?

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

      Yes, you should start from the vertex which has 0 in degree.

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

      If you would like to start dfs from some arbitrary node, you have to consider reverse edges as well with negative egde value. Check my code here.

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

For problem E — Avoiding Collision, can someone explain how dp1 or dp2 is calculated in the official editorial?

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

Problem E was so cool!

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

Was test case for problem E weak? For instance:

6 10
1 6
1 2 1
1 3 1
2 3 1
2 4 1
2 5 1
3 4 1
3 5 1
4 6 1 
5 6 1
4 5 1

I have found out that solutions printing 16 and 12 both get AC. Or am I missing something?

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

    There are 4 shortest paths and there are no collisions, except the case when both use exactly the same path, so the answer is 4*3 = 12.

    Do you have a url to some accepted submission, which prints 16?

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

      Yep it should be 12. I made two submission of which one should not have been ACed.

      Check: 2036877 prints 16 and 2036879 prints 12

      The difference is during the checking for the case of the two people meeting in an edge.

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

I made a special screencast episode from this contest, as I participated this contest while flying over the Pacific :)

https://www.youtube.com/watch?v=ZUIbqx6Bi3k

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

is the idea for solving bonus version of last problem to use extended euclidean algorithm to find answer incases where digits in r does not exceed 12(instead of two pointers used in easier version) and then the rest part can be done similar to described in editorial in sqrt(n).Is this right ???