WC '18 Contest 2 S4 - Car Convergence Chaos - Olympiads Online Judge

WC '18 Contest 2 S4 - Car Convergence Chaos

Points: 25 (partial)

Time limit: 1.8s

Memory limit: 256M

Author:

SourSpinach

Problem type

Woburn Challenge 2018-19 Round 2 - Senior Division

A nuclear bomb has been set up somewhere in Vancouver! Ethan Hunt and Solomon Lane have just learned of its location, and are each desperate to reach it first. If Ethan arrives on the scene first, he'll be able to shut it down, while if Solomon beats him to it, he'll surely detonate it to take the entire city down with him!

Vancouver has $N$ ~N~ $(1 \le N \le 5\,000)$ ~(1 \le N \le 5\,000)~ traffic intersections lined up in a row, numbered from $1$ ~1~ to $N$ ~N~ in order. Ethan is currently at some intersection $E$ ~E~, while Solomon is at a different intersection $S$ ~S~, such that $E < S$ ~E < S~ and $S-E$ ~S-E~ is even. The bomb happens to be located at the intersection $M$ ~M~ which is equidistant from both $E$ ~E~ and $S$ ~S~ (such that $M = \frac{E+S}{2}$ ~M = \frac{E+S}{2}~).

Ethan will drive a car through the sequence of intersections $E \to E+1 \to \dots \to M-1 \to M$ ~E \to E+1 \to \dots \to M-1 \to M~, while Solomon will drive through the sequence $S \to S-1 \to \dots \to M+1 \to M$ ~S \to S-1 \to \dots \to M+1 \to M~, until at least one of them arrives at intersection $M$ ~M~. Though they're both in quite the hurry, disobeying traffic laws would be too reckless, so they'll patiently wait at each intersection until the lights turn green. When a car is at an intersection $i$ ~i~, it must wait there for $T_i$ ~T_i~ $(1 \le T_i \le 100\,000)$ ~(1 \le T_i \le 100\,000)~ minutes before driving onwards to an adjacent intersection (either intersection $i-1$ ~i-1~ or $i+1$ ~i+1~), at which point the car will instantly move to that intersection.

For example, if $E = 3$ ~E = 3~ and $S = 7$ ~S = 7~, Ethan will spend the first $T_3$ ~T_3~ minutes at intersection $3$ ~3~ and the next $T_4$ ~T_4~ minutes at intersection $4$ ~4~, before reaching the bomb (intersection $5$ ~5~) after a total of $T_3 + T_4$ ~T_3 + T_4~ minutes. Meanwhile, Solomon will spend $T_7$ ~T_7~ minutes at intersection $7$ ~7~ followed by $T_6$ ~T_6~ minutes at intersection $6$ ~6~, and reach the bomb after $T_7 + T_6$ ~T_7 + T_6~ minutes. If $T_3 + T_4 = T_7 + T_6$ ~T_3 + T_4 = T_7 + T_6~, then both cars will reach the bomb. Otherwise, the slower car will stop driving as soon as the faster car reaches the bomb.

Meanwhile, Alan Hunley, the secretary of the IMF, will be monitoring the action closely. He'd like to keep track of how many times the identity of the agent currently closer to the bomb changes. To do so, he'll first form a Leader List, which has one entry for each minute (including both the very beginning, and the moment when a car reaches the bomb) indicating who is closer to the bomb (distance-wise) at that point in time. The distance between a car at some intersection $i$ ~i~ and the bomb (at intersection $M$ ~M~) is $|M-i|$ ~|M-i|~. Each entry in the Leader List is either Ethan, Solomon, or Neither (if they're both equidistant from the bomb), and the first entry (at minute $0$ ~0~) is always Neither. Alan will then remove all Neither entries from the Leader List (which may cause it to become empty). Finally, he will count the number of entries in the resulting Leader List which are either different than their preceding entry, or have no preceding entry. This count is formally known as the CCCC (Closer Car Change Count).

For example, if the initial Leader List is [Neither, Solomon, Ethan, Neither, Ethan, Ethan, Solomon], then Alan will reduce this to [Solomon, Ethan, Ethan, Ethan, Solomon], and determine its CCCC to be $3$ ~3~ (due to its $1$ ~1~st, $2$ ~2~nd, and $5$ ~5~th entries).

Due to some complex quantum time singularity science, the scenario described above will actually play out separately in one or more parallel universes, just with the initial state varying. Specifically, there is one parallel universe for each possible valid pair of starting intersections $E$ ~E~ and $S$ ~S~ (such that $E < S$ ~E < S~ and $S-E$ ~S-E~ is even). Considering each possible $(E, S)$ ~(E, S)~ pair independently, and computing its resulting CCCC value, what's the sum of all of these CCCC values?

Subtasks

In test cases worth $8/42$ ~8/42~ of the points, $N \le 300$ ~N \le 300~ and $T_i \le 20$ ~T_i \le 20~ for each $i$ ~i~.
In test cases worth $18/42$ ~18/42~ of the points, $T_i \le 20$ ~T_i \le 20~ for each $i$ ~i~.

Input Specification

The first line of input consists of a single integer, $N$ ~N~.
The next line consists of $N$ ~N~ integers, $T_{1 \dots N}$ ~T_{1 \dots N}~.

Output Specification

Output a single integer, the sum of all parallel universes' CCCC values.

Sample Input 1

4
5 6 5 3

Sample Output 1

Sample Input 2

7
7 3 6 2 5 2 8

Sample Output 2

Sample Explanation

In the first case, there are two possible $(E, S)$ ~(E, S)~ pairs: $(1, 3)$ ~(1, 3)~ and $(2, 4)$ ~(2, 4)~. The CCCC value for the first pair is $0$ ~0~, as both Ethan and Solomon will be 1 intersection away from the bomb for minutes $0 \dots 4$ ~0 \dots 4~, and then $0$ ~0~ intersections away at minute $5$ ~5~, resulting in an empty Leader List. The CCCC value for the second pair is $1$ ~1~, as Solomon will become $0$ ~0~ intersections away from the bomb at minute $3$ ~3~ while Ethan is still $1$ ~1~ intersection away from it, resulting in a Leader List of [Solomon]. The sum of these CCCCs is then $0+1 = 1$ ~0+1 = 1~.