11054 - Wine trading in Gergovia

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11054 - Wine trading in Gergovia

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

Any suggestion for a fast algorithm for this problem?

cmad
New poster
Posts: 5
Joined: Thu Sep 01, 2005 10:10 am

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

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

Post by rachvela » Sun Jul 23, 2006 4:33 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:

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

looks like I didn't really understand it... :oops:

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

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

11054 - Wine trading in Gergovia

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
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:

Post by JetBrain » Sun Jul 23, 2006 5:21 pm

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

ashikzinnatkhan
New poster
Posts: 8
Joined: Wed Jan 25, 2006 6:25 pm
Location: Dhaka, Bangladesh

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

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


--Thanks in Advance.

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

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
New poster
Posts: 9
Joined: Thu Feb 23, 2006 5:09 pm
Location: Taipei, Taiwan

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
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:

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

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

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
In being unlucky I have the record.

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

Re: 11054

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

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

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

5500
7500
1500
20
16500
9900
100

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

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
New poster
Posts: 15
Joined: Sun Jul 23, 2006 4:24 pm
Location: Cairo, Egypt
Contact:

Post by JetBrain » Sun Jul 23, 2006 6:36 pm

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

Post Reply

Return to “Volume 110 (11000-11099)”