Get Time
statistics_w  Match Editorial
SRM 269
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 Problems

AccessChanger rate it discuss it
Used as: Division Two - Level One:
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("->",".") + 

PatternOptimizer rate it discuss it

Used as: Division Two - Level Two:
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)
Used as: Division One - Level One:
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("\\*\\*", "*");

RegimentArming rate it discuss it
Used as: Division Two - Level Three:
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.

SecurityBunker rate it discuss it
Used as: Division One - Level Two:
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.

PieSharing rate it discuss it
Used as: Division One - Level Three:
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);
        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]);

By Andrew_Lazarev
TopCoder Member