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).
See Also : USACO 2021 Challenges
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[40]; 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][0][0] = 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[0][0][0]+dp[1][0][0] << "\n"; } }
Danny Mittal’s code:
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class LargestPasture { public static void main(String[] args) throws IOException { long[] pow3 = new long[39]; pow3[0] = 1; for (int e = 1; e <= 38; e++) { pow3[e] = 3L * pow3[e - 1]; } BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringBuilder out = new StringBuilder(); int n = Integer.parseInt(in.readLine()); for (int j = 1; j <= n; j++) { StringTokenizer tokenizer = new StringTokenizer(in.readLine()); long d = Long.parseLong(tokenizer.nextToken()); long x = Long.parseLong(tokenizer.nextToken()); long y = Long.parseLong(tokenizer.nextToken()); long[][][][][] dp = new long[3][2][3][2][40]; for (int a = 0; a < 2; a++) { for (int c = 0; c < 2; c++) { dp[a][0][c][0][0] = 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[1][0][1][0][39]).append('\n'); } System.out.print(out); } }
USACO 2021 February Contest
- Clockwise Fence USACO 2021 February Contest
- Just Green Enough USACO 2021 February Contest
- Year of the Cow USACO 2021 February Contest
- Comfortable Cows USACO 2021 February Contest
- Count the Cows USACO 2021 February Contest
- Modern Art 3 USACO 2021 February Contest
- Stone Game USACO 2021 February Contest
- Counting Graphs USACO 2021 February Contest
- Minimizing Edges USACO 2021 February Contest
- No Time to Dry USACO 2021 February Contest
- Maze Tac Toe USACO 2021 US
- Balanced Subsets USACO 2021 US
- Routing Schemes USACO 2021 US
- United Cows of Farmer John USACO 2021 US
Weekly Contest 247
- Maximum Product Difference Between Two Pairs
- Cyclically Rotating a Grid
- Number of Wonderful Substrings
- Count Ways to Build Rooms in an Ant Colony
Biweekly Contest 55
- Remove One Element to Make the Array Strictly Increasing
- Remove All Occurrences of a Substring
- Maximum Alternating Subsequence Sum
- Design Movie Rental System
Codechef Long Challenge Solutions
July Long Challenge 2021 Solutions
- Maximum Production
- Relativity
- XxOoRr
- Optimal Denomination
- K Path Query
- Chef vs Bharat
- Chef and Pairs
- Even Odd Partition
- Dakimakura Distribition
- Madoka and Ladder Decomposition
June Long Challenge 2021 Solutions
- Maximum Frequent Subarray Sum solution codechef
- Dual Distance solution codechef
- Optimal Xor Set solution codechef
- Minimum Subtree Cover solution codechef
- Minimum Dual Area solution codechef
- Bitwise Tuples solution codechef
- Shortest Route solution codechef
- Bella ciao solution codechef
- Summer Heat solution codechef
March Long Challenge 2021 Solutions
- An Interesting Sequence ISS SOLUTION
- Tree House THOUSES SOLUTION
- Valid Paths VPATH SOLUTION
- Modular Equation MODEQ SOLUTION
- Tic Tac Toe TCTCTOE SOLUTION
- Xor Equality XOREQUAL SOLUTION
- Golf LKDNGOLF SOLUTION
- Solubility SOLBLTY SOLUTION
April Long Challenge 2021 Solutions
- Chef and Dice SDICE Solution
- Worthy Matrix KAVGMAT Solution
- Binary String MEX MEXSTR Solution
- Boolean Game BOOLGAME Solution
- Tree Permutations TREEPERM Solution
- Destroy the EMP Chip CHAOSEMP Solution
- Chef and Pair Flips PAIRFLIP Solution
- String Power STRPOW Solution
- Brahma and Shiva SHRINES Solution
- Water Sort Puzzle (Challenge) WTRSORT Solution
- World Record BOLT Solution
- Strong Language SSCRIPT Solution
- Valid Pair SOCKS1 Solution
February Long Challenge 2021
- 1. Frog Sort Solution Codechef
- 2. Chef and Meetings Solution Codechef
- 3. Maximise Function Solution Codechef
- 4. Highest Divisor Solution Codechef
- 5. Cut the Cake Challenge Solution Codechef
- 6. Dream and the Multiverse Solution Codechef
- 7. Cell Shell Solution Codechef
- 8. Multiple Games Solution Codechef
- 9. Another Tree with Number Theory Solution Codechef
- 10. XOR Sums Solution Codechef
- 11. Prime Game Solution CodeChef
- 12. Team Name Solution Codechef
January Long Challenge 2021
- Chef and Division 3 DIVTHREE SOLUTION Code Chef
- Encoded String DECODEIT SOLUTION Code Chef
- Point Of Impact BILLRD SOLUTION Code Chef
- Fair Elections FAIRELCT SOLUTION Code Chef
- Watching CPL WIPL SOLUTION Code Chef
- Chef and Ants ANTSCHEF SOLUTION Code Chef
- Blackjack BLKJK SOLUTION Code Chef
- And-Or Game ORAND SOLUTION Code Chef
- Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef
- Expected Number of SCCs RCTEXSCC SOLUTION Code Chef
- Curious Matrix CURMAT SOLUTION Code Chef
- Cool Subsets COOLSBST SOLUTION Code Chef
- Sequence Creation ARCRT SOLUTION Code Chef
- Greedy Students GRDSTD SOLUTION Code Chef
November Challenge 2020 SOLUTION CodeChef
- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID
October Lunchtime 2020 CodeChef SOLUTIONS
- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP