## 11054 - Wine trading in Gergovia

Moderator: Board moderators

farzane
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

### 11054 - Wine trading in Gergovia

Any suggestion for a fast algorithm for this problem?

New poster
Posts: 5
Joined: Thu Sep 01, 2005 10:10 am
It's greedy. (i.e. O(N))
Last edited by cmad on Sun Jul 23, 2006 4:34 pm, edited 1 time in total.

rachvela
New poster
Posts: 1
Joined: Fri Jan 20, 2006 3:52 pm
I solved it with O(n) algo

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
looks like I didn't really understand it...

How could we get 9 and 9000 (in the sample output) ??? I wonder if somebody can explain it to me... thx...

JetBrain
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:

### 11054 - Wine trading in Gergovia

Hi guys..

I solved this problem & I keep getting WA althought I tried almost everything.. I wonder if anyone has got the test cases for it??? or anyone think about some case that may not work...

Thanks..

JetBrain
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:
I tried solving it, but I keep getting WA..
Any suggesstions??

ashikzinnatkhan
New poster
Posts: 8
Joined: Wed Jan 25, 2006 6:25 pm
Hi,
I am getting TLE.
Can any one help me?

ferng1021
New poster
Posts: 9
Joined: Thu Feb 23, 2006 5:09 pm
Location: Taipei, Taiwan
sample input 1

4 units of wine transport from 2 to 1
1 unit of wine transport from 4 to 1
1 unit of wine transport from 4 to 3
1 unit of wine transport from 4 to 5

4*1 + 1*3 + 1*1 + 1*1 = 9

ferng1021
New poster
Posts: 9
Joined: Thu Feb 23, 2006 5:09 pm
Location: Taipei, Taiwan
their is a linear algo. to solve this problem..

just think of how many units of wine transport form i to i+1 ...

JetBrain
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:
I am using linear algo & I keep getting WA..
this is really so strange.. I tried all test cases..

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
think about how much it costs if you want from one house to its adjacent , then you can solve it with O(n)

Hop it helps . . .
Arsalan
In being unlucky I have the record.

Victor Barinov
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

### Re: 11054

JetBrain wrote:Hi guys..

I solved this problem & I keep getting WA althought I tried almost everything.. I wonder if anyone has got the test cases for it??? or anyone think about some case that may not work...

Thanks..
Hi! I got WA at contest... Because answer can be grater than 2^31 - 1. When i've used long long, i got AC immediately!

Good luck!!!

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
JetBrain wrote:I am using linear algo & I keep getting WA..
this is really so strange.. I tried all test cases..
Try these test cases:

Code: Select all

``````10
100 200 300 400 500 -500 -400 -300 -200 -100
10
100 200 300 400 500 -100 -200 -300 -400 -500
10
100 -100 200 -200 300 -300 400 -400 500 -500
3
-10 20 -10
10
100 200 300 400 500 600 700 800 900 -4500
10
-2100 500 400 300 200 500 800 400 600 -1600
15
-1 -2 -3 -4 5 -6 7 -8 9 -10 11 -12 13 -14 15
0``````
My AC's output:

Code: Select all

``````5500
7500
1500
20
16500
9900
100``````

JetBrain
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:
Hi Martin

I tried ur sample input.. I am getting the same output as urs..
I dont know why am I getting WA !!!
my solution is O(n)..

Thanks anyway...

JetBrain
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:
what is long long ?? is that different from long ??