|
Match Editorial |
SRM 127Thursday, January 2, 2003
The Problems
PackingObjects
Used as: Division-II, Level 1:
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)
SpeedDial
Used as: Division-II, Level 2:
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.
TCSchedule
Used as: Division-II, Level 3:
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.
Used as: Division-I, Level 1:
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:
- Make sure your wake up time is always between 7 and 14.
- 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.
- Try to stay up from 15 to 17 hours and see what happens in every case.
- 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;
}
Tetramino
Used as: Division-I, Level 2:
Value
|
650 |
Submission Rate
|
18 / 93 (19.35%) |
Success Rate
|
6 / 18 (33.33%)
|
High Score
|
Jms137 for 395.45 points
|
70 out of 76 coders who opened Tetramino, received 0 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.
ColorCount
Used as: Division-I, Level 3:
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.
Reference implementation:
niteneb
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.
By
slavik
TopCoder Member