The second subround of Google Code Jam 2008 Round 1, consisted of three problems.

The first problem is a combination of geometry and combinatorics principles and was a bit on the hard side for the 15 points it was valued at.

The second problem was a blend between the Sieve of Erastosthenes and data structures.

The third problem was based on a classic solitaire card game. This one occurs to many as a standard exercise in data structures, like interval trees. However, here we will include a clever, simple solution that suits this problem very well.

This time, 39 contestants succeded in solving every input correctly from a total of 1715 who solved at least one dataset. The fastest to solve all tests was bmerry who took less than an hour!

**Credits**

Problem A. *Crop Triangles*
Written and prepared by Cosmin Negruseri.

Problem B. *Number Sets*
Written by John Dethridge. Prepared by Marius Andrei and John Dethridge.

Problem C. *Mousetrap*
Written by Jonathan Wills. Prepared by Frank Chu.

Contest analysis presented by Cosmin Negruseri, Xiaomin Chen, and John Dethridge.

Some pranksters have watched too much Discovery Channel and now they want to
build a crop triangle during the night. They want to build it inside a large
crop that looks like an evenly spaced grid from above. There are some trees
planted on the field.
Each tree is situated on an intersection of two grid lines (a grid point).
The pranksters want the vertices of their crop triangle to be located at
these trees.
Also, for their crop triangle to be more interesting they want the
*center* of that triangle to be located at some grid point as well.
We remind you that if a triangle has the vertices (x_{1},
y_{1}), (x_{2}, y_{2}) and (x_{3},
y_{3}), then the center for this triangle will have the coordinates
((x_{1} + x_{2} + x_{3}) / 3, (y_{1} +
y_{2} + y_{3}) / 3).

You will be given a set of points with integer coordinates giving the
location of all the trees on the grid.
You are asked to compute how many triangles you can form with **distinct**
vertexes in this set of points so that their center is a grid point as well
(i.e. the center has integer coordinates).

If a triangle has area 0 we will still consider it a valid triangle.

The first line of input gives the number of cases, **N**.
**N** test cases follow. Each test case consists of one line containing
the integers **n**, **A**, **B**, **C**, **D**,
**x _{0}**,

The parameters will be chosen such that the input set of trees will not have duplicates.

**X** = **x**_{0}, **Y** = **y**_{0}
print **X**, **Y**
for i = 1 to **n**-1
**X** = (**A** * **X** + **B**) mod **M**
**Y** = (**C** * **Y** + **D**) mod **M**
print **X**, **Y**

For each test case, output one line containing "Case #**X**: " where
**X** is the test case number (starting from 1).
This should be followed by an integer indicating the number of triangles
which can be located at 3 distinct trees and has a center that is a grid
point.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ **N** ≤ 10,

0 ≤ **A**, **B**, **C**, **D**, **x _{0}**,

1 ≤

3 ≤ **n** ≤ 100.

3 ≤ **n** ≤ 100000.

Sample Input

2 4 10 7 1 2 0 1 20 6 2 0 2 1 1 2 11

Sample Output

Case #1: 1 Case #2: 2

In the first test case, the 4 trees in the generated input set are (0, 1), (7, 3), (17, 5), (17, 7).

You start with a sequence of consecutive integers. You want to group them into sets.

You are given the interval, and an integer **P**.
Initially, each number in the interval is in its own set.

Then you consider each pair of integers in the interval.
If the two integers share a prime factor which is at least **P**, then you
merge the two sets to which the two integers belong.

How many different sets there will be at the end of this process?

One line containing an integer **C**, the number of test cases in the input file.

For each test case, there will be one line containing three
single-space-separated integers **A**, **B**, and **P**.
**A** and **B** are the first and last integers in the interval, and
**P** is the number as described above.

For each test case, output one line containing the string "Case #X: Y" where X is the number of the test case, starting from 1, and Y is the number of sets.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ **C** ≤ 10

1 ≤ **A** ≤ **B** ≤ 1000

2 ≤ **P** ≤ **B**

1 ≤ **C** ≤ 100

1 ≤ **A** ≤ **B** ≤ 10^{12}

**B** ≤ **A** + 1000000

2 ≤ **P** ≤ **B**

Sample Input

2 10 20 5 10 20 3

Sample Output

Case #1: 9 Case #2: 7

Mousetrap is a simple card game for one player. It is played with a shuffled
deck of cards numbered 1 through **K**, face down.
You play by revealing the top card of the deck and then putting it on the
bottom of the deck, keeping count of how many cards you have revealed. If
you reveal a card whose number matches the current count, remove it from the
deck and reset the count.
If the count ever reaches **K**+1, you have lost. If the deck runs out of
cards, you win.

Suppose you have a deck of 5 cards, in the order 2, 5, 3, 1, 4. You will reveal the 2 on count 1, the 5 on count 2, then the 3 on count 3. Since the value matches the count, you remove the 3 from the deck, and reset the count. You now have 4 cards left in the order 1, 4, 2, 5. You then reveal the 1 on count 1, and remove it as well (you're doing great so far!). Continuing in this way you will remove the 2, then the 4, and then finally the 5 for victory.

You would like to set up a deck of cards in such a way that you will win the game and remove the cards in increasing order. We'll call a deck organized in this way "perfect." For example, with 4 cards you can organize the deck as 1, 4, 2, 3, and you will win by removing the cards in the order 1, 2, 3, 4.

The first line of input gives the number of cases, **T**.
Each test case starts with a line containing **K**, the number of cards in
a deck.
The next line starts with an integer **n**, which is followed by **n**
integers (**d**_{1},**d**_{2}, ...), indices into the
deck.

For each test case, output one line containing "Case #**x**: " followed by
**n** integers (**k**_{1},**k**_{2}, ...), where
**k**_{i} is the value of the card at index **d**_{i}
of a perfect deck of size **K**.
The numbers in the output should be separated by spaces, and there must be at
least one space following the colon in each "Case #**x**:" line.

Memory limit: 1GB.

Time limit: 60 seconds.

**T** = 100,

1 ≤ **K** ≤ 5000,

1 ≤ **n** ≤ 100,

1 ≤ **d**_{i} ≤ **K**.

Time limit: 180 seconds.

**T** = 10,

1 ≤ **K** ≤ 1000000,

1 ≤ **n** ≤ 100,

1 ≤ **d**_{i} ≤ **K**.

Sample Input

2 5 5 1 2 3 4 5 15 4 3 4 7 10

Sample Output

Case #1: 1 3 2 5 4 Case #2: 2 8 13 4

The small case was easy to solve using brute force. For each combination of three points you needed to test if the center had integer coordinates. One tricky part was generating the sequence of points, since using 32-bit integers would have resulted in overflow when doing multiplications. One way to get around that problem was to use 64-bit integers.

The observation that helps in solving the large case is that we don't care
about the range of the coordinates for the points in the input. We only care
about the coordinates modulo 3.
We have 9 different classes of points. In bucket[i] we will count the number
of points for which

If the three points are in the same class then it's obvious that the center will have integer coordinates. It is easy to see that there is no triangle with two points in the same class and one point in a different class.

Here is some code that implements this idea:

for (int i = 0; i < n; i++) { bucket[((int)X0 % 3) * 3 + (int)Y0 % 3]++; X0 = (A * X0 + B) % M; Y0 = (C * Y0 + D) % M; } // The first case. for (int i = 0; i < 9; i++) // We use the formula for n choose 3 so that, // we don't use the same point twice or count // the same triangle more than once. ret += bucket[i] * (bucket[i]-1) * (bucket[i]-2) / 6; // The third case. for (int i = 0; i < 9; i++) for (int j = i + 1; j < 9; j++) for (int k = j + 1; k < 9; k++) if (((i / 3) + (j / 3) + (k / 3)) % 3 == 0) && ((i % 3) + (j % 3) + (k % 3)) % 3 == 0) ret += bucket[i] * bucket[j] * bucket[k]; cout << "Case #" << prob++ << ": " << ret << endl;

Test Data

We recommend that you practice debugging solutions without looking at the test data.

This problem describes a process where integers are grouped into sets, and then we are asked how many sets there are in the final result.

The process described is fairly slow:

- Create singleton sets of integers.
- Take each pair of integers;
- factor the two integers and see if they have a prime factor in common that is greater than or equal to P;
- if so, merge the sets that have these two integers.

We need to find the result of this process using a faster method. A few observations help here.

Firstly, we only need to find prime factors less than the size of the interval. If a prime is larger than or equal to the size of the interval, then at most one integer in the interval can have that prime as a factor, so it will never be used to merge sets.

Secondly, we can take a faster approach than finding the prime factors of
each integer separately.
Instead we consider each prime in turn and find all the integers in the
interval which have this prime as a factor, a technique generally called a
*sieve*.

Thirdly, joining sets can be implemented efficiently with a data structure
called *union-find* (or the *disjoint sets data structure*).
As we consider each prime and find all of the integers with that prime as a
factor, we join all of the sets containing those integers. We could also
build an undirected graph with nodes for the integers in the interval and the
primes, and edges representing which integers are divisible by which primes;
then the final sets are the connected components of this graph.

Prime sieving - Union-Find - Connected components

Test Data

We recommend that you practice debugging solutions without looking at the test data.

In this nice problem, there are two viewpoints one can start with.

- The current position is fixed and the array of cards is rotating each time.
- Think of the cards as a fixed ring (represented byan array) and the current position in focus as a pointer moving on the ring.

For most of us (and our programs), it is more convenient to adopt the second viewpoint.

After reading the story, it is not hard to see that the task is clear: put
card 1 in the first position, then for each card i (in the order 2, 3, ...,
**K**), we start from the current position, and find the i-th empty spot
to the right, wrap around as many times as necessary, then put card i there.

The problem is to simulate the process described above. What makes it
interesting is that **K** can be as big as 1000000, which makes the naive
**K**^{2})**K**)

Let **S** = √**K****K**
positions into **S** intervals of roughly equal size (also **S**). In
addition to bookkeeping which positions are occupied (an array of size
**K**, we call the first level counter), we also count for each interval
how many positions are occupied (an array of size **S** that we call the
second level counter).
With this information, we may skip intervals of length **S** as many as
possible, until we arrive at an interval where we know the card must belong
to. Then in that interval we only need to deal with at most **S** first
level counters.

Once we put down a card, it is a simple matter to update the counters. We only need to update one on the first level and one on the second level.

This solution runs in time **K**^{1.5})

Push the idea in the previous solution further. Why not have more levels of
counters?
In fact, one nice plan is to organize the levels into a binary tree. On the
bottom (first) level of the tree we have each position as a separate
interval. Every time we go up one level, we combine every other interval with
the next one. Thus we will have log**K** levels; the top level being a
single interval with all the positions. We omit the details, since we will
see this again in the analysis of a Round 1C problem.
We mention that the total number of counters is **K**)**K**) time to find the position and
another **K**)**K** log **K**)

For similar ideas in computer science, we refer to the Wiki page for interval trees.

Now let us do something different. At each step, after one position is occupied by card number i, we delete the position from the deck.

Notice that **n**, the number of queries is at most 100. We do not need to
relabel all the positions, it is enough to do this for those **n** that we
are interested in.

The solution can be implemented in two flavors, based on which viewpoint in the beginning of the analysis you pick. The short C++ program is, again, based on the second one, where the position (pos) changes as a pointer, and the deck does not move, except we delete one position in each step.

for (int j = 0; j < n; j++) answers[j] = -1; for (int i = 1, pos = 0; i <= K; i++) { // Compute the next position, after wrap-around. pos = (pos + i - 1) % (K - i + 1); for (int j = 0; j < n; j++) if (answers[j] < 0) { if (queries[j] == pos+1) { queries[j] = -1; answers[j] = i; } else if (queries[j] > pos+1) { // The effect of deleting the next position. queries[j]--; } } }

You can use a trick to combine the two arrays queries[] and answers[] into
one. The programs runs in **n K**)

Test Data

We recommend that you practice debugging solutions without looking at the test data.