The writer is wo_

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

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3553 |

3 | tourist | 3515 |

4 | Benq | 3508 |

5 | ecnerwala | 3390 |

6 | TLE | 3223 |

7 | scott_wu | 3209 |

8 | Petr | 3205 |

9 | ksun48 | 3197 |

10 | Radewoosh | 3188 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 203 |

2 | antontrygubO_o | 189 |

3 | pikmike | 187 |

4 | Monogon | 186 |

5 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 180 |

8 | SecondThread | 174 |

9 | Radewoosh | 172 |

10 | ko_osaga | 161 |

The writer is wo_

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

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/13/2020 05:59:39 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

When you realized that you have mistakenly registered the beginner contest and admin can't do anything about 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 ?

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.

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

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.

Thank you so much !

C was easy than usual one

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.

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

Check this case out:

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

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.

no. You could have something like this:

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

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

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

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?

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

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.

why this approach is not working for problem D

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

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 iss, indp_{2}source vertex istYou can also do it in dijkstra like this when exploring a new vertex v from u:

Where I can take official editorial ?

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

Editorial Tab pops up right after contest ends.

Can we have editorial in English Please

Scroll down, it is in english too.

Problem E was so cool!

Was test case for problem E weak? For instance:

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

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?

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.

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

great achievement, but how did you connect to internet, just curious?

It's 2018! :) In-flight wifi!

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