### brdy's blog

By brdy, history, 3 years ago, ,

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

 » 3 years ago, # |   +10
•  » » 3 years ago, # ^ |   +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 ?
•  » » » 3 years ago, # ^ | ← 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.
•  » » » » 3 years ago, # ^ |   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).
•  » » » » » 3 years ago, # ^ |   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.
•  » » » » » » 3 years ago, # ^ |   0 Thank you so much !
•  » » » 3 years ago, # ^ |   0 C was easy than usual one
 » 3 years ago, # |   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.
•  » » 3 years ago, # ^ | ← 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
•  » » » 3 years ago, # ^ | ← 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"
•  » » » » 3 years ago, # ^ |   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.
•  » » 3 years ago, # ^ |   0 no. You could have something like this:A->B 5 B->C 3 A->C 100which contradicts itself. (distance between AC != AC + BC)
•  » » 3 years ago, # ^ |   +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".
•  » » 3 years ago, # ^ |   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?
•  » » » 3 years ago, # ^ |   +1 Yes, you should start from the vertex which has 0 in degree.
•  » » » 3 years ago, # ^ |   +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.
 » 3 years ago, # | ← Rev. 6 →   0 why this approach is not working for problem D
 » 3 years ago, # | ← Rev. 2 →   0 For problem E — Avoiding Collision, can someone explain how dp1 or dp2 is calculated in the official editorial?
•  » » 3 years ago, # ^ |   0 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 →   0 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, # ^ |   0 Where I can take official editorial ?
•  » » » 3 years ago, # ^ |   +3 https://arc090.contest.atcoder.jp/editorialEditorial Tab pops up right after contest ends.
•  » » » » 3 years ago, # ^ |   0 Can we have editorial in English Please
•  » » » » » 3 years ago, # ^ |   +1 Scroll down, it is in english too.
 » 3 years ago, # |   +13 Problem E was so cool!
 » 3 years ago, # |   +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?
•  » » 3 years ago, # ^ | ← 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?
•  » » » 3 years ago, # ^ |   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 12The difference is during the checking for the case of the two people meeting in an edge.
 » 3 years ago, # |   +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
•  » » 3 years ago, # ^ |   +3 great achievement, but how did you connect to internet, just curious?
•  » » » 3 years ago, # ^ |   +4 It's 2018! :) In-flight wifi!
 » 3 years ago, # |   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 ???