Match Editorial

The Problems

Division-II - Level 1 - SpellBee 

The problem was straightforward and was testing how well you can type in the 4 different cases into your solution. One could easily determine if the last word is the same as a word to spell. The only thing left to determine if the list is consistent. All you have to do to check if list is consistent is to go through the list and check all adjacent words. If any second word doesn't starts with first one, the list doesn't agree. One thing to keep in mind is the length of both words and not run out of the word boundary.

After that is just 3 "if" statements:
If (spelled_correctly && agree) return 4;
If (!spelled_correctly && !agree) return 0;
If (spelled_correctly) return 1;
If (agree) return 3;
return 0;

Common bugs:

1. The size of every next word in the list should be more or equal then the size of the previous word
2. The next word should start with previous word and NOT contain previous word.

Division - II Level 2 - HareNap  
(reference Slavik solution)

The entire problem could be solved in 5 lines:

1. Calculate time for Hare to finish the route: Float H_time= (float) distance /hare_speed.
2. Calculate time for Tortoise to finish the route: Float T_time = (float) distance /tortoise_speed.
3. Calculate time left for Hare to sleep: Float sleep_time = T_time-H_time-winTime+ 0.5+1e-6
4. Take care of the special case: if sleep_time<=0.0 return 0
5. Return sleep_tim;

I have added 0.5 to the sleep time to round the result to the nearest integer and added 1e-6 to fix the rounding error.

Common bugs:

1. Use of ceiling or flow functions without adding or subtracting 0.5
2. Round off error. Example: 97,61,904,0 = 5.500084502, 84,35,750,8 = 4.5 (it would return 4 instead of 5 if you don't add extremely small number).

Division-II Level 3, Division-I Level 1 - RatRoute  
(reference Slavik solution)

Simple Brute Force recursive function would work fine for this problem:

1   int do_it(int x,int y,vector<string> &enc,int dx,int dy) {
2      if (x==dx && y==dy) return 1;
3      if (enc[y][x]=='X') return 0;
4      int total=0;
5      if (dx>x) total+=do_it(x+1,y,enc,dx,dy);
6      if (dx<x) total+=do_it(x-1,y,enc,dx,dy);
7      if (dy>y) total+=do_it(x,y+1,enc,dx,dy);
8      if (dy<y) total+=do_it(x,y-1,enc,dx,dy);
9      return total;
10   }

Where "x" and "y" are current coordinates and "dx" and "dy" are destination coordinates.

The worst case is when field is 10x10 and rat and cheese are located in different corners and no walls inside. It would take this function a little less then 185,000 iterations to find the solution. Dynamic programming can also be used for this problem but is not needed due to the small size of the field. This approach was taken by almost all the coders who has submitted this problem.

Common bugs:
Some people confused Y and X coordinates and caused segmentation faults.

Division-I Level 2 - ManyPics  
(reference Slamin solution)

To solve this problem consider representing a board as a 32-bin unsigned integer. (The area of the canvas (width*height) will be between 2 and 32, inclusive so 32 bits should be enough). To actually solve the problem one can do the following:

1. For each line create a set of all the solutions for entire canvas. Each solution can be represented as a 32-bit integer. So if canvas is "...","..." - a set of all the solutions for the line of a size 2 will be 3,6,24,48,9,18,36
2. Find all the combinations of solutions for all lines where no two lines overlap each other. To check that two lines do not overlap each other one should use logical AND operator:

   if ((line1 & line2) == 0) /* lines do not overlap */
   

   I think Slamin has very good and clear solution on how to combine all lines together:

   void doit(int n, int idx) {       
   // n is current canvas and idx is current line
   if (idx >= v.size()) {   
   // base case - all lines are added
   res.insert(n);      
   // insert solution into the set
   return;
   }
   // find all not overlapping solutions for "n" field and line "idx"
   for (set<unsigned int>::iterator it = v[idx].begin(); 
   it != v[idx].end(); ++it) { 
   // iterate through the set
   if ((n & *it) == 0) doit(n | *it, idx + 1); 
   // pick next line
   }
   }
   

3. The only thing left to do is to return a size of the result set.

   This problem would be much more difficult to solve if bitmaps were not chosen to represent canvas. The alternative to bitmap would be string and some coders such as ZorbaTHut chose a string to represent a canvas. Almost half of all successful solutions were using bitmap to represent canvas.

Many solutions timed out - the wrong data structure was selected to represent a canvas and inefficient code to put lines together.

I think this problem was the hardest one in SRM 103 and has biggest rate of failed solutions. There were 65 submissions overall for this problem and only 27 of them have passed the system test.

Division-I - Level 3 - CostlyOnes  
(reference SnapDragon solution)

To solve this problems two approaches should be considered: divide and conquer and dynamic programming. Another key in solving this problem is to count numbers which CAN be represented with given number of 1s and then just deduce the required count (count of numbers which can NOT be represented).

To count all the numbers, which can be represented with given number of 1s, we should reduce a problem by dividing an UL (upper limit) into two parts:

int part1 = 2^floor(log2(n))-1;   
int part2 = UL-part1+1;
So, if upper limit is 155     (10011011), 
2^floor(log2(n))=128     (10000000)  or it can be calculated as    
for( int x = 1; x*2 <= UL; x *= 2 ); (SnapDragon)
and second number is 27     (00011011)

So, total count of numbers, which can be represented by given number of 1s, is Do_it(127,C) + Do_it(27,C-1) - recursive calls to itself.

So, the only thing left to do is to memorize the result and return it right away if this function was already called before (Dynamic Programming)

map<pair<int, int>, int> mem; 
int do_it(int u, int c) { 
   if( c == 0 || u == 0 ) return 1;          
   // base case 
   int &ret = mem[pair<int,int>(u,c)];       
   // DP map
   if (ret) return ret;             
   // if called before return the result
   for( int x = 1; x*2 <= u; x *= 2 );          
   // find pivot point:  2^floor(log2(n))
   return (ret = do_it(x-1, c) + do_it(u-x, c-1));    
   // reduce the input and calculate separately
} 

The only thing left to do is to return count of numbers which cannot be represented: return UL+1-doit(UL,c);

There were only 23 submissions for this problem and only 7 of them have failed challenges or system tests.