Editorial for An Animal Contest 7 P3 - Squirrel Scramble

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.

Authors: WilliamWu277, julian33

Subtask 1

Hint 1

There are only two paths that matter from checkpoint $i$ to checkpoint $j$ .

Hint 2

You can either choose to use portals twice or don't use them at all to get from checkpoint $i$ to checkpoint $j$ .

Solution

It can be seen that when using a portal from checkpoint $i$ , it is only optimal to travel to the nearest one. Similarly, when coming out of a portal to get to checkpoint $j$ , it is only optimal to travel from the nearest portal to that checkpoint $j$ .

For each checkpoint, we can precompute the distance to the closest portal in $\mathcal{O}(N^2)$ time. When iterating through all pairs of checkpoints, we add to our answer the minimum of $dist\_to\_portal[i] + dist\_to\_portal[j]$ and $dist[i][j]$ .

Time Complexity: $\mathcal{O}(N^2)$

Subtask 2

Solution

There are multiple solutions for this subtask, but we will go over the solution that extends the best to subtask $3$ ~3~. We claim that for any index $i$ ~i~ there exists some index $k$ ~k~ such that for every $j$ ~j~ where $i < j \leq k$ ~i < j \leq k~ it is optimal to not use any portals, and for every $j$ ~j~ where $k < j \leq N$ ~k < j \leq N~ it is optimal to use portals. A proof will be shown in the subtask $3$ ~3~ solution. In order to find the index $k$ ~k~ we can use $2$ ~2~ pointers or binary search.

Time Complexity: $\mathcal{O}(N)$ or $\mathcal{O}(N \log N)$

Subtask 3

Solution

Now, we will prove our claim. If we use portals to go from $i$ ~i~ to $j$ ~j~ $(i < j)$ ~(i < j)~ the distance will be $f(i)+f(j)$ ~f(i)+f(j)~ where $f(x)$ ~f(x)~ is the distance to the nearest portal from checkpoint $x$ ~x~. If we choose to walk, the distance will be $p(j)-p(i)$ ~p(j)-p(i)~ where $p(x)$ ~p(x)~ is the sum of path lengths from the first checkpoint to checkpoint $x$ ~x~. In order for our claim about index $k$ ~k~ to be invalid, we need to find $3$ ~3~ integers $i$ ~i~, $y$ ~y~, and $z$ ~z~ where $1 \leq i < y < z \leq N$ ~1 \leq i < y < z \leq N~ and $f(i)+f(y) < p(y)-p(i)$ ~f(i)+f(y) < p(y)-p(i)~ and $p(z)-p(i) < f(i)+f(z)$ ~p(z)-p(i) < f(i)+f(z)~. If we subtract the first inequality from the second inequality we get: $\displaystyle \begin{align*} p(z)-p(i)-f(i)-f(y) &< f(i)+f(z)-p(y)+p(i) \\ p(z)-p(i)+p(y)-p(i) &< f(i)+f(z)+f(i)+f(y) \\ p(z)+p(y)-2p(i) &< f(z)+f(y)+2f(i) \end{align*}$ But, $f(z)$ ~f(z)~ is at most $f(y)+p(z)-p(y)$ ~f(y)+p(z)-p(y)~ because we can always choose to walk from $z$ ~z~ to $y$ ~y~ and then travel to $y$ ~y~'s nearest portal. So, we get: $\displaystyle \begin{align*} p(z)+p(y)-2p(i) &< f(y)+f(y)+p(z)-p(y)+2f(i) \\ 2(p(y)-p(i)) &< 2(f(y)+f(i)) \\ p(y)-p(i) &< f(y)+f(i) \end{align*}$ which is a contradiction of the initial inequality $f(i)+f(y) < p(y)-p(i)$ ~f(i)+f(y) < p(y)-p(i)~. Therefore, our claim was valid and we have solved the problem.

Time Complexity: $\mathcal{O}(N)$ or $\mathcal{O}(N \log N)$

Comments

There are no comments at the moment.