Problem A (Marks) - Problem statement
This is the typical div2 easy. Not much to do here besides implementation. Just find, for each subject, the maximum mark, then set students that have this mark in that subject as successful. Return the total number of students you set as successful.
int n, m;
char grades[100][100];
int countSuccessful()
{
bool success[n];
fill(success, success+n, false);
for (int i=0; i<m; i++) {
char b = '0';
//find maximum grade for this subject:
for (int j=0; j<n; j++) {
b = std::max(b, grades[j][i]);
}
//find succesful students for this subject.
for (int j=0; j<n; j++) {
if (grades[j][i] == b) {
success[j] = true;
}
}
}
//The total number of succesful students.
return count(success, success+n, true);
}
Problem B (Steps) - Problem statement
K and the coordinates can be quite large. So, the main trick to this problem is to do it in O(K) steps. In order to do this, we need to find the maximum steps of a given direction we can do in O(1) (Based on your current location and n and m).
You can actually treat dx and dy separately, and find the maximum for each coordinate. Then take the minimum of the maximums you found and that is the maximum number of steps overall. So, you have your current coordinate z, the direction dz, and t (the maximum value for the coordinate). Imagine for now that dz is positive. The problem becomes to find a maximum s such that: z + s * dz <= t. Solve this in-equation and you will find a formula like s <= (t - z) / dz . Since s has to be a integer, perform a integer division. When dz is negative, use the same process. In fact, what I did was just to convert the negative case to positive and use the same logic (you just need to reverse z, see code).
typedef long long int64;
#define long int64
long n,m;
int k;
long x, y;
long dx[10000];
long dy[10000];
const long INF = 1000000000000ll;
// Returns the maximum number of steps possible if your current
// coordinate is z, the maximum value of the coordnate is t (the minimum is 1)
// and the direction is dz.
long maxSteps(long z, long dz, long t)
{
if (dz == 0) {
return INF;
} else if (dz < 0) {
return maxSteps(t - z + 1, -dz, t);
} else {
//max s: (z + s*dz <= t)
// ( s*dz <= t - z )
// ( s <= (t - z) / dz
return (t - z) / dz;
}
}
long numSteps()
{
long total = 0;
for (int i=0; i<k; i++) {
long xsteps = maxSteps(x, dx[i], n);
long ysteps = maxSteps(y, dy[i], m);
long s = std::min(xsteps, ysteps);
x += s * dx[i];
y += s * dy[i];
total += s;
}
return total;
}
inline void init(){}
Problem C (Pocket book) - Problem statement
This one is mostly to think things through. You can swap the prefixes of any size between any pair of names. In fact, this overall means that for each character position in the names, you can pick any letter in this position available in any of the names. This means that for each position, there are (number of different letters in the position) choices. And these choices are actually independent. So, just multiple the number of choices for each position and you find the result.
Do you want a informal demonstration? Let us say we have the following names:
ABCD
1234
XYZW
According to our logic, the string 1BZ4 is possible. A strategy to reach this name, is to first pick the name that has 4 in the last position, and swap the entire strings:
1234
ABCD
XYZW
Now we want a Z in the third location. Let us just pick the string that has Z in that position and swap only the first three characters:
XYZ4
ABCD
123W
From here, you can continue doing it. Pick "AB" and place them in the first name. Then pick "1".
typedef long long int64;
#define long int64
const int MOD = 1000000007 ;
int n, m;
string names[100];
int countNames()
{
long c = 1;
for (int i=0 ; i < m ; i++) {
//Count the number of different letters we can use in this position
//a set is great for this:
set<char> st;
for (int j = 0; j < n; j++) {
st.insert(names[j][i]);
}
c = (c * st.size()) % MOD;
}
return (int)c;
}
Problem D (Frames) - Problem statement
Now this is an evil problem. Note that the coordinates mean that you need a O(n*m) solution. I could think of so many possible ways to fail it that it seemed risky. So I switched to E. Then I solved this problem whilst trying to find a solution for problem E.
Well, in fact, it is easy to find a solution for D. It is just difficult to find a solution that you can code without making your head explode and without much risk to make a wrong assumption and fail it. For example, you could always make code that detects each possible case. That will require you to do something short of 8 different solutions, each with something complicated.
My solution, which is still quite long to code involves noticing that there will be at most 7984 painted squares in a valid case. (Try it, in a 1000x1000 board paint as many squares by following the rules). Also, the top-left painted cell should forcefully be the top-left corner of at least one frame.
There are now only two possible cases: 1) The top-left painted cell is the corner of two rectangles (they could possibly overlap completely and thus it will look as one rectangle). or 2) This cell is the corner of only one of the rectangles (There is another top-left corner.)
A solution that needs less than 8000*8000 steps to detect case 1): After you find the top-left cell, try all 8000*8000 pairs of possible bottom-right corners you can find. You need a way to verify that a pair of top left and bottom right corners forms a valid rectangle. For this, it is best to use accumulated sums of the number of painted cells in the rectangle to calculate the number of cells inside a rectangle of squares in O(1). Subtract the middle rectangle from the smaller rectangle to find the number of cells in the border of the "frame". If this is equal to the perimiter, then this is a valid frame. If you find two corners that make a valid frame with the top left corner (Note that these two bottom-right corners might be equal) then you still have to verify that the cells that make these two frames are the only painted cells in the paper sheet. You will have to find a function that calculates the sum of the perimeters of two rectangles. That requires you to find the intersection of the perimeters of the rectangles, this is possible, but should take some case matching... (This is the reason I halted coding the solution).
Test case 2) Is similar. You first need to find the one unique bottom right cell that makes a valid frame with the top-left cell. After that, you can find the two corners of the other rectangle. This is once again at most 8000*8000 tries. You will need to reuse the code from case 1).
I am very sure there is an easier approach for problem D.
Problem E - Problem statement
This problem is similar to finding those trees that are like the minimum spanning trees but can use any intermediary points. This problem needs some sort of exponential solution. Which is likely confirmed by the small constraints of K. Also note that the size of the smallest dimension is at most 14 (Because n*m is at most 200). The solution likely abuses these constraints. Had to stop working in this problem when I thought I had a simple solution for D.
What do you think?
I liked the match until problem C. I think D is too convoluted. A lot of people preferred to skip to E, which seems nice.
0 comments:
Post a Comment