Ruler Of The Zoo
Contest: Codeforces Global Round 13
Difficulty rating: 3500
Tags: brute force, data structures

After realizing that Zookeeper is just a duck, the animals have overthrown Zookeeper. They now have to decide a new ruler among themselves through a fighting tournament of the following format:

Initially, animal $$$0$$$ is king, while everyone else queues up with animal $$$1$$$ at the front of the queue and animal $$$n-1$$$ at the back. The animal at the front of the queue will challenge the king to a fight, and the animal with greater strength will win the fight. The winner will become king, while the loser joins the back of the queue.

An animal who wins $$$3$$$ times consecutively will be crowned ruler for the whole zoo. The strength of each animal depends on how many consecutive fights he won. Animal $$$i$$$ has strength $$$A_i$$$ with $$$0$$$ consecutive win, $$$B_i$$$ with $$$1$$$ consecutive win, and $$$C_i$$$ with $$$2$$$ consecutive wins. Initially, everyone has $$$0$$$ consecutive win.

For all animals, $$$A_i > B_i$$$ and $$$C_i > B_i$$$. Also, the values of $$$A_i$$$, $$$B_i$$$, $$$C_i$$$ are distinct (all $$$3n$$$ values are pairwise different).

In other words, an animal who is not a king has strength $$$A_i$$$. A king usually has a strength of $$$B_i$$$ or $$$C_i$$$. The exception is on the first turn, the first king (animal $$$0$$$) has strength $$$A_i$$$.

Who is the new ruler, and after how many fights? Or will it end up that animals fight forever with no one ending up as ruler?

Input format:
The first line contains one integer $$$n$$$ ($$$4 \leq n \leq 6000$$$) — number of the animals.

$$$i$$$-th of the next $$$n$$$ lines contains $$$3$$$ integers $$$A_i$$$, $$$B_i$$$ and $$$C_i$$$ ($$$0 \leq A_i, B_i, C_i \leq 10^9$$$).

It is guaranteed that $$$A_i > B_i$$$ and $$$C_i > B_i$$$, and that all values of $$$A_i$$$, $$$B_i$$$ and $$$C_i$$$ are distinct.

Output format:
Output two integers in a single line. The first is the index of the animal that will become ruler, and the second is the number of fights passed until some animal becomes the ruler.

If the animals will fight for infinitely long, output -1 -1 instead.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The following describes the sequence of events for the second sample. Note that in fight $$$1$$$, the king (animal $$$0$$$) has strength $$$A_0$$$. The tournament ends at fight $$$7$$$ as animal $$$1$$$ wins fight $$$5$$$, $$$6$$$ and $$$7$$$.

Example input:
4
5 1 2
10 8 11
9 0 3
7 4 6

Example output:
-1 -1

Example input:
5
11 7 12
8 6 14
2 1 10
13 0 9
5 3 4

Example output:
1 7

Editorial:
part 1
Firstly, let's convert the queue into a circle. In our new problem, $$$n$$$ animals stand in a circle. The king fights the animal directly clockwise to it. If the king wins, he and the other person swap places, otherwise nothing happens. The animal that is king will always move 1 space clockwise regardless of what happens.

For example, in this scenario, 0 beats 1, so he stays as king. But he then loses to 2.
part 2
Let's give each animal a color. An animal $$$i$$$ is RED if $$$B_{i-1}$$$ > $$$A_i$$$. In other words, and animal is red if and only if the previous animal will beat it as king. The animals that are not red are called NONRED for now.
We can assume no two animals are consecutively RED* (*will elaborate more in part 4). Suppose we have 3 animals $$$XYZ$$$ in that order, and $$$Y$$$ is red while $$$X$$$ and $$$Z$$$ are non-red. Suppose $$$X$$$ becomes king and wins $$$Y$$$ but not $$$Z$$$. As such, the final arrangement is $$$YXZ$$$. The claim here is that $$$X$$$ and $$$Z$$$ cannot become RED.
For $$$X$$$, $$$X$$$ beats $$$Y$$$, We have $$$B_X > A_Y$$$, but since $$$A_X > B_X$$$ and $$$A_Y > B_Y$$$, we get that $$$B_Y < A_X$$$. As such, $$$X$$$ cannot be RED.
For $$$Z$$$, we have $$$C_X < A_Z$$$ (since X lost to Z) and $$$B_X < C_X$$$, we hence have $$$B_X < A_Z$$$. As such, $$$Z$$$ cannot be RED
Finally for $$$Y$$$, it is possible that it turns from RED to NONRED.
From these we can conclude that RED cannot be created, but can be destroyed
part 3
As such, we have the following conclusions:
• REDS are never created only destroyed
• The order of NONREDS will not change unless a RED inserts itself within the sequence
• REDS will never battle REDS (because of * assumption)
Since the number of times REDS can be destroyed is limited, we should exploit that. We define an event as either when a RED is destroyed or when the game ends. Since events can occur at most $$$O(n)$$$ times, we just need to find some way to quickly simulate the moves until the next event.
Let's visualize the moves like this: instead of the RED and NONRED swapping positions, the NONREDs are fixed in position, and the REDs move around anticlockwise.

After $$$n-1$$$ moves, every RED moves one space anticlockwise around the belt of NONREDs Then in that case, we just need to check how many sets of $$$n-1$$$ moves is needed until the first event occurs.
For convenience, let's split NONRED into BLUE and GREEN. If a NONRED beats a red in front of it, and it loses to next animal, then it is BLUE. If it wins one more time (and hence the entire game) it is GREEN.
Let's look at the conditions for the events:
1. A RED is destroyed. This occurs when $$$B_{nr} < A_{r}$$$ where $$$nr$$$ is any BLUE or GREEN
2. The game ends. This occurs when $$$B_{g} > A_{r}$$$ where $$$g$$$ is any GREEN
To find the first how many times the reds need to move anticlockwise, we could maintain a monotonic vector across the belt of NONREDs, and then for each RED, binary search the earliest position where an event occurs.
Finally, when we find the number of sets of $$$n-1$$$ we need to move backwards, we move everything manually, check if the game ends. Then we recompute the color of all animals, and repeat. If no event occurs, then it will repeat infinitely.
The step of finding the number of steps before first event occurs takes $$$O(nlogn)$$$ in total. Since REDs can disappear at most $$$O(n)$$$ times, then the total time complexity is $$$O(n^2logn)$$$.
It's worth noting that the constant factor for this algorithm is small as the number of REDs is $$$0.5n$$$ and binary search is a very fast log. Hence, it passes quite comfortably (author's solution is under 400ms) even though $$$n \leq 6000$$$.
part 4
In terms of implementation, we can run the first $$$2n$$$ by brute force just to handle some bad corner cases. In particular, it is mostly to handle the assumption "We can assume no two animals are consecutively RED".
If two animals are consecutively RED, then working out the inequalities will show that the one right before the two REDs should be able to win, and hence the game should end within $$$2n$$$ moves