Analysis: The Lazy Cow by Fatih Gelgi


Let's first consider about brute-force approach: try each position x (from 0 to 1,000,000). For each position x, calculate the amount of grass K steps to the left and right. In the worst case senario, it requires 1,000,000^2 = 10^12 operations which is very slow. In this approach, we don't need to check all positions one by one to the left and right; we just need to go check the patches in K distance to the left and right. That is 1,000,000 x N = 10^11 operations in the worst case which is still very slow.

Let's think about searching K steps to the left and right from a position x. That means to the sum of grass amount in the interval [x-k,x+k]. Now consider K steps to the left and right from position x+1. It is the sum of grass in the interval [x+1-k,x+1+k]. That's not very different from the previous interval. The only difference is to substract the amount of grass in position x-k and to add the amount of grass in postition x+1+k. We can use the idea of sliding [x-k,x+k] interval by just removing the grass in the leftmost position and adding the amount in the next position after the interval. Here's how the idea works on the example given in the problem:

Position    :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
Grass amount:  0  5  2  0  0  0  0  4  0  0  0  0  0  0  0 10
-------------------------------------------------------------
 x  interval             sliding window                        sum
--- -------- ------------------------------------------------- ---
  3    [0,6]  [0  5  2  0  0  0  0]                              7
  4    [1,7]     [5  2  0  0  0  0  4]                         *11
  5    [2,8]        [2  0  0  0  0  4  0]                        6
  6    [3,9]           [0  0  0  0  4  0  0]                     4
  7   [4,10]              [0  0  0  4  0  0  0]                  4
  8   [5,11]                 [0  0  4  0  0  0  0]               4
  9   [6,12]                    [0  4  0  0  0  0  0]            4
 10   [7,13]                       [4  0  0  0  0  0  0]         4
 11   [8,14]                          [0  0  0  0  0  0  0]      0
 12   [9,15]                             [0  0  0  0  0  0 10]  10

This approach roughly requires only 1,000,000 operations since we check each position only once which quite fast compared to the approches above. A sample code is provided below:

#include <fstream>

#define MAXX 1000001

using namespace std;

int n,k,line[MAXX],best;

int main()
{
	ifstream fin("lazy.in");
	fin >> n >> k;
	for (int i=0,x,g; i<n; i++)
	{
		fin >> g >> x;
		// mark the amount of the grass on the number line
		line[x]=g;
	}
	fin.close();

	// calculate the grass amount in the interval [0,2k]
	for (int i=0; i<MAXX && i<=2*k; i++)
		best+=line[i];

	int cnt=best;
	// slide the interval on the number line
	for (int i=2*k+1; i<MAXX; i++)
	{
		// slide the interval by 1
		cnt-=line[i-2*k-1];		// remove the first grass in the interval
		cnt+=line[i];			// add the grass in the next position
		if (best<cnt) best=cnt;	// update the best grass amount
	}

	ofstream fout("lazy.out");
	fout << best << endl;
	fout.close();
}

Although it is not necessary, the sliding window method above can be optimized. Instead of sliding the interval on the number line, we can slide it on the patches. We first need to sort the patches then we will slide it on the positions of patches. Let A and B be the indexes of the first and the last patches in the interval. Slide B if distance(A,B) <= 2K. If it is greater then slide A. Continue the process until B reaches N and the distance(A,B) <= 2K. The following figure shows how it works on the example:

Patch         :  0   1   2   3
Patch position:  1   2   7  15

A B Distance   Grass amount     sum
- - -------- ------------------ ---
0 0  0 (<=6)    [5]  2   4  10    5
0 1  1 (<=6)    [5   2]  4  10    7
0 2  6 (<=6)    [5   2   4] 10  *11
0 3 14 (>6)     [5   2   4  10]  11
1 3 13 (>6)      5  [2   4  10]  11
2 3  8 (>6)      5   2  [4  10]  11
3 3  0 (<=6)     5   2   4 [10]  10

This approach requires O(N log N) time for sorting and O(N) operations for sliding which is O(N log N) in total. Below is Tomek's code:

// Author: Tomek Czajka
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

template<class T> inline int size(const T&c) { return c.size(); }

struct Patch {
  int x;
  int g;
};

inline bool operator<(const Patch &a, const Patch &b) {
  return a.x < b.x;
}

int K;
vector<Patch> patches;

void ReadInput() {
  ifstream f("lazy.in");
  int n;
  f >> n >> K;
  patches.reserve(n);
  for(int i=0;i<n;++i) {
    Patch p;
    f >> p.g >> p.x;
    patches.push_back(p);
  }
}

void Write(int res) {
  ofstream f("lazy.out");
  f << res << "\n";
}

int Solve() {
  int res = 0;
  sort(patches.begin(), patches.end());
  int p=0;
  int sum = 0;
  for(int i=0;i<size(patches);++i) {
    sum += patches[i].g;
    while(patches[i].x - patches[p].x > 2*K) {
      sum -= patches[p].g;
      ++p;
    }
    res = max(res, sum);
  }
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  ReadInput();
  int res = Solve();
  Write(res);
}