10549 - Russian Dolls

[titid_gede]

hi,

backtrack is sufficient to solve this problem. i solved this prob using backtrack in 0.072 sec.

[Per]

Indeed it does! I hadn't even had the energy to try it because I thought it would be too slow, but I just coded it up and it worked very well. Thanks for the hint!

Now that I think of it, it isn't that strange. But that's always easy to say afterwards.

[gvcormac]

Indeed it does! I hadn't even had the energy to try it because I thought it would be too slow, but I just coded it up and it worked very well. Thanks for the hint!

Now that I think of it, it isn't that strange. But that's always easy to say afterwards.

Fair enough. It is always legitimate to find a solution that the problem setter did not have in mind. For this problem there have been several, including faster and slower solutions.

The fact that your exponential algorithm works is due to an oversight on my part. I set the bounds too low and/or wasn't diligent enough in preparing judging data.

However, there's more to life than AC (well, not in an live contest!) so you might find it instructive to continue to try to find a polynomial time solution.

[Per]

Well, it is always more fun to find the simple solutions not intended by the problemsetter.

Though in this case, I agree that it was just luck (or oversight on your part, if you will). It wasn't hard to construct a case with ~30 dolls that my solution utterly failed to handle.

I had a good take-home lesson though: if you can't find the good solution or definitely won't have time to code it until the contest ends -- code up the naive solution, and there is a (very very slight, but non-zero) possibility that you'll get lucky. (The Grasping At Straws Strategy )

[Solaris]

Does the input of little joey has some problems or am i gettin the problem wrong

6
100 100 2
99 99 1
98 98 1
97 97 3
95 95 3
94 94 2
0

First of all n should be 3 in this case. (i guess i have understood that part)
but I am not gettin how (98 98 1) can fit into (100 100 2) ??