10549  Russian Dolls
Moderator: Board moderators

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
10549  Russian Dolls
I try to olve this problem using LIS algorithm (applied once to reach a sequence of N elements, after that I should have two separated sets of dolls). Is this algorithm wrong ? Or I miss something ?
I try to read dimensions of dolls as integers and as doubles, but I got WA in both cases ...
Best regards
DM
I try to read dimensions of dolls as integers and as doubles, but I got WA in both cases ...
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
I think LIS stands for Longest Increasing Subsequence.
this approach doesn't look promising though, say we have N=100
and the longest inc. subseq. has length 150, how do you decide which 50 dolls to throw out so that they fit into the other sequence?
this is just as hard as the original problem.
Anyway, I tried the following algorithm during the contest (but didn't get it accepted).
consider the recurrence:
can( n,j )=is it possible to form a sequence of exactly j dolls such that the tallest doll is the n'th one (in a sorted list of dolls) ?
for convenience define the function fits( a,b )=does doll 'b' fit inside doll 'a'
to solve can(n,j) we have to identity the right doll to put under the n'th doll. Test all dolls i between 1 and n1, and pick the one that satisfies:
1. fits( n,i )
2. fits( i+2,i+1 ), fits( i+3,i+2 ), ... fits( n1, n2 )
3. fits( i+1, i1 )
4. can( i, j1 )
explanation:
1. obvious, doll n must fit on top of doll i.
2. since we're putting n on top of i, we must ensure that dolls [i+1,n1] form a valid sequence.
3. ensure that the sequence [i+1,n1] fits on top of the sequence [x,i1].
(we don't know what 'x' is from this point of view, but it doesn't matter)
4. obvious, we must be able to form a sequence of exactly j1 dolls with the tallest one being the i'th one.
(the base case is simple, can( n,1 )=1 for all n)
the final answer is obtained by reconstructing the solution of can( 2*n,n ).
this approach doesn't look promising though, say we have N=100
and the longest inc. subseq. has length 150, how do you decide which 50 dolls to throw out so that they fit into the other sequence?
this is just as hard as the original problem.
Anyway, I tried the following algorithm during the contest (but didn't get it accepted).
consider the recurrence:
can( n,j )=is it possible to form a sequence of exactly j dolls such that the tallest doll is the n'th one (in a sorted list of dolls) ?
for convenience define the function fits( a,b )=does doll 'b' fit inside doll 'a'
to solve can(n,j) we have to identity the right doll to put under the n'th doll. Test all dolls i between 1 and n1, and pick the one that satisfies:
1. fits( n,i )
2. fits( i+2,i+1 ), fits( i+3,i+2 ), ... fits( n1, n2 )
3. fits( i+1, i1 )
4. can( i, j1 )
explanation:
1. obvious, doll n must fit on top of doll i.
2. since we're putting n on top of i, we must ensure that dolls [i+1,n1] form a valid sequence.
3. ensure that the sequence [i+1,n1] fits on top of the sequence [x,i1].
(we don't know what 'x' is from this point of view, but it doesn't matter)
4. obvious, we must be able to form a sequence of exactly j1 dolls with the tallest one being the i'th one.
(the base case is simple, can( n,1 )=1 for all n)
the final answer is obtained by reconstructing the solution of can( 2*n,n ).
2konsept:
Your algorithm looks very good. Just a simple dinamic. You genius =).
May be you should change step 3. fits( i+1, i1 ) because
the i1 element may be inside the can( i, j1 ) /* I mean when you made can(i, j1) you may be used can(i1, j2). */.
To solve this problem I used another "baka" algorithm:
1. create two groups of numbers of elements that conflicts with each other:
a[M] and b[M], (don't know how to explain it. For example you take element 0 and increase a[0], then for that element find the elements that are conflicting with the first and add the number of them into b[0], then for every of the second el's you repeat this step adding to a[0] and so on. )
It's easy using DFS.
2. make for every i: a>b (by turning over if necessary)
3. from S subtract the sum of b and for every i: w = ab;
4. find the combination of w such that sum of it exactly S
and elemets that uses in the combination will be from first dolls, rest of them from second.
There is also special case if S==0
But I have WA too =( . I'll try your method =).
Your algorithm looks very good. Just a simple dinamic. You genius =).
May be you should change step 3. fits( i+1, i1 ) because
the i1 element may be inside the can( i, j1 ) /* I mean when you made can(i, j1) you may be used can(i1, j2). */.
To solve this problem I used another "baka" algorithm:
1. create two groups of numbers of elements that conflicts with each other:
a[M] and b[M], (don't know how to explain it. For example you take element 0 and increase a[0], then for that element find the elements that are conflicting with the first and add the number of them into b[0], then for every of the second el's you repeat this step adding to a[0] and so on. )
It's easy using DFS.
2. make for every i: a>b (by turning over if necessary)
3. from S subtract the sum of b and for every i: w = ab;
4. find the combination of w such that sum of it exactly S
and elemets that uses in the combination will be from first dolls, rest of them from second.
There is also special case if S==0
But I have WA too =( . I'll try your method =).
2konsept:
I found one problem in your algorithm (the same problem why standard dinamic doesn't work ).
For example when you choosing the element i, and have two diferent elements that you can use: i!=n1 and n1.
If you choose n1 element then the last element of another(alternative) doll list have sizes(d[j],h[j],w[j]]) for some j, at the same time if you chose i!=n1 then the last element of another(alternative) doll list have sizes(d[n1],h[n1],w[n1]]).
And how you would know which one of them should be taken if e.g. d[j]>d[n1] and h[j]<d[n1] w[j]=w[n1]. Sorry for bad explanation, I hope you understood.
I found one problem in your algorithm (the same problem why standard dinamic doesn't work ).
For example when you choosing the element i, and have two diferent elements that you can use: i!=n1 and n1.
If you choose n1 element then the last element of another(alternative) doll list have sizes(d[j],h[j],w[j]]) for some j, at the same time if you chose i!=n1 then the last element of another(alternative) doll list have sizes(d[n1],h[n1],w[n1]]).
And how you would know which one of them should be taken if e.g. d[j]>d[n1] and h[j]<d[n1] w[j]=w[n1]. Sorry for bad explanation, I hope you understood.
Lain: my original idea was indeed flawed, but i fixed it up. the new algorithm is just as fast, but uses slightly more memory.
we change the original recurrence relation, and introduce a new one.
first, let us distinguish between the 2 sequences we're trying to find by calling them primary, and secondary.
canP( n,j )=is it possible to form a sequence such that:
the primary sequence contains exactly j dolls
the tallest doll is the n'th one.
canS( n,j )=is it possible to form a sequence so that:
the primary (not secondary) sequence contains exactly j dolls
the secondary sequence ends with the n'th doll.
the relationship between canP and canS is very simple.
canP( n,j )=1 iff we can find a doll i between 1 and n such that:
fits( n+1,i1 )
fits( [i,n] )
canS( i1,jk ), where k is the number of dolls between i and n.
canS() has the same conditions except the last one is:
canP( i1,j )
So basically what this algorithm does is identity entire (continuous) subsequences instead of just 1 doll like in my first (incorrect) algorithm.
the reason why the first method was wrong, and why this one is correct is because when we select a subsequence [i,j] it's necessary to know that dolls i1 and j+1 belong to the other sequence.
anyway, i just implemented this algorithm and the judge accepted it; so we know it's correct this time
we change the original recurrence relation, and introduce a new one.
first, let us distinguish between the 2 sequences we're trying to find by calling them primary, and secondary.
canP( n,j )=is it possible to form a sequence such that:
the primary sequence contains exactly j dolls
the tallest doll is the n'th one.
canS( n,j )=is it possible to form a sequence so that:
the primary (not secondary) sequence contains exactly j dolls
the secondary sequence ends with the n'th doll.
the relationship between canP and canS is very simple.
canP( n,j )=1 iff we can find a doll i between 1 and n such that:
fits( n+1,i1 )
fits( [i,n] )
canS( i1,jk ), where k is the number of dolls between i and n.
canS() has the same conditions except the last one is:
canP( i1,j )
So basically what this algorithm does is identity entire (continuous) subsequences instead of just 1 doll like in my first (incorrect) algorithm.
the reason why the first method was wrong, and why this one is correct is because when we select a subsequence [i,j] it's necessary to know that dolls i1 and j+1 belong to the other sequence.
anyway, i just implemented this algorithm and the judge accepted it; so we know it's correct this time

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Sorry for long delay in reply ....
Yes, LIS means longest increasing sequence. I think, that it should be correct. I don't get TLE, but WA with time 0.041 s, so I have very big time margin. But maybe I miss something else.
I break this algorithm (LIS), when I reach N dolls in chain. After that I consider, that rest of dolls forms second chain (because I sort dolls earlier, I think, that I can only print second chain).
Best reagrds
DM
PS. DP solutions, which are discussed, are very intresting, but I want to know, why LIS is incorrect ...
Yes, LIS means longest increasing sequence. I think, that it should be correct. I don't get TLE, but WA with time 0.041 s, so I have very big time margin. But maybe I miss something else.
I break this algorithm (LIS), when I reach N dolls in chain. After that I consider, that rest of dolls forms second chain (because I sort dolls earlier, I think, that I can only print second chain).
Best reagrds
DM
PS. DP solutions, which are discussed, are very intresting, but I want to know, why LIS is incorrect ...
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
I think this problem could be solved with LIS (longest increasing subsequence ) in principle, but you should be very carefull:
 the length of the subsequence should be exactly half of the length of the complete sequence;
 the complementary sequence (the leftouts) should also form a valid sequence.
I can't think of a standard LISalgo that complies with these two restrictions.
Consider the input:
A LIS algo could find the valid subsequence but leave an invalid complementary sequencewhile there is a valid solution in this case.
 the length of the subsequence should be exactly half of the length of the complete sequence;
 the complementary sequence (the leftouts) should also form a valid sequence.
I can't think of a standard LISalgo that complies with these two restrictions.
Consider the input:
Code: Select all
6
100 100 2
99 99 1
98 98 1
97 97 3
95 95 3
94 94 2
0
Code: Select all
100 100 2
98 98 1
97 97 3
Code: Select all
99 99 1
95 95 3
94 94 2
I suggest that you should try to convince yourself why LIS is correct. In particular, why do you think dolls in the second set can be nested one within another?Dominik Michniewski wrote:Sorry for long delay in reply ....
Yes, LIS means longest increasing sequence. I think, that it should be correct. I don't get TLE, but WA with time 0.041 s, so I have very big time margin. But maybe I miss something else.
I break this algorithm (LIS), when I reach N dolls in chain. After that I consider, that rest of dolls forms second chain (because I sort dolls earlier, I think, that I can only print second chain).
Best reagrds
DM
PS. DP solutions, which are discussed, are very intresting, but I want to know, why LIS is incorrect ...
A lot of people post algorithms (worse still, undocumented code) and say "why doesn't this work?" Rather than asking this question, to yourself or to somebody else, ask "why should it work?" Prepare an argument, based on the problem statement, that your method really does solve the problem as stated. Then examine your code carefully to ensure that it really implements your method. When you've convinced yourself that your interpretation of the problem, your method, and your code are correct your are in a position to communicate your argument to somebody else, or to use the contest judge to verify your assumptions.
To use the contest judge, write routines that verify that the input and output meet your interpretation of the specifications. Use "assert" to cause a runtime error if they don't. If your assert fails, use a binary search to determine which one ... Sometimes the judge is wrong, but far more often you've made a mistake in your interpretation of the problem, your method, or your implementation.

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
Yes, I agree with you Gordon. I misinterpreted problem statement  I think, that when I find one chain of dolls, rest be ok too. That's my fault.
Best regards
DM
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)

 New poster
 Posts: 31
 Joined: Sun Feb 23, 2003 9:18 pm
 Location: Waterloo, Ontario, Canada
Nice algorithm, konsept!
Another excellent problem with a variety of viable solutions.
So far I'm aware of three essentially different solutions (not including heuristic exponential ones  you shouldn't be able to get away with that!), with time and space complexities between O(N^2) and O(N^3) inclusive.
Too bad the problem size is too small to reliably distinguish worstcase quadratic and cubic solutions. UVA: Home of the Constant Factor (TM)
Another excellent problem with a variety of viable solutions.
So far I'm aware of three essentially different solutions (not including heuristic exponential ones  you shouldn't be able to get away with that!), with time and space complexities between O(N^2) and O(N^3) inclusive.
Too bad the problem size is too small to reliably distinguish worstcase quadratic and cubic solutions. UVA: Home of the Constant Factor (TM)

 New poster
 Posts: 31
 Joined: Sun Feb 23, 2003 9:18 pm
 Location: Waterloo, Ontario, Canada
Well, I don't want to give too much away. It's fun to figure these things out for yourself.
Your first crack at a solution to this should be the headon approach. Analyse the problem logically  create some functions or relations, and define them in terms of each other.
If you can reduce the problem to one threeplace relation, then you can solve it using N^3/N^3 dynamic programming. Solution #1. This is likely the problemsetters 'intended' solution.
konsept went a bit deeper into the structure of the problem, and came up with an alternative DP formulation above which uses only N^2 space, but is conceptually less straightforward and still N^3 time in the worst case. Solution #2.
Finally, if you throw out all your assumptions about how this problem needs to be solved, and consider solving a generalization of the problem, you may come up with an unrelated method which works in time and space O(N^2). I'm sure I'm not the only one who's solved it this way  perhaps somebody else would like to offer a hint. I'd rather let some more people find it for themselves first  forums can be too tempting. Solution #3.
For contest purposes, everything beyond solution #1 is irrelevant.
Your first crack at a solution to this should be the headon approach. Analyse the problem logically  create some functions or relations, and define them in terms of each other.
If you can reduce the problem to one threeplace relation, then you can solve it using N^3/N^3 dynamic programming. Solution #1. This is likely the problemsetters 'intended' solution.
konsept went a bit deeper into the structure of the problem, and came up with an alternative DP formulation above which uses only N^2 space, but is conceptually less straightforward and still N^3 time in the worst case. Solution #2.
Finally, if you throw out all your assumptions about how this problem needs to be solved, and consider solving a generalization of the problem, you may come up with an unrelated method which works in time and space O(N^2). I'm sure I'm not the only one who's solved it this way  perhaps somebody else would like to offer a hint. I'd rather let some more people find it for themselves first  forums can be too tempting. Solution #3.
For contest purposes, everything beyond solution #1 is irrelevant.