OJ Board

Posted: **Sun Jul 23, 2006 4:28 pm**

Any suggestion for a fast algorithm for this problem?

Posted: **Sun Jul 23, 2006 4:31 pm**

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

Posted: **Sun Jul 23, 2006 4:33 pm**

I solved it with O(n) algo

Posted: **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...

Posted: **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..

Posted: **Sun Jul 23, 2006 5:21 pm**

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

Posted: **Sun Jul 23, 2006 5:32 pm**

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

--Thanks in Advance.

Posted: **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

Posted: **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 ...

Posted: **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...

Posted: **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

Posted: **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!!!

Posted: **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

Posted: **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...

Posted: **Sun Jul 23, 2006 6:36 pm**

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

OJ Board

11054 - Wine trading in Gergovia

11054 - Wine trading in Gergovia

11054 - Wine trading in Gergovia

Re: 11054