
Match Editorial 
SRM 113Tuesday, September 10, 2002
The Problems
GameCipher
Used as: DivisionII, Level 1:
Value

250 
Submission Rate

219 / 250 (87.60%)

Success Rate

148 / 219 (67.58%)

High Score

fiddlybit for 239.89 points

93 out of 241 coders who opened GameCipher, received 0 points.
Reference implementation:
Implementation
The problem is very straightforward and as easy as it has to be for DivII Level 1 250 problem. Al
To solve the problem check every pair for the following:
if a==b return index
if a is vowel and b is not vowel return index
if b is vowel and a is not vowel return index
if a is mapped return index
if b has mapping to return index
Nash
Used as: DivisionII, Level 2:
Value

550 
Submission Rate

88 / 250 (35.20%)

Success Rate

48 / 88 (54.55%)

High Score

uglyfool for 474.60 points

Reference implementation:
slavik (practice room)
179 out of 227 coders who opened Nash, received 0 points.
Implementation
To solve this problem we have to parse the entire input first which could be easily done by using String Tokenizer or strtkn() for C++ coders. Once we have entire matrix values in array structure in memory the best way to solve the problem is to find all columns maximum values for column player and all rows maximum values for row player. Once we have those two arrays we can go through the matrix one more time and for every element of the matrix check if this element is best for row player and is the best for the column player. To do that we just check if maximum for this row is the current element for row player and if maximum for this column is the current element for the column player. One those two conditions are meet we have found a Nash Equilibrium.
LazyYear
Used as: DivisionII, Level 3:
Value

900 
Submission Rate

27 / 250 (10.80%)

Success Rate

1 / 27 (3.70%)

High Score

uglyfool for 482.59 points

164 out of 165 coders who opened Nash, received 0 points.
Used as: DivisionI, Level 2:
Value

450 
Submission Rate

63 / 229 (27.51%)

Success Rate

19 / 63 (30.16%)

High Score

Garzahd for 275.47 points

108 out of 127 coders who opened LazyYear, received 0 points.
Reference implementation:
SnapDragon
Implementation
This problem was just plain ugly with no way to do it elegantly and short. The smallest and easiest to understand was solution by SnapDragon who realized that the next year with a valid date after the year such as year%4==0 is another year where year%4==0. So he just solved this problem by doing brute force computation where worst case took about 46 seconds.
To do a check on the year itself was not that hard  just a lot of ugly special cases.
Some people where checking the first 3 digits of the year and if those were not a valid date, skipped a significant amount of empty computations by incrementing those 3 digits instead of the least significant digits of the year.
Most common mistakes were:
 Incrementing year by 1 and timing out.
 Leap year computations.
 Special case as no date like 101XXXX.
CodeBloat
Used as: DivisionI, Level 1:
Value

250 
Submission Rate

120 / 229 (52.40%)

Success Rate

40 / 120 (66.67%)

High Score

b0b0b0b for 248.27 points

46 out of 126 coders who opened CodeBloat, received 0 points.
Reference implementation:
Slavik
Implementation
This problem was a typical enumeration problem where all possible combinations have to be enumerated and tried out. There are two ways of doing that: iterate from 0 to 2^N where each iteration in the loop is used as a bitmask to get combinations of inputs to try. The second and more efficient way is to build a recursive function which would try or not try every member of the input:
int do_it(int index,int cur,int maxx) {
if (cur>maxx) return 0;
if (index==d.size()) return cur;
int d1=do_it(index+1,cur,maxx);
int d2=do_it(index+1,cur+d[index],maxx);
return (d1>d2) ? d1:d2;
}
Logical
Used as: DivisionI, Level 3:
Value

1000 
Submission Rate

33 / 229 (15.31%)

Success Rate

25 / 33 (75.76%)

High Score

Yarin for 920.02 points

72 out of 97 coders who opened Logical, received 0 points.
Reference implementation:
ambrose
Implementation
One of the solutions to the problem is to enumerate all possible true and
false assignment to all letters used. There is a maximum of 20 distinct
letters which can be used in this problem, so this enumeration will take O
(2^20) combinations. Then each block in the statement has to be evaluated.
So, there should be a loop to remove blocks which values are false. Number
of the remove blocks should be compared to the best so far.
By
slavik
TopCoder Member