## 10549 - Russian Dolls

Moderator: Board moderators

Dominik Michniewski
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
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)

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
What's a LIS algorithm?

konsept
New poster
Posts: 22
Joined: Wed Dec 19, 2001 2:00 am
Contact:
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 n-1, and pick the one that satisfies:
1. fits( n,i )
2. fits( i+2,i+1 ), fits( i+3,i+2 ), ... fits( n-1, n-2 )
3. fits( i+1, i-1 )
4. can( i, j-1 )

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,n-1] form a valid sequence.
3. ensure that the sequence [i+1,n-1] fits on top of the sequence [x,i-1].
(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 j-1 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 re-constructing the solution of can( 2*n,n ).

Lain
New poster
Posts: 11
Joined: Sun Sep 21, 2003 5:45 pm
Location: Russia, PetrSU
Contact:
2konsept:

Your algorithm looks very good. Just a simple dinamic. You genius =).

May be you should change step 3. fits( i+1, i-1 ) because
the i-1 element may be inside the can( i, j-1 ) /* I mean when you made can(i, j-1) you may be used can(i-1, j-2). */.

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 = a-b;
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 =).

Lain
New poster
Posts: 11
Joined: Sun Sep 21, 2003 5:45 pm
Location: Russia, PetrSU
Contact:
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!=n-1 and n-1.
If you choose n-1 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!=n-1 then the last element of another(alternative) doll list have sizes(d[n-1],h[n-1],w[n-1]]).

And how you would know which one of them should be taken if e.g. d[j]>d[n-1] and h[j]<d[n-1] w[j]=w[n-1]. Sorry for bad explanation, I hope you understood.

konsept
New poster
Posts: 22
Joined: Wed Dec 19, 2001 2:00 am
Contact:
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,i-1 )
-fits( [i,n] )
-canS( i-1,j-k ), where k is the number of dolls between i and n.

canS() has the same conditions except the last one is:
-canP( i-1,j )

So basically what this algorithm does is identity entire (continuous) sub-sequences 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 i-1 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

Dominik Michniewski
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 ...
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)

little joey
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 left-outs) should also form a valid sequence.

I can't think of a standard LIS-algo 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``````
A LIS algo could find the valid subsequence

Code: Select all

``````100 100 2
98 98 1
97 97 3``````
but leave an invalid complementary sequence

Code: Select all

``````99 99 1
95 95 3
94 94 2``````
while there is a valid solution in this case.

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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 ...
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?

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 run-time 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.

Dominik Michniewski
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
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)

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
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 worst-case quadratic and cubic solutions. UVA: Home of the Constant Factor (TM)

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
ChristopherH:

Could you briefly mention the three solutions?

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
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 head-on 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 three-place 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.

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
Ok, I tried combining three of the following parameters:

length of the sequences, last doll in the sequences, first doll in the sequences, the first i dolls. However I couldn't work out a plausible three-place relation. I think I need more experience with DP. Please tell me the correct relation.

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
ChristopherH:

I really tried hard. Give me at least some hint about the three-place relation.