JOIN
 Match Editorial
SRM 123
Tuesday, December 10, 2002

# The Problems

Etiquette
Used as: Division-II, Level 1:
 Value 250 Submission Rate 214 / 233 / (91.84%) Success Rate 171 / 214 (79.91%) High Score yotaku for 247.32 points

Reference implementation: yotaku

60 out of 231 coders, who opened Etiquette, received 0 points.

#### Implementation

The problem was very straightforward. It was easy as it had to be for a Div-II, Level 1 problem.

```To solve the problem go through entire string and do the following for every char:
if current char is 'L' set LadyfirstState=true;
if current char is 'G' and LadyfirstState is true then increment badGentelment count;
if current char is space LadyfirstState=false;```

Return badGentelment after a loop is completed.

TypingJob
Used as: Division-II, Level 2:
 Value 550 Submission Rate 117 / 233 (50.21%) Success Rate 40 / 117 (34.19%) High Score Adrian Kuegel for 521.77 points
Reference implementation:slavik (practice room)

180 out of 220 coders, who opened TypingJob, received 0 points.

#### Implementation

The brute force can be used to solve this problem because we have 3 assistants and a maximum of 10 jobs to be assigned to them. The worst-case scenario would take 3^10 = 59049 iterations.

To actually solve this problem a recursive function can be built to assign every job to one of the 3 assistants. Once all jobs are assigned, take the maximum time for one of the three assistants to do the job and compare it to the best so far.

```void do_it(int index,int q1,int q2,int q3) {
if (index=a.size()) {
int current= q1>q2 ? q1
if (q3>current) current=q3;
if (current<best) best=current;
return;
}
do_it(index+1,q1+a[index],q2,q3);
do_it(index+1,q1,q2+a[index],q3);
do_it(index+1,q1,q2,q3+a[index]);
}

This approach could be optimized in the following ways:
If time for one of the assistants is more then current best, exit from the function.
Always assign job 1 to assistant one
(it would reduce number of iterations to 3^9=19683).
```

None of the optimizations are necessary because the problem would work fine without them. There are other ways to solve this problem but they would probably involve more typing.

TeaCoffee
Used as: Division-II, Level 3:
 Value 1000 Submission Rate 87 / 233 (37.33%) Success Rate 55 / 87 (63.22%) High Score vietchau for 767.64 points

143 out of 198 coders who opened TeaCoffee, received 0 points.

Used as: Division-I, Level 2:
 Value 450 Submission Rate 98 / 114 (85.96%) Success Rate 78 / 98 (79.59%) High Score SnapDragon for 429.52 points

32 out of 110 coders who opened TeaCoffee, received 0 points.

Reference implementation: Yarin

#### Implementation

This problem is a simulation problem where you just follow the rules to get a result. The most difficult part was probably the parsing of input. Most of the C++ coders already have tokenizers implemented and Java coders can always use the standard StringTokenizer class. There are two common ways to keep track of friends: to build an adjacency matrix or to create a vector of vectors. Most of the Div-I coders preferred building a vector of vectors to make the implementation easier and shorter. Once we have all inputs parsed and placed into easy-to-access data structures, the only thing left is to build a simulation which would work like this: Create a loop of 52 iterations and do the following for every iteration: If all people had the same drink last week (or the first time) the solution is found, return current week index. Create another list of drinks that people are having this week according to rules of the simulation. Set last week's list of drinks to the current week's list of drinks and go to the next iteration.

Return -1 if we went through all 52 iterations and no solution was found.

Cactus
Used as: Division-I, Level 1:
 Value 350 Submission Rate 45 / 114 (39.47%) Success Rate 37 / 45 (82.22%) High Score nullspace for 332.43 points

75 out of 112 coders who opened Cactus, received 0 points.

Reference implementation: Yarin

#### Implementation

This problem seems to be more difficult then its 350 point value because only 37 out of 114 were able to solve this problem correctly. Almost all successful solutions had the same approach to this problem: build four nested loops, where each one of them would iterate the number of cactuses of each color (or combination of colors). For this solution to work one must keep track of the maximum and minimum amount of money spent to buy the current number of cactuses. For the rare cactuses (red with a white) assume the price is 3500 for the first one and is incremented by 1 for each following cactus. Once the inner loop is reached and the minimum amount of money spent for the current number of cactuses is less then allocated money and the maximum amount of money spent for the current number of cactuses is greater or equal to the allocated money, we have a unique combination of colors we shall count.

BestCircle
Used as: Division-I, Level 3:
 Value 1000 Submission Rate 35 / 114 (30.70%) Success Rate 5 / 33 (14.29%) High Score SnapDragon for 778.96 points

85 out of 90 coders who opened BestCircle, received 0 points.

Reference implementation: SnapDragon

#### Implementation

The number of points (circle centers) for this problem is unlimited (because the center of the circle can be a pair of double numbers). So there is no way to brute force the solution for this problem. To solve this problem we just have to carefully choose the points we try:

1. All given points in the field shall be considered as circle center.
2. Let's consider all circle centers with the following coordinates: For every two given points, a and b, the circle center shall be x=(a.x+b.x)/2 and y=(a.y+b.y)/2;
3. Let's consider all circle centers with the following coordinates: For every three given points, a, b and c, create a triangle bounded by a, b and c and find the center of this triangle. To find the center of this triangle we need to find an intersection of two lines perpendicular to the two slopes of the triangle and crossing corresponding slopes of the triangle in the middle.

The worst case scenario for this solution is 50 + 50*50 + 50*50*50 = 127,550 (circle centers) and should not time out.

By slavik
TopCoder Member