
Match Editorial 
SRM 123Tuesday, December 10, 2002
The Problems
Etiquette
Used as: DivisionII, 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 DivII, 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: DivisionII, 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 worstcase 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: DivisionII, 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: DivisionI, 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 DivI coders preferred building a vector of vectors to make the implementation easier and shorter. Once we have all inputs parsed and placed into easytoaccess 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: DivisionI, 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: DivisionI, 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:
 All given points in the field shall be considered as circle center.
 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;
 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