Page Contents
Year of the Cow USACO Solution
Farmer John’s cows are excited to learn that Chinese New Year was recently celebrated, ushering in the year of the Ox, always a bovine favorite.
See Also : USACO 2021 Challenges
As we know, the zodiac animals for Chinese calendar years follow a 12-year cycle: Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat, and then Ox again. Slightly lesser known is the fact that a mysterious time portal opens up during every year of the Ox, allowing cows to travel through time to any other year of the Ox in the past or future.
Bessie the cow would like to take advantage of the time portal that has opened up this year to visit NN of her famous bovine ancestors who lived long ago in history, with 1≤N≤0x100001≤N≤0x10000 (it seems fitting, being the year of the Ox, to write the bound on NN in hexadecimal; note that 0x10000 is the same as 65536).
Unfortunately, time travel makes Bessie a bit queasy, and she would prefer to make at most KK jumps through time (1≤K≤N1≤K≤N). Please help Bessie determine the minimum number of years it will take her to visit all her ancestors and return to the present year, with at most KK total jumps through time along the way.
Bessie does not need to use the time portal in a given Ox year if she does not want to. Time portals connect the first days of each Ox year with each-other, so for example if Bessie travels to a time portal and then waits 12 years for the next time portal, she spends exactly 12 years in the process. Bessie starts her adventure on the first day of the present Ox year, so she can travel back in time right away. None of Bessie’s ancestors live in Ox years.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line of input contains NN and KK. The next NN lines contain NN distinct integers in the range 1…1091…109, indicating how many years ago each of Bessie’s NN ancestors lived.
OUTPUT FORMAT (print output to the terminal / stdout):
Print the minimum number of years it will take Bessie to visit all her ancestors and return to the present year.
SAMPLE INPUT:
5 3 101 85 100 46 95
SAMPLE OUTPUT:
36
One way for Bessie to visit all her ancestors and return in 36 years is as follows:
- Enter the portal in the present day and travel 48 years into the past.
- Wait 12 years, then enter the portal 36 years in the past and travel 108 years into the past.
- Wait 24 years, then enter the portal 84 years in the past and travel back to the present year.
Problem credits: Brian Dean and David Yang
(Analysis by Spencer Compton)
We start by thinking about the structure of Bessie’s journey through time. Since there are only time portals on years that are multiples of 12, and none of Bessie’s relatives are born in such a year, to visit some relative Bessie must also visit the preceding year of the Ox and wait 12 years. For example, if Bessie has a relative from 15 years ago, Bessie must visit the year of the Ox 24 years ago and must wait until at least the year of the Ox 12 years ago. In other words, we can think of each year xx as belonging to a 12-year cycle ⌊x+1112⌋⌊x+1112⌋, so 00 belongs to cycle 00, [1,…,12][1,…,12] to cycle 11, [13,…,24][13,…,24] to cycle 22, and so on. Meaning, if Bessie has a relative in cycle xx then Bessie must spend all 12 years in that cycle.
We must use a jump to go back to the earliest cycle, then with the remaining K−1K−1 jumps Bessie can skip over contiguous ranges of unnecessary cycles. It is then optimal to skip over the K−1K−1 largest contiguous ranges of unused cycles. One way we can accomplish this is by identifying all the cycles Bessie has relatives in, sorting them, identifying the gaps between adjacent cycles in the sorted list, and sorting those gaps to find the K−1K−1 largest. In total, this takes O(nlog(n))O(nlog(n)) time.
Brian Dean’s code:
#include <iostream> #include <set> #include <vector> #include <algorithm> using namespace std; set<int> blocks; vector<int> gaps; int main(void) { int N, K, years_ago, answer, last = 0; cin >> N >> K; for (int i=0; i<N; i++) { cin >> years_ago; blocks.insert ((years_ago+11)/12); } answer = *blocks.rbegin(); while (!blocks.empty()) { gaps.push_back(*blocks.begin() - last - 1); last = *blocks.begin(); blocks.erase(*blocks.begin()); } sort (gaps.rbegin(), gaps.rend()); for (int i=0; i<K-1 && i<gaps.size(); i++) answer -= gaps[i]; cout << answer * 12 << "\n"; }
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