## 11318 - Marble Game

Moderator: Board moderators

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:

### 11318 - Marble Game

Can someone tell me?
input

Code: Select all

``````3
1 1 1
``````
output

Code: Select all

``````3 3
``````
how?

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

### Re: 11318 - Marble Game

DP wrote:Can someone tell me?
input

Code: Select all

``````3
1 1 1
``````
output

Code: Select all

``````3 3
``````
how?
Cell 0,1,2 are all valid destinations,then the first number is 3.
for cell 0: 1 left ->0; 2 right ->0.So it needs only once,same as c1 and c2.
then we can get the second number is 1*3=3.
Btw,I haven't solved it yet. Struggling...

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I think there is no solution when the board is not symmetric with respect to the final destination. Here symmetric means the total distance going anti-clockwise is same as total distance going clockwise on the other side.

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm
I have an idea to check whether a position is valid in almost O(1),with the pre-process in O(n).
But how to calculate the minimum moves in a valid position?I am thinking about it.I will appreciate anyone can give a hint

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
I first thought the marbles from any box should move only in one direction and the marbles moving for a direction should be from contigious boxes.But the last sample input showed me that i was wrong.

Then I just guessed that, there should be at most one box from which the marbles can move in both directions. I was pretty sure that this logic should have something wrong , though I coded it and to my surprise it got AC.

What is the formal proof of this? I mean that there should be at most one box from which the marbles can move in both directions.

Is there any O(N) solution? My solution is O(NlogN).
Last edited by sunny on Tue Jan 01, 2008 10:43 pm, edited 1 time in total.

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
pineapple wrote:I have an idea to check whether a position is valid in almost O(1),with the pre-process in O(n).
But how to calculate the minimum moves in a valid position?I am thinking about it.I will appreciate anyone can give a hint
I don't know how you are doing this.
But in my solution I did a binary search for the pivoting index with some O(N) precalculations to determine both the validity and the minimum moves.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
My solution is O(N). In each step in my algorithm, I consider one of the node as destination. I partition the other nodes into 2 sides where the total distance the nodes on one of the side going clockwise and the distance the nodes on the other side going anti-clockwise is the same, or the absolute difference is minimum. Updating the 2 sides in each step can be done in constant time using cumulative sums.

As for how to calculate number of moves. Observe that in any optimal solution, the transfer of marbles between adjacent nodes must be in one direction only. Also, the direction that a particular marble travels is always the same. Thus there is a solution iff we can partition the marbles such that the left side only travels anticlockwise, the right side travels clockwise. Of course, we are allowed at most one node where they can travel in both directions. If the total distance the marble travels on left side is equal to right side, then the total distance itself is the solution. Otherwise, we need to consider the case there one of the nodes has both directions.
Last edited by sclo on Sun Oct 28, 2007 11:44 pm, edited 1 time in total.

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
sclo wrote:My solution is O(N). In each step in my algorithm, I consider one of the node as destination. I partition the other nodes into 2 sides where the total distance the nodes on one of the side going clockwise and the distance the nodes on the other side going anti-clockwise is the same, or the absolute difference is minimum. Updating the 2 sides in each step can be done in constant time using cumulative sums.
Yeah, I did almost the same thing without that I did a binary search for the pivoting index.
I dont know why but my NlogN solution took 1.35 secs which is slightly faster than your O(N) 1.74 secs solution.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
sunny wrote:
sclo wrote:My solution is O(N). In each step in my algorithm, I consider one of the node as destination. I partition the other nodes into 2 sides where the total distance the nodes on one of the side going clockwise and the distance the nodes on the other side going anti-clockwise is the same, or the absolute difference is minimum. Updating the 2 sides in each step can be done in constant time using cumulative sums.
Yeah, I did almost the same thing without that I did a binary search for the pivoting index.
I dont know why but my NlogN solution took 1.35 secs which is slightly faster than your O(N) 1.74 secs solution.
Probably because I used cin and cout..

My time is now 1.030s

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina
Hello!, can anyone give me the correct output for this input:

Code: Select all

``````12
4
10 2 3 2
4
4 5 32 100
4
0 2 0 3
4
0 2 0 4
5
77 78 100 101 99
5
10 11 12 13 23
6
0 2 0 0 4 0
6
12 13 412 43 0 1
7
0 1 0 1 0 1 2
20
100 10 20 30 40 50 60 70 80 90 100 10 20 30 40 50 60 70 80 90
30
234  42 22 22 10 2 2 2 2 2 44 44 100 12 100 16 18 10 20 30 20 30 40 50 60 60 30 20 30 10
40
4 4 2 10 30 20 10 20 30 40 40 10 20 30 40 40 10 10 20 20 30 20 20 40 10 10 8 10 0 0 0 0 0 10 10 10 0 0 0 0

``````
Thanks! Eric.

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina
I found my bug, the correct output seems to be:

Code: Select all

``````1 12
1 118
1 2
2 6
0 0
1 35
6 29
1 680
1 4
20 55220
2 8190
4 12384
``````
gl!, Eric.