1024. Three Machine Types in a Cycle

A factory has n machines, and every machine is one of exactly three TYPES. The types form a cycle: type A beats type B, type B beats type C, and type C beats type A. Which machine has which type is not given.

m claims arrive in order, each of the form

1 u v u and v are the same type 2 u v the type of u beats the type of v

A claim is FALSE when it contradicts the claims accepted before it, and a false claim is thrown away. Print how many of the m claims are false.

3 machines, claims 2 1 2 / 2 2 3 / 2 3 1 -> 0 3 machines, claims 2 1 2 / 2 2 3 / 2 1 3 -> 1 2 machines, claim 2 1 1 -> 1 5 machines, claims 2 1 2 / 2 2 3 / 2 3 4 / 2 4 5 / 1 1 4 -> 0

The first two examples differ only in the last claim. After "1 beats 2" and "2 beats 3", the three types are pinned relative to one another and 3 beats 1, so the third claim of the first example is true and the third claim of the second is false.

The fourth example walks the cycle four times: 1 beats 2 beats 3 beats 4 beats 5, so machine 4 is three steps round from machine 1, which brings it back to the same type.

## What most people try first

Assign a type to each machine by traversal and check every accepted claim after each new one. That is O(n + m) per claim.

The second common attempt is to keep only "same as" groups and treat "beats" separately. It fails on the first example, where no two machines are the same type and yet everything is determined.

## Triple the elements

Give every machine THREE elements:

u the type of u u + n the type that u beats u + 2n the type that beats u

Then both kinds of claim become merges, and both kinds of contradiction become lookups.

``` same(u, v): false when u shares a group with v + n, or with v + 2n otherwise merge u with v, u+n with v+n, u+2n with v+2n

beats(u, v): false when u shares a group with v, or with v + n otherwise merge u+n with v, u with v+2n, u+2n with v+n ```

## Reading the three merges of a "beats" claim

Take u of type A and v of type B, so that A beats B.

u + n is "what u beats", which is B, and v is B -> merge them v + 2n is "what beats v", which is A, and u is A -> merge them u + 2n is "what beats u", which is C, and v + n is "what v beats", which is C -> merge them

Every one of the three is a statement about which type an element stands for, and all three must be made, exactly as in problem 1023 where two were needed.

## Why the lookups catch every contradiction

beats(u, v) is impossible when u and v are already forced to be the same type, which is u sharing a group with v, and when v is already forced to beat u, which is u sharing a group with v + n, since v + n is exactly the type v beats. Those are the only two ways a claim can clash, because with three types in a cycle any two types are either equal or in one of the two beating orders.

same(u, v) is impossible when v is already forced to be what u beats or what beats u, which are the other two elements of v.

## A machine against itself

same(u, u) is always true and merges nothing new. beats(u, u) is always false, and the first lookup says so, since u shares a group with itself. No special case is written.

## Why the tripling rather than a value modulo 3

The alternative is problem 1020's structure with the carried value taken modulo 3, and it works. The tripling is written out because it needs no modular arithmetic at all and extends to any fixed number of states in a cycle by adding more copies, whereas the weighted version has to get the modulus right in three separate places: the compression, the merge and the check.

## Overflow

The structure has 3n elements, which is 3 * 10^5, and the answer is at most m. Nothing here approaches the 2147483647 a signed 32 bit integer holds.

## Cross-reference

Problem 1023 is this with two states instead of three, where the cycle collapses to a single flip and the tripling becomes a doubling. Problem 1022 is the same two-state question carrying one bit instead.

## Cost

Time O((n + m) alpha(n)). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ m ≤ 200000` - `t` is 1 or 2. - `1 ≤ u, v ≤ n` - `u` may equal `v`.