input

Code: Select all

```
3
1 1 1
```

Code: Select all

```
3 3
```

**Moderator:** Board moderators

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

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

Last edited by sunny on Tue Jan 01, 2008 10:43 pm, edited 1 time in total.

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.

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.

Last edited by sclo on Sun Oct 28, 2007 11:44 pm, edited 1 time in total.

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.

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

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

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