11141 - Sugar Cubes

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11141 - Sugar Cubes

Post by 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
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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
New poster
Posts: 31
Joined: Sat Nov 17, 2001 2:00 am
Contact:

Post by Ilham Kurnia »

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Hmm

Post by 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
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by 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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

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

Post by minskcity »

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by 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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by 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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

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

Post Reply

Return to “Volume 111 (11100-11199)”