July CookOff Contest Problem Editorials

Problem Tester for the July Cook-off was Anton Lunyov

*****

GARDENSQ (written by Shilp Gupta) - (Trivial)

*****

The elegance of the garden could be easily calculated in O(N*N*N) time. A quick look at the limits should give you ample amount of confidence for the same! There were no mysteries. There were no intricacies. But, that's how a trivial problem is expected to be.

Simply iterate over the top left cell of any square (N*N) and then the size (N). Checking for whether a square is valid or not is constant time. Just check whether the four corners are the same color.

Problem Setter Solution

Problem Tester Solution

*****

MISINTER (written by Shilp Gupta) - (Easy)

*****

Chef's brother permutes the characters that Chef uses. This permutation has cycles. A cycle in a permutation is such that p[p[p[...p[i]...]]] = i; where p[x] depicts the position to which the item at x has been permuted to.

The key observation to this problem was that all the positions that participate in a cycle, need to have the same character. Thus the problem reduced to finding the number of cycles in the permutation, that Chef's brother will do.

The largest number of cycles for any case could be 4892.

The result will be (26 to the power C), where C is the number of cycles.

Problem Setter Solution

Problem Tester Solution

*****

CHIEFETT (written by Shilp Gupta) - (Medium)

*****

The intended solution to this problem is of complexity O(N*K).

The time limits proved to be tight.

The key observation in this problem is that, once Chief selects the items she wants to buy, the discounts are applied on them such that the largest discount is used on the item with the highest cost, the second largest discount is used on the item with the second highest cost and so on..

So first, we sort all the prices and discounts.

There are two solutions to this problem now.

Method 1.

Find the probability that we apply discount j on item i. Let this be p(i,j). Both i and j are 1-based.

- p(i,j) = c(i-1,j-1)*c(N-i,K-j)/c(N,K)

Explanation: if discount j is being used on item i, means there are j-1 items selected from i-1 items. Further, there are K-j items selected from the remaining N-i items. This is true, because we know that j'th smallest discount will only be used on item i; if the order of item i is 'j', in the sorted order of purchases made.

The expected discount is

- summation(1<=i<=N, 1<=j<=K, p(i,j)*price[i]*discount[j]/100)

Explanation: If we see the expected discount as small contributions from each item, we see that each item contributes to the expected discount whenever it is picked in a combination. And its contribution to the expected discount is the order index in which this item is picked. By linearity of expectation, we can consider the tuple of: each item (i), and the order index at which it is picked (j) - as the random variable. We know the probability of this variable, and its contribution to expected discount too. Hence this formula is valid.

Implementation of this algorithm had to be done carefully to avoid overflowing doubles. The time limits were quite tight if this approach was used. But since p(i,j) would be 0 for a large number of j - if K is almost equal to N - the optimization: iterate for only those j for which p(i,j) is non-zero - was enough.

Method 2. (Thank you Anton for pointing out this approach!)

Let, dp[i][j] = expected maximal discount that we can obtain if we consider only first 'i' items and first 'j' discounts.

Consider the following two cases:

1) i-th item is chosen

We apply j-th discount to i-th item and get discount price[i]*discount[j] and turn to situation with (i-1) items and (j-1) discounts. So in this case, expected discount is equal to a[i]*b[j]+dp[i-1][j-1].

The probability of this happening is p = j/i. Since we must choose j items from i, and probability that i'th item will be chosen is equal to j/i.

2) i-th item is not chosen

The answer is dp[i-1][j].

The probability of this happening is 1-p.

Thus we obtain the formula

dp[i][j] = (a[i]*b[j] + dp[i-1][j-1])*p + dp[i-1][j]*(1-p)

Then dp[n][k] is the answer.

Problem Setter Solution

Problem Tester Solution_1 and Solution_2

*****

MEANMEDI (written by Shilp Gupta) - (Medium - Hard)

*****

The time limits for this problem would seem very misguided in retrospect.

The expected complexity for the solution was O(N*S), where S was the largest sum that would be considered in the knapsack as described below.

First, needless to say, sort the numbers.

Now, iterate over each number, assuming it to be the Median, let this position be i. This forces us to select (K-1)/2 numbers towards the left of the median, and K/2 numbers towards the right of the median.

Perform a knapsack and pre-calculate the sums possible by selecting (K-1)/2 numbers in each segment from the beginning to any point within the array.

Perform a knapsack and pre-calculate the sums possible by selecting K/2 numbers in each segment from the end to any point within the array.

The optimization here, is on the fact that K/2 can be 30 at the most. So knapsack could be optimized to take only O(N*S) time, rather than O(N*K*S). This can be done by storing for each sum s the bit-mask of those values j for which s is representable as the sum of j numbers from the first i numbers of the array.

Now, we can treat the sums from the left and right of the median separately.

We can select each sum from the left, and a corresponding sum from the right; to find the sum, with which the mean is closest to the selected median. This determination step will be O(S) in complexity.

When a larger sum is selected on the left, we obviously select a smaller sum from the right. We can avoid doubles here by considering median*(K-1) and selecting the two sums, such that, their sum is closest to median*(K-1).

Most contestants were optimizing their O(N*K*S) solution. The test cases were such that such solutions were bound to fail the time limit. The time limits should not have been (but unfortunately were) tight for solutions with complexity O(N*S).

Problem Setter Solution

Problem Tester Solution

*****

CHEF_GAM (written by Shilp Gupta) - (Hard)

*****

A lot of time was spent in building this intricate problem. The inspiration for the problem came from an IMO 1986 problem, called the "pentagons problem".

The expected solution was O(N log N) in complexity. The solution is described below in two sets of insights required to solve the problem.

Set 1. Basic solution

Given the array of N numbers A[0 to N-1]. Let us imagine an infinite array a, such that a[i+N] = a[i].

Let us construct the sums array

b[0] = 0

b[i] = b[i-1] + a[i] for i > 0

We notice that the array is periodically increasing.

That is, because s = summation(0<=i<N, a[i]) > 0 (given in the problem statement) and

b[N+i] = b[i] + s

Now, we notice that if a[i] is negative, then b[i] < b[i-1] and if a[i] is positive, then b[i] > b[i-1].

The above is true for all i, N+i, 2N+i, 3N+i and so on.

Hence, we say that negative a[i] create inversions.

There are may be an infinite number of inversions in the sums array.

Let us say, whenever we are performing the operation on A[i], that is adding its value to A[i-1] and A[i+1] and changing its sign, we are also performing the operation on a[i+N], a[i+2*N], a[i+3*N] and so on, but we do not perform the operation on a[i].

Notice that performing operation on a[t], swaps adjacent values in the b array constructed from this a. In fact, performing operation on a[t], swaps b[t-1] and b[t]. It also swaps b[t-1+N] and b[t+N]; b[t-1+2N] and b[t+2N] and so on.

We can only invert the two indexes i and i+1 if N <= i < 2N.

The sums array is sorted and increasing when we have reached a solution.

Thus, this is similar to sorting an array by inverting adjacent elements.

Now we use some non-intuitive insight!

1. Let T be the number of inversions such that there is an N <= i < 2N and j > i where b[j] < b[i].

(in fact T is same for any consecutively selected N items from the sums array. we can select 0 <= i < N also.)

2. Every time we invert two values b[i] and b[i+1], such that b[i+1] < b[i], we reduce T by 1.

(note that inverting adjacent values means we invert the sign of a[i+1] and add its previous value at a[i] and a[i+2])

3. Every time we invert two values b[i] and b[i+1], such that b[i+1] > b[i], we increase T by 1.

4. If T is not 0, there would always be an inversion in i and i+1 for N <= i < 2N

5. When T is 0, we have solved the problem.

Thus,

The solution to the problem is calculating the number T. The number of inversions i and j, such that 0 <= i < N and j > i where b[j] < b[i].

Note that we can infer there is no *optimal* way of solving a particular given array of A. We can safely select any negative number each time and perform the operation on that.

The array will consist of all non-zero values in the same number of steps every time!

But, the test cases are such that the number of steps might be very large - most results not fit in 32-bit integers! So simply simulating will not solve the problem :-)

The number of inversions in b can be calculated in O(N*N) time.

Namely let 0 <= i < N, i < j < i + N. Then due to the condition b[k+N]=s+b[k] we have b[j+k*N]=b[j]+s*k. So for k >= 0 we have that b[i] and b[j+k*N] give an inversion if b[j]>b[j]+k*s. So the number of inversions that gives i with j, j+N, j+2*N, ... is equal to ceil( (b[i]-b[j])/s ), where ceil(x) is equal to the least integer not less than x.

But that will time-out within the time limits. There is a better solution still.

Set 2. Advanced solution

(This solution is all courtesy Anton. Thanks a ton! Most of the notes in this editorial are made by himself.)

1. Rotate A such that b has all positive values.

Let b[0] = a[0] and b[i]=b[i-1]+a[i] (1 <= i < n).

Let s = b[n-1]. That is s is the sum of all a[i]'s.

Next we find such index i0 (0 <= i0 < n) such that b[i0] <= b[i] for 0 <= i < n.

That is b[i0] is the minimal value from all b[i]'s.

We can rotate A such that i0 is at the 0'th index. This way, the new array b, has only positive values.

2. Sort b

But not just sort :-)

We note that the solution still is the number of inversions in b.

We calculate the number of inversions in b, while sorting b. We notice that we now get a partially sorted array

0=b[0]<=b[1]<=b[2]...b[n-1]

s=b[n]<=b[n+1]<=b[n+2]...b[2n-1] and so on.

Let the number of inversions calculated be I.

3. The formula for remaining inversions

Since 0=b[0]<=b[1]<=...<=b[n-1] the answer can be calculated in the following manner.

Let 0<=i<n. Find k such that b[k-1]+s < b[i] <= b[k]+s (b[-1] = -infinity).

The number of inversions in b, due to b[i], are

summation(0<=j<k, ceil( (b[i]-b[j])/s ) - 1 ).

Note that value of k can only increase when i steps to i+1.

Now, ceil( (a-b)/s ) = ceil(a/s) - ceil(b/s) + int(r(a) < r(b))

where r(a) = (a % s) > 0  ?  (s - (a % s))  :  0

and int(x < y) is equal to 1 if x < y, and equal to 0 if x >= y.

Using this formula we can rewrite our formula as follows

summation(0<=j<k, ceil(b[i]/s) - ceil(b[j]/s) + int(r(b[i]) < r(b[j])) - 1) =

k*ceil(b[i]/s) - summation(0<=j<k, ceil(b[j]/s) ) - summation(0<=j<k, int(r(b[j]) <= r(b[i])) )

summation(0<=j<k, ceil(b[j]/s)) can be pre-calculated by formulas

sb[0] = 0

sb[k] = sb[k-1] + ceil(b[k-1]/s) (0<k<n).

The only left question is how to calculate the summation(0<=j<k, int(r(b[j]) <= r(b[i])) ) part.

4. Binary indexed tree to the rescue!

Let's construct sorted array of all different values among r(b[i]) (0<=i<n) and denote them by

0<=r[1]<r[2]< ...<r[m].

We must maintain a table R[x] which will tell us the index 'i', such that r[i] = x.

Let f[1],f[2],...f[m] be a binary-indexed tree for summation.

As was said before the value k will only increase when i steps to i+1.

So, every time we increment k, we make an addition query to our tree at R[r(b[k])].

The value of summation(0<=j<k, int(r(b[j]) <= r(b[i])) ) would now be the summation query for R[r(b[i])]!

Thus we obtain a solution with O(N log N) time complexity:

1st step is O(n)

2nd step is O(n log n) (merge sort)

3rd step is O(n)

4th step is O(n log n) (O(n) queries to the binary indexed tree each requires O(log n) operations).

Problem Setter Solution

Problem Tester Solution