October 2011 Contest Problem Editorials

Problem Tester for the October 2011 Contest was Harsha S.

-------------------------------------------------------------------------------------------------------

BAKE (written by Anirban Mitra)

This problem presents a typical OLAP problem scenario with multiple dimensions with each having an hierarchy of levels. In this problems the dimensions were product, location, gender and age. The level hierarchy for the location dimension, for example, is country->province->city->region.

The expected solution for this is to pre-aggregate the sale information at different levels of dimensions so that queries can be efficiently answered. The combinations of levels of each dimension at which a query can be asked are as follows

product_id.product_size, country.province.city.region, gender, age
product_id.product_size, country.province.city, gender, age
product_id.product_size, country.province, gender, age
product_id.product_size, country, gender, age
product_id, country.province.city.region, gender, age
product_id, country.province.city, gender, age
product_id, country.province, gender, age
product_id, country, gender, age

So, pre-aggregate the data at all these levels. For example, say for the combination {product_id, country.province.city, gender, age} there is a 4-dimensional matirx, say mat, where mat[PID][CITYID][GID][YRS] keeps the totals sales for the product with id PID, in city with id CITYID, done by person of gender GID of age YRS. Similarly, maintain a matrix for the the combinations because a query can only ask about sale information at these levels. Hence, for a single input, you will have to update multiple matrices at all the appropriate matrices.

But because for the fourth dimension, i.e. age, there can be range queries that is give me the sum for age START_AGE to END_AGE. So, for the fourth dimension, I used Binary Indexed Tree (BIT) to maintain range aggregates. They are easy and efficient to both update and query.

You can view the solution here:

Problem Testers' solution

Problem Setter's solution

-------------------------------------------------------

DISHDIS (written by Vamsi Kavala)

This was the Easy problem for this month. The problem is a standard combinatorics problem which asks us to find the number of solutions possible for:

x1 + x2 + x3 + ........ + xm = n

with the constraints ai<=xi<=bi

Though the problem can be solved using combinatorics, the constraints and the time limit of the problem allow a simple O(n3) dp solution to pass. The recurrence is straight-forward. Let dp[x][y] denote the number of ways of preparing y dishes by the first x cooks. Clearly, our answer will be dp[m][n]. The recurrence is as follows:

dp[i][j]=Σdp[i-1][j-k]      where x[i]<=k<=y[i]

A lot of people had a problem passing the time limit with a recursive solution. It's always better to write an iterative code for your solution, especially if the recurrence is simple.

You can view the solution here:

Problem Setter's solution

Problem Tester's solution

-------------------------------------------------------

LAND (written by Gennady Korotkevitch)

This problem brought a very close race into this contest. With only two hours to go, it was still unclear who would win.

Even though a lot of coders are finishing the contest with 6 points, the difference in their approaches is quite significant -- that is, even with 6 points it's still very difficult to climb up the rankings to the very top places. For example, a score of at least 0.997 could be achieved by the following very simple approach. First, fill all the empty cells with the same number, say, 25 (so that it's close to the average of the possible values). Then take any cell, try to change its value into some other value (usually just adding or subtracting 1) and see if this action improves the score (if it doesn't, undo the change); do this until there are no more cells which can be improved.

Simulated annealing is a better approach, as it allows changes which actually make the score worse with some probability -- and the earlier is the moment we try to perform such a change the higher is the probability. For more information on this approach, Wikipedia may help (or some other resource which I don't know or don't remember).

The biggest drawback of the mentioned approaches is their locality -- that is, sometimes changing the value of a cell doesn't help unless we change the values of a whole bunch of cells. So, it might be worth taking an "area" of equal values and trying to change all the values in the area (except the cells which weren't empty from the start). Trying to improve a particular row or column may also help.

You can view the solutions here:

Problem Tester's solution

Problem Setter's solution

-------------------------------------------------------

REPSTR (written by AnhDQ)

At first, it is easy to prove that if there exists a substring with the length of K (K > 1) appearing the most times, there must exist another substring with the length of K-1 appearing the same times (it is such a prefix of the substring length K). So we will find the most appearing substring with the length of L to determine the most times T (first result). Then to find the longest substring appearing T times (second result), we just use binary search to solve it.

The key of both steps is counting the number of times that a substring appears. Theoretically we can use a SUFFIX TREE to solve it (easy to find documents over the internet). However I suggest another way which is easier to code and also understand but still usable to solve this. It is using HASH. As we know it is possible to use a MAP to directly store the appearing times of any substring, but it takes a long time to find and compare the strings. So I choose to encode any given substring in the base of 26 (because we have only 26 different characters), then take the modulo of a prime key (because the value of encoding may be very large, search for documents about the technique of HASH) then use it as the key to use in mapping. Another problem is, it may be wrong comparing different substring sharing the same key, so to make the keys completely different, I use a pair of prime keys to take the modulo of. And it is enough to pass this problem.

You can view the solution here:

Problem Setter's solution

-------------------------------------------------------

LUCKPAL (written by Ankul Garg)

.

You can view the solutions here:

Problem Setter's solution

Problem Tester's solution

-------------------------------------------------------

PARSIN (written by Hiroto Sekido)

You can view the editorial here.

You can view the solutions here:

Problem Setter's solution

-------------------------------------------------------