brdy's blog

AtCoder Regular Contest 090 / AtCoder Beginner Contest 087
By brdy, history, 6 years ago, In English

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

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

Comments Comments (30)
| Write comment?
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

When you realized that you have mistakenly registered the beginner contest and admin can't do anything about it.

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

    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 ?

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

      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.

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

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

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

          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.

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

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    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

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

      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"

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

        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.

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

    no. You could have something like this:

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

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

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

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

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

    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?

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

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

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

      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.

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

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

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

    After dijkstra from source vertex, you can start a dfs from the destination vertex. Number of shortest paths from source vertex to current vertex = SUM(number of shortest paths from source vertex to children of current vertex (given the child lies in the shortest path)). in dp1 source vertex is s, in dp2 source vertex is t

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

    You can also do it in dijkstra like this when exploring a new vertex v from u:

    if (d[v] > d[u] + dist)
    d[v] = d[u] + dist, dp[v] = dp[u], pq.emplace(...);
else if (d[v] == d[u] + dist)
    dp[v] += dp[u];
    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Where I can take official editorial ?

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

Problem E was so cool!

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

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?

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

    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?

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

      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.

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

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

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

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 ???

→ Reply