Single Round Match 524
Thursday, November 17th, 2011
Match summary
Hello everyone!
I'm cgy4ever, and this is the first time I'am writing an SRM.
In division one, 717 coders participated. The easy problem looks very easy, thus
so many coders submitted this problem in a short time, but then some of them find
they fall into a trap. As for the medium and hard one, they
are a bit of tough. Our genius coders tourist and Petr, who ranked 1st and 2nd
in ratings, were assigned to the same room. And they performed exceptionally well
in the first few minutes. Particularly, tourist had submitted both easy and
medium in nearly 10 minutes, and got the highest scores for both of them. But they couldn't
submit a correct answer for hard, which needs to consider many details. The winner
was Egor, and followed RRx. They are the only coders to solve all 3 problems.
The 3rd place went to liympanda, who solved easy and hard successfully.
In division two, 828 coders participated. The easy one and medium one was easier than normal,
so they could allow time for the tough hard one. The winner is groverc002, followed by
innocentboy2 and 1412.
Due to the trick in the problem MagicDiamonds, the challenge phase was busy.
As a result, there was 200 challenge requests in division one, precisely!
I would like to appreciate for [[rng_58]] for helping me all the way,
mystic_tc for giving great suggestions while testing them and misof for correcting every word in problem statements.
The problem is to minimize the sum of 3 positive integers which their product N is given.
It is pretty straightforward. As N is only 200, a brute force algorithm works.
Code
publicint minimalCost(int N)
{
int minCost = N + 1 + 1; // the answer will not exceeded N+1+1, because a box with dimensions N*1*1 is a solution.
for(int a = 1; a <= N; a++)
for(int b = 1; b <= N; b++)
for(int c = 1; c <= N; c++)
if(a * b * c == N)
if(a + b + c < minCost)
minCost = a + b + c;
return minCost;
}
The above algorithm can run in O(N^3).
Further Tasks
1. This problem has a solution with the time complexity O(N), can you figure out how to do it?
(Hint: pre-processing the factors of N.)
2. If the limit "You can't leave any empty space in the box" was removed, then the above algorithm will not work, can you give out a counter-example?
The problem is : Decompose N into the sum of non-prime positive numbers. You
are asked to find minimize the amount of numbers.
There is an ordinary DP solution with the time complexity O(N^2)
But N can be as large as 10^12, so we need some observation.
Observation:
For enough N, the answer will be 2 if N is a prime and 1 otherwise.
Proof:
If N is a large prime, the answer can't be 1. And (N-1) can't be a prime, because any even number larger than 2 is not a prime.
So we have a solution which contains 2 numbers: N = (N-1) + 1.
So we can solve the who task in O(sqrt(N)) since we can test the primality in O(sqrt(N)) time.
But their is still a trap: If N equals or less than 3, then the answer will be N.
When we are testing this problem, two tester(Include me)'s solution fails on N=1.
So we thought it would be too evil, and then add this test case into examples. The only tricky case is N=3, which is a powerful case for challenge.
Code
publicboolean isPrime(long x)
{
if(x == 1)returnfalse;
for(long i = 2; i*i <= x; i++)
if(i < x && x % i == 0)
returnfalse;
returntrue;
}
publiclong minimalTransfer(long N)
{
if(!isPrime(N))return 1;
if(N == 3)return 3; // N = 3 is a special case.
return 2;
}
Future Tasks
Let's consider the inverted version of this problem:
Decompose N into the sum of primes. Return the minimal of amount of numbers, if there is no solution, return -1 instead.
There is also an ordinary DP solution with the time complexity O(N^2)
(Or O(N^2/logN) more precisely, using the fact: Prime number theorem)
Can you come up with a solution with the time complexity O(sqrt(N))?
The intend solution is not proved yet, but many mathematicians think it should be right.
Can you figure out what I'm talking about? :)
The problem is : Find the minimal multiple of N such that its decimal representation
doesn't contain any forbidden digits.
Since the limit is about its digits in decimal representation, you can treat it as a string.
So there is a basic question raised: If we have a string, how to check whether it is the multiple of N or not?
Indeed, we can establish a DFA (deterministic finite automaton) like this:
- There are N states, named 0 ... (N-1).
- For each state s and each digit d that is not forbidden, we establish a transition from s to (s*10+d)%N with the symbol d.
- The initial state is 0, and the accept state is also 0.
So the question transforms to: Find a non-empty string s which can be accepted by the above DFA, minimize its length.
(If we have strings with the same length, choose the lexicographical smallest one.)
Now it is nearly a basic problem in graph theorem: find the shortest path in a graph which every edges weighted 1.
So it can be solved by a simple BFS. The algorithm can run in O((10 - |forbiddenDigits|) * N).
Note that if you are thinking in a DP way, you can also reach the above algorithm:
DP[i] := The optimal string s such that s % N = i.
But this time you need to think about the order to do this DP, and finally you will reach the same destination.
Why the DP method is very similar to the DFA solution? Becuase the key point in DP is to establish states, which is the core of a DFA.
So sometimes we can think a DP problem in a DFA way, and vice versa.
Code
publicString minMultiples(int N, int[] Limit)
{
String DIGI = "0123456789";
String currentBest[] = newString[N];
int currentLen[] = newint[N];
boolean forbidden[] = newboolean[10];
int queue[] = newint[N + 1];
int current = 0, queueTail = 0;
queue[0] = 0;
currentLen[0] = 0;
for(int i = 0; i < N; i++)
currentBest[i] = "";
for(int i = 0; i < Limit.length; i++)
forbidden[Limit[i]] = true;
while(current <= queueTail) // The BFS loop.
{
int now = queue[current];
for(int i = 0; i <= 9; i ++)
if(!forbidden[i]) // for every non-forbidden digit.
if(now > 0 || i > 0) // The string can't start with 0.
{
int nextMod = (10 * now + i) % N; // Calculate the next state.
String possibleString = currentBest[now] + DIGI.charAt(i); // Save the answer.
if(currentBest[nextMod] == "") // The optimal string is always the one that we reaches at first time, by the BFS properties.
{
currentBest[nextMod] = possibleString;
currentLen[nextMod] = currentLen[now] + 1;
if(currentBest[nextMod].length() > 10) // We can't store the whole string, since it will cause MLE.
{
int len = currentBest[nextMod].length();
currentBest[nextMod] = currentBest[nextMod].substring(0, 5) + currentBest[nextMod].substring(len - 5, len);
}
queueTail ++;
queue[queueTail] = nextMod;
}
}
current ++;
}
if(currentBest[0] == "") // Case 1: No solution.
return"IMPOSSIBLE";
int len = currentBest[0].length();
if(len >= 9) // Case 2: Solution is longer than 9 digits, inclusive.
{
String ret = "";
for(int i = 0; i < 3; i++)
ret += currentBest[0].charAt(i);
ret += "...";
for(int i = len - 3; i <= len - 1; i++)
ret += currentBest[0].charAt(i);
ret += "(";
ret += String.valueOf(currentLen[0]);
ret += " digits)";
return ret;
}
return currentBest[0]; // Case 3: Solution is not longer than 9 digits.
}
Future Tasks
I didn't talk about how to find the lexicographical smallest string.
It's not hard. When we reach a node while do the BFS, we only update the answer if the current one is more optimal than the before.
Indeed, there is a better way, which is used in the above code:
While BFS, search in the order '0' to '9', update the answer only if there is no solution before.
Can you give a proof for the correctness of this method?
(Hint: Induction is a good way to do it.)
The problem is: find the length of the longest sequence of real numbers that satisfies some conditions.
And each condition is "The sum of every consecutive k terms must be (positive) negative."
First we can find the following fact simply:
Observation 1:
If we have a sequence with k terms that satisfies all the conditions, then there exist a sequence with (k-1) terms also satisfies all the conditions.
Proof:
It's almost obviously, because if we delete the last term of a sequence that satisfies all the conditions, then it will still satisfies all the conditions.
So we can do a binary search on the number of terms, then we can solve this problem if we solve the following subtasks:
Subtask 1: Check whether there exists a sequence with k terms that satisfies all the conditions.
Subtask 2: Find the upper bound of the answer.
Subtask 1
Since the sequence contains of real numbers, we are not going to find a solution depend on its terms.
Let's analyze the first example: {-2,3}, the answer is 3, thus we can't find a sequence with 4 terms. Why? We can write out the inequations for conditions (The index is start with 1 for convenience):
So they are contradict.
We want to generalize the above argument, but it seems difficult, since the number of terms in the inequations depends on the conditions.
To use accumulated sums will make it easier. For instance, let's define:
Now every condition is in the form: S[i] > S[j]. It looks like a system of difference constraints,
so we can establish a graph:
Each terms of S correspond to a vertex, and for each inequation S[i] > S[j],
we add an edge: S[i] -> S[j], the graph will contain (k+1) vertexes.
We have the following important result:
Observation 2:
We have an valid sequence if and only if the corresponding graph is a DAG (i.e. no directed cycle).
Proof:
On one hand, if the graph contains a cycle, it will lead a contradiction. For instance, in the above example,
we have a cycle 0 -> 2 -> 4 -> 1 -> 3 -> 0, so we have S[0] > S[2] > S[4] > S[1] > S[3] > S[0], which is a contradiction.
On the other hand, if this graph is a DAG, we can get the topological ordering, so we can assign real numbers to every terms in S according to this ordering.
Then we can restore the required sequence from S, which will be valid.
Now there is a question: how to find the cycle?
You can do a BFS (or DFS) from every vertex, but the following observation will reduce the amount of work:
Observation 3:
If the graph contains a cycle, then there exist a cycle contains vertex 0.
Proof:
For a certain cycle, we can shift it to the left: replace vertex i to vertex (i-1), then we will get a new cycle.
Why? Because the graph is automorphism: suppose t is infinite, when we delete the vertex 0, the remain graph will be isomorphic to the original one.
So we can solve this subtask in O(t * |C|) time.
Subtask 2
If all elements in C are positive (or negative), then the answer will be -1, obviously.
Otherwise, it will be finite, because we can get an upper bound: |C[i]*C[j]| (Where C[i] > 0 and C[j] < 0).
We only need to consider the sum of all terms in the sequence, it is easy to proof.
So we get a upper bound, which can be as large as 1,000,000. We can find a better upper bound:
Observation 4:
The answer will not exceed (|C[i]| + |C[j]| - 1) (Where C[i] > 0 and C[j] < 0).
I want to left the formal proof to you, and now I give an example to show a possible idea.
Suppose the conditions are: {-3,4}, we can create the following table:
The sum of every row is negative, and the sum of every column is positive. Contradict.
So we get a upper bound which is O(maxC).
Thus the whole algorithm can run in O(log(maxC) * |C| * maxC).
Code
publicboolean haveSequence(int len, int[] condition) // Subtask 1 in the solution.
{
boolean visited[] = newboolean[len + 1];
int queue[] = newint[len + 1];
int nowInQueue = 0, queueTail = -1;
for(int i = 0; i < condition.length; i++)
if(0 <= 0 + condition[i] && 0 + condition[i] <= len)
{
visited[0 + condition[i]] = true;
queueTail ++;
queue[queueTail] = 0 + condition[i];
}
while(nowInQueue <= queueTail) // This is a BFS method, DFS also works.
{
int now = queue[nowInQueue];
for(int i = 0; i < condition.length; i++)
// There is a trick: To establish the graph implicitly instead of explicitly will make the program more effective.
if(0 <= now + condition[i] && now + condition[i] <= len)
if(!visited[now + condition[i]])
{
visited[now + condition[i]] = true;
queueTail ++;
queue[queueTail] = now + condition[i];
}
nowInQueue ++;
}
return !visited[0];
}
publicint maxLength(int[] condition)
{
int L = 0, R = 2 * 1000 , M = (L + R) / 2;
if(haveSequence(R , condition)) // Check the infinite case.
return -1;
while(R - L > 1) // Binary search
{
M = (L + R) / 2;
if(haveSequence(M , condition))
L = M;
else
R = M;
}
return L;
}
Note that there is a trick which was used in Petr's solution:
Since the constraints are not very large, you can use linear search instead of binary search.
And you can use a code with non-terminal loops without find the upper bound. Then you can run your code,
if you find it works for many large inputs, you can submit it for a very high score.
It's a good strategy in contest.
Future Tasks
This problem is the generalization of this problem(The 2nd problem in International Mathematical Olympiad 1977).
There is a result for 2 conditions {+a,-b} (where a and b are positive.):
The answer is a + b - gcd(a , b) - 1 , where gcd is the greatest common divisor.
Can you proof it?
The problem is: find the number of matrixes with nature number terms which satisfy:
- The maximum value of row[i] is heightsOfLeftView[i].
- The maximum value of column[i] is heightsOfFrontView[i].
First, let's do some observation:
Observation 1:
If we swap the terms in heightsOfLeftView or heightsOfFrontView, the answer will not change.
Observation 2:
The answer is not zero(before module 10^9+9) if and only if the maximum in heightsOfFrontView is the same as in heightsOfFrontView.
So we can sort the elements in both heightsOfLeftView and heightsOfFrontView for convenience.
Let's think the following thing: what will happen if we fill in a number into x[i][j]? (Let's use x to denote the matrix.)
It will be 3 cases (We define maxHeight[i][j] := min(heightsOfLeftView[i] , heightsOfFrontView[j]) for convenience):
Case 1: x[i][j] > maxHeight[i][j] : It can't be a valid solution due to this element.
Case 2: x[i][j] = maxHeight[i][j] : One or two of the conditions will be satisfied by this element.
Case 3: x[i][j] < maxHeight[i][j] : None of the conditions will be satisfied by this element.
The condition that a certain element in matrix can satisfy, is determined by its maxHeight.
So we can divide this problem by different maxHeight.
Let's take a look of the position of different maxHeight.
For instance, suppose heightsOfLeftView = {0, 1, 2, 4, 5} and heightsOfFrontView = {1, 1, 4, 5}, then the maxHeight will look like:
Note that every part with same maxHeight forms a 'L' shape, it's obvious.
So we divide the task into some subtasks, the answer will be the product of each subtask.
Subtask
A subtask can be described by {enoughSize, fullSize, h1, h2, h}.
Where the first element describe the size of the 'L' shape, and h denote the maxHeight.
An example is here:
We are asked to find the number of ways to fill in the 'L' shape such that:
1. Each element will not exceed h.
2. for first h1 rows and enoughSize columns, there is at least one element has the value h.
We can use DP to solve it. Specifically, we can fill the matrix by rows from top to bottom.
Let's use DP[i][j] to denote the answer to the following question:
If we already filled first i rows, and the conditions of those rows are satisfied.
At the same time, j of first enoughSize columns has been satisfied. What's the number of ways to fill in the left cells(and then be valid)?
For instance, the picture in the following shows a situation that we are consider DP[3][2]:
Now the first two rows have been filled, and there are two of first 4 columns are satisfied. (Note that we don't need to know which one has been satisfied, we only need the number of such columns.)
We want to fill in the 3rd row (Which is colored red and scarlet).
The only way we can increase the number of satisfied columns in first 4 ones is to fill h into the non-satisfied cells of first 4.
There are (enoughSize - j) many of such cells. (which is colored scarlet)
So the method of transition comes out:
We enumerate the number of new satisfied columns, the answer will be the sum of each cases.
If this number is k, the number of ways can be calculated after answer the following questions:
1. Which of scarlet cells will be satisfied? It will be C(enoughSize - j , k), where C is the binomial coefficient.
2. How to fill in the scarlet cells that will be satisfied? It will be 1, we must fill in h.
3. How to fill in the scarlet cells, except the one will be satisfied? It will be: h^(enoughSize - j - k).
4. How to fill in the red cells? It will be: (h+1)^(j + (curLen - enoughSize)), where curLen is the length of current row, it equals to: (h<=h1)?enoughSize:fullSize.
5. How to fill in the left cells? It will be: DP[i+1][j+k].
There is still one question we don't consider:
If i<=h1, is this row be satisfied?
It can happen only when k=0, so we can use P.I.E. to solve it.
More detailed, we take off the case that we don't satisfied the condition of this row, which means every element is less than h.
The amount of it will be: h^curLen * DP[i+1][j].
So the subtask can be solved in O(Area * enoughSize), where Area is the number of cells in the 'L' shape, and enoughSize will be less than |heightsOfFrontView|.
Totally, the algorithm can run in O(|heightsOfFrontView|^2 * |heightsOfLeftView|) time.
Code
publiclong power(long a, int n) // Calculate power using divide and conquer.
{
long ret = 1 , MOD = 1000000009L;
while(n > 0)
{
if(n % 2 == 1)
ret = (ret * a) % MOD;
a = (a * a) % MOD;
n = n / 2;
}
return ret;
}
publicint howManyWays(int[] heightsOfLeftView, int[] heightsOfFrontView)
{
long answer = 1 , MOD = 1000000009L;
long C[][] = newlong[51][51];
for(int i = 0; i <= 50; i++) // Pre-process of generate binomial coefficient.
{
C[i][0] = 1L;
C[i][i] = 1L;
for(int j = 1; j < i; j++)
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
int n = heightsOfLeftView.length , m = heightsOfFrontView.length;
int maxHeight[][] = newint [n][m];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(heightsOfLeftView[i] < heightsOfFrontView[j])
maxHeight[i][j] = heightsOfLeftView[i];
else
maxHeight[i][j] = heightsOfFrontView[j];
int differentHeights[] = newint[n + m]; // You can also enumerate the height from 1 to 10,000, since it is not very large.
for(int i = 0; i < n; i++)
differentHeights[i] = heightsOfLeftView[i];
for(int j = 0; j < m; j++)
differentHeights[n + j] = heightsOfFrontView[j];
for(int u = 0; u < n + m; u++)
{
boolean repeat = false;
for(int v = u + 1; v < n + m; v++)
if(differentHeights[u] == differentHeights[v])
repeat = true;
if(!repeat)
{
int fullSize = 0 , enoughSize = 0; // The following is to calculate fullSize and enoughSize.
int curHeight = differentHeights[u];
int h[] = newint[n + 1]; // h correspond to curLen of each row.
for(int i = 0; i < n; i++)
{
h[i] = 0;
for(int j = 0; j < m; j++)
if(maxHeight[i][j] == differentHeights[u])
h[i] ++;
if(heightsOfLeftView[i] == curHeight)
fullSize = h[i];
}
for(int i = 0; i < m; i++)
if(heightsOfFrontView[i] == curHeight)
enoughSize ++;
for(int i = 0; i < n; i++)
for(int j = 0; j < n - 1; j++)
if(h[j] > h[j+1])
{
int t = h[j];
h[j] = h[j+1];
h[j+1] = t;
}
if(h[n-1] == 0)
answer = 0;
else
{
long dp[][] = newlong[n+1][m+1]; // DP start here.
dp[n][enoughSize] = 1L;
for(int i = n - 1; i >= 0; i --)
for(int j = 0; j <= h[n-1]; j++)
{
if(h[i] == 0)
dp[i][j] = dp[i+1][j];
else
{
for(int k = 0; j + k <= enoughSize; k++)
{
long t = power(curHeight + 1, j + (h[i] - enoughSize)); // Correspond to question 4
t = (t * power(curHeight, enoughSize - j - k)) % MOD; // Correspond to question 3
t = (t * C[enoughSize - j][k]) % MOD; // Correspond to question 1
t = (t * dp[i + 1][j + k]) % MOD; // Correspond to question 5
dp[i][j] = (dp[i][j] + (t)) % MOD;
if(k == 0 && h[i] == fullSize) // Use P.I.E. here.
dp[i][j] = (dp[i][j] - (power(curHeight, h[i]) * dp[i+1][j]) % MOD + MOD) % MOD;
}
}
}
answer = (answer * dp[0][0]) % MOD;
}
}
}
return (int)answer;
}
Here is Egor's solution, which was coded in 26 minutes, how fast and accurate he is!
Congratulations to him again!
Further Tasks
1. Prove observation 1.
2. Prove observation 2.
3. The above DP solution is a bit complex, can you come up with a better method?
Please read the guidelines (http://apps.topcoder.com/wiki/display/tc/Guidelines+for+editorial+writers
) before editing editorials. Specifically, use wiki markup, because if you use rich text, the markup gets bugged, extra line breaks get added and the links to the problems go missing.