10658 - ReArrange

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

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

10658 - ReArrange

Post by little joey »

What a horrible problem description. The fact that the answer to input 15 is 14043 is the most descriptive part of the whole problem :evil:. UVA unworthy...
technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug »

there were some really crappy descriptions on the latest problems.....
BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Post by BiK »

So what's the idea of the solution?
rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM »

BiK wrote:So what's the idea of the solution?
Try to calculate solution for small numbers (from 1 to 10),
and you understand what to do :)))
Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

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 5-step solution?

Code: Select all

1234
123 | 4
12 | 4 | 3
1 | 4 | 3 | 2
13 | 4 | 2
13 | 24
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.
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

No, you use 4 sequences, but you should use less than 4 sequences, which is an other way of saying a maximum of 3 sequences.
Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

Dang, I can't believe I fell for that simple trick. :oops:
Silly silly.
dll
New poster
Posts: 16
Joined: Fri Oct 17, 2003 9:51 am

Post by dll »

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 => ............
Last edited by dll on Tue Jun 01, 2004 1:27 pm, edited 1 time in total.
Nothing is impossible
Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

Dang, I can't believe I fell for that simple trick.
Silly silly
I also misunderstood the problem like this during the online contest.
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 :oops:
subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am

Post by subbu »

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(n-3)+(1<<(n-2))+(1<<(n-3)).
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,n-1,,,,1"?

Thanks,
Subbu.
dll
New poster
Posts: 16
Joined: Fri Oct 17, 2003 9:51 am

Post by dll »

0
1
3
6
13
27
54
109
219
438
Nothing is impossible
subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am

Post by subbu »

Those are exactly what i get,

can you provide output for

2
64
65

mine says :
7905747460161236406
15811494920322472813

Thanks,
subbu.
subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am

Post by 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.
Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

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 :wink:
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
Md. Sajjad Hossain
New poster
Posts: 9
Joined: Sat Jan 19, 2002 2:00 am
Location: Bangladesh

Post by Md. Sajjad Hossain »

I confess that the description was not well furnished :( I will fix it ASAP and try to avoid such situations in my next available chance :)
Post Reply

Return to “Volume 106 (10600-10699)”