Match Editorial

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 Problems

Value	250
Submission Rate	238 / 259 (91.89%)
Success Rate	149 / 238 (62.61%)
High Score	HoldMeDown for 244.08 points (4 mins 26 secs)
Average Score	193.73 (for 149 correct submissions)

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);
    }

Value	500
Submission Rate	188 / 259 (72.59%)
Success Rate	138 / 188 (73.40%)
High Score	lishengren for 486.14 points (4 mins 49 secs)
Average Score	360.83 (for 138 correct submissions)

Value	250
Submission Rate	214 / 220 (97.27%)
Success Rate	200 / 214 (93.46%)
High Score	tomek for 247.25 points (3 mins 0 secs)
Average Score	218.17 (for 200 correct submissions)

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("\\*\\*", "*");
    }

Value	1000
Submission Rate	102 / 259 (39.38%)
Success Rate	47 / 102 (46.08%)
High Score	cep21 for 894.03 points (10 mins 1 secs)
Average Score	589.77 (for 47 correct submissions)

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.

Value	500
Submission Rate	146 / 220 (66.36%)
Success Rate	63 / 146 (43.15%)
High Score	tmyklebu for 452.50 points (9 mins 24 secs)
Average Score	277.05 (for 63 correct submissions)

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 Floyd-Warshall 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.

Value	1000
Submission Rate	87 / 220 (39.55%)
Success Rate	24 / 87 (27.59%)
High Score	tomek for 911.96 points (9 mins 0 secs)
Average Score	626.06 (for 24 correct submissions)

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, cnt-1] + 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, cnt-1) + pieces[ps]);
    }
}