brdy's blog

By brdy, history, 3 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

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it
  • »
    »
    3 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 ?

    • »
      »
      »
      3 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.

      • »
        »
        »
        »
        3 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).

        • »
          »
          »
          »
          »
          3 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.

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

      C was easy than usual one

»
3 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.

  • »
    »
    3 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

    • »
      »
      »
      3 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"

      • »
        »
        »
        »
        3 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.

  • »
    »
    3 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)

  • »
    »
    3 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".

  • »
    »
    3 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?

    • »
      »
      »
      3 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.

    • »
      »
      »
      3 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.

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

why this approach is not working for problem D

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

  • »
    »
    3 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 dp 1 source vertex is s, in dp 2 source vertex is t

  • »
    »
    3 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];
    
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Where I can take official editorial ?

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Problem E was so cool!

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

  • »
    »
    3 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?

    • »
      »
      »
      3 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.

»
3 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

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