Match Editorial

The Problems

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.

Value	550
Submission Rate	117 / 233 (50.21%)
Success Rate	40 / 117 (34.19%)
High Score	Adrian Kuegel for 521.77 points

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.

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.

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.

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.

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.

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.

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.

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.