JOIN
 Match Editorials
TCHS SRM 14
Monday, September 11, 2006

## 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

Xox
Used as: Division One - Level One:
 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;
}
```
It doesn't seem difficult to code, and yet many, even high rated coders, got it wrong. Most of the failed solutions weren't wrong answers, but exceptions when one reaches out of the array or string bounds, for testcases like "h". You can also look at the nice fpavetic solution that uses set, in place of array, for marking letters.

FriendsTrouble
Used as: Division One - Level Two:
 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
This approach can be seen injakozaur's code.

TournamentSchedule
Used as: Division One - Level Three:
 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
```
All A,B,C represent the same round, but only C is corresponding to the above constraints. Please note that every round setting can be uniquely represented in this fashion. So generating only rounds in this format will ensure that you will count each of the schedules exactly once. Now generating all the schedules can be done by recursive function, which generates pairs one by one:
```            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;
}
```
The only thing missing is compliance with the given preferences. You just need to add a check in each step, before generating the pair (a,b) in any round, to test if a or b needs to play with somebody else in that round. If it's so, you don't take this pair. The other way is to add a check, after generating the each whole round, to see if the needed matches are in it. You can take a look on the fastest solution by Weiqi, who used this approach.

By slex
TopCoder Member