JOIN
 Match Editorial
SRM 113
Tuesday, September 10, 2002

# The Problems

GameCipher
Used as: Division-II, 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 Div-II 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: Division-II, 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: Division-II, 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: Division-I, 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 4-6 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:

1. Incrementing year by 1 and timing out.
2. Leap year computations.
3. Special case as no date like 1-01-XXXX.

CodeBloat
Used as: Division-I, 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: Division-I, 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