Match Editorial

The Problems

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

Value	550
Submission Rate	88 / 250 (35.20%)
Success Rate	48 / 88 (54.55%)
High Score	uglyfool for 474.60 points

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.

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.

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.

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.

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.

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; 
} 

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.

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.