Editorial for SAC '22 Code Challenge 4 Junior P5 - Obligatory Output Only Problem - Olympiads Online Judge

Editorial for SAC '22 Code Challenge 4 Junior P5 - Obligatory Output Only Problem

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: maxcruickshanks

There are many solutions to this problem.

The main prerequisite to solving this problem is knowing how Dijkstra's algorithm runs.

Below is an outline of a solution:

$N = 10^5$ ~N = 10^5~

Connect $1$ ~1~ to $i$ ~i~ $(1 < i < N)$ ~(1 < i < N)~ with a weight of $i$ ~i~.

Connect $i$ ~i~ to $N$ ~N~ with a weight of $2 \times (N-i)$ ~2 \times (N-i)~.

Finally, output $N$ ~N~, $M$ ~M~, and the edges on separate lines.

Time Complexity: $\mathcal{O}(M)$ ~\mathcal{O}(M)~

This graph will push $N$ ~N~ into the queue many times since Dijkstra's algorithm will traverse $i$ ~i~ first and then discover $i$ ~i~ to $N$ ~N~ is better, but then $i+1$ ~i+1~ to $N$ ~N~ is better, and so forth.

$N$ ~N~ will check each of its adjacent edges $(N-1)$ ~(N-1)~, causing the counter variable to exceed $10^7$ ~10^7~.

Comments

There are no comments at the moment.