Thursday, May 1, 2008 Match summary1400 coders participated in the memorable 400th SRM which was a rather turbulent one. In division one, problems are not hard at first glance, but solving them correctly is anything but easy. This property of the set leads to the high submission rate and the low success rate. Petr won the match as the only coder who solved all problems correctly. Before the challenge phase, he was in 90th place. Nevertheless, after the system test, he reached first place. He hit a new record high of the rating 3857 as a result of this match. ACRush and exod40 took second and third place respectively by solving Easy and Medium fast and getting many points in the challenge phase. I also congratulate xhl_kogitsune as another coder who solved Hard correctly other than Petr. In division two, Easy in an easy problem ineed but Medium and Hard were rather hard; the low submission rate and the low success rate. WSM was the only coder who solved all problems and took first place. gnarlycow and magicdlf follow by solving Easy and Hard correctly. The ProblemsGrabbingTaxiUsed as: Division Two  Level One:
This problem is a simple one. Let n be the number of taxi stands. There are (n + 1) ways to go to the goal; you may walk to the goal directly or walk to the ith taxi stand and go to the goal by taxi from the stand (1 ≤ i ≤ n). Your task is to find one which requires the minimum length of time by a simple iteration. You can see the fastest solution by jackson.liao31 for reference. StrongPrimePowerUsed as: Division Two  Level Two: Used as: Division One  Level One:
Because n can be as large as 10^{18}, iterating over all primes less than or equal to n^{1/2} is not a practical solution. The key insight is that the exponent q is less than or equal to 59 because 2^{60} > 10^{18}. Thus examining all possible q (2 ≤ q ≤ 59) and testing if there is a prime p such that p^{q} = n for that q seems a good idea.
Now we consider the problem of how to find an integer p such that p^{q} = n
if exists for given q and n. You can see p = n^{1/q} by simple mathematics.
You can calculate
n^{1/q} as a floating point number
by a standard library in each language (pow() in The rest part of the problem is testing if p is a prime or not. Because such calculated p satisfies p ≤ n^{1/2} ≤ 10^{9}, you can do it by the following simple function. boolean isPrime(int x){ for(int i = 2; i * i <= x; i++) if(x % i == 0) return false; return true; } Now the total solution can be written as follows in Java. public int[] baseAndExponent(String sn){ long n = Long.parseLong(sn); for(int q = 2; q <= 59; q++){ double dp = Math.pow(n, 1.0 / q); int p = (int)Math.round(dp); if(!isPrime(p)) continue; long x = 1; for(int i = 0; i < q; i++) x *= p; if(x == n) return new int[]{p, q}; } return new int[]{}; }LightedPanels Used as: Division Two  Level Three:
First we can observe that it makes no sense to touch the same panel twice because it does not change the state of panels at all. This means we only have to consider the case each panel is touched at most once. Next we can observe that the order in which panels are touched is not related to the end state. Because of this, we may impose a particular oder in which panels are touched. Here we assume panels are touched in order of increasing row and inside a row left to right. Let's first consider a restricted version of the problem, where we can touch only panels with row ≥ 1 and column ≥ 1 (rows and columns are 0origin). In this version of the problem, the only way to flip the panel (0, 0) is to touch the panel (1, 1). Thus we can determine if the panel (1, 1) should be touched or not only by the state of the panel (0, 0). After this, the only way to flip the panel (0, 1) is to touch the panel (1, 2). Thus we can determine if the panel (1, 2) should be touched or not only by the current state of the panel (0, 1). In a similar way, we can determine each panel should be touched or not. Now we can know how to solve this restricted version of the problem. If all panels are lighted, the number of panels you touched is the answer. If there is a panel which are not lighted, it is impossible to light up all panels  the answer is 1. Let us return to the original version of the problem. Each panel in row 0 and in column 0 can be either touched or not, and we can brute force all possibilities. The number of patterns is less than or equal to 2^{8+81} = 2^{15} = 32768. For each fixed pattern our problem reduces to the problem in the previous paragraph. You can see the fastest solution by magicdlf for reference. ReversalChainUsed as: Division One  Level Two:
The success ratio of this problem is low. This is because many coders solved this problem by a wrong greedy algorithm. The intended solution of this problem is dynamic programming. To explain the solution, we will create a 4D array called dp. Let us denote the substring of the string str which begins at b and extends to the character at e  1 by str(b, e). dp[x][a][b][r] stores the minimum length of the reversal chain to transform the substring of init(a, a + x) with r reversals (r is zero or one) to the substring of goal(b, b + x). If there is no such reversal chain, it stores the special value which indicates the fact. We will call this special value inf. The size of dp is 50 * 50 * 50 * 2 = 250000. The basic idea of the reccurence is to match a character in init and a character in goal (maybe after a reversal) and then solve the problem with the remaining strings. The recurrence relation can be written as follows (ignoring boundary conditions). We suppose inf is a special value which is larger than any other integers. dp[x][a][b][0] = min{ init[a] == goal[b] ? dp[x1][a+1][b+1][0] : inf, init[a+x1] == goal[b+x1] ? dp[x1][a][b][0] : inf, init[a] == goal[b+x1] ? dp[x1][a+1][b][1] + 1 : inf, init[a+x1] == goal[b] ? dp[x1][a][b+1][1] + 1 : inf } dp[x][a][b][1] min{ init[a] == goal[b] ? dp[x1][a+1][b+1][0] + 1 : inf, init[a+x1] == goal[b+x1] ? dp[x1][a][b][0] + 1 : inf, init[a] == goal[b+x1] ? dp[x1][a+1][b][1] : inf, init[a+x1] == goal[b] ? dp[x1][a][b+1][1] : inf } You can see the very fast solution by ACRush for reference. He uses a string as a key to access the table for dynamic programming and this makes his code simple. His solution is really neat. CollectingBonusesUsed as: Division One  Level Three:
This problem is a really tough one but I think this problem is so educative. To solve this problem, not only the knowledge of mathematics but also the technique of handling numerical errors in floating point arithmetic is required. First we construct the mathematical formula of the answer. Let T(x) be the expected number of bottles you must buy to collect x different codes. We suppose we have collected x different types of codes already. If we buy a bottle, the probability of its code is a new one is (n  x) / n. This leads to the equation T(x + 1)  T(x) = 1 + (x / n)(T(x + 1)  T(x)), which follows T(x + 1) = T(x) + n / (n  x). From this reccurence relation, we get the representation T(k) = n / n + n / (n  1) + ... + n / (n  k + 1). Now the problem is how to calculate this value efficiently (the brute force method will time out). There is a good news for you. The answer may contain a relative error of 1E9, so the good approximation is enough. Here is a keyword "harmonic number". Harmonic number is defined as H(n) = 1 + 1 / 2 + 1 / 3 + ... + 1 / n. T(k) can be represented as n * (H(n)  H(n  k)) using harmonic number. If you know the keyword "harmonic number", you can put it into the search engine and get the approximation formula. I introduce here a reference from MathWorld. You will know that H(n) can be approximated as gamma + ln (n + 1 / 2) (see (15) in the reference), where gamma is an EulerMascheroni constant which is about 0.5772156649015313. Because the error of this approximation is about 1/24n^{2}, it is precise enough for large n. Now we can calculate H(n) both efficiently and precisely as follows. If n is smaller than a constant, like 10000000, we calculate H(n) by brute force. Otherwise we calculate H(n) by the approximation formula. If you don't know the word "harmonic number", you can make the similar approximation formula if you know the idea of approximating the sum of a sequence by the integration of a corresponding function. The answer of the problem is T(k) = n * (H(n)  H(n  k)) and you have the precise value of H(n) and H(n  k). The remaining task is only a subtraction. You may think this problem is solved. However, the subtraction contains a trouble. Though H(n) and H(n  k) is precise, H(n)  H(n  k) may not be precise. The subtraction of two nearly equal floating point numbers increases relative error. This phenomenon is called loss of significance. How can we avoid this problem? We suppose both n and k are large enough, becuase if we can solve such cases, handling other cases is not hard. Becuase H(n) and H(n  k) are approximated as gamma + ln (n + 1 / 2) and gamma + ln(n  k + 1 / 2) respectively, H(n)  H(n  k) can be represented as ln(n + 1 / 2)  ln(n  k + 1 / 2) = ln((2 n + 1) / (2 n  2 k + 1)). Now there is no subtraction and the trouble seems to be removed. However, there is another trouble. The relative error of log(x) as implemented in the standard library is large where x is near to 1. To avoid this trouble, the function log1p(x) is prepared in the standard library of C and Java (see "math.h" for C and java.lang.Math for Java). This function calculate ln(1 + x) precisely even if x is near to 0. What should C# coder and VB coder do? In fact, implementing log1p() is a not hard task. If x is large enough, call log(1 + x). Otherwise, use the Taylor expantion of logarithm function around 1. Petr did it in his C# solution. After all, the solution can be written as follows in Java. static final long M = 10000000; public static double expectedBuy(String sn, String sk){ long n = Long.parseLong(sn); long k = Long.parseLong(sk); long m = n  k + 1; double res = 0.0; while(m <= M){ res += 1.0 / m; if(m == n) return n * res; m++; } // 1 / m + ... + 1 / n = H(n)  H(m  1) res += Math.log1p((double)(2 * n  2 * m + 2)/ (double)(2 * m  1)); return n * res; } You can learn three things from this problem. Harmonic number can be approximated using logarithm function. Subtraction of two close floating point numbers causes loss of significance. The standard library function log(x) is not precise where x is near to 1. I would like to add one more thing. You can trust the precision of the answer for the system test; it is calculated very precisely using BigDecimal. 
