11054 - Wine trading in Gergovia

farzane · Post by **farzane** » Sun Jul 23, 2006 4:28 pm

Any suggestion for a fast algorithm for this problem?

cmad · Post by **cmad** » Sun Jul 23, 2006 4:31 pm

It's greedy. (i.e. O(N))

rachvela · Post by **rachvela** » Sun Jul 23, 2006 4:33 pm

I solved it with O(n) algo

jan_holmes · Post by **jan_holmes** » Sun Jul 23, 2006 5:12 pm

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 · Post by **JetBrain** » Sun Jul 23, 2006 5:20 pm

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 · Post by **JetBrain** » Sun Jul 23, 2006 5:21 pm

I tried solving it, but I keep getting WA..
Any suggesstions??

ashikzinnatkhan · Post by **ashikzinnatkhan** » Sun Jul 23, 2006 5:32 pm

Hi,
I am getting TLE.
Can any one help me?

--Thanks in Advance.

ferng1021 · Post by **ferng1021** » Sun Jul 23, 2006 5:34 pm

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 · Post by **ferng1021** » Sun Jul 23, 2006 5:39 pm

their is a linear algo. to solve this problem..

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

JetBrain · Post by **JetBrain** » Sun Jul 23, 2006 5:49 pm

I am using linear algo & I keep getting WA..
this is really so strange.. I tried all test cases..
its getting me mad...

arsalan_mousavian · Post by **arsalan_mousavian** » Sun Jul 23, 2006 5:59 pm

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

Victor Barinov · Post by **Victor Barinov** » Sun Jul 23, 2006 6:14 pm

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 · Post by **Martin Macko** » Sun Jul 23, 2006 6:25 pm

JetBrain wrote:I am using linear algo & I keep getting WA..
this is really so strange.. I tried all test cases..
its getting me mad...

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

JetBrain · Post by **JetBrain** » Sun Jul 23, 2006 6:34 pm

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 · Post by **JetBrain** » Sun Jul 23, 2006 6:36 pm

what is long long ?? is that different from long ??

OJ Board