Match Editorial

The Problems

Value	250
Submission Rate	170 / 187 / (90.91%)
Success Rate	120 / 170 (70.59%)
High Score	guagua for 243.85 points

61 out of 281 coders who opened PackingObjects, received 0 points.

Implementation

The problem is very straightforward. Simply, go through the list of all the boxes and see if a given object can fit inside. If "Yes" then compare the box area to the best so far.

Reference implementation: slavik (practice room)

Value	550
Submission Rate	130 / 187 (69.50%)
Success Rate	84 / 130 (64.62%)
High Score	Dimkadimon for 437.25 points

90 out of 174 coders who opened SpeedDial, received 0 points.

Implementation

int cmp(pair<int,int> a,pair<int,int> b) {
   return (a.first-2)*a.second > (b.first-2)*b.second;
}

int get_size(int a) {
   char temp[20];
   sprintf(temp,"%d",a);
   return strlen(temp);
}

int assignNumbers(vector <int> a, vector <int> b, int c) {
   vector<pair<int,int> > numbers;
   for (int i=0;i<a.size();i++) numbers.push_back(make_pair(get_size(a[i]),b[i]));   
   sort(numbers.begin(),numbers.end(),cmp);
   int total=0;
   for (int k=0;k<numbers.size();k++) {
      if (k>=c) total+=numbers[k].second*numbers[k].first;
      else      total+=numbers[k].second*2;
   }
   return total;
}

To solve this problem we have to figure out how many numbers can be saved by using speed dial versus if the number is dialed the regular way. To solve this problem we can insert all the numbers into an array (where every member would have a size of the number and number of times this number is dialed). Then we can sort this array by number of key presses saved if this number is speed dialed. Number if key presses saved = (length of the phone number - 2) * number of times this phone numbers is dialed. Finally we shall go through the sorted array and calculate the total number of key presses needed to dial all the numbers using the given amount of speed dial slots.

Value	1050
Submission Rate	13 / 187 (6.95%)
Success Rate	2 / 13 (15.38%)
High Score	Dr. Gluk for 508.97 points

129 out of 131 coders who opened TCSchedule, received 0 points.

Value	300
Submission Rate	40 / 93 (43.01%)
Success Rate	20 / 40 (50.00%)

72 out of 92 coders who opened TCSchedule, received 0 points.

Implementation

The problem was much harder then it suppose to be for the Div 1 Level I problem (well, it was pretty hard for Div 2 Level III either) according to the round results. The problem statement had some useless and confusing information, which took coders some time to parse through and understand the problem Once the problem is understood it is not that hard to come up with a brute force algorithm to solve it:

I have solved this problem using a recursive function which would try all possible combinations of valid day schedules:

1. Make sure your wake up time is always between 7 and 14.
2. If there is a real life even you must wake up at a given time or before that time otherwise entire branch of recursion is not valid.
3. Try to stay up from 15 to 17 hours and see what happens in every case.
4. if you have to go bad two hours after the competition starts you can participate in it.

Dynamic programming could be used for this problem if current day and current woke up time are used as a key to get maximum number of competitions. If the number of competitions so far is less than the previous try (on the same day and the same wake up time) disregards this recursion branch.

int best=0;
void do_it(int so_far,int cur,int index,vector <int> &a, vector <int> &b) {
   if (cur<7 || cur>14) return;
   if (index==a.size()) 
      if (so_far>best) best=so_far;
      return ;
   }
   if (a[index]!=-1 && cur>a[index]) return;
   for (int i=15;i<=17;i++) {
      int wake_up=(cur+i+8)%24;
      int go_to_bad=(cur+i)%24;
      if (b[index]!=-1 && go_to_bad>=b[index]+2 && go_to_bad!=23) 
         do_it(so_far+1,wake_up,index+1,a,b);
      else 
         do_it(so_far,wake_up,index+1,a,b);
   }
}
int howMany(vector <int> a, vector <int> b) {
for (int i=7;i<=14;i++) do_it(0,i,0,a,b);
   return best;
}

Value	650
Submission Rate	18 / 93 (19.35%)
Success Rate	6 / 18 (33.33%)
High Score	Jms137 for 395.45 points

Reference implementation: jms137

Implementation

The problem is straightforward and easy to understand. On the other hand, implementation would require a lot of typing and special case handling.

There 19 possible shapes which can be generated from 7 given pieces (when using rotations). I think it would be a good idea to create an array of all 19 pieces represented as bitmap or as integer arrays and then try to fit them into the play field (using all possible x,y coordinates of the play field). Once the empty place is found (and given piece is fully inside the playfield) make sure there is something that would hold the piece in place (not empty field right below the piece). Then make sure all the spaces above the found position (1,2,3 or 4 columns depending on the piece) are empty (that would allow the piece drop). Once the position is found, calculate the number of filled rows and compare this number to the best so far.

Value	1000
Submission Rate	2 / 93 (2.15%)
Success Rate	1 / 2 (50%)
High Score (and only score)	niteneb for 778.96 points

48 out of 49 coders who opened ColorCount, received 0 points.

Implementation

I wish the max size of the field was something like a thousand then the problem would be easily solved using a huge array representing all the pixels in the field. But in that case the problem would not be a Div I Hard problem.

To actually implement this problem the following approach shall be taken:

Build two set of coordinates x and y. Those sets shall contain all unique x and y coordinates of all the given shapes. All those points will divide the entire field into rectangles which might have different colors assigned to them. For this problem the maximum number of unique x coordinates is 100 and the maximum number of unique y coordinates is 100. So the maximum number of rectangles, which might have different color is bounded by 100*100=10000.

To simplify this problem all the given shapes might be represented as rectangles: Pixels is a rectangle with width=1 and height=1
Horizontal line is a rectangle with height=1
Vertical line is a rectangle with width=1

Now we have to go through all shapes again and assign a color to one or to many rectangles (there are a maximum 10000 different rectangle which can be created and we know all the coordinates for them)

Let M=sizeof(x coordinate set)
Let N=sizeof(y coordinate set)

Let c[M][N] is a list of colors assigned to every possible rectangle rectangle. Once the Fill command is given the DFS (Depth First Search) algorithm shall be used to color all the adjacent rectangles.

Once we passed through all commands again we have a list of adjacent rectangles with different colors assigned to them.

Now we have to pass through all those rectangles and calculate the number of different pixels for each color.