Hello, this my first question here…

My program seems to work for all the test cases I make up, but for some reason it always exceeds the time limit. Here’s a link to my code: http://www.codechef.com/viewsolution/5201339

I can’t figure out how else to optimize my algorithm.

(I don’t know any set way to write pseudocode, but here’s an attempt)

```
int grass=0;//initial units of grass=0
Loop through array of villages D[] {
while (D[i]>=0) {
loop again through array of villages {
pick negative village j closest to the beginning
break;
}
increase negative number by one D[j]++
decrease positive number by one D[i]--
add Math.abs(i-j) units to grass
}
}
```

How do I further reduce the time this takes to run?

This is what I did.

The Algorithm works in O(N) Time.

```
import java.util.*;
class DevuLand
{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(--t>=0)
{
long grass=0,dnv=0;
int n=sc.nextInt();
long a[]=new long[n];
for(int i=0;i<n;i++)
{
a[i]=sc.nextLong();
}
for(int i=0;i<n;i++)
{
dnv+=a[i];
if(dnv>0)
grass+=dnv;
else
grass-=dnv;
}
System.out.println(grass);
}
}
}
```

3 Likes

This is what I did. Might not be the best way but still O(n). Since it is python, I don’t think explanation is needed. But sure you can ask if you have any doubt.

```
def solve():
#print "solving"
N = int(raw_input())
D = map(int, raw_input().split())
V = []
L = []
index = 0
cost = 0
while(D):
visit = D.pop(0)
if(visit > 0):
V.append((visit, index))
else:
L.append((abs(visit), index))
index += 1
#print V, L
while(V and L):
laddus, indexL = L.pop()
villagers, indexV = V.pop()
if(laddus > villagers):
laddus -= villagers
cost += villagers*abs(indexV-indexL)
L.append((laddus, indexL))
else:
villagers -= laddus
cost += laddus*abs(indexV-indexL)
V.append((villagers, indexV))
print cost
T = int(raw_input())
while(T):
T -= 1
solve()
```

Cheers !!

I’m unable to understand the logic behind your algorithm–how does it work? And what exactly does variable dnv hold?