Wednesday, October 26, 2005 Match summary In Division 1, ploh took the first prize followed by the close triplet jvpardon, Egor and radeye. Ruberik, who was a leader for a long time, had to resubmit the 1000th problem because of a silly mistake and lost more than 500 points. Gluk became yellow by taking the 14th place. In Division 2, cep was the first, followed by lishengren and HoldMeDown. The ProblemsAccessChangerUsed as: Division Two  Level One:
Each line of the program can be processed separately. For each line we can find the part of the line which is a comment by searching for "//" string. After that we can remove the comment, make the required replacement and get the comment back. Here is a sample Java code. for (int i = 0; i < program.length; i++) { int ps = program[i].indexOf("//"); if (ps < 0) ps = program[i].length() ; program[i] = program[i].substring(0, ps).replaceAll(">",".") + program[i].substring(ps); }PatternOptimizer Used as: Division Two  Level Two: Used as: Division One  Level One:
After a short thought we are realizing that all we need to solve the problem is to replace each substring consisting of only '?' and '*' characters that contains at least one '*' by the string with '*' followed by the same amount of '?' as was in the original substring. This operation can be done manually or by iterative replacing "?*" with "*?" and "**" with "*". Here is a sample Java code. while (pattern.contains("?*")  pattern.contains("**")) { pattern = pattern.replaceAll("\\?\\*", "*?"); pattern = pattern.replaceAll("\\*\\*", "*"); }RegimentArming Used as: Division Two  Level Three:
Let get the first N guns and then go forward. Each time we will take one more gun to the right and return the leftmost gun. How did the sum of gun power change? Each time it is changed by the same constant until the new gun type is taken or returned. Therefore, the maximal sum of gun power will be such interval of the guns that either starts with the new gun type or ends with it. So, we can try all positions where type of the gun changes and get one with the maximal result. You can use the cep21's solution as an example. SecurityBunkerUsed as: Division One  Level Two:
Let build the weighted graph where vertices are bombs and secret objects. This graph will have edges from any one bomb to all others bombs and to all secret objects. Weight of any edge is a distance between vertices in terms of the problem. All secret objects in the bunker can be destroyed by the explosion of any one bomb if and only if there is such a path between each pair of a bomb and a secret object that the weight of any edge in this path is not greater than D. We can find the minimum edge in the path for all pairs of vertices using FloydWarshall algorithm. You can use the ante's submit as a sample of this solution. Some coders wrote solutions which are based on the Prim algorithm. These solutions are also correct. PieSharingUsed as: Division One  Level Three:
Take the N pieces with the maximal total size so that no two of them are adjoined. Okey, we have an answer. Let prove that if we have the described set of N pieces we can always choose the order in which we can eat all of them. Because Ted will eat much more pieces than you, you can always find two successive Ted's pieces and eat your nearest piece. In this case, the remaining pieces will satisfy the requirement that no your adjoined pieces exists and we can repeat the eating. Now, let's find how to take the N pieces with the maximal total size so that no two of them are adjoined. This can be done using the dynamic programming. To remove the circular nature of the pie we will solve the problem twice  for the taken first piece and for the case when we don't take it. In the first case we can't take the second and the last pieces. Let A[ps, cnt] be a maximal total size that can be taken by cnt pieces starting from the position ps. The A array can be calculated using the recursive formula A[ps, cnt] = max ( A[ps+2, cnt1] + pieces[ps], //get the piece in the position ps A[ps+1, cnt] // do not get it ) Here is the sample Java code. public class PieSharing { int[] pieces; int n,m; int data[][]; public int share(int[] pieces) { this.pieces = pieces; n = pieces.length; m = n/3; data = new int[n+2][m+1]; for(int[] line : data ) { Arrays.fill(line, 1); } int ans1 = get(1, m); n; for(int[] line : data ) { Arrays.fill(line, 1); } int ans2 = get(0, m); return Math.max(ans1, ans2); } int get(int ps, int cnt) { if (data[ps][cnt] != 1) return data[ps][cnt]; if (cnt == 0) return 0; if (ps >= n) return 2; return data[ps][cnt] = Math.max(get(ps+1, cnt), get(ps+2, cnt1) + pieces[ps]); } } 
