Monday, December 4, 2006 Match summaryThe 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 ProblemsFibonacciSequenceUsed 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 nonmemoized solutions to run in time. Most of the coders got this problem very quickly. 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[i1] + F[i2]; 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 10^{5}, just examining all palindromes would still work. See fatit's code as an example to this approach. 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 DPbased solutions tend to have a uniform and sequencedriven line of thinking ,which i shall try to explain now. Step #1: Make observations about properties of the system.
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):
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 (optimalvalue). Here, since the optimal value under description is the "totalwaitingtime," 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?
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 + "timetocrosstheriver"), 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 forloop 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 runtime 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. 
