I know that I haven't been making updates to this blog lately. But I bring news. The good news is I have finished the editorial for the easy problems in this editorial. The bad news is that I am still clueless about the geometrilicious div1 hard. So it might take a while.
The link to the complete preliminary editorial is at : http://apps.topcoder.com/wiki/display/tc/SRM+585 meanwhile, I will write about my experience in this match and also show the div1 500 explanation:
The match
I had some bad luck in this match , I think I could have done much better in different circumstances.
I opened div1 medium. A LISNumber of a sequence is the minimum number of increasing sequences that need to be concatenated to make the sequence. You have `"cardsnum"[i]` cards with number `i` written on them, what is the number of ways to make sequences out of these cards such that they have a LISNumber equal to `K` ? `(K <= 1296)` and the number of card types and the number of cards of each card are at most 36.
I felt I should be able to solve the problem, it looked like a dynamic programming one that needs you to be clever to make it run in time. So I gave it a try. I was able to come up with the reduction to represent the state as just the number of card types left to place and the number of new sequences you need to start in addition to the ones already placed. Taking care of the duplicates was very hard. I was first trying to do it using two dynamic programming problems, one nested inside the other. When I noticed that the nested problem required too much memory, I was able to come up with an alternative that didn't take as much memory : 3 dynamic programming problems in total, 2 nested inside the other!
While coding that mess, I noticed that the timer was approaching the 10 minute mark. I am supposed to open the division 1 easy problem at that time. But I was so close to debug my approach and I was so sure it was going to work that I decided to stay with 500. A couple of minutes later, I finished the code and it was giving correct results... Except for a case, that had segmentation fault! . For some reason (I think it might be case 2) which has {36, ... 36,...,36}, 36 as input), I thought that K was going to be at most 36, but it is in fact at most 36^2. The approach with nested dynamic programmings would work with `K <= 36` , but 1296 was too much. By the time I figured, it was too late to try to come up with a faster solution, my last chance was the easy problem.
The easy problem was easy, but I only had 4 minutes to solve it. It actually seemed like I was able to solve it. I guessed a solution formula (that turned out to be wrong) and I coded it. I finished it, but when the time I noticed it was wrong, it was too late). Scored a flat 0.00 in this match.
The editorial preview
First, It is good to see interpret the LISNumber as 1 + (Number of times an element in the sequence is less than or equal to the previous element).
Ignore the repetitions
It is useful to first ignore that there are going to be multiple cards with the same number and just solve the variation of the problem in which each card is unique, no repetitions. We want to count the number of sequences of n distinct elements such that the number of times an element is strictly less than the previous one is K - 1. We will call these positions the start of an additional sequence.
It is convenient to have an order when deciding the positions of the cards. Let us try decreasing order. For example, a card [3] when n is 7, so cards [4],[5] and [6] were already placed. If, for example, the current sequence of cards was {4,6,5}. There is already one position in which a new sequence starts: From 6 to 5. We have some choices:
- Since all the cards are already larger, then placing card [3] at the beginning of the sequence: {3,4,6,5} will not change the number of sequences.
- Placing [3] after 4 or 5, will increase the number of increasing sequences: {4, *3, 6,5}.
- Placing [3] after 6, will not increase the number of increasing sequences: {4,6, 3,5}. This is a interesting case, because `(6 >= 5)`, there is already a separation, this is already the beginning of a new increasing sequence. All the elements are greater than [3], so we are guaranteed that placing [3] at the beginning of a sequence will not increase the number of sequences.
For the most part, when all the placed cards are already greater than the card you are placing, then positions you pick for the card will increase the number of sequences unless the position is already the beginning of an increasing sequence. Let us try to define a state for the current problem. Let us say that we need to count the number of ways to add the t remaining cards (0, 1, 2, ... , t-1) after (n-t) cards (t, t+1, ... n-1) were already placed , such that we create k additional decreasing positions. In other words, (K - 1 - k) positions are already decreasing (A position of a number that is strictly smaller than the previous number) . The function f(k, t) will return the total number of ways to do the objective.
- As a base case, when t=0, there are no cards left to place, If k is 0 then we don't need to create any additional decreasing position, so the result is 1. If k is not 0, then we cannot create the needed decreasing positions, there are zero ways to do it.
- Otherwise, we have (n - t) cards, of them (K - 1 - k) are already decreasing positions.
- There are `(K - k - 1 + 1 = K - k)` positions that won't change the number of sequences (The beginning of the main sequence and the beginning of the additional ones). After picking one of these positions and placing card (t-1) there will be (t-1) cards left and k will not change. There are `(K - k) * f(k, t - 1)` different ways to complete the objective making this choice.
- There are `(n - t + 1 - K - k)` remaining positions in which placing card (t - 1) will increase the number of sequences: `(n - t + 1 - K - k) * f(k - 1, t - 1)`.
- The addition of those two results is the total number of ways, the result for `f(k , t)`.
- Finally, the overall result for the main problem is `f(n, K-1)`. There are n cards and we need (K-1) starting positions for new sequences.
This recurrence relation can be calculated efficiently by using memoization or iterative dynamic programming. The complexity is `O(n * K)`.
Repetitions
The real version of the problem has up to 36 repetitions of each card type. There are n card types and cardsnum[i] cards of type i.
What will complicate the problem is that, if you place two consecutive equal cards like 3,3, you create a new sequence. Since they are equal we need to be careful about counting different each setup only once.
Otherwise, the problem is similar in that you can still tell about the available positions that increase or not the number of sequences by just t and k (Where t is the number of card types whose positions were not assigned yet). Formally, let us solve `f(k, t)`, the total number of ways to place the cards of types `(0,1,...t-1)` if cards of types `(t,t+1,...,n-1)` are already placed and `(K-1-k)` of the already-placed cards are the beginning of a new increasing sequence.
- The base case is identical. when t=0, there are no cards left to place, k must be 0.
- There are `(K-k)` positions such that we can place a card of type (t-1) without changing the number of sequences. For convenience, we will call this number slotsUp.
- There are `S + 1 - (K - k)` positions in which we can place a type (t-1) card and create a new starting position for a sequence. We will call this number slotsDown.
Of the `(s = "cardsnum"[t-1])` cards of type t-1, some will be placed next to the slotsUp positions that don't change the number of sequences. Others will be placed next to the slotsDown positions that do. The remaining cards must be placed next to cards of the same type. Let us name these numbers up, down and (s - up - down), respectively. There are `O(s^2)` triples `("up","down", s-"up"-"down")`. There are `O(n * K)` different argument combinations for function `f()`. With `(n, s <= 36)` and `(K <= 1296)`, these constraints are actually small enough to allow us to simply try all possible values of `("up","down", s-"up"-"down")`. Let us do it. For fixed values of down and up:
- There are `C( "slotsUp", "up")` ways to pick the up positions. Where C is the binomial coefficient
- There are `C( "slotsDown", "down")` ways to pick the down positions.
- Let `"eq" = s - "up" - "down"`, we would like to distribute eq extra cards and place them next to other cards of type (t-1). There are initially (up + down) cards placed. The sub-problem involves assigning a certain number of additional cards to go in each of the (up + down) cards. We split the eq set in (up + down) partitions, how many ways are there to do it? I will leave it as an exercise because it is a common riddle, but the value is `C("up" + "down" + "eq" - 1, "eq")`.
- down and eq positions will become the start of a new increasing sequence. k will be reduced accordingly. t will also be reduced because we processed all the cards of type t-1.
- In short, for fixed `("up","down", "eq")`, the number of ways is:
`C( "slotsUp", "up") * C( "slotsDown", "down") * C("up" + "down" + "eq" - 1, "eq")` `* f(k - "down" - "eq", t-1) `
Wit the help of Pascal's triangle we can pre-calculate all the needed binomials in `O(n^2*s^2)` time ( slotsDown can be as large as the number of cards above t-1). There are `O(n*K)` ways to call the function, in which we do `O(s^2)` iterations. For a total complexity of `O(n*K*s^2)`. For the given constraints it will be fast enough.
Code
{html}{code}
static const int MOD = 1000000007;
long C[1298][1298];
int count(vector <int> cardsnum, int K)
{
//We would like there to be (K-1) elements i such that:
// v[i] <= v[i-1].
int n = cardsnum.size();
//total number of cards (at most 36^2) :
int S = accumulate(cardsnum.begin(), cardsnum.end() , 0);
// Precalculate binomials using Pascal's triangle:
memset(C, 0, sizeof(C));
for (int i=0; i<=S+1; i++) {
C[i][0] = 1;
for (int j=1; j<=i; j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
long dp[K][n+1]; //The size is at most ~ 36^3
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int t=1; t<=n; t++) { // O(n)
//S = total number of cards greater than t-1:
S -= cardsnum[t-1];
for (int k=0; k<=K-1; k++) { //O(n*K)
int s = cardsnum[t-1];
int slotsUp = (K - k);
int slotsDown = S + 1 - (K - k);
dp[k][t] = 0;
// Fix (up, down, eq):
for (int up = 0; (up <= s) && (up <= slotsUp); up++) { //O(n*K*s)
for (int down=0; (down + up <= s) && (down <= slotsDown); down++) {
//O(n*K*s*s) : 36^5
int eq = s - up - down;
// ways to pick up , down:
long a = C[slotsUp][up];
long b = C[slotsDown][down];
long res = (a * b) % MOD;
// The lower cards, continue the recurrence:
if (nk >= 0) {
res = (res * dp[k - down - eq][t-1]) % MOD;
} else {
res = 0;
}
if (eq > 0) {
//repeated cards
res = (res * C[eq + up + down - 1][eq] ) % MOD;
}
dp[k][t] += res;
}
}
dp[k][t] %= MOD;
}
}
return dp[K-1][n];
}
No comments :
Post a Comment