11141 - Sugar Cubes

[Ilham Kurnia]

Could anyone explain why the answer for the last case in the sample I/O is 31? I fail to construct more than one arrangements.

TIA.

[Moha]

Cube 1 cube 2 .. 5 = 5
Cube 1-2, 1-3,1-4,1-5=4
Cube 1-2-3,1-2-4,1-2-5=3
.
.
.
You can compute the rest. also please pay attention to 31=2^5-1 = C(5,1)+C(5,2)+C(5,3)+C(5,4)+C(5,5)
Ok?

[little joey]

I must have read the problem statement at least 20 times, but it never occured to me that you were allowed to leave out some cubes from the arrangement. So either I am a bit stupid or the problem statement is a bit unclear. Looking again at the pictures, with this knowledge, it appears that the former conclusion is the correct one..., but I think the statement could have been a bit more explict in this respect.

But if you are allowed to leave out some cubes, why aren't you allowed to leave them all out? That's quite unusual in combinatoric problems, and because in this problem empty arrangements are forbidden, I think this fact should have been stated in the problem description. Or were you trying to get as few solvers as possible by making the problem statement intentionally vague? Not that I'm criticising it; I'm only saying that you were very successful in that attempt.

[Ilham Kurnia]

I must have read the problem statement at least 20 times, but it never occured to me that you were allowed to leave out some cubes from the arrangement. So either I am a bit stupid or the problem statement is a bit unclear. Looking again at the pictures, with this knowledge, it appears that the former conclusion is the correct one..., but I think the statement could have been a bit more explict in this respect.

I agree. It is only mentioned once, and in a somewhat symbollic way:

Let the sugar cubes in a arrangement be s1, s2, ..., sk, where 1<=k<=N

. It would have saved a lot of times if it is written explicitly. I suppose sometimes problem setters want to test the reading skill of the contestants by doing so.

[shahriar_manzoor]

From past experience I can say that in most cases the problemsetter omits the info by mistake ofcourse I don't know what happened in this case. And even if someone else reads it he can't find it unless he seriously tries to solve the problem. That's why whenever I get chance I pay tribute to Kisman because he has done it for most of my problems. And problemsetters must find someone else to write a solution for him.

[Hadi]

I suppose sometimes problem setters want to test the reading skill of the contestants by doing so.

Aren't you ilham at topcoder.com? I think my post at http://forums.topcoder.com/?module=Thre ... =34#565805 implies that we didn't write unclear problem statements intentionally. And We weren't trying to test the solvers problem reading skills. It just happened.

[minskcity]

Could anybody who solved the problem post the answers to the following test cases?

8
1
2 5 4 2 6 2
2
5 1 4 2 3 2
3 2 6 5 1 1
3
5 5 6 3 4 4
3 3 3 2 2 2
6 1 1 1 6 4
4
2 5 2 5 4 4
4 6 3 2 3 3
6 1 6 5 2 3
3 4 3 3 5 2
5
4 4 3 4 3 6
5 4 2 6 1 4
1 4 3 4 3 3
4 3 2 1 1 3
3 1 4 6 3 2
6
1 1 3 1 2 5
5 1 1 6 4 5
3 5 6 4 6 3
4 1 5 3 2 3
3 2 4 6 5 6
5 4 4 2 4 6
7
4 6 4 2 4 5
6 4 1 6 5 6
6 3 5 4 3 6
4 6 1 1 5 6
5 4 1 6 3 2
3 4 2 6 6 5
3 3 2 3 2 5
8
3 5 1 5 6 3
4 4 6 2 4 5
5 6 6 5 6 6
1 2 3 2 6 2
4 2 3 3 4 4
1 4 3 5 2 2
6 3 3 5 5 5
1 1 4 4 6 1

[little joey]

I get

Code: Select all

3
9
12
42
41
181
175
766

[minskcity]

Thanks, got AC now . It's just ridiculous how badly I misinterpreted the problem statement .

[sclo]

I'm trying to solve the problem.
The problem is easy if we restrict s.right = s[i+1].left since the indices of the cubes must be strictly increasing.
I haven't figured out how to deal with the case s.right < s[i+1].left,
in these cases, the index of the cube at s[i+1] could be smaller than the index of the cube at s, which makes this problem harder. What's the best way to deal with that?

[minskcity]

Try to define a state that represents all arrangments at the same time - there are only 6 arrangments (did they exlude that from the problem statement??), so the state space is not too large. Then add the cubes one by one (all possible rotations) and recurse on the new arrangments state / cube id. At least that's what I did

[sclo]

Thanks, I can't believe that I missed that.

My dp doesn't work, and I'm still stuck.

Let f(a,b,k) be the number of arrangements where the leftmost face is >=a, and the righmost face is <= b, using cubes with indices >= k.

f(a,b,k) = f(a,cube[k].left-1,k+1)*f(cube[k].right,b,k+1) + f(a,b,k+1)

Somehow, it doesn't work because the cubes with indices >=k might be in both left and right of cube[k] if I count them this way. I haven't figured out a good way to reduce the count.

Now, I have a new idea to fix it, instead the simple approach above, we now define the state to be
f(a1,b1,a2,b2,a3,b3,...,am,bm,k) where ai<=bi and bi<a(i+1) and ai is the leftmost face, bi is the rightmost face and the pair ai,bi defines a partial arrangement where the right face of the cube must equal the left face of the next cube. Thus the indices of the cubes between ai and bi must be strictly increasing. The entire arrangement is consisted of a few partial arrangements, so m is at most 6.