|
Match Editorials |
Monday, December 4, 2006
Match summary
The relatively simple easy and medium helped the match start with a blast. Within 20 minutes, most of the coders submitted the first two problems and moved on to the hard. The 1,000 proved challenging, however, as there were only two submissions, and only one of them passed the system tests. The challenge phase had some problems, with a challenge uncovering a bug in the reference solution. Most of the solutions got challenged, and rejudging was done. In the end, tomekkulczynski got a close win with 885.76, though he was the only person to get all problems correct. He was followed closely by XPEHOTEHb with 874.63, who managed to put up an impressive performance in the challenge phase.The Problems
FibonacciSequence
Used as: Division One - Level One:
The problem asked for counting the number of Fibonacci numbers between any two given numbers. Constraints were quite low to allow even recursive non-memoized solutions to run in time. Most of the coders got this problem very quickly.
Value 250 Submission Rate 188 / 194 (96.91%) Success Rate 167 / 188 (88.83%) High Score Zuza for 249.68 points (1 mins 1 secs) Average Score 225.92 (for 167 correct submissions)
Here is the code from Zuza, code who managed to solve it in just a minute:
int F[ 100 ];
class FibonacciSequence {
public:
int numFibs( int a, int b ) {
F[0] = 0;
F[1] = 1;
int sum = 0;
for( int i = 2; i < 100; ++i ) {
F[i] = F[i-1] + F[i-2];
sum += ( a <= F[i] && F[i] <= b );
if( F[i] > b ) break;
}
return sum;
}
};
CarParking
Used as: Division One - Level Two:
The problem asked for finding the nearest palindrome from a given number, within a given range. Many solutions had overflow errors. tomekkulczynski's code had overflows involved, but proved to be correct. For this problem, it was enough to find the next lower and the next higher palindrome. In fact, since the number of palindromes within the given constraint was less than 105, just examining all palindromes would still work. See fatit's code as an example to this approach.
Value 500 Submission Rate 160 / 194 (82.47%) Success Rate 66 / 160 (41.25%) High Score fatit for 493.25 points (3 mins 20 secs) Average Score 377.16 (for 66 correct submissions)
Here is Olexiy's code, which finds the closest palindrome on either sides:
import java.util.*;
public class CarParking {
public int closestShed(int now, int streets) {
long q = now;
for (int i = 0; ; i++) {
if (ispal("" + (q - i))) return (int)q - i;
if (q + i <= streets && ispal("" + (q + i))) return (int)q + i;
}
}
boolean ispal(String s) {
String q = "";
for (int i = 0; i < s.length(); i++) q += s.charAt(s.length() - 1 - i);
return q.equals(s);
}
}
RiverCrossing
Used as: Division One - Level Three:
This problem proved to be relatively hard, with low submission and success rates. It's solution is based on dynamic programming (DP). Most DP-based solutions tend to have a uniform and sequence-driven line of thinking ,which i shall try to explain now.
Value 1000 Submission Rate 2 / 194 (1.03%) Success Rate 1 / 2 (50.00%) High Score tomekkulczynski for 486.60 points (39 mins 20 secs) Average Score 486.60 (for 1 correct submission)
Step #1: Make observations about properties of the system.
- All units of cargo are identical to one another. Hence it only matters how many units of cargo wait on either sides, not which ones wait. (Here "matters" refers to affecting the optimal value of the solution).
- During the boat's optimal journey, when it starts from a bank, it will either carry all the units pending at that time, on that bank, or get completely filled. It never moves partly empty while there are units pending.
While doing this look at all terms you would use to uniquely describe a "situation." More specifically, here, the system consists of boats and units. What "matters" to the optimal value of the solution -- what must be used to describe the system -- would be the properties of the boat and the units. The boat could be on either side of the bank, or travelling inbetween, partly or completely loaded, etc. The units can be on either side of the bank, and they can arrive at different times. During the formulation, we need to describe what's going on at each stage. Here: the boat travels from one bank to another loading units. Cargo continually keep appearing on either sides.
So one convenient way to describe it would be to avoid or disallow the boat to be desribed when it is travelling. which makes sense since, if you were asked to narrate the sequence of events that took place on the boat, you would naturally not narrate those positions. Thus, we end up describing the system with the following attributes (or answers to the following questions):
- On which side of the bank is the boat currently located?
- How many units are there on either sides of the bank?
- What is the time now?
This step often lets you completely estimate the amount of memory your program is going to take. Dynamic programming works by computing optimal solutions to every reachable state of the system and describing the solution by a sequence of changes between these states. Hence the storage would mostly map a (state) to an (optimal-value). Here, since the optimal value under description is the "total-waiting-time," it can be described in an integer. A state can be described with a tuple of answers to the above three questions. So now what is the maximal number of tuples that exist?
- Side can be either left or right, hence 2 possiblities.
- For units on either side, the constraints guarantee that their total will be less than 200. If there can be a maximal of i units on one side, there can be at most 200-i units on the other. The number of distinct ways in which units can remain after getting picked up by the boat will be (i+1)*(201-i). Since the product is maximised when the two units go equal, there can be atmost 101*101 distinct values for these tuples. Noting this might help you to reduce memory usage, without which describing tuples indivually in static arrays is going to cost you 201*201 tuples.
- For time, the example indicates that the total amount of time taken for all these operations can be enormously large. Hence we need to devise an intelligent method to store time. To answer this, trace back and goto where time came into the picture in the first place. We used time only to describe the sequence of changes that occur to the "units-on either-sides" property. It is not necessary to know the current time precisely to dynamically update the second attribute. Accordingly the question "What is the time now?" can be answered differently. Let T be the time of arrival of the last unit. The question needs to be answered with the exact time if the current time was less than T, otherwise you can just say that "current_time >= T". This is because, after all units have arrived, time is no longer required for updating the second attribute("units-on either-sides"). So now how many distinct answers exist to this question? Since T is given <= 100, the number of distinct answers is at most 101.
Step #3: Describe the sequence of changes that occur to the system in terms of the states of the system.
The changes are brought about by the boat moving here and there and the time varying continually. Here the aim is to let the boat take the best choices to minimize the optimal value. In other words, out of the sequence of possible states attained by the various ways the boat can move, choose the most favorable one. What are the various ways by which the boat can move? From the current time (t1), wait until a time (t2). During this interval we continually load units (on that side of the bank) into the boat as they arrive (See observation #2). After this we end up on a state with the bank switched, time updated to (t2 + "time-to-cross-the-river"), and some units arriving (during the time we crossed the river) on either sides of the bank.
This completes the solution. See tomekkulczynski's code for an implementation of this idea. His function go(c,g,a,b) describes a state, with c = current_time, g = side_of_bank, a = units_on_left_side, b = units_on_right_side. He saves the states so that no state is computed twice, using ma. The first for-loop in go() updates the units that will arrive at either sides of the bank, if we start right now. The second loop describes the situation "wait till time i before you start crossing."
The time complexity is going to be the number_of_states * (avg_number_of_moves_possible_per_state). Since waiting until time i can be described by a loop, which can run at most 100 times, we have our program run in approximately 2M * 100 = 200 million. Note that this is only an upper bound, where we estimated all states to be reachable and maximized transitions/state. In this problem, the actual number of reachable states seems quite low, hence this solution must be safe. However there was a way to reduce the (avg_number_of_moves_possible_per_state). The idea is to detail the events in a differrent way -- instead of saying how long you wait at a bank, say how many units you load at the bank. This will ask you to wait until a particular time at which that number of units becomes available. Since the number of units that the boat can load is at most 50, the transitions/state is at most 50. While this might not really help the run-time of the problem, it's a useful idea to try out various ways to describe the changes, and choose ones which minimize the transitions/state.
