notes.txt

Key points from various problems

USACO 2022 December Silver Problem 1: Barn Tree
Tags: (Graph Theory) (Tree DP) (Topological Sorting) (Bottom Up) (Top to Bottom)
- Assume subtree v works, DFS u to make subtree u work without changing v
- Only moves are to take or give to parent
- Problem is might take more than parent has, therefore need to change order of operations
- How to order operations?
- 1. Sort children based on sum of h[i] within child subtree
- 2. Topological sort technique

USACO 2022 December Silver Problem 2: Circular Barn
Tags: (Math) (Game Theory) (Prime & Composite Numbers) (Factors & Multiples) (Simplification of Problem) (Precomputation)
- Prime numbers: Sieve, O(sqrt(N)) to get factors
- How many prime numbers less than 5e6? 
- Think about when N=1
- Farmer John loses N=1 when a1 = 0 (mod 4)
- Precompute for each prime how long it take for it to become 0
- Loser of the barn wants to maximize number of turns it takes, strategy is to keep n even so that winner is forced to take p=2 each time
- Find first barn to become 0, that determines who wins

USACO 2022 December Silver Problem 3: Range Reconstruction
Tags: (Ad Hoc) (Brute Force) (Backtracking) (Simplification of Problem)
- Assume 1 .. i works then add i+1
- Only need to check a[i][i+1] to make array !
- 2 choices for each element ans[i-1] + a[i][i+1], ans[i-1] - a[i][i+1], if one doesn't work take the other


DMOPC 2022 Contest 2 P2: Line Trace
Tags: (Sorting)  (Inversion Counting)
- Answer is number of inversions
- A connector that connects line i with i+1 swaps i and i+1 in the answer

YAC 5 P2: Big Score
Tags: (Strings) (Special Operations)
- Lexographically greatest array must be Josh
- Since each of Josh's moves removed two coins from a vault and added one coin to a vault left of vault , the leftmost vault operated on by Josh must contain more coins than it had originally.
- Conversely, since each of Nils's moves removed two coins from a vault  and added one coin to a vault right of vault , the leftmost vault operated on by Nils must contain fewer coins than it had originally.
- Lexographically smallest array is Nils

AAC 7 P3: Squirrel Scramble
Tags: (Graph Theory) (Binary Search)
- Only ever use portal once, arrive at nearest portal to destination
- For node i, there will always be a k such that it is optimal to walk to each node from i to k-1 and use a portal to reach node k ... n

AAC 4 P2: Lavish Lights
Tags: (Data Structures) (Prefix Sums) (Binary Search) (Factors & Multiples) (Lowest Common Multiple)
- Array b where b[i] is the LCM of a[1] ... a[i]
- Stop when b > 1e9 !! (because t[i] <= 1e9 and cannot be a multiple of anything > 1e9)
- Binary search for last index i such that t[i] = 0 (mod b[i])
- i+1 is answer

AAC 4 P3: Snowy Slopes
Tags: (Math) (Data Structures: Map) (Combinatorics)
- x[j]-x[i]/y[j] - y[i] = k[a]/d[a] for indices i, j, a
- d[a](x[j] - x[i]) = k[a](y[j]-y[i])
- d[a]*x[j] - k[a]*y[j] = d[a]*x[i] - k[a]*y[i]
- store frequency counts of d[a]*x[i] - k[a]*y[i] for each a and i
- combinatorics to get answer 

DMOPC 2021 Contest 5 P1: Permutations & Primes
Tags: (Math) (Ad Hoc) (Simple Sums) (Parity)
- Odds on one side, evens on the other
- Pick constant a, b to be middle such that a is odd and b is even (eg. 5, 4)
- Answer will be all odd numbers <= n other than 5 ... 5 4 ... all even numbers <= n other than 4

DMOPC 2021 Contest 5 P2: Permutations & Primes
Tags: (Math) (Ad Hoc) (Sum of First N Numbers) (Prime & Composite Numbers)
- N = 1 return 1
- N = 2 return -1
- N = 3 works with answer 1 3 2
- Claim: if N-1 works N works too
- Add a number to the end will never get prime sum
- Sum of N numbers is N*(N+1)/2 which is always composite if N >= 3 because it is product of two numbers, N and (N+1)/2

DMOPC 2021 Contest 5 P3: Permutations & Primes
Tags: (Math) (Ad Hoc) (Game Theory) (Permutations) (Precomputation)
- if N <= 2 return -1
- Precompute all primes and whether permutation 1.. N is winning
- Winner will either be 1.. N, 1.. N-2 N N-1, or 1 .. N N-2 N-1 respectively
- 1...N-2 N N-1 and 1.. N N-2 N-1 same as 1 ... N-1 and 1... N-2 because since you cant go right N is basically N-1 or N-2 respectively
- Therefore we can precompute and answer in O(1)

CCC 2015 S4: Convex Hull
Tags: (Graph Theory) (2D Dijkstra) (Path Finding) (Shortest Path)
- 2D Dijkstra
- dis[u][state k] : shortest path from start to u with state k 

Mock CCC 2022 Contest 2 J5: Dominating the Olympics
Tags: (Graph Theory) (Dynamic Programming) (Longest Path in Directed Acyclic Graph) (Topological Sorting)
- Longest path in DAG
- Connect all u where outdegree[u] = 0 to an arbitrary node 0
- dp[u] = max time to reach u from a node v such that indegree[v] = 0
- answer is dp[0]

DMOPC 2017 Contest 1 P3: Hitchhiking Fun
Tags: (Graph Theory) (Dijkstra) (Path Finding) (Shortest Path)
- Dijkstra
- Break ties with minimum roads

DMOPC 2017 Contest 2 P2: Balance
Tags: (Data Structures: Stack/Deque) (Bracket Matching)
- Bracket matching with stack or deque

Codeforces Contest Goodbye 2022 Problem D: Koxia and Game
Tags: (Ad Hoc) (Graph Theory) (Game Theory) (Math) (Permutations) (Combinatorics) (Undirected Cycles) (Graph Construction) 
- Strategy for Koxia is to leave Mahiru with two same numbers to pick from
- Let p be array of lengthn where we can set p[i] to either a[i] or b[i] (will always be either a[i] or b[i] if want to leave Mahiru with no choice)
- Koxia wins if there exists a way to make p a permutation
- To check if p can be permutation, make graph with a bidirectional edge for each (a[i], b[i])
- Nodes are the numbers from 1 to N that make permutation
- When at node a[i] going to node b[i], means you choose to leave Mahiru with a[i]
- Need a cycle to make it a permutation
- Let u be last node visited, you need an already visited node v adjacent to u to sacrifice allowing Mihiru to take u
- Therefore graph must be bunch of cycles, if not then answer is NO
- For each cycle, count number of ways to make it a permutation of all nodes u in the cycle
- Case 1: Self loop (N ways)
- Case 2: Regular cycle (2 ways for each node in the cycle, go clockwise or counterclockwise)

DMOPC 2022 Contest 3 P2: New Components
Tags: (Graph Theory) (Connected Components) (Directed Cycles) (Removing Edges) (Precomputation)
- Removing x edges from a cycle creates x-1 new components ! (first break does not add to answer)
- Each node u in S needs to find a node not in S to tie to (choose node going into u)
- If node going into u is in S, then u is useless (does not add to answer)
- Precompute # of components in orignal graph

AAC 5 P3: Ski Resort
Tags: (Graph Theory) (Sorting) (Math) (Binary Search)
- Sort edges and skill levels
- Determine upper and lower bound skill level to go through each edge
- Binary search to find how many pandas between upper and lower bound

USACO 2021 December Silver P3 - Convoluted Intervals
Tags: (Ad Hoc) (Combinatorics) (Running Answer) (Constraints Optimization)
- Think about how answer changes when M-1 goes to M
- Answer substracts all b[i]+b[j] == M-1
- Answer adds all a[i]+a[j] == M

CCC 2022 S3: Good Samples
Tags: (Ad Hoc) (Lower Bound of Answer) (Upper Bound of Answer) (Construction)
- Find min and max value for K given N and M
- Every K between min and max works
- Good sample at most length M
- Answer is some array followed by same number (1 2 3 4 4 4 4)
- At index i, check which 1 .. M works
- ans[i] = ans [ max(i-M, 1LL) + min(0LL, total-K) ]
- Checker goes through each index i and adds how many new good samples index i creates

COCI 2008 Contest 6 P4: Cuskija
Tags: (Math) (Modulars) (Simplification of Problem) (Grouping)
- Simplify problem to 0, 1, 2
- Solution always group of 1 or group of 2 between 0s

AAC 4 P4: Reindeer Racing
Tags: (Ad Hoc) (Lower Bound of Answer) (Upper Bound of Answer) (Graph Theory) (Impossible Cases) (Construction) (Graph Construction)  
- Always take L turns, R doesn't matter unless its 0
- Find last position x such that k[x] = F takes baton
- Can make all cells (i, j) in answer 1 such that j <= x or i != F
- If that number < L then it is impossible
- There are other tricky cases where it is impossible as well

DMOPC 2021 Contest 6 P4: Colourful Paths
Tags: (Graph Theory) (Graph Coloring) (Path Finding) (Impossible Cases) (Greedy Solutions) (Shortest Path)
- Answer always 2 because if not impossible, then there will always be one edge from C to D not in the shortest path from A to B
- Color that one edge 2, rest 1
- Impossible if C to D are adjacent or C to D in all paths from A to B
- Find shortest path that doesn't go through A and B 
- This can be done with BFS and dis[u][i (0, 1) ][j (0, 1) ] shortest path from A to u, if i is 1 then visited C, if j is 1 then visited D)
- Or run a BFS without node C and one without node D
- Let u be the node out of {A, B} the shortest path doesn't go though; color all edges adjacent to u with 2

Codeforces Contest 838 Problem C: Binary Strings are Fun
Tags: (Binary Strings) (Running Answer) (Combinatorics)
- Let A be 0/1 and B be 0/1 such that A != B
- Suppose the binary string is A(1) ... A(k)... B
- What does the B change? There are k As and therefore N-k Bs (1 choice)
- Suppose the binary string is A(1) ... A(k) .. A(k+1)
- What does A(k+1) change? A is already median and therefore all gaps can be A or B (2^k choices)
- Now suppose there is binary string S; what changes from S[1.. i] to S[1..i+1]?
- Let s[i+1] be B
- If s[i] == B then answer of s[i] is multiplied by 2
- If s[i] == A then answer is 1 (all spare gaps now must be B)

USACO 2022 January Silver P3: Cereal 2
Tags: (Graph Theory) (Connected Components) (Tree) (Tree with Extra Edge) (Disjoint Set) (Undirected Cycles) (Permutations) (Impossible Cases) (Graph Construction) 
- Create a undirected graph with types of cereal as vertices and an edge between f[i] and s[i] for each cow i
- Graph will be a bunch of connected components
- For each connected component, if E = V-1 or E=V then all cows can be satisfied
- Otherwise E-V cows go hungry

COCI 2021 Contest 4 P2: Autobus
Tags: (Graph Theory) (3D Floyd Warshall) (Dynamic Programming) (Path Finding) (Simplification of Problem)  (Shortest Path)
- Shortest path goes through at most n-1 edges (otherwise there is a cycle and a shorter path)
- K = min(n-1, K)
- 3D Floyd Warshall dp[k][i][j] is shortest travel time from i to j using at most k routes

Codeforces Contest 843 Problem C: Interesting Sequence
Tags: (Binary Operations) (Impossible Cases) (Bitwise AND)
- Impossible if x > n
- Find rightmost bit i such that n&(1 << i) = (1 << i) and x&(1 << i) = 0 (bit i is ON in n and OFF in x)
- Need to change that bit to 0, earliest possibility is using bit i+1
- If bit i+1 is 1, then use bit i+2 (and so on)
- Since operations go sequentially, if a bit before i is ON in x then it is impossible
- Otherwise m is n but with a 1 in the i+1 bit and a 0 in the ith bit

USACO 2020 December Silver P1: Cowntagion
Tags: (Graph Theory) (Greedy) (Tree) (Top to Bottom) 
- Optimal for each farm to take 1 cow from its parent then grow enough to give 1 to each of its children

Codeforces Contest 843 Problem D: Friendly Spiders
Tags: (Graph Theory) (Prime & Composite Numbers) (Factors & Multiples) (Graph Construction) (Path Finding) (Shortest Path)
- Edge from spider to each of its prime factors
- BFS to get shortest path

Codeforces Contest 845 Problem C: Quiz Master
Tags: (Sorting) (Data Structures: Deque) (Factors & Multiples) (Running Answer)
- If team is proficient for every topic from M/2 + 1..M then it is proficient from 1..M
- Declare vector that stores {i, j} in ascending order such that a[i] is a multiple of j for j in M/2 +1..M
- Use deque to store the current team of {i, j} in ascending order and map to store number of each j in deque
- When add {i, j} to deque, increase count of j in map
- If {a, b} is the pair at the front of the deque and count b > 1 (it is proficient somewhere else, no need for this suboptimal minimum), pop front
- If deque contains proficiency for every topic from M/2 + 1..M (store a count everytime a new j is added), try it as answer

Codeforces Educational Contest 142 Problem B: Stand-up Comedian
Tags: (Math) (Grouping) (Impossible Cases)
- If a1 = 0 then answer is always 1
- Final order of type of joke told is always 1 1 1 .. 2 3 2 3 .. 2 2 2 .. 4 4 4 .. (2 and 3 can be switched)
- Always tell all type 1 jokes first and tell all type 4 jokes last
- Group of 1s has length a1
- Group of 2, 3 has length min(a2, a3)
- Group of 2 has length min(leftover a2/a3, leftover a/b)
- Leftover a2 or a3 is simply a2-min(a2, a3) and a3-min(a2, a3) respectively
- To find leftover a or b, notice the group of 2, 3 doesn't change a or b so a = b = a1
- Group of 4 has length min(a, b, a4)
- After everything, if there is still a joke not told, tell it (ans++)

Codeforces Educational Contest 142 Problem C: Min Max Sort
Tags: (Greedy) (Sorting) (Two Pointers) (Binary Search) (Simplification of Problem) (Recursion) (Impossible Cases)
- For permutation of length N, either no operations are used (array is sorted) or last {x, y} will always be {1, N}
- Therefore we can ignore elements 1, N and solve for permutation 2 .. N-1
- Recursive solution with base case when array is sorted
- Need to find first sorted subsequence of elements 1+X .. N-X
- Solution 1: Binary Search for X
- Solution 2: Use array idx[i] and add elements 1+x, N-X instead of removing them (check sorted when adding)

CCC 2021 Senior 4: Daily Commute
Tags: (Graph Theory) (Data Structures: Set) (Binary Search) (Running Answer) (Path Finding) (Precomputation) (Shortest Path)
- Always optimal to use subway before walking 
- Store set of size N with each element {x, i} such that x is the shortest distance to N if taking first i subway stations
- Answer always *set.begin()
- To find x, precompute distance from N to each station i (x = dist[N to i] + i)
- For each query, only elements {x, X} and {x, Y} in the set change
- Therefore recalculate those two elements and insert back in

CCO 2015 Day 1 Problem 2: Artksjid
Tags: (Graph Theory) (Bitmask) (Dynamic Programming) (Binary Operations) (Path Finding) (Longest Path) (Brute Force)
- Use dp[i][msk] to store longest path to node i having a visited bitmask of msk
- Go through all paths recursively in DFS(u, msk)

Back To School 2017 Problem 4: Wet Mud
Tags: (Data Structures: Monotonic Stack/Queue/Deque) (Dynamic Programming) (Running Answer)
- Minimum time to get to patch i stored in dp[i] 
- Transition: dp[i] = min(dp[j]) for 1 <= j < i
- How to optimize transition to O(1)?
- Min(dp[j]) can be found with running monotonically decreasing stack (stack.top() stores optimal j) 

A Math Contest Problem 3: LIS Reconstruction
Tags: (Construction) (Running Answer) (Impossible Cases)
- Impossible if a[i] > a[i-1] + 1 or a[i] < a[i-1] or a[1] != 1
- Adjacent elements therefore differ by at most 1
- Say from some index i to j such that a[i] == a[i+1] == .. a[j] and a[j+1] != a[j], how can we place elements A, B, C, .. such that A < B < C ..
- Claim: Answer has to be ..CBA (in decreasing order) 
- Proof 1: If there is a {i, j} such that j > i and ans[j] > ans[i], then LIS length will increase, but a[i] == a[j]
- Proof 2: If ans[i] is not C, then there is something greater than it after, which makes LIS length increase (therefore ans[i] must be C, ans[i+1] must be B, ..)
- Let ans be 1 2 3 .. N
- For every {i, j} reverse(ans[i] to ans[j])
- This works since all {i, j} will never overlap based on definition

DMPG 2016 Senior 5: Pizza Bag
Tags: (Data Structures: Monotonic Stack/Queue/Deque) (Prefix Sums) (Circular Array)
- See editorial

CPC 2021 Contest 1 Problem 4: AQT and Directed Graph
Tags: (Graph Theory) (Reverse Graph) (Vertex Finding)
- Instead of fixing X and searching for Y, do the vice versa on the reverse graph
- Run dfs(Y) in reverse order from Y = N, N-1, .. 1
- Store in ans[Y] the maximum X that Y can reach
- Find best answer from all (Y, ans[Y]) pairs

DMOPC 2018 Contest 4 Problem 4: Dr. Henri and Lab Data
Tags: (Offline Processing) (Precomputation) (Data Structures: Binary Index Tree) (Sorting) (Prefix Sums)
- Query answer equivalent to sum of subarray minus 2 * sum of all values less than K
- Sort queries by K value
- For each query, update all values less than K (this can be turned into an update query)
- Binary Index Tree to sum of values between every L and R (this returns sum of all values less than K)

USACO 2022 December Gold Problem 1: Bribing Friends
Tags: (Dynamic Programming) (0/1 Knapsack) (Greedy) (Binary Search)
- Naive way 3D Knapsack
- Sort cows by X[i]
- Observation: There is some index i such that it is optimal to use cones to pay all cows < i and use moonies to pay all cows > i
- For index i, we may use both cones and moonies
- Proof: For every j cones spent on a cow i, every cow < i should have already been paid for or skipped if C[i] is too large. If mooney was spent on a cow < i, then is it optimal to spend the j cones on that cow instead of cow i
- dp1[i][j] stores maximum answer for first i cows using j cones
- dp2[i][j] stores maximum answer for last i cows using j mooney
- Combine dp1 and dp2 for answer (remember there could be one cow who we pay with both cones and mooney, specifically index i)

USACO 2022 December Gold Problem 2: Mountains
Tags: (Data Structures: Set) (Running Answer) (Constant Optimization) (Precomputation)
- Set<int> a[i] stores all the mountains j > i such that i can see j
- How do you know if mountain i can see mountain j?
- Only if for all k such that i < k < j, slope from mountain i to k is less than slope from i to j
- Since set stores in monotonically increasing order, only necessary to check last element as k
- Precompute set<int> a[i] and starting answer
- For each update at index x, there are three cases
- For every mountain i < x, x may need to be inserted into a[i] and some j after x may need to be removed from a[i] (since update always adds height)
- For mountain x, it is necessary to recalculate a[x]
- For every mountain i > x, the set doesn't change since it only considers elements after i
- Update answer while updating each set
- Use insert, erase, lower_bound for logN with high constant factor ( O(Q*NlogN) comfortably AC )

USACO 2023 January Contest Silver Problem 3: Moo Route
Tags: (Greedy) (Grouping) (Construction) (Simulation)
- Answer guaranteed to exist
- Need least amount of direction changes
- Intuitive greedy is to go as far right as possible then as far left as possible over and over
- Let current position be pos
- A[i] stores number of times needed to cross i-0.5
- Keep going right as long as A[pos+1] > 1 (need to cross pos+1)
- Then change direction and go left
- If A[pos] > 1 (still need to cross pos), then can only go left (substract pos) to A[pos] > 3 (go to pos-1, come back to pos, return to pos-1)
- If A[pos] == 1 (only need to return to pos-1), then go left (substract pos) as long as A[pos] = 1 (if A[pos] > 1, then it becomes first case of going left)
- Everything in while loop for simple code

USACO 2022 December Contest Gold Problem 3: Strongest Friendship Group
Tags: (Graph Theory) (Connected Components) (Graph Cutting) (Data Structures: Priority Queue) (Data Structures: Disjoint Set)
- Array deg[x] stores degree of node x
- Let v be the cow in the graph with the minimum degree
- If use v, then can take all nodes in the graph v is connected to
- Otherwise, v can be cut
- Use priority queue to repeatedly take v
- DFS to find all nodes v is connected to
- Or use Disjoint Set to simulate adding edges instead of cutting edges
- O(N + NlogN)

MAC Contest 1 Problem 5: Slacking Subsequences
Tags: (Dynamic Programming) (Data Structures: Binary Index Tree) (Grouping) (Flip Array)
- Naive state: dp[i][k] is minimum cost for subsequence of length k using first i numbers and ending with a[i]
- Naive transition: dp[i][k] = min(dp[j][k-1] + abs(a[i] - a[j]) for 1 <= j < i)
- Optimize by eliminating absolute value function and grouping terms with variable j
- If a[j] <= a[i] dp[i][k] = min(dp[j][k-1] - a[j]) + a[i]
- If a[j] > a[i] dp[i][k] = min(dp[j][k-1] + a[j]) - a[i]
- Can get transition in O(log N) with prefix and suffix minimum Binary Index Tree
- Since Binary Index Tree only support prefix RMQ, need to reverse it to store suffix
- Flip array if needed

APIO 2012 Problem 1: Dispatching
Tags: (Graph Theory) (Data Structures: Priority Queue/Multiset) (Tree) (Greedy) (Heuristic Merge)  (Tree DP)
- Keep priority queue for each node u that stores the optimal set of ninjas if node u is the manager
- Assume we have priority queues for all children nodes of u
- Node u's priority queue is the combination of the priority queues of u's children and node u
- Combine priority queues with heuristic merge
- Greedily remove ninja in priority queue with the largest cost if total exceeds budget
- Answer for node u is pq.size()*lvl[u]
- Priority queue interchangeable with multiset

CCO Preparation Test 6 Problem 3: HopScotch
Tags: (Sqrt Decomposition: Data Based) (Dynamic Programming)
- Use 0 .. N-1 indexing
- Split array into sqrt(N) blocks
- At each index i, store dp[i] = minimum number of hops to leave current block and pos[i] = where i ends up after dp[i] hops
- To query, while (i < n) {ans += dp[i]; i = pos[i]; } O(sqrt(N))
- To update, rebuild current block

DMPG 2018 Senior 5: Mimi and Division
Tags: (Sqrt Decomposition: Data Based) (Factorization)
- Use 0 .. N-1 indexing
- Split array into sqrt(N) blocks
- Store array cnt[i][j] = how many multiples of j in the ith block
- To update, let i be the block of u
- For each multiple j of a[u], decrease cnt[i][j] by 1
- For each multiple j of v, increase cnt[i][j] by 1
- To query, [l, r] will always fully cover some sqrt(N) blocks and two subsections at either end
- First add cnt[i][x] for each block i completely covered in [l, r]
- Loop through block of l and r to calculate for incomplete blocks