|
Match Editorial |
SRM 113Tuesday, 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:
- Incrementing year by 1 and timing out.
- Leap year computations.
- 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