ICPC PNW 2016/Camera.java

Main article: ICPC PNW 2016

Code

import java.util.* ;
public class Cameras {
   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in) ;
      int N = sc.nextInt() ;
      int K = sc.nextInt() ;
      int R = sc.nextInt() ;
      boolean c[] = new boolean[N] ;
      for (int i=0; i<K; i++)
         c[sc.nextInt()-1] = true ;
      int mincam = 2 ;
      int r = 0 ;
      int s = 0 ;
      for (int i=0; i < c.length && i<R; i++)
         if (c[i])
            s++ ;
      int pa = 0 ;
      int pb = R ;
      while (pb <= N) {
         int ca = pb - 1 ;
         while (s < mincam) {
            while (c[ca])
               ca-- ;
            c[ca--] = true ;
            s++ ;
            r++ ;
         }
         if (pb >= N)
            break ;
         if (c[pa++])
            s-- ;
         if (c[pb++])
            s++ ;
      }
      System.out.println(r) ;
   }
}

Explanation

This problem requires a greedy approach; scan through the consecutive
sets of houses of width R, count the number of cameras already there,
and if we don't have enough, add as many as needed as far right
(towards the next sets of houses) as possible.  It is easy to see
that adding cameras as far right as possible maximizes their utility
for subsequent sets.

To keep the running count, we maintain a trailing and a forward
pointer and calculate it incrementally; a quadratic solution will
not run in time.

   int trail = 0 ;
   int lead = 0 ;
   int sum = 0 ;
   while (lead < R) // calculate number of cameras in initial set
      if (hascamera[lead++])
         sum++ ;
   int r = 0 ;
   while (true) {
      for (int k=lead-1; sum<2; k--) // add cameras for this gap
         if (!hascamera[k]) {
            hascamera[k] = true ;
            r++ ;
         }
      if (lead >= N) // done?
         break ;
      if (hascamera[trail++]) // advance pointers
         sum-- ;
      if (hascamera[lead++])
         sum++ ;
   }