PRLADDU -how do I not exceed the time limit?

general
, , ,
1

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?

2

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);
            }
        }
    }
2 Likes
3

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

4

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