### 11318 - Marble Game

Posted:

**Mon Oct 22, 2007 8:36 am**The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=41&t=23672

Page **1** of **1**

Posted: **Mon Oct 22, 2007 8:36 am**

Posted: **Mon Oct 22, 2007 9:59 am**

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

Posted: **Fri Oct 26, 2007 8:39 pm**

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.

Posted: **Sat Oct 27, 2007 3:59 am**

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

But how to calculate the minimum moves in a valid position?I am thinking about it.I will appreciate anyone can give a hint

Posted: **Sun Oct 28, 2007 9:53 pm**

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).

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).

Posted: **Sun Oct 28, 2007 10:31 pm**

I don't know how you are doing this.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

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.

Posted: **Sun Oct 28, 2007 11:28 pm**

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.

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.

Posted: **Sun Oct 28, 2007 11:37 pm**

Yeah, I did almost the same thing without that I did a binary search for the pivoting index.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.

I dont know why but my NlogN solution took 1.35 secs which is slightly faster than your O(N) 1.74 secs solution.

Posted: **Sun Oct 28, 2007 11:46 pm**

Probably because I used cin and cout..sunny wrote:Yeah, I did almost the same thing without that I did a binary search for the pivoting index.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.

I dont know why but my NlogN solution took 1.35 secs which is slightly faster than your O(N) 1.74 secs solution.

My time is now 1.030s

Posted: **Sat Jan 05, 2008 3:16 am**

Hello!, can anyone give me the correct output for this input:
Thanks! Eric.

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
```

Posted: **Sat Jan 05, 2008 5:04 am**

I found my bug, the correct output seems to be:
gl!, Eric.

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
```