Match Editorials

Match summary

This problem set was a bit harder then the average High School match. Though the problems didn't require a knowledge of complex algorithms, all of them required some careful coding, especially when handling border cases. These challenges led to a success rate of around 60% for each of the problems.

The begining of the match belonged to Zuza, who got the fastest solution on the easy problem and the second fastest on the medium, giving him an impressive 744.01 out of 750 points. Many other coders were not far behind, however, and the final result came down to their performance on the tricky 1,000 point problem. After the end of the coding phase Weiqi held first place with a great score of 1563.93, thoconracroi was second with 1491.21, followed by ahyangyi, with Burunduk2 right after him, both with over 1480 points. After the challenge phase Weiqi was still in first, with an extra 25 points. ahyangyi moved to second, thanks to 75 points from challenges, and hupo001 advanced to third after grabbing 225 challange points. It's worth noting that both ahyangyi and hupo001 were fighting for challenges in the same room. System tests brought down a fair number of solutions, but didn't change the top three spots.

The Problems

Value	250
Submission Rate	153 / 158 (96.84%)
Success Rate	94 / 153 (61.44%)
High Score	Zuza for 249.24 points (1 mins 34 secs)
Average Score	219.87 (for 94 correct submissions)

All you need to do is to loop through the text, mark all the letters that are included in a "xox" and return the number of marked letters. The sample code can be as follows:

    public int count(String text) {
    int res=0;
    boolean b[]=new boolean[50];
    for(int i=0;i<text.length()-2;i++)
    if(text.substring(i,i+3).equals("xox")) b[i]=b[i+1]=b[i+2]=true;
    for(boolean x : b)if(x)res++;
    return res;
    }

Value	500
Submission Rate	131 / 158 (82.91%)
Success Rate	82 / 131 (62.60%)
High Score	cypressx for 496.30 points (2 mins 27 secs)
Average Score	400.91 (for 82 correct submissions)

If you are familiar with the basis of the grah theory, this problem can be translated into

Given an undirected graph, find the number of connected components.

Most of the coders used dfs to mark all the vertices of the connected component. The answer in that case is the number of the times you need to run dfs to cover the whole graph. The fastest submission by cypressx uses exaclty this idea.

There is another possible solution, that doesn't require any graph knowledge. The pseudo code follows:

• Iinitalize Group[i]=i for each person i
• For every pair of friends (i,j)
• if Group[i] != Group[j] merge i and j into single group
• Return the number of groups left

Value	1000
Submission Rate	38 / 158 (24.05%)
Success Rate	22 / 38 (57.89%)
High Score	Weiqi for 836.11 points (13 mins 7 secs)
Average Score	559.90 (for 22 correct submissions)

After taking a glance at the constraints one should realize that, with a maximum of six teams, a bruteforce solution won't have a problem running in time. There are two things you need to handle when generating the schedule:

• Do not count the same schedule twice.
• Make sure that schedule is in accordance with the given preferences.

To address the first point you can assign the unique representation to every round. One way to do that is representing it as a list of n/2 pairs, where each pair has the lower index on the first position and additionally pairs are sorted by the first element. In example:

            A B C
            3-5 1-2 0-4
            2-1 3-5 1-2
            0-4 4-0 3-5
        

            int generate(int round, int match){
            if(round == n-1){ //we have found a solution
            return 1;
            }
            if(match == n/2){ //the whole round was generated
            return(round + 1, 0);
            }
            int result = 0;
            int a = 0;
            //we set a to the first team that wasn't assigned in that round
            while(usedInRound[a][round])a++;
            usedInRound[a][round] = true;
            //b will be always greater than a
            for(int b = a+1;b<n;b++){
            if(usedInRound[b][round])continue;
            //every two teams can play only once, one against the other.
            if(played[a][b])continue;
            usedInRound[b][round] = true;
            played[a][b] = true;
            result += generate(round, match+1);
            usedInRound[b][round] = false;
            played[a][b] = false;
            }
            usedInRound[a][round] = false;
            return result;
            }