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