Match Editorial

The Problems

StringMult (value 250) 

Used as: Division-II, Level 1

Submission Rate - 174/184 (94.57%)
Success Rate - 163/174 (93.68%)
High Score - javaisthe_unwin for 247.92 points
Avg. Points - 219.42944

Implementation
To solve this problem you just need to build a loop from 0 up to absolute multiplier and every iteration add another instance of a string to the resulting string (resulting string should be set empty before the loop to account for 0 multiplier). If multiplier is negative reverse the result.

ListOps (value 500: Div-II) (value 300: Div-I) 

Used as: Division-II, Level 2

Submission Rate - 133/184 (72.28%)
Success Rate - 76/133 (57.14%)
High Score - javaisthe_unwin for 486.66 points
Easy Avg. Points - 299.80264

Used as: Division-I, Level 1

Submission Rate - 96/99 (77.78%)
Success Rate - 77/96 (80.20%)
High Score - ZorbaTHut for 292.16 points
Avg. Points - 229.38962

Implementation
One of the ways to solve this problem is to illuminate all duplicates from the list of numbers and build all possible pairs in the following nested loops:

for (int i=0;i<num.size()-1;i++) {
   for (int k=i+1;i<num.size();i++) {
   int a = num[i];
   int b = num[k];
   ....
   ....
}
}

The only thing left to do is to see if any of the following operations: a+b, a*b, a-b, b-a, a/b and b/a would result with number in the original list:

There are two special cases in this problem: division by 0 and division with reminder not equal to 0.

if (b!=0 && a%b==0 && num.find(a/b)!=num.end() ) {
   count++;
   continue;
}

Reference implementation: slavik

Treasure (value 1000: Div-II) 

Used as: Division II, Level 3

Submission Rate - 52/184 (28.26%)
Success Rate - 35/133 (67.31%)
High Score - javaisthe_unwin for 941.84 points
Avg. Points - 591.77

This problem can be solved by using a brute force search. The max number of iterations is 3^10 = 59049, so we do not have to worry about timing out. When the last position is reached insert the coordinates into the set. Return the set size as a result. (

void do_it(int index,int x,int y) { 
      if (index==dir.size()) { // base case when last point is reached
         sols.insert(make_pair(x,y)); 
         return; 
      } 
      char c = dir[index]; 
      if (find(all(inc),index)!=inc.end()) {  // if map has a mistake at this location:
         if (c!='U') do_it(index+1,x,y+1); 
         if (c!='D') do_it(index+1,x,y-1); 
         if (c!='L') do_it(index+1,x-1,y); 
         if (c!='R') do_it(index+1,x+1,y); 
      } 
      else { // if map has no mistake at this location
         switch(c) { 
         case 'U': do_it(index+1,x,y+1);break; 
         case 'D': do_it(index+1,x,y-1);break; 
         case 'L': do_it(index+1,x-1,y);break; 
         case 'R': do_it(index+1,x+1,y);break; 
         } 
      } 
} 

Dynamic programming can be used to speed the process up by is not necessary:

...
char temp[20]; 
sprintf(temp,"%d_%d_%d",x,y,index); 
if (dp.find(temp)!=dp.end()) return; 
dp[temp]=1; 
...

Reference implementation: slavik

KnightMove (value 600: Div-I) 

Used as: Division I, Level 2

Submission Rate - 81/99 (81.82%)
Success Rate - 77/81 (95.06%)
High Score - RobertLu for 582.77 points
Avg. Points - 442.08

Implementation
To solve this problem you have to find the shortest distance from the original square to every square on the board. The Knight should keep unraveling until it cannot find any square on the board which he has not visited or until he cannot find any shorter distance to any of the squares on the board. The simple way to keep track of the visited squares and distances to all of them from the origin is to create a two dimensional array of size 100:100 and initialize all values to infinity.

Start traveling from origin and travel in all 8 possible destinations:

The easy way to implement traveling to build a two dimensional array with all possible movements:

int off[8][2]={ {1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1} };

struct node{
        int x,y,d;
};
...
node t,c;
...
for(i=0;i<8;i++) {
   t=c;
   t.x+=off[i][0]; t.y+=off[i][1]; t.d++;
   if (t.x >= 0 && t.x < N && t.y >= 0 && t.y < N && t.d < dis[t.x][t.y]) {
      dis[t.x][t.y]=t.d;
      qu.push_back(t);
   }
}

PartyPromo (value 900: Div-I) 

Used as: Division-I, Level 3

Submission Rate - 43/99 (81.82%)
Success Rate - 15/43 (34.88%)
High Score - jonmac for 737.32 points
Avg. Points - 580.2

Implementation
The first thing you have to do to solve this problem is to build and adjacency matrix of all promoters who knows each other directly or through common friends.

The hard part is to include all "friend of a friend" into the matrix. This task can be done by exhaustive search:

for( k = 0; k < a.size(); k++ ) 
   for( i = 0; i < a.size(); i++ ) 
      for( j = 0; j < a.size(); j++ ) 
         adj[ i ][ j ] |= ( adj[ i ][ k ] && adj[ k ][ j ] ); 

Now we have all people divided into groups where you one group can have as small as 1 person ior as many as all promoters.

Now we have to find the maximum number of people for each group of promoters. This task can be accomplished by building a dynamic array of all possible cash values from 0 to amount of money allocated:

for( j = 0; j < grp.size(); j++ ) { 
   int promoter = group[ j ]; 
   int cost = a[ promoter ]; 
   for( k = d; k >= cost; k-- ) 
      cshi[ k ] = max( cshi[ k ], cshi[ k - cst ] + people[ promoter ] ); 
   } 
   ...
}

Reference implementation: jonmac