Saturday, January 13, 2007 Match summaryIn Division 1, the problems were much easier than those in SRM 333. We didn't have to wait long for the first submissions, with many coders scoring around 240 points on the easy problem. The remaining two problems also didn't stop the top competitors for long. After the first 20 minutes of the coding phase bmerry took the lead, thanks to the fastest submission of the hard followed by tomek the fastest solution of the medium problem. After only 5 minutes, however, the situation began to change. tomek climbed to first place with all three submissions after 27 minutes of the match had gone by. However he ended up in second place at the end of coding, with krijgertje taking over his spot in first place.The hard problem was a little below average, in terms of difficulty, and the idea for it was pretty standard. Because of that, more than 100 coders were able to submit all three problems by the end of the coding phase. During the challenge phase tomek gained 125 point with three successful challenges on the easy problem and overcame krijgertje, who took second place. lovro finished third, thanks to four challenges on the easy problem. In Division 2, only a dozen coders were able to solve more than two problems. First place was taken by Argentinian newcomer lucasr. lucasr solved all three problems and successfully challenged two other coders' solutions. After this SRM lucasr moved to Division 1 with 1900 rating points. monoid came in second in Division 2, followed by Rahenri in third. The ProblemsSupermarketDiscountUsed as: Division Two  Level One: Generally, in real life, it's hard to optimize purchases in order to get the maximal discount. Fortunately, we have a very simple sales rule and only three girls who do not want to split up goods across multiple transactions. In our case the girls have only three possibilities: pay separately, pay together or combine purchases for two of three girls. There are three ways to select two of three girls, so we have five possibilities in total. Here is the sample Java solution. int discounted(int x) { return x >= 50 ? x10 : x; } int minAmount(int[] goods) { int ans = Integer.MAX_VALUE; ans = Math.min(ans, discounted(goods[0]) + discounted(goods[1]) + discounted(goods[2])); ans = Math.min(ans, discounted(goods[0]+ goods[1]) + discounted(goods[2])); ans = Math.min(ans, discounted(goods[0]+ goods[2]) + discounted(goods[1])); ans = Math.min(ans, discounted(goods[2]+ goods[1]) + discounted(goods[0])); ans = Math.min(ans, discounted(goods[0]+ goods[1] + goods[2])); return ans; } KnightTour Used as: Division Two  Level Two: The solution for this problem is pretty straightforward. We just need to emulate the knight's trip through the given path and check whether it is really a valid reentrant knight's tour or not. Here is rrox's Java code, which nicely shows this idea: public class KnightTour { boolean vis[][]; boolean valid(String a, String b) { int la = a.charAt(0)  'A'; int na = a.charAt(1)  '1'; int lb = b.charAt(0)  'A'; int nb = b.charAt(1)  '1'; if (vis[la][na]) return false; vis[la][na] = true; int dl = Math.abs(la  lb); int dn = Math.abs(na  nb); return (dl == 1 && dn == 2)  (dl == 2 && dn == 1); } public String checkTour(String[] a) { vis = new boolean[6][6]; boolean ok = true; for (int i = 0; i < a.length; i++) { ok &= valid(a[i], a[(i+1) % a.length]); System.out.println("Round " + i + ": " + ok); } return ok ? "Valid" : "Invalid"; } } ExtendedHappyNumbers Used as: Division Two  Level Three: Used as: Division One  Level Two: First of all, let's find the upper limit for a number that can be reached in the sequence N, S_{K}(N), S_{K}(S_{K}(N)) and so on, where N is not greater than 1 million and K is not greater than 6. It is easy to see that this upper limit is less than 4*10^{6} because S_{6} for any number below 4*10^{6} is not greater than 3^{6} + 6*9^{6} = 3189375. Now, let's begin to solve the problem. The naive solution is to take each number N from A
to B, inclusive, and build the sequence N, S_{K}(N), S_{K}(S_{K}(N))
and so on, until some number in this sequence appears twice. After that there will be no
new values in the sequence because its elements begin to repeat. We can find the minimal element in
this (already built) sequence's prefix, and it will be the answer for the N.
This is a fairly easy problem for Division One, and doesn't require much effort to solve and code. Nevertheless, many coders wrote a naive solution and were beaten in the challenge phase. The naive solution is as follows: Try all possible assignments between letters and digits and take the one that leads to the best result. For the fixed assignment we can calculate the total sum by iterating along all given summands. Clearly, this solution is not fast enough, but even small improvements allow it to fit to the time limit. Let's interpret each integer, which needs to be summed as follows (where n is the length of current integer): Letter_{0} * 10^{n1} + Letter_{1} * 10^{n2} + ... + Letter_{n1} * 10^{0},After that we can combine the items around each letter from 'A' to 'J'. Now, if we know the assignment between letters and digits, we can calculate the total sum by 10 operations. This is much faster than without precalculation. This optimization was good enough to pass system tests  see JongMan's solution as an example. You can move forward, however, and create A solution without iterations of all possible assignments at all. The main idea is that, after the optimization described above, you can easily state your preferences about the values of the letters. The only thing you should worry about is a zero digit that cannot be assigned to some of the letters. Terrorists Used as: Division One  Level Three: In this problem you are required to find a sum of the edges of a minimal cut in the given graph. According to the maxflow mincut theorem a sum of the edges of a minimal cut that separates two vertexes v1 and v2 equals to the maximum flow in the given graph with v1 and v2 as a source and a sink respectively. For any cut in the graph the town 0 will be separated from some other town. So, to solve the problem we can fix the town 0 as a source and try all other towns as a sink. The minimal of the obtained result will be the answer for the original problem. You can view kia's solution with this idea here. 
