Crop Triangles
Problem
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 (x1, y1), (x2, y2) and (x3, y3), then the center for this triangle will have the coordinates ((x1 + x2 + x3) / 3, (y1 + y2 + y3) / 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.
Input
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, x0, y0 and M separated by exactly one space. n will be the number of trees in the input set. Using the numbers n, A, B, C, D, x0, y0 and M the following pseudocode will print the coordinates of the trees in the input set. mod indicates the remainder operation.
The parameters will be chosen such that the input set of trees will not have duplicates.
X = x0, Y = y0
print X, Y
for i = 1 to n-1
X = (A * X + B) mod M
Y = (C * Y + D) mod M
print X, Y
Output
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.
Limits
1 <= N <= 10,
0 <= A, B, C, D, x0, y0<= 109,
1 <= M <= 109.
Small dataset
3 <= n <= 100.
Large dataset
3 <= n <= 100000.
Sample
Input
Output
2
4 10 7 1 2 0 1 20
6 2 0 2 1 1 2 11
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).
Number Sets
Problem
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?
Input
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.
Output
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.
Limits
Small dataset
1 <= C <= 10
1 <= A <= B <= 1000
2 <= P <= B
Large dataset
1 <= C <= 100
1 <= A <= B <= 1012
B <= A + 1000000
2 <= P <= B
Sample
Input
Output
2
10 20 5
10 20 3
Case #1: 9
Case #2: 7
MouseTrap
Problem
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.
Input
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 (d1,d2, ...), indices into the deck.
Output
For each test case, output one line containing "Case #x: " followed by n integers (k1,k2, ...), where ki is the value of the card at index di 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.
Limits
Small dataset
T = 100, 1 ≤ K ≤ 5000, 1 ≤ n ≤ 100, 1 ≤ di ≤ K.
Large dataset
T = 10, 1 ≤ K ≤ 1000000, 1 ≤ n ≤ 100, 1 ≤ di ≤ K.
Sample
Input
Output
2
5
5 1 2 3 4 5
15
4 3 4 7 10
Case #1: 1 3 2 5 4
Case #2: 2 8 13 4
Round 1B
Contest Analysis
Problem - Crop Triangles
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 x % 3 = i / 3 and y % 3 = i % 3. There are three different ways of choosing 3 points out of the 9 classes of points: three points from the same class, two points from the same class and one from a different class and three points from three different classes.
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;
Problem - Number Sets
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.
Problem - MouseTrap
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 Θ(K2) simulation too slow for our 8-minute time limit. For each step, we need to compute the next position much faster than Θ(K) as in the naive approach. We describe three solutions below.
Solution A.
Let S = √K, we partition the 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 O(K1.5).
Solution B.
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 logK 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 O(K), and for each card we will need O(log K) time to find the position and another O(log K) time to update the counters. The running time of this method is O(K log K).
For similar ideas in computer science, we refer to the Wiki page for interval trees.
Solution C.
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) time.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment