OJ Board

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

What's a LIS algorithm?

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

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 =).

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.

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

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 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: A LIS algo could find the valid subsequence but leave an invalid complementary sequencewhile there is a valid solution in this case.

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?

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

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

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)

ChristopherH:

Could you briefly mention the three solutions?

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.

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.

ChristopherH:

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