
Match Editorial 
SRM 109Wednesday, August 21, 2002
The Problems
StringMult (value 250)
Used as: DivisionII, 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: DivII) (value 300: DivI)
Used as: DivisionII, 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: DivisionI, 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, ab, ba, 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.
Here is a possible solution for a/b case:
if (b!=0 && a%b==0 && num.find(a/b)!=num.end() ) {
count++;
continue;
}
Reference implementation: slavik
Treasure (value 1000: DivII)
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,y1);
if (c!='L') do_it(index+1,x1,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,y1);break;
case 'L': do_it(index+1,x1,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: DivI)
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} };
Now we just have to make sure the Knight is not outside of the board:
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);
}
}
Reference implementation:
along
PartyPromo (value 900: DivI)
Used as: DivisionI, 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
By
slavik
TopCoder Member