1. Alphabet Soup

**Auction**

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 10^{7}), 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 P_{s}, s < periodP. These are products with indexes s + i * periodP, i = 0,1,..,floor((N-s) / periodP)-1, let’s call this set B_{s}. The respective weights of products in B_{s} 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 B_{s} starting 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 B_{x} 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 B_{s} 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).