10658 - ReArrange

[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 . UVA unworthy...

[technobug]

there were some really crappy descriptions on the latest problems.....

[BiK]

So what's the idea of the solution?

[rotoZOOM]

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]

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]

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]

Dang, I can't believe I fell for that simple trick.
Silly silly.

[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 => ............

[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

[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]

0
1
3
6
13
27
54
109
219
438

[subbu]

Those are exactly what i get,

can you provide output for

2
64
65

mine says :
7905747460161236406
15811494920322472813

Thanks,
subbu.

[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]

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

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.

[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