Facebook Hacker Cup 2012 Round 3 @ https://www.facebook.com/hackercup/scoreboard?round=222291111185610

A - Trapezoids.txt

Consider two horizontal lines and a set of N trapezoids. A trapezoid T[i] 
between these lines has two vertices situated on the upper line and the other 
two vertices on the lower line. We will denote by a[i], b[i], c[i] and d[i] the 
upper left, upper right, lower left and respectively lower right vertices of 
the trapezoid T[i]. Assume that no two trapezoids share a common vertex 
(meaning that all a [i] and b [i] coordinates on the upper line are different, 
and the same holds for the bottom line and coordinates c [i] and d [i]). A 
trapezoid set is called disconnected if one can separate the trapezoids in two 
or more groups such that no two trapezoids from different groups intersect. 
Determine the smallest number of trapezoids to remove, such that the remaining 
trapezoids form a disconnected set. If the solution does not exist, output -1.

Input
The first line of the input file contains an integer T, and this is followed by 
T test cases. Each test case is given in the compressed format.

The first line of each test case contains the number of trapezoids N, an 
integer K, and integer parameters X, A, B, M, p, q. In the next K lines are 
given integer numbers aa[i], bb[i], cc[i], dd[i]. The following code is used 
for generating the next random number using linear congruential generator with 
the starting value X and parameters A, B and modulo M:
long long prior = X;
long long next() {
  prior = (A * prior + B) % M;
  return prior;
}
The following code is used for extending the auxiliary sequences aa, bb, cc and 
dd:
for (int i = K; i < N; i++) {
    aa [i] = aa [i - K] + next() % (2 * p) - p;
    bb [i] = aa [i] + 1 + next() % (2 * (bb [i % K] - aa [i % K]));
    cc [i] = cc [i - K] + next() % (2 * q) - q;
    dd [i] = cc [i] + 1 + next() % (2 * (dd [i % K] - cc [i % K]));
}
The final coordinates of the trapezoids are given by:
for (int i = 0; i < N; i++) {
    a [i] = aa [i] * 1000000 + i;
    b [i] = bb [i] * 1000000 + i;
    c [i] = cc [i] * 1000000 + i;
    d [i] = dd [i] * 1000000 + i;
}
Note that above code generates trapezoids that satisfy all conditions of the 
problem, and '%' denotes the remainder of division.
Output
For each of the test cases numbered in order from 1 to T, output "Case #i: " 
followed by a single integer, the minimum number of trapezoids that need to be 
removed such that the remaining trapezoids form a disconnected set.

Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 300 000
1 ≤ K ≤ N
0 ≤ X, A, B ≤ 2 000 000 000
-2 000 000 000 ≤ aa [i], bb [i], cc [i], dd [i] ≤ 2 000 000 000
1 ≤ p, q, M ≤ 2 000 000 000
Examples
In the first example, one can remove trapezoids 5 and 6 leaving two 
disconnected sets with trapezoids (1, 2, 3, 4) and (7, 8).

In the second example, the coordinates of ten trapezoids are

1000000 4000000 3000000 5000000
7000001 8000001 2000001 6000001
2000002 7000002 2000002 5000002
5000003 7000003 2000003 6000003
4 6000004 2000004 3000004
4000005 5000005 3000005 8000005
-999994 6 6 2000006
4000007 6000007 1000007 7000007
-999992 8 -999992 2000008
5000009 6000009 9 7000009

Example input
5

8 8 1 1 1 1 1 1
1 3 1 3
2 5 6 10
4 8 5 8
6 9 2 4
7 11 11 13
10 13 7 9
12 16 14 15
14 15 12 16

10 2 2 1 1 7 2 2
1 4 3 5
7 8 2 6

100000 2 1 1 1 2 1 1
-2 -1 -1000001 -1000000
-1000001 -1000000 -2 -1

200 3 5 1 2 1117 11 13
1 10 1 10
2 11 2 11
3 12 3 12

10000 1 0 0 1 2 1 1
1 10000 1 100000

Example output
Case #1: 2
Case #2: 6
Case #3: 50002
Case #4: 61
Case #5: -1

B - Divisor Function Optimization.txt

Let d(N) be the number of positive divisors of positive integer N. Consider the 
infinite sequence x(n) = d(n)a / nb, n = 1, 2, 3, … where a and b are fixed 
positive integers. It can be shown that this sequence tends to zero. Hence it 
attains its maximum. Denote it by p/q where p and q are co-prime positive 
integers. Your task is for given a and b find p and q modulo M = 109+7. But to 
keep input and output small you will be given tuples (b1; b2; a1; a2; c) and 
need to calculate the sum of (p mod M) for all pairs (a; b) such that b1 ≤ b ≤ 
b2, a1 ≤ a ≤ a2 and a ≤ c*b, and the same sum for q-values.

Input
The first line contains a positive integer T, the number of test cases. T test 
cases follow. The only line of each test case contains five space separated 
positive integers b1, b2, a1, a2 and c.

Output
For each of the test cases numbered in order from 1 to T, output "Case #i: " 
followed by a space separated pair of integers: the sum of (p mod M) for all 
pairs (a; b) mentioned above and the sum of (q mod M) for all such pairs. Note 
that you need to find the sum of residues not the residue of sum (see testcase 
3 as a reference).

Constraints
1 ≤ T ≤ 20
1 ≤ b1 ≤ b2 ≤ 10000
1 ≤ a1 ≤ a2 ≤ 250000
1 ≤ c ≤ 25
in each testcase the total number of pairs (a; b) for which the answer should 
be calculated does not exceed 100000

Example input
5
1 1 1 3 10
1 2 1 88 3
1 10 1 50 5
1 1 1 15 15
30 33 1 29 25

Example output
Case #1: 1540 37
Case #2: 2377233 1491
Case #3: 75232917907 54682660016
Case #4: 5956707232 7441063226
Case #5: 116 116

C - Unfriending.txt

It's time to clean up your friends list after friending too many people on 
Facebook over the winter. The set of your friends' user ids is F = {x0, x1, 
..., xn-1}. Each friend from F is on zero or more friend lists that you use to 
organize your friends. There are M friend lists, c0, c1, ..., cm-1. You can 
unfriend (remove from F) some of your friends, but because you want to stay in 
touch with people, you can only unfriend one person from each friend list. You 
may also choose not to unfriend anyone from friend list. Any friend that isn't 
on a friend list cannot be unfriended.

Your goal is to find the maximum possible distance between the two friends 
whose user ids are the closest after you are done unfriending people. The 
distance between user id x and user id y is defined as abs(x-y).

Input
The first line contains a positive integer T, the number of test cases. T test 
cases follow.

The first line of each test case contains the number of friends N, and number 
of friend lists M, separated by a space. The second line contains x0 and 
integer parameters a, b, and p, separated by spaces. You must use these to 
generate the remaining numbers x1, …, xn-1 according to this formula:

xi = (xi-1 * a + b) mod p
The next M lines of each test case define the friend lists for that test case. 
Each line consists of the following integers, separated by spaces: size, y0, a, 
b. The size is the number of friends in the friend list. y0 is the index in F 
of the first friend in the list. You must generate the remaining friends in the 
friend list y1, …, yn-1 according to the following formula:
yi = (yi-1 * a + b) mod n
If a friend list contains more than one of a given index, consider it to only 
contain that index once.
Constraints
1 ≤ T ≤ 20
2 ≤ n ≤ 50 000
0 ≤ m ≤ 1 500
0 ≤ sum of sizes of all friend lists ≤ 1 000 000
Numbers used in generators:
0 < a, p < 230
0 ≤ b < 230

Output
For each of the test cases numbered in order from 1 to T, output "Case #", 
followed by the case number, followed by ": ", followed by the maximum possible 
distance between the two closest user ids that you are still friends with for 
that case.

Example input
5
9 2
48071530 715583197 479567108 1050406
2 6 743132951 85415827
2 3 376850600 968665455

11 3
787260730 352556659 382266931 1057730
2 9 734333632 693274928
4 2 109921566 4305285
2 6 677574083 984173544

10 3
395307869 893188066 853669149 1056195
4 7 225271526 816658669
4 0 131869161 339696459
4 7 709635520 662395613

12 3
796525811 590453825 261103276 1050505
3 9 594759110 714784928
3 5 431449006 621243801
3 10 638845242 279357772

12 2
609821186 802201942 33450613 1048819
4 3 988115593 116841583
4 0 327812052 590896542

Example output
Case #1: 7392
Case #2: 5130
Case #3: 15318
Case #4: 63175
Case #5: 5814