2015 Feb Gold Problem 1 Cow Hopscotch (Gold)
Jump to navigation
Jump to search
Official Problem Statement[edit]
Problem[edit]
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[edit]
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[edit]
C++[edit]
#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;
}
Java[edit]
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;
}
}
}
Python[edit]
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()