One of the reasons I was trying a risky strategy to put more focus on div1 medium / hard and risk not solving div1 easy is matches like this one, you only solve div1 easy, and you take too long, so you get a low score and is not too different from getting a zero, but much more boring. It gets frustrating.
Div1 250: The one with planets.
You get two arrays A, B, lists of planets in increasing order of distance from the sun. Each list might be missing some of the planets in the solar system. The lists contains planet dimensions, but both lists use a different measurement system, so two planets with sizes {6, 18} in one list might have {10, 30} in another list. Return the minimum number of planets in a solar system for both lists to be correct. In other words, find the maximum number of planets the lists can have in common (and the proportions have to be consistent) and subtract from the total number of planets in the list.
I took too long to think of this solution, but the key is to figure that at least one pair of planets from each list can be equal. (Worst case scenario, you make the last planet in one list and the first planet in the other equal). We can iterate through all possible pairs `(A[i], B[j])` and ask "What is the minimum number of planets if we assume these two are equal?". If we determine that two integers `A_i,B_j` describe the same planet in different measurement systems, then it is easy to see the conversion rate between the two systems. One unit in system A is equivalent to `B_i/A_i` units in system B. So we can just multiply all planets with that proportion. If we want to avoid doubles, we can actually find the greatest common divisor `g = gcd(A_i,B_j)`, and multiply each array by `B_j/g` and `A_i/g` , respectively, that would make all numbers in the same measurement system.
Once all numbers have the same system, we just need to find the maximum number of planets that are equal. Since both lists have the same order. This is actually the same as the longest common subsequence, a classical dynamic programming problem.
long gcd(long a, long b)
{
while (b != 0) {
tie(a,b) = make_tuple( b, a % b);
}
return a;
}
vector<long> fix(vector<int> A)
{
int g = A[0];
for (int x: A) {
g = gcd(g, x);
}
vector<long> LA;
for (int &x: A) {
LA.push_back(x / g);
}
return LA;
}
int sub(vector<long> A, vector<long> B, int i, int j)
{
//if we assume A[i] and B[j] are the same planet, what is the
// minimum number of planets?
long a = A[i], b = B[j];
long g = gcd(a, b);
// Scale vectors such that the new vectors A' , B'
// Have: A'[i] = B'[j] = lcm(A[i], B[j])
for (long & x: A) {
x *= (b / g);
}
for (long & x: B) {
x *= (a / g);
}
// largest common subsequence:
int nA = A.size(), nB = B.size();
int dp[nA + 1][nB + 1];
for (int s = 0; s <= nA; s++) {
for (int t = 0; t <= nB; t++) {
if (s == 0 || t == 0) {
dp[s][t] = 0;
} else {
bool eq = (A[s-1] == B[t-1]);
dp[s][t] = max( {dp[s-1][t], dp[s][t-1], eq + dp[s-1][t-1] } );
}
}
}
return nA + nB - dp[nA][nB];
}
int minimalPlanets(vector<int> _A, vector<int> _B)
{
// if the result is not |A| + |B|, at least one pair must be equal
vector<long> A = fix(_A);
vector<long> B = fix(_B);
int nA = A.size(), nB = B.size();
int res = nA + nB;
for (int i=0; i<nA; i++) {
for (int j=0; j<nB; j++) {
res = std::min(res, sub(A,B, i,j));
}
}
return res;
}
I had a fun delay, when multiplying A by `B_j/g` and B by `A_i/g`, I didn't notice that `A[i]` changes after the first step. Good thing example 2 catches this mistake.
Div1 550
I tried plenty of things with no success. At first I thought it was clearly a Maximum Flow problem. It is at least very easy to know, through min-cut the minimum number of black checkers needed to remove all white checkers. Is there a way to do the same but to remove only a limited number of white checkers? I have no idea. But I noticed Petr uses maxflow. Albeit a bit more straightforward, maybe there is a way to solve the whole problem with max flow.
Later I thought [maybe it is greedy?] but nah, I was able to come up with counter examples to any greedy idea I had, so probably not.
Challenge phase
I thought that maybe overflow was going to be a possible mistake guys would make. But not too much luck.
There was a greedy solution to 550 in my room, but it took me a while to understand its strategy and come up with a counter example, someone else challenged while I was inputting my challenge case.
So...
I need to improve my speed. No idea how can it be done. I thought limiting the time I have for 250 to 10 minutes would work, but it didn't seem to. Any comments about the match?
0 comments:
Post a Comment