# Count the Cows USACO 2021 February Contest

Page Contents

## Count the Cows USACO Solution

As is typical, Farmer John’s cows have spread themselves out along his largest pasture, which can be regarded as a large 2D grid of square “cells” (picture a huge chessboard).

The pattern of cows across the pasture is quite fascinating. For every cell (x,y)(x,y) with x≥0x≥0 and y≥0y≥0, there exists a cow at (x,y)(x,y) if for all integers k≥0k≥0, the remainders when ⌊x3k⌋⌊x3k⌋ and ⌊y3k⌋⌊y3k⌋ are divided by three have the same parity. In other words, both of these remainders are odd (equal to 11), or both of them are even (equal to 00 or 22). For example, the cells satisfying 0≤x,y<90≤x,y<9 that contain cows are denoted by ones in the diagram below.

```        x
012345678

0 101000101
1 010000010
2 101000101
3 000101000
y 4 000010000
5 000101000
6 101000101
7 010000010
8 101000101
```

FJ is curious how many cows are present in certain regions of his pasture. He asks QQ queries, each consisting of three integers xi,yi,dixi,yi,di. For each query, FJ wants to know how many cows lie in the cells along the diagonal range from (xi,yi)(xi,yi) to (xi+di,yi+di)(xi+di,yi+di) (endpoints inclusive).

#### INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains QQ (1≤Q≤1041≤Q≤104), the number of queries.

The next QQ lines each contain three integers didi, xixi, and yiyi (0≤xi,yi,di≤10180≤xi,yi,di≤1018).

#### OUTPUT FORMAT (print output to the terminal / stdout):

QQ lines, one for each query.

#### SAMPLE INPUT:

```8
10 0 0
10 0 1
9 0 2
8 0 2
0 1 7
1 1 7
2 1 7
1000000000000000000 1000000000000000000 1000000000000000000
```

#### SAMPLE OUTPUT:

```11
0
4
3
1
2
2
1000000000000000001
```

#### SCORING:

• Test case 2 satisfies di≤100di≤100 for each query.
• Test cases 3-6 satisfy x+d=330−1x+d=330−1 and y=0y=0 for each query.
• Test cases 7-12 satisfy no additional constraints.

Problem credits: Benjamin Qi

Looking at the diagram provided in the sample case, the locations of the cows is essentially an X where each of the five squares that form the X are recursively replaced by Xes.

Subtask 2: Define f(k,dif)f(k,dif) to be the number of cows (x,y)(x,y) in the square [0,3k)×[0,3k)[0,3k)×[0,3k) such that x−y=difx−y=dif. We can do this in O(k)O(k) time by reducing to k−1k−1, as gen_fullgen_full does in the code below. Assume dif≥0dif≥0.

Case 1: dif<3k−1dif<3k−1

The diagram below displays the relevant positions for k=2,dif=2k=2,dif=2. In this case, f(k,dif)=3⋅f(k−1,dif)f(k,dif)=3⋅f(k−1,dif).

```        x
012345678

0 10*000101
1 010.00010
2 1010.0101
3 00010*000
y 4 000010.00
5 0001010.0
6 10100010*
7 010000010
8 101000101
```

Case 2: dif≥3k−1dif≥3k−1

The diagram below displays the relevant positions for k=2,dif=6k=2,dif=6. In this case, f(k,dif)=f(k−1,dif−2⋅3k−1)f(k,dif)=f(k−1,dif−2⋅3k−1).

```        x
012345678

0 101000*01
1 0100000*0
2 10100010*
3 000101000
y 4 000010000
5 000101000
6 101000101
7 010000010
8 101000101
```

Full solution: We use the same idea of reducing from 3k3k to 3k−13k−1. For the details, see recrec in the code below.

```#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<ll> po3 = [](){
vector<ll> res{1};
for (int i = 1; i < 40; ++i)
res.push_back(3*res.back());
return res;
}();

ll full;
void gen_full(int k, ll dif) {
// count # of cows (x,y) in [0,3^k) x [0,3^k)
// such that x-y=dif
dif = abs(dif);
if (k == 0) {
full[k] = (dif == 0);
return;
}
if (dif >= po3[k-1]) {
gen_full(k-1,dif-2*po3[k-1]);
full[k] = full[k-1];
} else {
gen_full(k-1,dif);
full[k] = 3*full[k-1];
}
}

ll rec(ll x, ll y, int k) {
x %= po3[k], y %= po3[k];
// count # of cows in [0,3^k) x [0,3^k)
// on the segment from (x-min(x,y),y-min(x,y)) to (x,y)
if (k == 0) return 1;
if (x < y) swap(x,y);
if (x-y >= po3[k-1]) {
if (x < 2*po3[k-1]) return 0;
if (y < po3[k-1]) return rec(x,y,k-1);
if (y >= po3[k-1]) return full[k-1];
}
if (x < po3[k-1]) return rec(x,y,k-1);
if (y < po3[k-1]) return full[k-1];
if (x < 2*po3[k-1]) return full[k-1]+rec(x,y,k-1);
if (y < 2*po3[k-1]) return 2*full[k-1];
return 2*full[k-1]+rec(x,y,k-1);
}
ll diag(ll x, ll y) {
if (x < 0 || y < 0) return 0;
gen_full(39,x-y);
return rec(x,y,39);
}

int main() {
int Q; cin >> Q;
while (Q--) {
ll d,x,y; cin >> d >> x >> y;
cout << diag(x+d,y+d)-diag(x-1,y-1) << "\n";
}
}
```

Alternatively, we can ignore the diagram and do dynamic programming on the base-3 digits directly to count the number of k∈[0,d]k∈[0,d] such that (x+k,y+k)(x+k,y+k) contains a cow. We determine the digits of kk from least significant to most significant. If we’ve determined the first ii digits so far, we should keep track of the following information:

• whether k<d%3ik<d%3i (0), k=d%3ik=d%3i (1), or k>d%3ik>d%3i (2) in cmpcmp.
• whether x%3i+k≥3ix%3i+k≥3i in xcxc
• whether y%3i+k≥3iy%3i+k≥3i in ycyc
```#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define F0R(i,a) for (int i = 0; i < a; ++i)

int main() {
vector<ll> po3{1};
for (int i = 1; i < 40; ++i)
po3.push_back(3*po3.back());
array<array<array<ll,2>,2>,3> dp, DP;
int Q; cin >> Q;
while (Q--) {
ll d,x,y; cin >> d >> x >> y;
dp = {}; dp = 1;
F0R(i,39) {
DP = {};
int dd = d/po3[i]%3, xd = x/po3[i]%3, yd = y/po3[i]%3;
F0R(cmp,3) F0R(xc,2) F0R(yc,2) F0R(j,3) {
int XD = (xd+xc+j)%3, XC = (xd+xc+j)/3;
int YD = (yd+yc+j)%3, YC = (yd+yc+j)/3;
int CMP = cmp;
if (j > dd) CMP = 2;
if (j < dd) CMP = 0;
if (XD%2 == YD%2)
DP[CMP][XC][YC] += dp[cmp][xc][yc];
}
swap(dp,DP);
}
cout << dp+dp << "\n";
}
}
```

Danny Mittal’s code:

```import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class LargestPasture {

public static void main(String[] args) throws IOException {
long[] pow3 = new long;
pow3 = 1;
for (int e = 1; e <= 38; e++) {
pow3[e] = 3L * pow3[e - 1];
}
StringBuilder out = new StringBuilder();
for (int j = 1; j <= n; j++) {
long d = Long.parseLong(tokenizer.nextToken());
long x = Long.parseLong(tokenizer.nextToken());
long y = Long.parseLong(tokenizer.nextToken());
long[][][][][] dp = new long;
for (int a = 0; a < 2; a++) {
for (int c = 0; c < 2; c++) {
dp[a][c] = 1;
}
}
for (int e = 0; e <= 38; e++) {
int lim = (int) ((d / pow3[e]) % 3L);
int xDigit = (int) ((x / pow3[e]) % 3L);
int yDigit = (int) ((y / pow3[e]) % 3L);
for (int h = 0; h < 2; h++) {
for (int digit = 0; digit < 3; digit++) {
for (int k = 0; k < 2; k++) {
int hNext = (xDigit + digit + h) / 3;
int xNewDigit = (xDigit + digit + h) % 3;
int kNext = (yDigit + digit + k) / 3;
int yNewDigit = (yDigit + digit + k) % 3;
int compare;
if (digit < lim) {
compare = 0;
} else if (digit == lim) {
compare = 1;
} else {
compare = 2;
}
if (xNewDigit % 2 == yNewDigit % 2) {
for (int a = 0; a < 2; a++) {
for (int c = 0; c < 2; c++) {
dp[a][hNext][c][kNext][e + 1] += dp[a == 1 ? compare : 0][h][c == 1 ? compare : 0][k][e];
}
}
}
}
}
}
}
out.append(dp).append('\n');
}
System.out.print(out);
}
}```