Facebook Hacker Cup - Auction
Problem statement:
You have encountered a new fancy online auction that offers lots of products. You are only interested in their price and weight. We shall say that product A is strictly preferred over product B if A costs less than B and is not heavier (they may be of equal weight) or if A weighs less and is not more expensive (they can have equal price).
We shall call a product A a bargain if there is no product B such that B is better than A. Similarly, we shall call a product C a terrible deal if there exists no product D such that C is better than D. Note that according to our definitions, the same product may be both a bargain and a terrible deal! Only wacky auctioneers sell such products though.
One day you wonder how many terrible deals and bargains are offered. The number of products, N, is too large for your human-sized brain though. Fortunately, you discovered that the auction manager is terribly lazy and decided to sell the products based on a very simple pseudo-random number generator.
If product i has price Pi and weight Wi, then the following holds for product i+1:
Pi = ((A*Pi-1 + B) mod M) + 1 (for all i = 2..N)
Wi = ((C*Wi-1 + D) mod K) + 1 (for all i = 2..N)
You carefully calculated the parameters for the generator (P1, W1, M, K, A, B, C and D). Now you want to calculate the number of terrible deals and bargains on the site.
Input
The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case with 9 space-separated integers: N, P1, W1, M, K, A, B, C and D.
Output
Output T lines, one for each test case. For each case, output "Case #t: a b", where t is the test case number (starting from 1), a is the number of terrible deals and b is the number of bargains.
Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 1018
1 ≤ M, K ≤ 107
1 ≤ P1 ≤ M
1 ≤ W_1 ≤ K
0 ≤ A,B,C,D ≤ 109
Example input
5
5 1 4 5 7 1 0 1 2
3 1 3 3 3 1 0 1 1
8 1 3 3 3 1 0 1 2
13 5 7 5 9 1 3 2 5
11 2 3 5 7 11 13 17 19
Example output
Case #1: 3 3
Case #2: 3 3
Case #3: 2 3
Case #4: 2 2
Case #5: 3 1
Auction was by far the most difficult problem in the qualification round, with only 28 correct solutions. Solving the task efficiently required a few key observations. First of all, note that bargains and terrible deals are completely symmetrical under transformation P' = M + 1 - P, W' = K + 1 - W. Therefore we only need to consider the bargains part of the problem.
If the product is a bargain, it has minimum weight among all products with the same price. Since the constraints on K and M are relatively low (at most 107), it's possible to keep track of the product with minimum weight for each particular price and to consider only these products in the rest of the solution. Also we should account for products with the same weight and price by keeping the number of times each minimum occurs among products.
Let's assume that these minimum weights have already been calculated. Then in order to find all bargains we have to loop through all potential products in the order of increasing price, maintaining current minimum of weight. If the next product weights less than the current minimum, then it is in fact a bargain. By explicitly calculating the weight and price of each product using the formulas given in the statement and calculating the minimum weight for each price, we can get a solution that works in O(N) time. Unfortunately, N might be pretty big and this solution therefore won't run in less than 6 minutes.
In order to speed up the solution, we have to notice that because of pseudorandomness the sequences of prices and weights are periodical, maybe except for some small number of products in the beginning of the sequence. Even though the full period of both product properties may be as large as K*M, we can take advantage of the separate periods for price and weights. First, we process the non-periodic part of the product sequence and determine the periods of prices and weight -- let them be periodP and periodW. Consider all products that have price Ps, s < periodP. These are products with indexes s + i * periodP, i = 0,1,..,floor((N-s) / periodP)-1, let's call this set Bs. The respective weights of products in Bs are W(s + i * periodP) mod periodW. Now consider products in B(s + periodP) mod periodW. They all have the same price and the sequence of weights is the same as for Bsstarting from the second element. Thus if we write down the cycle of weights { W(s + i*periodP) mod period W, i = 0,1,2,...} then weights of products in Bx appear as a continuous subsequence in this cycle. We want to find the minimum value in each of these subsequences. Moreover, the number of elements in Bs for different s may differ at most by 1. This is a well-known Sliding Range Minimum Query problem that can be solved in linear time. If periodP is not prime we may need to consider several such cycles in order to cover all possible weights of products.
This way, minimum weights for each price can be found simultaneously for all prices in time O(periodP+periodW). It's not hard to add proper bookkeeping to handle repeating products with the same price and weight. Overall the solution has a complexity of O(K+M).
