Editing 2015 Feb Gold Problem 1 Cow Hopscotch (Gold)

== Official Problem Statement ==

[http://www.usaco.org/index.php?page=viewproblem2&cpid=532 Cow Hopscotch (Gold)]

== Problem ==
In the game of Cow Hopscotch, several cows (which might include Bessie) are standing on a grid of squares that is R (1 ≤ R ≤ 750) rows by C (1 ≤ C ≤ 750) columns. The square at the intersection of row r and column c contains a number H_rc (1 ≤ H_rc ≤ R*C), which is different for every square.

A move consists of a jump from the current square to any square that is strictly to the right (higher column) and strictly downwards (higher row) – i.e., a move is to a square that is diagonally down-and-to-the-right. When making a move, the cow must jump to a square with a different number than the one she is currently standing on.

Given the layout of the grid and the starting and ending squares, what is the number of different ways a cow can get from the starting square to the ending square, moving only by legal moves? Please print your result modulo 10^9+7.

== Solution ==

The solution to this problem uses the concept of dynamic programming. Here is the key idea of the solution:

    Create a 2D dynamic programming array dp[][] where dp[i][j] indicates the number of different ways a cow can get to the cell (i, j). The base case is dp[0][0] = 1, as there's only one way to reach the starting cell.

    For every cell (i, j), iterate over every cell (p, q) that is to the upper-left of (i, j), i.e., where p < i and q < j. If the cell (p, q) has a different number than (i, j), then add dp[p][q] to dp[i][j].

    The final answer will be dp[R-1][C-1] (0-indexed), which is the number of ways to reach the final cell from the starting cell.

    To speed up the solution and avoid the O(n^2) scan for each cell, one might use a Fenwick tree or a segment tree to accumulate the dp values and update them.

== Code ==

=== C++ ===
<pre>
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9+7;
vector<vector<int>> grid;
vector<vector<int>> columns;
vector<BIT*> bits;

class BIT {
    public:
        vector<int> tree;
        vector<int> indices;
        
        BIT(vector<int>& set) {
            indices.resize(set.size() + 2);
            tree.resize(indices.size());
            indices[0] = -1;
            int index = 1;
            for(int out: set) {
                indices[index++] = out;
            }
            indices[indices.size() - 1] = INT_MAX;
        }
        
        void update(int index, int val) {
            int actual = lower_bound(indices.begin(), indices.end(), index) - indices.begin();
            while(actual < indices.size()) {
                tree[actual] += val;
                if(tree[actual] >= MOD) tree[actual] -= MOD;
                actual += actual & -actual;
            }
        }

        int query(int index) {
            int left = 0;
            int right = indices.size() - 1;
            while(left != right) {
                int mid = (left+right+1)/2;
                if(indices[mid] > index) {
                    right = mid-1;
                } else {
                    left = mid;
                }
            }
            int ret = 0;
            while(left > 0) {
                ret += tree[left];
                if(ret >= MOD) ret -= MOD;
                left -= left & -left;
            }
            return ret;
        }
};

void initializeGrid(int r, int c, int colors) {
    grid.resize(r, vector<int>(c));
    columns.resize(colors + 1);

    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            cin >> grid[i][j];
        }
    }
}

void processColumns(int r, int c) {
    for(int j = 0; j < c; j++) {
        for(int i = 0; i < r; i++) {
            int color = grid[i][j];
            if(!columns[color].empty() && columns[color].back() == j) continue;
            columns[color].push_back(j);
        }
    }
}

void initializeBits(int colors) {
    bits.resize(colors + 1);
    for(int i = 1; i < bits.size(); i++) {
        if(!columns[i].empty()) {
            bits[i] = new BIT(columns[i]);
        }
    }
}

void processFullBIT(int r, int c, BIT* full) {
    for(int i = 1; i < r - 1; i++) {
        for(int j = c - 2; j > 0; j--) {
            int val = full->query(j - 1) - bits[grid[i][j]]->query(j - 1);
            if(val < 0) val += MOD;
            full->update(j, val);
            bits[grid[i][j]]->update(j, val);
        }
    }
}

int calculateResult(int c, int r, BIT* full) {
    int result = full->query(c - 2) - bits[grid[r - 1][c - 1]]->query(c - 2);
    if(result < 0) result += MOD;
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int r, c, colors;
    cin >> r >> c >> colors;

    initializeGrid(r, c, colors);
    processColumns(r, c);
    initializeBits(colors);

    vector<int> gen(c);
    iota(gen.begin(), gen.end(), 0);
    BIT* full = new BIT(gen);
    full->update(0, 1);
    bits[grid[0][0]]->update(0, 1);

    processFullBIT(r, c, full);

    int result = calculateResult(c, r, full);
    cout << result << '\n';

    return 0;
}

</pre>

=== Java ===
<pre>
import java.io.*;
import java.util.*;

public class BarnJumpGold {
    static final int MOD = 1000000007;
    static int[][] grid;
    static ArrayList<Integer>[] columns;
    static BIT[] bits;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("barnjump.in"));
        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("barnjump.out")));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int colors = Integer.parseInt(st.nextToken());

        initializeGrid(br, r, c, colors);
        processColumns(r, c);
        initializeBits(colors);

        ArrayList<Integer> gen = new ArrayList<>();
        for(int i = 0; i < c; i++) {
            gen.add(i);
        }

        BIT full = new BIT(gen);
        full.update(0, 1);
        bits[grid[0][0]].update(0, 1);
        
        processFullBIT(r, c, full);
        
        int result = calculateResult(c, r, full);
        pw.println(result);
        pw.close();
    }

    private static void initializeGrid(BufferedReader br, int r, int c, int colors) throws IOException {
        grid = new int[r][c];
        columns = new ArrayList[colors+1];
        for(int i = 1; i < columns.length; i++) {
            columns[i] = new ArrayList<>();
        }
        for(int i = 0; i < r; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < c; j++) {
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    private static void processColumns(int r, int c) {
        for(int j = 0; j < c; j++) {
            for(int i = 0; i < r; i++) {
                int color = grid[i][j];
                if(!columns[color].isEmpty() && columns[color].get(columns[color].size()-1) == j) continue;
                columns[color].add(j);
            }
        }
    }

    private static void initializeBits(int colors) {
        bits = new BIT[colors+1];
        for(int i = 1; i < bits.length; i++) {
            if(columns[i].size() > 0) {
                bits[i] = new BIT(columns[i]);
            }
        }
    }

    private static void processFullBIT(int r, int c, BIT full) {
        for(int i = 1; i < r-1; i++) {
            for(int j = c-2; j > 0; j--) {
                int val = full.query(j-1) - bits[grid[i][j]].query(j-1);
                if(val < 0) val += MOD;
                full.update(j, val);
                bits[grid[i][j]].update(j, val);
            }
        }
    }

    private static int calculateResult(int c, int r, BIT full) {
        int result = full.query(c-2) - bits[grid[r-1][c-1]].query(c-2);
        if(result < 0) result += MOD;
        return result;
    }

    static class BIT {
        public int[] tree;
        public int[] indices;

        public BIT(ArrayList<Integer> set) {
            indices = new int[set.size()+2];
            tree = new int[indices.length];
            indices[0] = -1;
            int index = 1;
            for(int out: set) {
                indices[index++] = out;
            }
            indices[indices.length-1] = Integer.MAX_VALUE;
        }

        public void update(int index, int val) {
            int actual = Arrays.binarySearch(indices, index);
            while(actual < indices.length) {
                tree[actual] += val;
                if(tree[actual] >= MOD) tree[actual] -= MOD;
                actual += actual & -actual;
            }
        }

        public int query(int index) {
            int left = 0;
            int right = indices.length-1;
            while(left != right) {
                int mid = (left+right+1)/2;
                if(indices[mid] > index) {
                    right = mid-1;
                }
                else {
                    left = mid;
                }
            }
            int ret = 0;
            while(left > 0) {
                ret += tree[left];
                if(ret >= MOD) ret -= MOD;
                left -= left & -left;
            }
            return ret;
        }
    }
}

</pre>

=== Python ===
<pre>
MOD = int(1e9+7)

class BIT:
    def __init__(self, arr):
        self.indices = [-1] + arr + [float("inf")]
        self.tree = [0] * len(self.indices)

    def update(self, index, val):
        actual = self.indices.index(index)
        while actual < len(self.indices):
            self.tree[actual] += val
            if self.tree[actual] >= MOD: 
                self.tree[actual] -= MOD
            actual += actual & -actual

    def query(self, index):
        left = 0
        right = len(self.indices) - 1
        while left != right:
            mid = (left + right + 1) // 2
            if self.indices[mid] > index:
                right = mid - 1
            else:
                left = mid

        ret = 0
        while left > 0:
            ret += self.tree[left]
            if ret >= MOD: 
                ret -= MOD
            left -= left & -left

        return ret

def barnGold():
    r, c, colors = map(int, input().split())
    grid = [list(map(int, input().split())) for _ in range(r)]
    columns = [[] for _ in range(colors + 1)]
    bits = [None] * (colors + 1)

    for j in range(c):
        for i in range(r):
            color = grid[i][j]
            if columns[color] and columns[color][-1] == j: 
                continue
            columns[color].append(j)

    for i in range(1, len(bits)):
        if columns[i]: 
            bits[i] = BIT(columns[i])

    gen = list(range(c))
    full = BIT(gen)
    full.update(0, 1)
    bits[grid[0][0]].update(0, 1)

    for i in range(1, r - 1):
        for j in range(c - 2, 0, -1):
            val = full.query(j - 1) - bits[grid[i][j]].query(j - 1)
            if val < 0: 
                val += MOD
            full.update(j, val)
            bits[grid[i][j]].update(j, val)

    ret = full.query(c - 2) - bits[grid[r - 1][c - 1]].query(c - 2)
    if ret < 0: 
        ret += MOD

    print(ret)

barnGold()

</pre>

[[Category:Yearly_2014_2015]]
[[Category:Gold]]
[[Category:2D Array]]
[[Category:Dynamic Programming]]