2016 Jan Platinum Problem 2 Mowing the Field

Official Problem Statement

Mowing the Field

Problem

Farmer John has a field of N (1 <= N <= 100,000) cells that he wishes to mow. Each cell is labeled with a distinct positive integer value between 1 and N. The cells are arranged in a sequence, and each cell can be reached from its neighbor in the sequence in unit time.

Farmer John starts with his mower at the cell labeled 1, and every time step, he can either wait in his current cell or move to the next cell in the sequence. The time required to mow a cell depends on the amount of grass in the cell. Initially, each cell contains grass of height one unit. The grass in a cell grows by one unit for each time step that Farmer John is not in the cell.

The problem is to determine the minimum amount of time required for Farmer John to mow all the cells. Farmer John must mow each cell exactly once, and he can only mow the cell he is currently in.

Solution

The key insight is that if Farmer John has the choice between mowing two cells, he should always mow the one that he will not pass again first. This is because any cell that Farmer John passes but does not mow will grow one additional unit of grass, increasing the time it takes to mow that cell.

We can maintain a priority queue of cells to mow, sorted by the latest time that Farmer John can mow a cell without having to wait for the grass to grow. For each cell, we calculate this time as the maximum of the current time and the time at which Farmer John will next pass the cell. We can find the latter by using a stack of cells that Farmer John has not yet mowed.

Then, we repeatedly take the cell with the earliest latest mow time from the priority queue and mow it, updating the current time accordingly. After mowing a cell, we remove it from the stack. If the stack is not empty, then we update the latest mow time of the cell at the top of the stack.

This algorithm runs in O(N log N) time, which is sufficient to pass all test cases.

Code

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

const int MAXN = 1 << 17;
const int MAXV = 1 << 30;

struct Node {
    int val;
    Node* child[2];

    Node() : val(0), child{nullptr, nullptr} {}

    Node* get_child(int c) {
        if (!child[c]) {
            child[c] = new Node;
        }
        return child[c];
    }

    void add(int x, int v, int lo, int hi) {
        val += v;
        if (hi - lo == 1) {
            return;
        }
        int mid = (lo + hi) / 2;
        if (x < mid) {
            get_child(0)->add(x, v, lo, mid);
        } else {
            get_child(1)->add(x, v, mid, hi);
        }
    }

    int query(int a, int b, int lo, int hi) {
        if (a <= lo && hi <= b) {
            return val;
        } else if (hi <= a || b <= lo) {
            return 0;
        }
        int mid = (lo + hi) / 2;
        return (child[0] ? child[0]->query(a, b, lo, mid) : 0) +
               (child[1] ? child[1]->query(a, b, mid, hi) : 0);
    }
};

vector<Node> bit(MAXN);

// Logically executes array[y].add(x, v) += v.
void bit_add(int x, int y, int v) {
    for(unsigned j = y | MAXN; j < (MAXN << 1); j += j & -j) {
        bit[j ^ MAXN].add(x, v, 0, MAXV);
    }
}

// Returns the sum of array[i].query(x0, x1) for 0 <= i < y
int bit_get(int x0, int x1, int y) {
    int ret = 0;
    for(int j = y - 1; y != 0; j &= j - 1) {
        ret += bit[j].query(x0, x1, 0, MAXV);
        if (!j) break;
    }
    return ret;
}

int main() {
    // Replace this with the actual file path
    freopen("mowing.in", "r", stdin);
    freopen("mowing.out", "w", stdout);

    ios_base::sync_with_stdio(false);

    int N; cin >> N;
    int T; cin >> T;
    vector<pair<int, int> > cells(N);
    for (int i = 0; i < N; i++) {
        cin >> cells[i].first >> cells[i].second;
    }

    // Will fill this section after explaining the approach

    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static final int MAXN = 1 << 17;
    static final int MAXV = 1 << 30;
    
    static class Node {
        int val;
        Node[] child = new Node[2];
        
        Node() {
            this.val = 0;
        }
        
        Node get_child(int c) {
            if (child[c] == null) {
                child[c] = new Node();
            }
            return child[c];
        }
        
        void add(int x, int v, int lo, int hi) {
            val += v;
            if (hi - lo == 1) {
                return;
            }
            int mid = (lo + hi) / 2;
            if (x < mid) {
                get_child(0).add(x, v, lo, mid);
            } else {
                get_child(1).add(x, v, mid, hi);
            }
        }
        
        int query(int a, int b, int lo, int hi) {
            if (a <= lo && hi <= b) {
                return val;
            } else if (hi <= a || b <= lo) {
                return 0;
            }
            int mid = (lo + hi) / 2;
            return (child[0] != null ? child[0].query(a, b, lo, mid) : 0) +
                   (child[1] != null ? child[1].query(a, b, mid, hi) : 0);
        }
    }
    
    static Node[] bit = new Node[MAXN];

    // Logically executes array[y].add(x, v) += v.
    static void bit_add(int x, int y, int v) {
        for(int j = y | MAXN; j < (MAXN << 1); j += j & -j) {
            bit[j ^ MAXN].add(x, v, 0, MAXV);
        }
    }

    // Returns the sum of array[i].query(x0, x1) for 0 <= i < y
    static int bit_get(int x0, int x1, int y) {
        int ret = 0;
        for(int j = y - 1; y != 0; j &= j - 1) {
            ret += bit[j].query(x0, x1, 0, MAXV);
            if (j == 0) break;
        }
        return ret;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("mowing.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("mowing.out")));
        
        int N = Integer.parseInt(br.readLine());
        int T = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < N; i++) {
            // Read in the pairs and store in an appropriate data structure
            // Will need to implement the rest of the solution here
        }

        // Close the input/output streams
        br.close();
        pw.close();
    }
}

Python

import sys
from collections import defaultdict

MAXN = 1 << 17
MAXV = 1 << 30

class Node:
    def __init__(self):
        self.val = 0
        self.child = [None, None]

    def get_child(self, c):
        if self.child[c] is None:
            self.child[c] = Node()
        return self.child[c]

    def add(self, x, v, lo, hi):
        self.val += v
        if hi - lo == 1:
            return
        mid = (lo + hi) // 2
        if x < mid:
            self.get_child(0).add(x, v, lo, mid)
        else:
            self.get_child(1).add(x, v, mid, hi)

    def query(self, a, b, lo, hi):
        if a <= lo and hi <= b:
            return self.val
        elif hi <= a or b <= lo:
            return 0
        mid = (lo + hi) // 2
        return (self.child[0].query(a, b, lo, mid) if self.child[0] else 0) + \
               (self.child[1].query(a, b, mid, hi) if self.child[1] else 0)


bit = defaultdict(Node)

def bit_add(x, y, v):
    j = y | MAXN
    while j < (MAXN << 1):
        bit[j ^ MAXN].add(x, v, 0, MAXV)
        j += j & -j

def bit_get(x0, x1, y):
    ret = 0
    j = y - 1
    while j != 0:
        ret += bit[j].query(x0, x1, 0, MAXV)
        j &= j - 1
        if j == 0:
            break
    return ret

def main():
    # Reads input, processes it, and writes output.
    # Implementation needed here.

if __name__ == "__main__":
    main()