10658  ReArrange
Moderator: Board moderators

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
10658  ReArrange
What a horrible problem description. The fact that the answer to input 15 is 14043 is the most descriptive part of the whole problem . UVA unworthy...
I guess I'm missing something here, but something seems really off the wall in this problem.
I just got AC by doing the obvious generalisation of the sample input (hint: look at the sample output in binary if you don't know what I mean).
But that approach will, for instance, give the answer "6" for input "4", which I think is wrong. For instance, why isn't the following a valid 5step solution?
where "" is used to delimit sequences. (In some sense, one could even claim that the first three steps solve the problem, since they do separate odd and even marbles)
As I interpreted the problem, it basically breaks down to doing a bunch of Hanoi tower solutions on piles of size roughly n/2, and the answer should be around 2^{n/2}. But that's obviously not what was intended.
I just got AC by doing the obvious generalisation of the sample input (hint: look at the sample output in binary if you don't know what I mean).
But that approach will, for instance, give the answer "6" for input "4", which I think is wrong. For instance, why isn't the following a valid 5step solution?
Code: Select all
1234
123  4
12  4  3
1  4  3  2
13  4  2
13  24
As I interpreted the problem, it basically breaks down to doing a bunch of Hanoi tower solutions on piles of size roughly n/2, and the answer should be around 2^{n/2}. But that's obviously not what was intended.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
look at this , just some sequences of hanoi moves
1 2 3 4 5 6 7 =>
1 2
3 4 5 6 7 =>
1
2
3 4 5 6 7 =>
1
2 4 5 6 7
3 =>
1 3
2 4 5 6 7 =>
1 3
2 4 5
6 7 =>
1 3 5
2 4
6 7 => ............
1 2 3 4 5 6 7 =>
1 2
3 4 5 6 7 =>
1
2
3 4 5 6 7 =>
1
2 4 5 6 7
3 =>
1 3
2 4 5 6 7 =>
1 3
2 4 5
6 7 =>
1 3 5
2 4
6 7 => ............
Last edited by dll on Tue Jun 01, 2004 1:27 pm, edited 1 time in total.
Nothing is impossible

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
I also misunderstood the problem like this during the online contest.Dang, I can't believe I fell for that simple trick.
Silly silly
I had a method where I was not sure it would generate minimum number of steps, but since my result for n = 15 was way below 14043, I was sure I misunderstood one constraint. But I wasn't able to find this constraint during online contest
I interpret this problem as follows.
Given 3 towers and n disks, 1,2,3,,,n
separate the odd numbered disks from the even numbered disks
standard towers of hanoi rules applying.
My solution for this matches for n = 15(14043)
Can anybody give outputs for the following:
10
1
2
3
4
5
6
7
8
9
10
Also my answers for the above interpretation have a nice bit pattern.
recurrence is something like f(n) = f(n3)+(1<<(n2))+(1<<(n3)).
The pattern being
011011011011...
< n bits > as can be seen from the recurrence.
And, what is the significance of "numbering can be 1,2,3...,n or n,n1,,,,1"?
Thanks,
Subbu.
Given 3 towers and n disks, 1,2,3,,,n
separate the odd numbered disks from the even numbered disks
standard towers of hanoi rules applying.
My solution for this matches for n = 15(14043)
Can anybody give outputs for the following:
10
1
2
3
4
5
6
7
8
9
10
Also my answers for the above interpretation have a nice bit pattern.
recurrence is something like f(n) = f(n3)+(1<<(n2))+(1<<(n3)).
The pattern being
011011011011...
< n bits > as can be seen from the recurrence.
And, what is the significance of "numbering can be 1,2,3...,n or n,n1,,,,1"?
Thanks,
Subbu.
Got it now,
i missed(??!!) the case n=0(my base cases were n=1 2 and 3)
n=0 doesn't really make sense even though it is not forbidden
by the input.I was misled by the statement that the numbering
can be 1,2,3...,n interpreting that there was atleast 1 marble.
I guess the input should be challenging but not certainly by imposing such (sometimes) annoying constraints like these.
I also hope that the problem descriptions are more clear,
nothing against the setters, they are doing a nice job,but really
this problemset is probably the most cryptic set i have ever seen.
Thanks,
Subra.
i missed(??!!) the case n=0(my base cases were n=1 2 and 3)
n=0 doesn't really make sense even though it is not forbidden
by the input.I was misled by the statement that the numbering
can be 1,2,3...,n interpreting that there was atleast 1 marble.
I guess the input should be challenging but not certainly by imposing such (sometimes) annoying constraints like these.
I also hope that the problem descriptions are more clear,
nothing against the setters, they are doing a nice job,but really
this problemset is probably the most cryptic set i have ever seen.
Thanks,
Subra.
I think everyone here agrees that the problem description is just bad bad bad...
Ah well...
P.S. subbu's interpretation of this task above helps me a lot
Ah well...
P.S. subbu's interpretation of this task above helps me a lot
subbu wrote:Given 3 towers and n disks, 1,2,3,,,n
separate the odd numbered disks from the even numbered disks
standard towers of hanoi rules applying.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org

 New poster
 Posts: 9
 Joined: Sat Jan 19, 2002 2:00 am
 Location: Bangladesh