May 2024

 

CodeForces

1. Fenwick Tree
   1. Find the structure and pattern of taking the Fenwick tree to powers
   2. It involves stars and bars method and combinatorics, counting method.
   3. Also helpful to have understanding about how binary indexed tree or fenwick trees work.
2. Equal XOR Segment
   1. Related to range xor queries
   2. Can precompute the xor sums just like prefix sums algorithm.
   3. Greedy you split into either 2 or 3 segments.
3. Division + LCP (Hard Version)
   1. z-algorithm
   2. memoization binary search
4. Trails (medium)
   1. dynamic programming
   2. matrix exponentiation
5. Trails (hard)
   1. Associativity in matrix multiplication. BCBCBC = B(CBCB)C
   2. matrix multiplication is not commutative.
   3. Get into format where it is a 2 x 2 matrix
6. Exact Neighbors (hard)
   1. constructive, pattern
   2. If ai = 0, then you can place rest in zig zag
   3. They are all distinct can place (1, 2, …, n) in zig zag
   4. There is no ai ≠ 0 and they are all distinct, place zig zag, but skip at first repeat
7. Min-Fund Prison (medium)
   1. graph theory
   2. connected components
   3. Tarjan’s bridge finding algorithm for finding the bridges in undirected graph
   4. Subset sum problem algorithm, slightly modified to track if a split has happened, can be done with boolean
8. Min-Fund Prison (hard)
   1. reversible knapsack or subset sum dynamic programming algorithm
   2. Review this one
9. Tower Upgrades
   1. dynamic programming on tree
   2. preorder tree traversal
10. Feeding Elmo
    1. dynamic programming
    2. size of arithmetic sequence
11. ±1
    1. 2-SAT problem
    2. strongly connected components
    3. Tarjan’s algorithm to find strongly connected components
    4. directed implication graph
12. Engineer Artem
    1. Equivalent to just having cell be odd and all it’s neighbors even
    2. Envision a checker board
    3. Assign first block to be odd, and then determines the rest greedily from that.
13. Tensor
    1. partially ordered sets
    2. Dilworth’s theorem
    3. vertex set for a DAG ordered by reachability
    4. other applications of partially ordered sets
       1. Set of natural numbers with the relation of divisibility
       2. Set of strings ordered by substring
       3. Set of sequences ordered by subsequence
    5. The largest antichain is equal to the minimum number of chains needed to cover the entire vertex set.
    6. For this example you can prove that the largest antichain is just a set of two nodes, therefore you only have two chains.
    7. logic is important to this problem, cause you can have vertex j reach vertex i and they can be the same color or different colors, but the only thing that is actually illegal is that you cannot have vertex j and vertex i be same color and i is unreachable from j.
    8. The reason the chains work, is because a chain is a totally ordered set, so that means each element in the chain is reachable from earlier elements, or in other words they are comparable.
    9. This guarantees you will never have two elements of same color but they are in-comparable.
    10. You can develop a three stack solution to find the two chains. The reason you need three stacks is because sometimes an element can reach both colors.
    11. You are also iterating from smallest to largest integer because the larger ones reach the smaller
14. Set
    1. bitmasks and binary encoding of sets
    2. Decision tree problem
    3. Start with a state of a set S = xxxx, where every element in the set is undecided, and each can be value 0 which represents S does not contain that element or 1 meaning S contains that element. Where the index from the left to right indicates the element value.
    4. So through the tree you will decide on some elements that S contains, so you could end up in a state like S = xx10, where you have made a decision partially about what S contains.
    5. From that partial decision, you can use a pattern in the binary encodings to merge constraints and half the constraints at each step, or in other words half the number of T sets that will be used for next iteration.
    6. It uses the fact that if you disregard the last element, you will notice you have pairs of binary encodings where the prefix are equal, so you can merge those two T sets, cause you only care about the prefix in the next element you consider cause it is a bit at the next position.
15. Money Buys Happiness
    1. Variation of Knapsack problem
    2. Min Cost Knapsack Problem
    3. Slight constraint added where the cost cannot exceed some prefix sum of your current amount of money you can have up to some day.
    4. Solve in dp with O(NM), N = number of items, and M = total weight
16. Cutting Game
    1. Can be solved with techniques involving two pointers and marking what was used
    2. Treat the rows and columns independently.
17. Money Buys Less Happiness Now
    1. tricky greedy algorithm
    2. You can kind of think of it by considering the cases mentally
    3. Use a lazy segment tree with range addition queries
       1. Add elements and it computes the sums over ranges
       2. It can return the min or max for the query, I think anything
18. Ingenuity-2
    1. Just have to come up with the simulation
    2. Must be careful though in doing so.

CodeSprint LA

1. Catbus Planning

   1. Eulerian paths and circuits

   2. undirected graphs

   3. Count degree of nodes

   4. Even number of nodes with odd degrees in any undirected graph

AtCoder

1. MST Query

   1. Interesting union find algorithm
   2. Since you have only 10 weight values, you create 10 separate graphs with union find
   3. Then you perform union find for elements in those 10 graphs

2. Remove Pairs

   1. minimax algorithm
   2. recursive dynamic programming with bit manipulation

3. Clique Connect

   1. Lucked out on this one maybe, but just used a greedy algorithm with minimum spanning tree

4. MST Query

---

CodeChef

1. Graph Cost

   1. Not that challenging
   2. Some form of greedy and suffix computation

2. Milky Dark Chocolate

3. Envious Pile

4. Limit Mex

   1. max(A[l:r]) + 1 - count(distinct[l:r])
   2. You want to calculate these sums for each subarray that is the maximum element in the ranges
   3. Find the nearest element greater than A[i] to the left
   4. Find the nearest element greater than A[i] to the right
   5. Perform two monotonic stack sweeps in different directions to compute these.
   6. This will give you the number of times A[i] is the maximum value. So now you can sum that up
   7. Still need to compute the total sum of distinct elements in each subarray range.
   8. consider the value x = 5, the first time you see it in the array, you now know that it can be the distinct element for potentially N * (N + 1) / 2 subarrays so you subtract that from answer. Because you are subtracting count(distinct[l:r])
   9. If you see x again so you see at index = 3 and index = 7, then you know that it is not a distinct for the range from [4, 6], so you want to count the number of subarrays in that range, and add that to the answer.

5. Prison Escape

   1. multisource dikjstra from the outside of a grid and moving inwards
   2. calculates the minimum number of distance or in this case number of guards that must be passed to reach the outside of the grid
   3. It finds the cell that has the maximum distance to escape

6. Chef and Bit Tree

   1. You can simplify the problem if you know an identity relating addition to bitwise operation x + y = x & y + 2*(x^y)
   2. Once you do that you have a property of pigeonhole principle
   3. So you will never have to explore a path longer than 1000
   4. So it can be solved almost with brute force algorithm that finds the LCA, by using two pointers and moving the one at a lower depth in the tree upwards.
   5. As it climbs the tree to find LCA, it tracks what values have been seen with a marked array
   6. If two values seen in a path, which will happen before 1000, because only 1000 distinct elements possible. Then the answer is 0 because you are able to get the problem to a minimize of x ^ y, and yeah you can minimize if x = y cause it is 0.
   7. Else you use another important property of the following problem
   8. Given an array of elements the minimum xor of a pair will come from two adjacent integers.

7. Permutation Cycle Queries

   1. compute multiple prefix sums
   2. Avoid division with observation that you can compute prefix product and suffix products

8. Mex Path

   1. Hard one but you need to construct a graph with fewer edges to run dijkstra algorithm to find shortest path
   2. create forward edges from start node to every other node using mex for edge weight
   3. create forward edges from every other node to end node.
   4. create backward edge between adjacent elements with edge weight = 0, this correct for overshooting
   5. creates these edges from the last time a value was seen in array to the next time, you can create an edge of weight to connect just before value seen and set the edge weight to that value.
   6. Get’s it down to 4N edges and now can perform traditional Dijkstra

LeetCode

1. Special Array II
   1. good practice for offline query algorithm and line sweep
   2. Also need to use a python list and know which queries are still within the range.
2. Sum of Digit Differences of All Pairs
   1. Easy implementation, just need to understand problem.
3. Find Number of Ways to Reach the K-th Stair
   1. dynamic programming with Counter
   2. k is large, but the jumps will increase 2^x, so actually the number of states is smaller than it appears
4. Block Placement Queries
   1. Use a max segment tree with coordinate compression
   2. If you draw it out you can see what to do
   3. It does need sorted list to keep track of obstacle locations
   4. And you can query given some obstacle position, and find the maximum size of a contiguous segment
   5. There are ghost obstacles that have no been placed yet but need to be included in the segment tree so they can be added.
   6. Use binary search to find the nearest obstacle and then find distance to that obstacle and and query the max segment tree for anything to the left of that obstacle
5. Student Attendance Record II
   1. dynamic programming with simple transitions if you add A L or P to the string
   2. But you can only add them under certain conditions etc. Just need to follow the rules
6. K-th Smallest Prime Fraction
   1. binary search for fraction from 0 to 1.0 and count number of fractions less than each possible candidate.
   2. O(n^2) to calculate the number of elements fractions that are less than some target
7. Find the Minimum Cost Array Permutation
   1. dp bitmask where you are minimizing the score
   2. And you always start from 0 because you want the lexicographically smallest and it is circular
   3. And you also perform the dp algorithm with a backtracking pointer
8. Distribute Coins in Binary Tree
   1. dfs post order traversal of the tree
   2. determine the number of coins you need to travel up the tree and sometimes negative if it needs coins
   3. and the number of coins that much move on this edge is absolute value sum of the excess and shortage
9. Score After Flipping Matrix
   1. greedy algorithm, where you want to always flip all the bits along a row if it doesn’t start with a 1
   2. Then you flip if the column count has more 0s then 1s
10. Find the Maximum Node Sum of Node Values 1.

Problems

1. Another Longest Increasing Subsequence Problem
   1. 2D LIS or LIS on pairs
   2. Creative algorithm using this sorting with staircase can solve it in O(n(logn)^2) time
   3. This algorithm visualized is like a bunch of disjoint staircases that never intersect each other. And you are always trying to minimize the area under the staircases.