## 11141 - Sugar Cubes

Moderator: Board moderators

Ilham Kurnia
New poster
Posts: 31
Joined: Sat Nov 17, 2001 2:00 am
Contact:

### 11141 - Sugar Cubes

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
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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
New poster
Posts: 31
Joined: Sat Nov 17, 2001 2:00 am
Contact:
little joey wrote: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
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### Hmm

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.

Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I get

Code: Select all

``````3
9
12
42
41
181
175
766
``````

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
Thanks, got AC now . It's just ridiculous how badly I misinterpreted the problem statement .

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm