All Problems

Problem Summary:

Given a tree of N <= 2e5 nodes, find a centroid, meaning if it were the root, every subtree has at most floor(n/2) nodes.

Notes:

A naive thought is enumerate the tree, check the sum up above this node (so everything outside the subtree), and the sum of our subtree minus 1, and if those are both <= floor(n/2) we have a subtree. This doesn't guarantee a find though. Imagine a spoke tree and the spoke is the root. Actually we want to compare the max of any child subtree size to floor(n/2) and the up outside region too. Every tree has a centroid, logic is kind of like this: call f(node) the max size of any piece when we cull node from the graph. If f(node) <= floor(n/2) we finish. Otherwise there is 1 piece > floor(n/2), which is equivalent to 1 piece > n/2. We move our node towards that subtree piece. After moving, everything outside that subtree could not exceed n/2, because we just said that subtree was >n/2. But the size of our subtree has now shrunk as we moved towards it. Something like that.

re-read, mostly for centroid

Problem Summary:

Given N <= 2e5 numbers <= 1e9, and K <= N, find the MEX of all windows of size K

Notes:

1/ O(n log n), we fixed sliding window where we store MISSING values. We only need up to N values, not max(arr), because the MEX cannot be >= N. So we add and remove and just query sortedList[0]. 2/ O(n log^2 n) probably TLEs. We store PRESENT values in a sorted container and use binary search to find mex. Since find k-th is logN then each binary search iteration takes logN time. 3/ We use fast set on MISSING values for O(n * log_64(1e5)). We store all MISSING values in the fast set, do updates, and query next(0) which takes log_64(U) time. I think other data structures like persistent seg tree, wavelet tree, etc, maybe be able to do online variants or even with updates

just re-read

Problem Summary:

We have N <= 2e5 nodes and K <= N. Find how many paths in a tree have exactly K edges.

Notes:

1/ O(n log n) Each node returns a map of # edges -> count of how many paths with those edges We small to large merge To update the entire map at once when we return up, we increment an offset by 1 good practice with the offset trick, C++ syntaxes, etc One note: we also have to score any paths that go from a child directly to our node, which can be easy to forget, one way is to consider, when we select the heavy child, we also add a path of size 0 (representing our root node, it has nowhere to go yet), now any other light children will be able to merge with that 0, but this also feels weird to me 2/ O(n log n) centroid decomp probably intended

re-implement #1, probably learn #2 lol

Problem Summary:

We have a tree of N <= 2e5 nodes with values <= 1e9. And Q <= 2e5 queries which are either node point updates, or root->node path sum queries.

Notes:

Obviously HLD could work here but its O(n log^2 n). Instead we will use an euler tour which works on sums because they are invertible. We create a global timer=0 and DFS in some arbitrary order. When we enter a node we set tin[node] = timer++ (set to timer, then increment). When we exit a node we do tout[node] = timer, we do NOT increment. So the total array is still size N. What does this mean? Well tout[node]-tin[node] happens to be the size of the subtree. [tin[node], tout[node]) is also the half-open interval of that subtree which we could use for subtree queries but I prefer to do it by size. But what about paths? Think of it more like an event based sweep line, when we enter a node we are in its subtree, the event "starts". We add vals[node] to tin[node] because any root->node2 path, where that node2 is in the subtree of node, needs to include the sum of node. But this stops happening at tout[node]. So for every node's initial value we add it to tin[node] and subtract it from tout[node]. Now to get an arbitrary root->node path sum we think, well some nodes are going to be in the subtree of that node, we don't want those. So we stop at tin[node] because that happens before any children are visited. But what about other nodes we visited first, but they ended before we reach our current node? Like we went in and out of their subtrees. Well their sums won't contribute because they got removed via tout. So any nodes still "active" are basically our ancestors and their sums contribute. Now we can get path sums because the sum query from root->node is invertible. Every time we do a point update, we find the old value, the new value, get the new difference, apply that difference to tin[node] and -1*diff to tout[node] A root->node sum query is a st.querySum(0, tin[node]) then, it's like prefix sums of the active events basically. Also worth noting unrelated but if we want to do range adds on subtrees but only point queries, we can use a normal seg tree. To range add we do st.add(tin[node], diff) and st.add(tout[node], -diff) kind of similar. Now to point query we can do a prefix sum because it's all the "active events" kind of similar.

should implement

Problem Summary:

We have N <= 2e5 nodes and M <= 2e5 paths. For each node, count how many paths it is on.

Notes:

We could do a lazy hld seg tree where we range add by 1 and point query, mine TLEd on the last test though, prob can be optimized, it's O(n log^2 n) Or we do this euler tour trick, O(n log n) take two nodes A and B and their lca L (find via binary lifting) diffs[A]++ means the path flowing up from A to root gains by 1 diffs[B]++ diffs[L]-- we have to not double count the lca diffs[parent[L]]-- dedupe the path Now we do a postorder DFS to find the sum of diffs below us

review idea

Problem Summary:

We have N <= 1e5 nodes in a tree and edges that are weighted <= 1e9. We have Q <= 1e5 queries (node1, node2, K) and we need to know the XOR of all edges with weight <= K.

Notes:

First initialize a tree with all edges 0. Process queries in increasing K. Each K we add on new edges that have weight <= K, by setting them with a HLD. Now we do a range query for the XOR. I think we could also do some ETT thing

I guess just a reread

Problem Summary:

We have a tree of N <= 1e5 nodes which are either black or white chocolates (1s or 0s). We have Q <= 1e5 queries (node1, node2). For each query, find the simple path between those two nodes. We want to find the number of triplets of nodes (A, B, C) where all 3 nodes are on the simple path node1<>node2, and any pair from the triplet has at least one black chocolate among that path A<>B, B<>C, and A<>C. Find the # of triplets for each query.

Notes:

It's hard to find the # of triplets where every triplet pair has a black chocolate between them, so we do complement counting. We basically want to find bad triplets. A bad triplet is one where A<>B is fully white-only, or B<>C. A<>C would be implicitly bad then. We use HLD with seg trees. We want this information: -length of the seg node segment -count of black chocolate cities -length of the white-only prefix on that seg node -length of the white-only suffix -number of white-white chains, meaning # of pairs where all nodes on that path are white -number of bad triplet in that seg node To aggregate: The hard ones are new bad triplets and new white-white pairs New white white pairs are the white-white pairs in the left and the right, and also the aSuffix * bPrefix length since we pick 1 white from each New bad triplets is: -bad triplets fully in the left or the right -number of white-white pairs on one side * length of other segment, as we can pick any node -we can ALSO form a white-white pair via the aSuffix and bPrefix, and pick a third node But that third node CANNOT be in the aSuffix or bPrefix because we would have counted this before Also note we need to reverse the data for one side because this operation is not commutative

Problem Summary:

Given a tree of N <= 1e5 nodes and Q <= 1e5 queries. Support "add X to every node in this subtree" and "what is the max on this a...b path?"

Notes:

Lazy seg tree with HLD for log^2 n queries!

quickly review that HLD can support subtree and path updates if we DFS order in the "visit heavy child first" method

Problem Summary:

Given a tree of N <= 2e5 nodes, each node has a value. Support point node updates and path range max queries.

Notes:

It's heavy light decomp for O(n log^2 n). Let's go over the structure of a heavy light decomposition and its proofs: Also reference: https://www.youtube.com/watch?v=_G_LMuLWMaI First the idea, we can decompose a tree into heavy and light chains. If we want to query a path decompose it into logN chains, and each chain query takes logN time, then we get log^2 N query time. At a node, we find its largest sized child subtree (arbitrary if tie). If we travel down from our node to that child, that is a heavy edge. When we do a path query imagine the max # of chains we must cross as we go up from a node A to its LCA. If we pass at most logN light edges we also pass at most logN heavy chains (since heavy chains are only divided by light edges). Every time we cross a light edge, our current subtree size at least doubles in size, so there are logN at most. We want to store data structures for each heavy chain, or each single-node light "chain". We could store a different one for each or try to use a single array, like one big segment tree, that is basically a bunch of tiny segment trees for each chain. To do this, we need each heavy chain to be contiguous in our big array segment tree. Then to query that chain we can just query the indices of the end points of that chain inside the array. We need a few things to get started: -par[node] generally useful for parent -depth[node] can be generally useful -size[node] the subtree size, used to determine heavy children -heavy[node] the heavy child of a node, or -1 if no children -seg[segNode], a standard segment tree simultaneously handling every node at once -pos[node], a tree nodes position in our "linear" virtual array that we squish the tree into, we also feed this linear array into the segment tree to build on it so pos[top of heavy chain] <-> pos[bottom of heavy chain] is like a contiguous segment in our seg tree, or more like a contiguous range of our linear array which we feed into the seg tree and build on top of, and now if we need some index range say 3...7 in our linear array we don't even need the linear array, we just feed the seg tree those endpoints and it can find it with the tl tr recursive querying -head[node] the top of the chain for a node, either itself if light, or the top of the heavy chain if heavy Most of these are easy to set up. To get pos so that every heavy chain is contiguous, we basically keep a global timer, do a dfs order, and visit heavy children first always. To get the head we just do dfs(node, chainHead) and if recursing to a light child reset the head to that child. Now we have positions of every node so we can create a linear array. Build a seg tree using these positions. Set up a point update where it gets a node in the public interface, we convert to its position using our pos array, and we update that point. For path range maxes there are a few options: 1/ We build lift tables to find kth ancestor and lca. In a path we compute their lca. Now we do upQuery(startNode, excludedAncestor) on two separate paths up, then separately include the LCA. To do that query, we do a query from our node to the head[node], again using pos array. Even for a light node it's just a range query on a single node using the seg tree that's fine. We then move up by 1 with a parent array to get to the next chain. The moment head[currNode] is the same as head[excludedAncestor] we are on the same heavy chain (or the same node, a "light node") and we slow down. If our current node equals the excluded ancestor we are on the light node so we just return our current result. Otherwise both our current node and the excluded ancestor lie on the same heavy chain. We want the node right below the excluded ancestor. We could use kthAncestor + depths array. Or we could use a trick, pos[excludedAncestor] + 1 would be the node right below it because of how our dfs order timer works. 2/ We avoid kth ancestor, lca, and binary lifting entirely. We do a dual walk from a->lca and b->lca at the same time. WLOG we assume a's head is deeper than b's head. It is always safe to range query a<>a's head then jump to parent of a's head. Once the heads of a and b match, either they are the same node or they are on the same heavy chain and one of the two is an lca. We range query from a to b either way. How is the dual walk safe? Honestly a bit confusing, if you visualize some cases (A is on a heavy chain, B on a light node, etc etc) it kind of makes sense. Both implementations are in the CSES result and the github code, the dual walk is commented out. Note I think a link-cut tree might be logN per query

should implement a working version, at LEAST in top down python or something and pass a few tests, ideally C++ though

Problem Summary:

Given a words.txt of space separated words, output a word -> frequency mapping

Notes:

We use awk which is a terminal based scripting command, honestly best to read the code I have comments explaining how it works and its kind of cool

Problem Summary:

Given a file.txt output all valid lines that are phone numbers given 2 allowed formats

Notes:

# grep searches for lines matching a pattern, automatically reads in every line and outputs every line # -E gives extended matching # the middle part is just a regex i stole from online lol

Problem Summary:

Given a file.txt output the 10th line

Notes:

# normally tail reads last 10 # -n sets the number of lines, + prefix flips to mean start from # pipe symbol takes the output and redirects it to an input in the next command # head prints first lines of something, -n 1 makes it just the first line

Problem Summary:

We have a 2d matrix of size NxN (N <= 100) with cells <= 1e9 in it. We will paint vertical black strips (see picture) starting from the top in some columns, we can pick how far down to go for each column. Then the overall score is the sum of white cells horizontal to a black cell. Find the max score.

Notes:

A naive dp is: dp(colI, prevPaint, prevPrevPaint) and we loop on new options to paint. We need both prev and prevPrev because when we paint some amount of cells, we might paint a lot in this column and thus score cells in the column behind us, but we need to dedupe if 2 columns ago accounted for those. We normally score the column we paint, forwards (we gain score for the future column on the right). But we also need to score backwards. Like think if our current column we only paint 2 cells, and two columns from now we paint 100, that needs to score backwards. But we need to dedupe. To speed this up we track a best dp where we have scored the previous column, and a best where we havent. These are initialized to all 0s and we can even start on column 1 in our loop because we can't get any score with just the 0th column. We loop over the new painted amounts and the previous painted amount and use this state machine like updating pattern kind of. n^2 loop inside the outer n loop makes O(n^3). I think we can do top down like dp(colI, prevPainted, prevScoredBoolean) and loop on the new painted amounts, prev scored is either true or false if we scored it or not There is some O(n^2) optimization and I think even a log based one in the solutions tabs.

just review the idea of having these two different dps

Problem Summary:

A set of integers S is beautiful if for every two numbers X and Y in the set, either X divides Y or Y divides X. We are given L <= R <= 1e6. Find all beautiful sets with integers in that range. We need to output 2 numbers: -max possible size of a set with these constraints -# of sets with the same length as the max

Notes:

For the condition to hold, every number needs to build up bigger and bigger. Like if a 2 is in the set and we want to add another number to the set, we must add a multiple. Say 10. Now {2, 10} is the set. We want to add another, it must be a multiple of 10 (we don't worry about it being a multiple of 2 as it implicitly is, since 10 was). Say 40. Obviously the max length set is just doubled every time, so {L, 2L, 4L, 8L, ...}. We compute this. We could use any multiplier at any point, so {X, 5*X, 2*(5*X), ..} If we ever use a multiplier of 4 or bigger that is bad as we could replace with two 2 multipliers and increase the length. So a 3 multiplier is the most allowed. We cannot use two of those though because that would multiply by 9, which is more than using three 2x multipliers. So we optionally allow a 3x multiplier. We can binary search for the largest starting number where we allow one 3x multiplier. Same with no 3x multipliers allowed. O(n log n). I think the editorial just uses math instead of binary search, like integer division. To compute "the largest number X, when multiplied by some multiplier, is <= R". I think they just floor divide R by the multiplier or something.

Problem Summary:

We have to make two arrays A and B of length M <= 10 with numbers N <= 1000. Each A_i should be <= B_i, and A is mono-increasing and B is mono-decreasing. How many ways?

Notes:

0/ A naive dp is dp(m_i, prevA, prevB) and we loop over the next A and B to pick. This is O(m * n^4). 1/ We speed this up with prefix sum DP. The bottom up version is very trippy. We basically have pf[prevA][prevB] is the answer for those cases. We loop over the M elements. We build this prefix. Building this prefix is odd because it's like a prefix from 1...prevA and prevB...m, like the top and bottom portions of the ranges. The way to build this is inclusion exclusion. pf[a][b] = cache[a][b] + pf[a-1][b] + pf[a][b+1] - pf[a-1][b+1]. So we build this in n^2 time. Now in our dp cache we just set all of dp[prevA][prevB] to equal the pf value. Since the # of ways to make a sequence have a new A and new B value is the sum of the prefix options. Overall O(m * n^2). Also to seed the dp I did it by considering the first pair of elements already placed, felt easier as a base case than trying to come up with values when no elements have been placed 3/ We can imagine the increasing array A and the decreasing array B, where they never cross, as one long increasing array if we flip B in reverse. Now to compute the # of ways to form this increasing sequence of length 2*m is just a naive dp(m_i, prevNum) and loop over new nums. O(2 * m * n^2) 4/ The above but we prefix sum optimize. O(2 * m * n) 5/ Some combinatorics solution (editorial) with stars and bars or something but I didn't learn it

just re-read all

Problem Summary:

We have two arrays A and B with numbers <= 1e7, sizes <= 5000. We can reverse one subarray in A. We want to maximize the sum of all A_i * B_i.

Notes:

dp(l, r) is the sum of the portion of we reverse a[l...r]. We enumerate all n^2 options and get the reversed sum. We use prefix and postfix for the outside ranges.

quick re-read since reversing a subarray normally is trippy but the n^2 allowance makes it easy

Problem Summary:

We have N <- 2e5 numbers where abs(num) <= 1e9. We have to add X <= 1e9 to exactly K <= 20 positions, and subtract it from the others. What is the maximum sum subarray we can make?

Notes:

Remember we can do interval DP on stuff like this! Kind of like kadane's top down. We just do dp(i, opsLeft, state). Where state is before or inside the current subarray. There's a lot of edge cases and tricks with the state machine like implementation. there are also greedy ideas apparently

good practice to implement this tricky state machine / interval thing top down

Problem Summary:

Write a JS function that yields date values from start to end, incremented by step

Notes:

get the current and ending dates, while current <= end we yield and increment

Problem Summary:

Given two arrays of objects we need to merge the objects with a spread

Notes:

Basically store a map of id -> object, for the second array spread if it already existed

Problem Summary:

Write a function that returns an infinite method object, like this: Input: method = "abc123" Output: "abc123" Explanation: const obj = createInfiniteObject(); obj['abc123'](); // "abc123" The returned string should always match the method name.

Notes:

We use a proxy. It basically intercepts any get access and returns a function that returns the name of the property that was invoked.

Problem Summary:

Make a javascript generator of nested lists

Notes:

yield* basically recurses on the inner list, otherwise yield

Problem Summary:

We have N <= 100 numbers <= 100. We want to delete the array. We can pick a subsequence {a, b, c, ...} that is ascending and score a * b * c * .... What is the min score to delete?

Notes:

We want to delete elements separately. Except for 1 we want to delete it with others if we can. We can delete all 1s with another element if any element is on the right of the furthest 1.

Problem Summary:

An array is good of max-min = gcd of all elements. Given a permutation of length N <= 2e5, how many subarrays are good?

Notes:

Imagine an array with 3 elements: A, A+X, A+2X max-min = 2x But not every element can be divisible by 2x of course since they are off by X. Or any other value for that matter. So only arrays of size 2 need checking.

Problem Summary:

We have N <= 2e5 numbers <= 1e6. We can replace every number (optionally) with that number % some other number. We can do this once. Then we want to find the MEX of the new array. Max MEX possible?

Notes:

First understand what the replacement operation does: On number 100 we could mod it by 1, 2, 3, ... 101 Note that 100%100 is 0. 100%99 is 1. And so on down to 100%51 is 49. So we can cover all of 0...49. Anything 50 or below like 100%50 or 100%33 is guaranteed to be <= 49 so those doesn't help. So for even numbers we can reach a range 0...v//2 - 1. For odds we can reach 0...v//2. We can ALSO reach exactly V by modding 100 with anything >100. So a range might look like [0...49, 100] With these ranges we want to find the max MEX we can make. Some ideas: 1/ Sort the ranges perhaps by lowest reach range first. Greedily take the next required mex. If we can't take this, like if we are at mex=55 but the range is 0...49, we add 100 to a storage to use later and move on. We take from storage as we can. Sounds right but didn't end up working... We might not want to take from a range just because we can, maybe we want to save that higher single point. For instance if the single point is 10, like [0...5, 10] we could save that 10 for later, not use this range, build up to 9, take our 10, then maybe use a single 11 after, or more bigger ranges. It feels like there should be a way to make the greedy work but it's confusing to think about (and I think there is no way) The annoying problem is we don't know whether to save that later single bigger digit or not. 2/ Instead work backwards. See "can we make a MEX of 10"? First we need a 9. If the 9 is in a single position like [0...4, 9] we should take that 9 versus taking it from a range [0...20, 40] because it's never worse. So we binary search on the answer and do some bookkeepping I used a multiset for O(n log^2n)

re-read, idea of what values we can get after mod, work backwards, covering a range with weird types of segments

Problem Summary:

We have N <= 1000 numbers all initially 0. We have a goal array B of N numbers <= 1000. We want to turn our initial array of 1s (call it A) into B in as many indices as possible. If we turn A_i into B_i we gain C_i <= 1e6 coins. We are allowed to use K <= 1e6 operations. In an operation we can take a number in A, some integer X>0, and make A_i = A_i + floor(A_i/X) So 100 we could floor divide by 6, get 16, and then get 100->116 in one operation. Find the max coins we can score.

Notes:

First we need to understand these floor operations. A naive approach is for each number from 1 to 1000, we could enumerate all denominator options from 1 to 1000, get their floor values, and find the new reachable number. We want to reach each target number in min moves. We could use BFS or DP. We could use quotient buckets to compute the transition faster. A number has rootN unique (number/x) floor options. To generate them, start by dividing by 1. Obviously we get num/1 = num, so that's one floor division option. What is the maximum denomiator we could have used to make num though? It's also 1. Better example: 100//21 is 4. What is the largest denominator that makes 4? Well do 100//4 and we get 25. If we got something like 25.2328... then the largest is 25 still. So we "jump" over all the values from 21-25 and know 26 produces a new number (3.84!). This allows a rootN transition. Okay now we have the min cost for each A_i to reach B_i. We have N <= 1000 possible bags each with a cost and a coin gain. Naive dp is dp(i, opsLeft) but that is 1e9 since K<=1e6. But we don't need this many operations ever... At most to get to any number in 1...1000 we need 12 or 13 operations (forgot), I tested with the BFS. So really our bound for operations is N*13 as we allow that many for each. Now the knapsack becomes tenable. Bundle splitting stuff or other techniques don't seem to apply here, it's really the cap on K that is the key component

review, cap on K was essential, quotient buckets is good too

Problem Summary:

We have N <= 1e9 rows of cinema seats with 10 seats per row. 1-3, 4-7, and 8-10 form sections. We want to place 4 in a row, if they straddle a section it must be 2 and 2 on each side. We have M <= 1e4 blocked seats, how many groups can we place?

Notes:

basically groups are 2,3,4,5 4,5,6,7 6,7,8,9 and we can get at most 2. I just checked all 3 per row. Kind of a poorly worded question. Unoccupied rows just contribute 2 groups.

Problem Summary:

We need to add a JS method to arrays to do a snail traversal of an array, see picture, but basically columns left to right in alternating direction

Notes:

First make sure dimensions line up, then just do it

Problem Summary:

Write a function that takes in an object and returns an immutable version with specific rules (see question)

Notes:

this is what a proxy is, it can intercept things. get and set can get the original object and other params, we have to do some recursive stuff to handle like obj.arr.push being denied, see the code it's pretty cool

Problem Summary:

Update the JS date class to have a nextDay function which gets the day after as a formatted string

Notes:

use `this` which is the instance of the class to grab the current date, find the next one, return that

Problem Summary:

We need a JS function like settimeout but it has a backoff time duration.

Notes:

We track a nextFreeId. When we start our procedure we do one call to set timeout with the initial required delay. We grab a fresh id from the nextFreeId and then increment nextFreeId for later use. We set our returned id from the initial set timeout in a map of id -> clear ids for the clear function to access. That single set timeout calls another function which reschedules itself with a new delay and updates the map with a new clear id

Problem Summary:

We have a binary tree of N <= 3e5 nodes. Node 1 is infected. On a turn we can cut a node, trimming off that subtree. The node we cut dies but nodes in its subtree basically get saved. Then the infection spreads. Max # of nodes we can keep alive?

Notes:

We should either cut the left or right child, gaining that subtree sum (minus the node we cut) and recursing. No dp is needed.

Problem Summary:

We have an NxN (N <= 3e5) chessboard. We place rooks one at a time on (r, c) and the opponent places an opposite color rook at (c, r) if they can (they cannot if r=c). Some moves we initially placed and the opponent responded. We place rooks such that no two attack each other (color does not matter). We place until we cannot place more. How many ways can we do this?

Notes:

To visualize the opponent moves just think of them reflecting moves over the major diagonal. Also note N rooks always get exactly placed. We can never place >N rooks (pigeonhole) and if we place fewer than N rooks it implies there is always some row with no rooks, and some column with no rooks, so their intersection can have another rook. We actually don't need to think about the positions so much. But rather the # of free rows left. We consider the topmost row with a rook. Say there are 2 rows that still need pieces. We could place on the r=c line now there is 1 row left. Or we could place the rook on any other available column in that row, which is basically the # of free rows left too (off by 1, since we don't count the r=c line). When we place it there the opponent mirrors in a necessarily free spot so we reduce the # of free rows by 2. And we could have placed on either side of the reflection line. So it just ends up being DP. There is also a combinatorics version where we enumerate on the # of type 1 moves (we place on the r=c line) we can do and use some other combinatorics I didn't look into it

worth a re-read just about the fact we don't need to actually know the positions of the rooks, just the # of free rows left, and remembering that exactly N rooks can be placed on an NxN grid, and we can always add another rook if we haven't placed N yet

Problem Summary:

We have N <= 1e5 stars with coordinates (x, y) <= 100. And Q <= 1e5 queries which correspond to a subrectangle of the sky. Stars have a max brightness of C <= 10 and each one has some starting brightness. Over time they go from brightness a, a+1, a+2, ..., C, 0, 1, ... For each query find the total sum of brightness of all stars in the sky at this point in time

Notes:

2d prefix sum [x][y][initStarBrightness] tells us the # of stars with that initial brightness in that range. Basically 11 2d prefix sums. For each query we do 11 loops also, tabulating over initial brightnesses, computing the current brightness, and adding.

Problem Summary:

We are given N <= X <= 1e18. We want to form some sequence N & N+1 & N+2 & ... & M = X Find the smallest M that does this, or -1 if not possible

Notes:

Notice how the AND value can only ever go down, and at most log(N) times too. So we could binary search for the smallest M that does it. Call the AND of elements L...R rangeAnd. If the rangeAnd(n, some binary search value) is exactly X, we update answer and try a smaller range If the rangeAnd is too big, we need to AND more values, search higher If the rangeAnd is too small, we ANDed too many values, search fewer To rangeAnd L...R it's actually just the shared prefix of the two. The code is nice. The intuition is basically start at the largest bit of L and R, if they match then they always will for all numbers from L...R. Move on to second bit. If they don't match, then it's a fail. We could also do rangeAnd with digit DP. We could do this without binary search too, some observations: since N&N+1&... can only drop, and never gain bits, if X has a bit N doesn't we fail. So X must be a submask of N. Claude explanation I didn't read: For each bit b set in N, the smallest m ≥ N where bit b of m becomes 0 is flip(b) = ((N >> (b+1)) + 1) << (b+1). Once m hits flip(b), bit b is gone from the AND forever. Bits set in both N and X must survive → m < flip(b). Bits set in N but not X must die → m ≥ flip(b).

review, mostly for range AND

Problem Summary:

We have N <= 2e5 numbers abs(num) <= 1e9. Some numbers are 0s. We can replace a 0 with any integer. Find the max # of prefix sums that total 0 after these replacements.

Notes:

An initial thought might be to turn a 0 into the inverse of the sum before it, like [2, 0, 2, 4, -4, 4, -4] we might turn the 0 into a -2 to score it: [2, -2, 2, 4, -4, 4, -4] But actually that just guarantees our ...0 prefix gets a point. We should instead look RIGHT because we can affect all the prefixes bigger than us. We see the (4,-4) and (4,-4) pairs are basically 0s, but there is a 2 right before it in index 2 that is offsetting us. If we set our 0 to a -4: [2, -4, 2, 4, -4, 4, -4] then we would score 2 points instead. So for each 0, walk right and maintain a map of the maximum prefix sums from that 0 onwards, the highest frequency determines how much we can score. Include the initial 0 in that frequency map too. Also, we have to score the prefix before the first 0, separately.

just reread

Problem Summary:

We have an NxN (N <= 1e5) grid. To represent this grid we have an array R and C of size N, and grid[i][j] is R_i + C_j We have Q <= 1e5 queries (point1, point2). Those two points are always even numbers. Can we connect the two points with a path that stays on even numbers?

Notes:

At first it seems complex, maybe we have to go really far right from one point, up, then loop back up. But this cannot happen, if we could go really far right, then up, we could also go up immediately. Because it means going right our parity never changed, and so going up from that point on the right our parity didn't change, we could just go up immediately. So precompute how far right and up we can go from cells to maintain the same parity, I used dp, but we could union find on adjacent parity that match. Then check if they can reach. We can always do it in a single right then up (or right then down) path.

Problem Summary:

We are given N <= 5e5 numbers <= X <= 5e5. Determine if A_0! + A_1! + ... is divisible by X! (NOT x)

Notes:

One observation, say all the terms are >= 5!, like 5! + 5! + 8! + 6! Then obviously we are divisible by all 1...5 because we are just adding terms divisible by those. Note this does NOT necessarily mean we are divisible by 5! (but maybe it's true?) For instance if we are divisible by 2 and 4, say 4, we are not necessarily divisible by 2*4. So just being divisible by 1,2,3,4,5 doesn't mean we are by 1*2*3*4*5 (but again maybe it is, not sure if there is a proof...). The claim we make is different. If every term is >= 5! that means every term is also divisible by 5!, since 6! = 6 * 5! for example. So obviously we are divisible by 5!. But the moment we hit 6? Are we divisible by it? We can take everything >=6, so (6! + 8!) and call it (stuff divisible by 6!) and then take all the 5 factorials (5! + 5!) and see it is not divisible by 6!. Because we require 6 of them. So basically we get a counter of every factorial. We loop up starting at 1. Look at how many 1! we have. Maybe it's 5. Two 1!s add to a 2! so that combines into 2! + 2! + 1!. Well we know this is like (stuff divisible by 2!) + (something not divisible by 2!, since we don't have enough to combine, I mean 1 * 1! is literally smaller than 2! so it could never be divisible). So we know 1! is the biggest stopping point. But if we had 6 of them, it forms three 2!s, we bubble up a count, and keep going.

re-read

Problem Summary:

We are given N <= 1e6 pairs (x, y) <= 1e7. For each pair we keep incrementing by 1, so (x+1,y+1), (x+2,y+2), and so on, forming a chain. A pair is lucky if gcd(x, y) = 1, find the length of the longest lucky chain for each pair

Notes:

First note if X and Y share a factor it isn't lucky and the chain is size 0. If they are coprime, any individual factor from X or Y would never be an answer because X&f != Y%f Any factor of X+? and Y+? must also be a factor of Y-X because of the offsets. So we want to analyze each factor of Y-X and check the smallest one >= X. But constraints are tight. Note we can just check prime factors, not all factors. So we need an SPF sieve in N log log N up to 1e7 and then to prime factorize we use the spf which is worst case logN time since all primes reduce by at least 2x division.

review ideas of using a sieve and spf instead of trying to spam pollard rho everywhere, mod remainders is cool too

Problem Summary:

We have a square of side length S <= 1e9. We have 4 <= P <= 1.5e4 points along the borders. We also have 4 <= K <= 25 which is how many points we have to select. What is the maximum minimum manhattan distance we can have between the K selected points? Basically we want to space out things as far as possible.

Notes:

First thing to note, manhattan distance feels annoying because we are working on perimeters. But actually because 4 <= P we know we could never space out all the points by > S anyway. This means that an annoying situation like 2 points on opposite sides of the square, having a smaller manhattan distance than perimeter distance, actually does not bother us since we don't need to consider manhattan distances > S anyway. Next we map the border points to a flat array see code. Let's binary search on the answer so we introduce a log(S) factor since it's at most S. For each answer we can consider every point as a starting point. It feels like we maybe have to do some annoying circular array technique for our binary search but we actually do not need to. Since SOME point is going to be the starting point, say starting from (0,0) moving clockwise around the square, whatever point that is, when we pick that as a starting point, we can just travel the array right only, ending back at the bottom edge of the square (moving towards 0,0). So no circular binary searching needed. We consider P possible starting points. For each point, we binary search for the next point spaced out by our guess in logP time. After doing this K times, we check if our ending point wrapped around too close to our starting point. This gives log(S) * P * logP * K. 2/ We could drop the K by building jump tables... For each possible distance in the binary search we spend P log P time finding the next position for every point, and then P log K time building out the jump tables. Now when we enumerate starting distances, we immediately jump ahead K spots in log time with the jump tables and check if it wrapped too far. 3/ I think there is an even better one than jump tables using two pointers: https://leetcode.com/problems/maximize-the-distance-between-points-on-a-square/solutions/8098454/java-binary-search-with-feasibility-chec-x48a/?envType=daily-question&envId=2026-04-25 4/

re-read full notes, liked ideas about starting points only having to go right and not loop back to the start in the binary search, liked jump tables idea, see code for the flattening of border points -> array

Problem Summary:

Bob picks some power of 2 <= 1e9. Alice will take her turns (she plays only) trying to bring it down to 0. She can divide / 2 if even, or she can subtract by 1. We give her K <= 1e9 turns. How many numbers <= N can she not reach 0?

Notes:

Think in binary, a subtract operation turns the LSB from 1->0, a divide removes that last 0. Obviously we need to divide out until we clear the MSB. But among those there might be other 1s in the middle we subtract out. It's combinatorics, for each possible MSB, like 10000 or 100 we check how many other 1s can be placed in the tail 0s, such that alice still has enough operations to clear it, basic nCk. Handle the edge case of the number equaling N exactly, separately, because we can't add 1s under it or it would exceed N. Digit DP can probably be used too

Problem Summary:

We have N <= 5000 numbers <= 1e9. We will delete the array one at a time. We pick a number, delete it, and add MEX(arr) to our score. We want the minimum score, what is it?

Notes:

Naive way of thinking works O(n^2), our current mex is some value. We can clear out a lower value and get a new mex. It's not guaranteed which one to clear out though. Like maybe there's a LOT of 0s so we shouldn't clear those out, there's a single 5 let's clear it out quickly to stem the bleeding, etc. Note it's not just clear one type then clear 0, we can actually chain them, so we need dp(mex). Base case is mex=0 we pay 0 to clear the remaining array. We test all unique values. A bit of a trick, if the current mex is 10 and there are three 5s, and we clear those three 5s, we only pay 10 twice, because we pay the mex after we clear the number. This makes the score updating a bit annoying but the cleanest way was to add on a 5 in the recurrence (see long long score = paid + nxt + x), the +x basically makes it so we pay that 5 in the future, because otherwise the 5 we pay now doesn't get counted, but this makes it so basically any mex that wasn't the first captures that extra time. If it doesn't make sense don't worry it was just a clean way to handle something.

just re-read honestly such a great question

Problem Summary:

Super weird problem, basically we have L <= 2e5 seconds in the night, and N <= L animatronics, every second one of the animatronics danger levels rises by 1 (initially all are 0). We don't know which rises basically it can be picked adversarially. We have N <= L flashlights at given second times, we can flash an animatronic to reset its danger. The overall danger is the maximum final danger at the end of the night. What is the smallest value of this? Also # animatronics * L <= 2e5

Notes:

The idea is kind of like this, say the enemy only incremented 1 animatronic over and over, we would just flash it repeatedly, and end up scoring L - last flashlight time (it increments at the very end un-interuppted). So obviously the enemy would want to increment more animatronics, it could increment 2, then you execute your final flash, and they spend all their increments on the non-flashed one at the end which is at least as good as the only ever increment 1 case. If we have X flashlights remaining there isn't a point for them to increment >= X+2 animatronics. We can only flash X of them, so dispersing flashes among the other 2 is bad. I kind of lost the intuition now but basically they want to increment exactly X+1 where X is the current amount of flashlights we have. They do this "evenly" to sort of build up this weak frontier. If we they went more min-maxed in their incrementing we would nuke the big ones quickly first so they need to do it evenly. I simulated but probably could be simulated faster.

just refresh the idea of an even defensive increment before reset

Problem Summary:

We have an N <= 2000 grid that is H <= 1e9 tall, bottom blocks are land top are water (just see pictures). We can place two drains which drain water from any cell that can travel laterally and down. Max water we can drain?

Notes:

My idea was for each drain position, assess all prefixes and suffixes containing that drain. We can form a prefix of the prefix for the best results (sounds confusing, really its not though) and then test splits points. I'm sure there's many more ideas I won't really look into them though.

Problem Summary:

Given a tree and two nodes P and Q, move P into the subtree of Q, some weird rules if Q is inside P

Notes:

basically just follow instructions, different cases for the positions of P and Q, track parents

Problem Summary:

Given a tree of N <= 1e5 nodes with <= 26 letters on edges, find how many paths we can have where we re-arrange the letters to form a palindrome.

Notes:

SOLUTION: small to large It would be nice if at a node we could enumerate all down-chains in all its descendants, well that is what small to large does We track a map of parity bitmask -> count since things like 0010000 can form a palindrome. When we merge in light nodes there's a few things that happen: 0/ the base case for us is a map of bitmask 0 -> frequency of 1, and we call shift(mask) before we bubble up to account for that edge (or we could just insert the actual mask and not shift it) 1/ light node mask can XOR with itself to form a mask of 0, which allows a palindrome (no odd frq letters) 2/ light node mask can XOR with any mask that is exactly 1 bit wrong against that, to form a palindrome mask with a single bit set 3/ we should enumerate all these options first, then fold in the lightnode, or it pollutes 4/ we also want to score all paths that end at the node exactly, I added handling at the end for both the no single bit set, and the single bit set cases, maybe we could just initialize the heavy node we pick with the root nodes data? that felt confusing though because things were on edges not nodes. 5/ When we do add the root node data later, it's annoying because we want to modify the bitmask of every node in our final heavy output, since they all get affected by this edge, to handle this we can store an offset in our Info class 6/ When merging default dicts I ran into some issue where reading a 0 in a map created an empty 0:0 key:value pair or something like that, it TLEd for me, I don't know if it actually affects complexity, claude seemed kind of unsure, to fix this I just made the .get() and .add() abstractions to the info struct to deal with it -I did a manual implementation in the submission at the bottom but it was hard -Easiest is to build the abstractions in the info class of my top submission SOLUTION: prefix XORs First get the XOR of every root to leaf path. Now any two nodes that have a palindromic bitmask XOR form a path. We can do this with a single loop + hashing.

re-implement, tricky handling of Info class, offset shifting, dealing with small to large on edges

Problem Summary:

We have an array of N <= 1e5 numbers <= 1e9. We can pick a subset and bitwise OR them together. What is the smallest number we cannot make?

Notes:

We basically need all bits in a range b...32 to make at 32 bit number. So we check 1, 2, 4, 8, 16, etc if they exist

quick reread

Problem Summary:

We have a string of letters and ?, replace every ? so no two letters are adjacent

Notes:

Only need up to 3 letters per option, when we write we need to read res[i-1] not s[i-1] in case the previous letter was a ?

Problem Summary:

We are given a SQL table of seats and people, we need to swap every 2 seats, except the last if odd

Notes:

literally can just do CASE WHENs on the parities

Problem Summary:

We roll a 6 sided die. We can choose to reroll for $1. If we stop we get a payout of the upwards face. Basically we get at most 1 reroll. Expected payout?

Notes:

An average roll is 3.5, so a 4 5 and 6 won't reroll a 3 wouldn't reroll either since we pay $1 So a 1 or 2 (1/3rd of the time) we lose $1 and then get $3.5 on average, so $2.5 payout 50% 1/3rd of the time. 2/3rd of the time we get an average of a 4.5 (from 3 4 5 6). ends up being 23/6

Problem Summary:

We are given 8 coins and flip all at once. After we can reflip any amount one time. We get $1 per head. Payout?

Notes:

A single coin basically gives $0.75 payout, since 3/4 times it pays $1, so $6 total

Problem Summary:

We have 4 balls, two black two yellow. We pick out random ones one at a time without replacement. Before each one we guess the color, if we are right we get in dollars the # of balls in the container before we chose it. Expected payout?

Notes:

First guess we get $2 EV since it is 2|2 Now it splits into 2|1 0.33 chance we get nothing, 0.66 chance we get $3, so this layer has ev $2 Keep writing it out like this there might be a linearity of expectation idea too

review, we can literally just write it out

Problem Summary:

Price of a stock starts at $100, then drops 1%, then goes up 1%, forever, what does it converge to?

Notes:

After one cycle price is $99.99 so we lost 0.01% P_n + 100 * (0.9999)^n which approaches 0 Is there a formal proof? I wrote this before idk: for any positive integer r r = e ^ (ln r) r^n = e^ (n ln r) same with the fraction .9999^n = e ^ (n ln .9999) since ln(.9999) < 0 we have e^-inf which is 0

Problem Summary:

We roll a standard 6-sided die. After, given we rolled K, we roll a (6+K) sided die, find the expected value that appears on the second roll.

Notes:

We condition on the first roll all with equal chances, so if first roll is a 1, we have a 7 sided die which gives us 4 on average, and so on, average all those up

quick review condition on first idea

Problem Summary:

We are sailing from 1 island to another. Travel time takes 12 minutes but there are 5 wave checks. Four of the waves stop us with 25% chance and add a minute. Last stops us with 75% chance and adds 4 minutes. Find expected duration.

Notes:

The stops are entirely independent so I don't think we even need linearity of expectation idea really, but yeah just add them up

Problem Summary:

A bagel factory delivers good (G) and bad (B) bagels. If a bagel is G the next one is G with 2/5 chance. If B the next one is B with 3/5 chance. The first bagel is bad. Find the # of expected bagels that pass until another bad one.

Notes:

Note each bagel has a 2/5 chance to be G and 3/5 to be B regardless. So what is the expected # of trials to get a B where the independent chance is 3/5? It's just the inverse 5/3 but we can do a formula. E = 3/5 * 1 + 2/5 * (1 + E), kind of recursive E = 0.6 + 0.4 + 0.4 E E = 5/3

review the formula representation

Problem Summary:

We generate a random number from (0, 1). We can keep it or generate a new one. Payout is the last number generated. Find expected payout.

Notes:

If the first one is above 0.5 we keep it and get 0.75 in expectation, otherwise we get 0.5, so 0.625

review

Problem Summary:

You have 5 unique locks with 5 unique keys for them, each unlocking one lock. What is the max # of times we need to test locks to identify all that open them?

Notes:

4 fails for first key, 3 for second, 2 for third, 1 fail for fourth, then no fails for last

Problem Summary:

How many values of N are there such that a regular n-gon has interior angles that are integer values?

Notes:

Exterior angles sum to 360, but cannot be 180 or 360, so take all other factors of 360, since exterior angle must be an integer which makes interior one an integer

quick review

Problem Summary:

You are in a river with an unknown length and current speed. If you remain stationary (not swimming) in the river, it takes you 6 seconds to reach the opposite bank. If you swim downstream at a speed of 3 feet per second, it takes you 4 seconds to reach the opposite bank. What is the length of the river (in feet)?

Notes:

W = width Passive movement goes W/6 feet per second If we go down at 3fps our speed is (3 + W/6) fps d = r * t W = 4 * (3 + W/6) W = 36

review how to set up equations

Problem Summary:

You are trying to fill up an inflatable kiddie pool. One hose can fill it up in 20 minutes. Another hose can fill it up in 10 minutes. If the pool is full, it takes 15 minutes to drain out the water after the drain is opened. How long does it take in minutes to fill the pool with both hoses and the drain being open?

Notes:

h1 fills C/20 per minute h2 fills C/10 per minute d drains at C/15 per minute total rate gain C/12 per minute so 12 minutes

Problem Summary:

Jenny is firing her revolver, which has 6 chambers. The time from the first shot to the last is 1 minute. Assuming a uniform firing rate, how many seconds will it take Jenny to fire 3 shots?

Notes:

1 gap = 12s so we use that to get 24s

Problem Summary:

A bacteria population doubles every 10 minutes. At t₁ = 55 minutes, the population consists of 200 bacteria. How many bacteria does the population consist of at t₂ = 95 minutes?

Notes:

It doubles 4 times so 3200

Problem Summary:

On a circular table of 5 seats, five people denoted 1, 2, 3, 4, 5 are seated. 4 wishes to sit immediately to the right of 2 while 2 sits immediately to the right of 5. Additionally 1 does not want to sit next to either one of 2 or 5. Who is to the left of 5?

Notes:

just basic logic

Problem Summary:

We have a 6x6 grid, we are in the bottom left and want to move up and right, how many ways to reach 6,6?

Notes:

We need to interleave U and R which is the normal 12!/(6! * 6!) idea

Problem Summary:

We have N <= 20 digits <= 9. We are trying to form "01 03 2025" from the digits, when could we have earliest assembled that date?

Notes:

just loop and counter, have need could work too I guess

Problem Summary:

We have N <= 2e5 students with skills <= 1e9. A team is strong if its strength is >= X (<= 1e9). Strength is # of members * min skill. We want to partition the students (subsets, not subarrays) and find the max # of strong teams we can get.

Notes:

Start at the biggest, if that alone isn't strong we have to take someone smaller, the biggest can't be the min. Take the next smallest, keep going until we are strong, then that is a team. No reason to add more.

just re-read, kind of a weird greedy, basically we have to start from the strongest, not the weakest

Problem Summary:

We have N <= 1e5 numbers <= 1e9. In an operations we can take i and j, and perform these two updates at the same time: nums[i] = (nums[i] AND nums[j]) nums[j] = (nums[i] OR nums[j]) We can do this operation any # of times. After this, we will pick K <= N elements and sum their squares. What is the max sum we can get?

Notes:

Imagine two numbers like this: 111 111 000 000111 111 Basically the operations "pass" non shared bits from one number to another, like this: 000 111 000 111 111 111 We can do this in both directions This intuits that maybe we can greedily form as big numbers as possible. So we count up all the bits in all numbers and assemble the largest K possible. We can see this is doable because we can take any number that has some 0 bits, and any number which has 1 bits for those spots, and pass it over. So we can basically just keep filling up any number with as many 1s as possible.

just re-read notes, the bit operations sometimes sound tricky but are easy to understand

Problem Summary:

Given a SQL table of employees find all employees who make the second highest distinct salary in their department

Notes:

I avoided some partition thing, instead I select all employees WHERE then do a subquery where the count of distinct salaries greater than our salary is 1

Problem Summary:

We have a SQL table of tree nodes with a node id and a parent id, return a table showing whether a node is a root, inner node, or leaf

Notes:

root is when parent id is null, inner node is when some other node has us as a parent (subquery check), else leaf

Problem Summary:

We have a SQL table of tree nodes with a node id and a parent id, return a table showing whether a node is a root, inner node, or leaf

Notes:

root is when parent id is null, inner node is when some other node has us as a parent (subquery check), else leaf

Problem Summary:

Given N <= 1e5 numbers <= 1e9 we want to find some array of the same length. Arr[i] is the sum of |i-j| for all nums[j] == nums[i]. Find this array

Notes:

Map val -> indices For each unique value we have a list of indices, for each of those indices we want to find the sum of distances to all other indices 1/ Compute the answer for bucket[0] initially by looping over all i in 1...end of bucket When we move from bucket[i] to bucket[i+1] the answer changes in a predictable way, the # of elements less than us we know, and we know they grow each in distance by the bucket[i] to bucket[i+1] gap, and ones on the right move closer 2/ Or we could probably do some prefix / suffix thing

Quickly reread first idea

Problem Summary:

We have N <= 1e5 nodes each with different values, for each subtree, find the smallest missing value in it

Notes:

0/ Some weird union find variant? didn't look into it https://leetcode.com/problems/smallest-missing-genetic-value-in-each-subtree/solutions/1458284/union-find-with-thinking-process-a-bonus-l4n2/ 1/ Small to large with sorted lists, we merge it, to find smallest missing we binary search + find kth which is log^2 n (I think because there is no O(1) find kth?), overall thing is n log^2 n because of merging sorted lists too 2/ Dylan had an O(n log n) version https://leetcode.com/problems/smallest-missing-genetic-value-in-each-subtree/solutions/1458702/java-small-to-large-merging/ He did small to large using hash sets but each node also stored its smallest missing value, so when we bubble up all the children, I guess we can do something with that 3/ O(n) Well note since values are distinct anything missing the single 1 is going to have answer 1. Only ancestors of 1 need to be recomputed. We could walk up from the 1 node adding all elements in and seeing the smallest missing, I guess with a SortedList in N log N but there is some O(n) boolean array idea I didn't look into... 4/ tree flattening Flatten into euler tree, now we need to find smallest missing in a range for a bunch of l...r ranges Normal mo's is like with a SortedList so n root n log n, too slow I think tin has some weird trick remember, like MEX with mo's, using sqrt decomp with O(1) update rootN query or something, so N root N time? REVIEW THIS We can use fastset too, on the absent values not in the tree, basically we can insert and remove from the set in log_64(U) and to find the smallest missing it's just next(1) which is log_64(U), so we get N root N * log_64(U) got an AC here in C++ https://leetcode.com/problems/smallest-missing-genetic-value-in-each-subtree/submissions/1985777388/ Note our fastset is on abset values, we could also do it on present values, but then to find the MEX we could binary search and call prev(i) which is logU * log_64(U) WE COULD ALSO USE SEG TREE: Remember we want to find smallest missing value in a range L...R (for each tree range) We could use a seg tree on values, each leaf stores lastPos[v], internal nodes store the minimum lastPos over its range of values Sort queries by increasing R lastPos[v] = -1 for everything since nothing is seen yet Sweep r = 0, 1, 2, ..., n - 1 update lastPos[val[r]] = r with a point update For every query (L, R) with R==r answer it now: smallest value with a lastPos < L? How to answer a query (L, R). We want the smallest value v with lastPos[v] < L. Do a segment tree descent from the root: At each node, look at the left child's minimum. If left.min < L, then some value in the left half has lastPos < L, so the answer lives in the left half — recurse left. Otherwise, every value in the left half has lastPos ≥ L (meaning they all appear in [L, R]), so the answer must be in the right half — recurse right. At a leaf, return the value index. OR PERSISTENT SEGMENT TREE: Didn't look into it yet: Version 2: Persistent segment tree (makes it online) The core idea. Instead of mutating one segment tree as we sweep, we keep a snapshot after every update. roots[r] = the root of the segment tree as it was after processing position r. To answer query (L, R), use roots[R] and do the same descent as before — querying at R without having to be physically there in a sweep. How to store N snapshots without blowing up memory. Naively, N copies of a tree with O(V) nodes = O(NV) memory, catastrophic. The persistence trick: when you do a point update, only O(log V) nodes on the path from root to leaf actually change. So create new versions of only those nodes, and have them point to the old (unchanged) children. Each new "version" of the tree shares almost all its nodes with the previous version. Result: each update creates O(log V) new nodes. Total memory: O(N log V). For N = V = 10⁵, that's ~2·10⁶ nodes — fine. Pipeline. Build initial tree with all -1s. roots[-1] = this tree. For r = 0 to N-1: roots[r] = update(roots[r-1], val[r], r). For each query (L, R): answer = query(roots[R], L). Total complexity. O((N + Q) log V) time, O(N log V) memory. Same time as Version 1 but online. When you'd use this. If the queries come one at a time and you must answer each before seeing the next. Or if the queries depend on previous answers. Or if you're inside a competitive programming problem that explicitly forces online. For this LeetCode problem, all queries are known upfront, so Version 1 is simpler. I think we can do wavelet tree for range mex? and even with updates??? https://codeforces.com/blog/entry/137068 And 3d mo's??? for n^(5/3)

just re-read

Problem Summary:

We have N <= 1e5 nodes with labels <= 1e9. We want to find the total # of pairs (u, v) where A_lca(u,v) = A_u * A_v Basically the total # of pairs where their node labels multiply to form their LCA. How many pairs are there?

Notes:

Small to large merging, we store counters of number -> frq, as we merge we can look up the complement value to update result

just another re-read of notes

Problem Summary:

We have a tree of N <= 5e4 nodes with values. We have Q <= 5e4 queries (node, k). Call the path XOR sum of a node the XOR from the root of the tree down to a node. Each query gives us a node and wants us to find the Kth smallest distinct path XOR sum in that subtree, or -1 if it doesn't exist

Notes:

Small to large merging, base case is we return a SortedSet with just the single XOR from the root to that leaf, we do this via dfs(node, aboveXor) To merge two SortedSets (or SortedLists) just get the heavy child and merge in light childs ensuring no duplicates if using a SortedList We answer queries at the time we get the SortedList fully set up for a subtree The problem is a bit weird because normally we think of small to large as merging things coming from below, but in this case we are still doing that, it's just we track the aboveXor during the thing 2/ https://leetcode.com/problems/kth-smallest-path-xor-sum/solutions/6870202/trie-merging-in-nlogn/ There is some crazy trie merging idea The idea is you have a binary trie, top node is MSB, and each node stores a counter for the # of elements in that subtree So to find kth smallest is easy, we just do a trie-walk based on the counts, cause anything on the 0-bit child subtree is smaller than anything in the 1-bit child So we can find kth in log(MAX) Then using some weird way to merge tries I didn't learn we can get n log MAX I guess 3/ I think tin found some online way using a sqrt persistent seg tree

the small to large feels weird here because it's using a SortedList and because the path XOR comes from above, but that's actually fine, just peak at code

Problem Summary:

Given a tree of N <= 1e5 nodes of colors <= N, a color C is dominating in a subtree if there are no other colors appearing more times than C (so multiple can be dominating). For each vertex find the sum of its dominating colors.

Notes:

1/ We can use mo's and a flattened tree to get n root n 2/ We can use small to large For each node we track a frequency of color -> count, we track our max frequency, and the sum of all dominating colors Store this in an Info struct Sort the children by map size, pick the first as the heavy child, grabbing it with move() (I think this is needed?) Loop over other ones, merge them in, updating the sums/frqs as needed, also merge in the root node Update result of our node before we bubble up the map, I think required to do it like this because the maps get bubbled and re-used and we want to capture the data now while it is fresh 3/ Someone said we can use centroid decomp and they were a GM 4/ They also said n*DSU is doable in the editorial comments idk how There is another idea which is like small to large but avoids merging unordered maps which is slow. We use a global array and global dominatingSum and maxFreq representing the values for SOME subtree. First we loop over all light children processing them, walk down the child, fill out the data, get the answer for that light child. When we bubble back up we reset the global data. Then we loop into the heavy child, get the data, answer for that subtree, go back up, but don't drain. Now loop over all small ones again, adding them back up, now we have a full tree. Proof of complexity is something like nodes are part of light children only logN times since they at least double in size when they walk up. Didn't practice this.

good to practice Info struct, merging, grabbing nodes with C++ syntax, etc

Problem Summary:

Some basic math question honestly not re-reading

Notes:

just very basic math and gcd

Problem Summary:

Given N <= 2e5 numbers <= 1e9, find the maximum XOR of any subarray

Notes:

Remember XOR of subarray is just prefix XORs of r and l-1 So add all prefix XORs to a bit trie, each time we add then find the best XOR against any of those not adding to drills because I have more complex bit trie problems in drills

Problem Summary:

We have an array of numbers, we want some prefix (can be nothing) and some suffix (can be nothing) that don't overlap and have a max XOR, find that XOR

Notes:

bit trie can find max XOR against numbers in a set, so prefix/suffix that

should probabily implement the bit trie and read its functionalities...

Problem Summary:

We have a tree, nodes are good or bad. A good node gives +1 and bad node gives -1. A subgraph of the tree is the sum of scores of its nodes. For each node, find the max score subgraph containing that node.

Notes:

Reroot DP First compute down[node] Then I used full[node] since the answer is just that minus down[child] to get the up portion, or we can gain 0 from that up portion if we don't want it, basically a pretty simple case

sure why not, pretty easy just another solve

Problem Summary:

We are given a tree of nodes with values. The price sum of a path is the sum of node values on that path. The tree can be rooted at any node root of your choice. The incurred cost after choosing root is the difference between the maximum and minimum price sum amongst all paths starting at root. Return the maximum possible cost amongst all possible root choices.

Notes:

First observe the min is just the node itself so we really just care about the max price sum path for each root First compute down[node] which is max price sum where we go down Then I did up[node] (we have to seed it before dfs2! since its just price[node]) and res[node]. Update res[node] in the root call. I build a prefix and suffix and used the exclude trick but it was annoying. https://leetcode.com/problems/difference-between-maximum-and-minimum-price-sum/submissions/1985534087/ Or we can do a trick where we store top 2 price sums going down, and which child we went through for the best one. Now at a child, if the parents best didn't go through that child, our up[child] can just use that, otherwise we use second best. That's for the go up from child -> parent -> back down to a sibling case. I actually found this way easier to write, separating upThenDown, upUp, and down. https://leetcode.com/problems/difference-between-maximum-and-minimum-price-sum/submissions/1985561955/ We could also not store the best child node to pass through from the parent, but I think we could just recompute the scores if we went from node through child node, and compare if the biggest down from node was through the child, but I found storing the best node we passed through easier

I have some similar implementation practice in CSES tree distances 1, but for this one I want to specifically try the concept "store the best child we passed through" cause I found it really easy to implement

Problem Summary:

Given a tree, find the sum of distances from a node to all other nodes, for every node

Notes:

Reroot DP First I did down[node] and we compute it using the size of subtrees as well Then I did full[node], seeded full[0] The distance for a child is just the parent node distances, but all child nodes move 1 closer, all other nodes move 1 away

re-read notes / quick glance at code, have other reroot dp in implements drills

Problem Summary:

We have a tree. We want to find the root so we make guesses, in a guess we pick two nodes U and V and ask "is U the parent of V"? Bob doesn't tell us which guesses are right but tells us how many are right. How many possible roots can there be?

Notes:

Reroot dp first solve down, so in a subtree find how many valid guesses there are now we solve full, we seed full[0] and update res[child] style, maybe can do a different way Only transition is the single reroot edge

just re-read code, have enough reroot dp drills I think

Problem Summary:

Given two rectangles find if they have a positive area overlap

Notes:

We can find intersected AREA of each dimension and multiply those 1/ casework- -A contains B -B contains A -A fully left of B -B fully left of A -A partially left of B (I think we can check either the left or right edges? a few ways? if we process this last) -B partially left of A 2/ clamp- Everything reduces to taking the max of the left edges and the min of the right edges, and the difference is their width We have to max with 0 because non-intersecting regions have negative area max(0, min(x2, x4) - max(x1, x3))

re-read notes

Problem Summary:

We have K <= N <= 50. N people from 1 to N. We start at person 1, they pass to the right by K, then person 2 passes to the right by 2*K, and so on (circular array). Game ends when someone gets the ball for a second time. The losers are those who never got the ball, return these.

Notes:

Simulation using a counter

Problem Summary:

We are given a string, decompose it into blocks like [aa, b, yyy, aaa] Given a digit string s, decompose the string into some number of consecutive value-equal substrings where exactly one substring has a length of 2 and the remaining substrings have a length of 3. See if we can do this^

Notes:

I basically looped over letters, tracked streaks, tracked how many were divisible by 3, and how many required that extra 2 (we need exactly one of these), but it's annoying because the way I code this it requires another check outside the for loop for the last streak some improvements: 1/ append a '#' to the end which flushes out the last character 2/ we can use itertools.groupby req2 = 0 for _, g in groupby(s): n = sum(1 for _ in g) r = n % 3 if r == 1: return False if r == 2: req2 += 1 if req2 > 1: return False return req2 == 1

review tricks

Problem Summary:

We have N <= 1e5 numbers <= 1e9. For each index i, find the # of indices j where i<j and nums[j]<nums[i] and nums[j] has an opposite parity to nums[i]

Notes:

I used two SortedLists for odds and evens and looped backwards

Problem Summary:

We are given N <= 1e4 points X,Y <= |1e5|. The points are uniformly and randomly distributed in some unknown sized rectangle. We are given a circle radius 100 <= R <= 1000. Guaranteed the circle doesn't exceed >10% of the area of the rectangle. We wish to place circles on the plane such that: -No two overlap -Each circle contains at least one point -We use at most N circles -89%+ of the points are contained by a circle Find such a construction where each circle has an integer center.

Notes:

First note the points are random, we need something that covers a lot of the plane. Hexagonal packing covers ~89%. Imagine row0 is aligned at y=0 so we have circles there. Rows in the next row above get nestled in-between, so offset by a shift of R. The vertical distance is r+root(3) (can derive from height of an equilateral triangle). See a hex packing diagram to get the idea. We actually space out the heights by ceil(r * root3) to ensure integer centers and the idea is this shouldn't produce a lot of loss of area. Now for each point try to find a circle containing it. First guess it's row based on the ceil(r * root3) distance. Similar math we use for the column (they're spaced by 2*R). Note we could center our circles anywhere since we are just tiling things, so centering at R,R might be easier. We get an approximate row and col but due to the way they nestle we aren't quite sure which circle it falls in, so I checked a 3x3 grid around that area. If any circle contains that point (euclid distance) we add that circle to the group. We can do this since we can spend up to N circles.

review

Problem Summary:

We are given X < Y <= 1e18. Y is a multiple of X. Find if there is a Z for: X < Z < Y Z is a multiple of X Y is not a multiple of Z

Notes:

First ensure there is at least one multiple between X and Y If there is I guess we could just pick the highest one, like Y-X, and if Y/X>=3 this always works In contest I did a more brute force approach

Problem Summary:

Consider a sequence [1, 2, 3, ... N]. We are given X <= N <= 1e18. Find the # of subsegments L...R that contains N and has an XOR of 0

Notes:

Remember an XOR of L...R is pfXor[r] ^ pfXor[l-1]. But pfXors follow a pattern: Define f(k) = 1 ⊕ 2 ⊕ 3 ⊕ ... ⊕ k. f(k) follows a period-4 cycle based on k mod 4: | k mod 4 | f(k) | |---------|------| | 0 | k | | 1 | 1 | | 2 | k+1 | | 3 | 0 | Why? Well pairs of numbers that start with an even always XOR to 1. Like [4, 5] XORs to 1. We can write out the cases: ### Case k = 8 (k mod 4 = 0) f(8) = (0⊕1) ⊕ (2⊕3) ⊕ (4⊕5) ⊕ (6⊕7) ⊕ 8 = 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 8 = 0 ⊕ 8 = 8 Four complete pairs cancel, leaving k dangling. Result: f(k) = k. ### Case k = 9 (k mod 4 = 1) f(9) = (0⊕1) ⊕ (2⊕3) ⊕ (4⊕5) ⊕ (6⊕7) ⊕ (8⊕9) = 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 = 1 Five pairs → odd number of 1s. Result: f(k) = 1. ### Case k = 10 (k mod 4 = 2) f(10) = (0⊕1) ⊕ (2⊕3) ⊕ (4⊕5) ⊕ (6⊕7) ⊕ (8⊕9) ⊕ 10 = 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 10 = 1 ⊕ 10 = 11 For two things to XOR to 0 we want f(r) and f(l-1) to be equal. This happens when they are both 1, or are both 0. Specifically blocks of [0, 1, 2, 3] [4, 5, 6, 7] , ... And [2, 3, 4, 5] [6, 7, 8, 9], ... XOR to 0 And these are the only such cases, so a subarray XORs to 0 only with a composition of these blocks, in 1, 2, 3, ..., N To prove that we could basically write out the 4x4 matrix of cases and show only those hold So now we just count how many blocks of these forms exist and do some math

re-read / refresh idea

Problem Summary:

We have a 2xN grid of red and black cells, N <= 2e5. We want to repaint some cells so we can do this: -group the cells into pairs -pairs of cells must be two adjacent cells -pairs must share a color Min # of repaints to make?

Notes:

I did bottom up DP, like prevMatch, prevBR, prevRB, kind of state machine logic, there may be some greedy as well

Problem Summary:

We have a string S of length <= 2e5 of A's and B's. We want to make it alternating (so ABAB... or BABA...). We can pick some subarray, invert all the letters, and optionally reverse it. Can we make it alternating?

Notes:

I think dp works but it gets fairly complex. I did casework: Count the consecutive blocks like [aaa, b, aa, bbb]. If any block of size >= 4 exists we fail. We can have at most a single block of size 3 (AAA -> ABA) and no other blocks of 2 or more). If we have blocks of size 2, we can split them up so like AA ... BB we place the ends here A|A ... B|B, so we can have at most 2

Problem Summary:

We want to give children cookies, each gets at most 1. Children have greed factors where they need a cookie at least g[i]. Each cookie has a size. What is the max # of children we can give a cookie to?

Notes:

Sort and then two pointers

Problem Summary:

Given a string, find the length of the longest palindrome we could make if we rearrange

Notes:

Evens contribute, one odd

Problem Summary:

Given N, return a fizz buzz array, if divisible by 3 and 5, FizzBuzz, just 3 is Fizz, 5 is Buzz, otherwise number

Notes:

Check 15, 3, 5, then number

Problem Summary:

Given all numbers from [0, n] except one find the missing one

Notes:

sum-subtract, xor everything against 1...n

Problem Summary:

We can scramble S to get T doing this: If length is 1, stop If length is >1, split it into two substrings at a random index, S = X + Y Randomly decide to swap the two, so S = Y + X Apply the algorithm on each X and Y Given S1 and S2, can S1 become S2?

Notes:

dp(l1, r1, l2, r2) and we test every scramble point. This looks n^5 but the # of states is n^3 because r2 is derived since the lengths are constant.

Problem Summary:

Given X <= 2^31, find the square root rounded down without a built-in

Notes:

Binary search for the smallest number squared <= X there is some trick though where rootX is e^(1/2 log x) or something lol We could also use recursion. Base case is when x is 1. Note rootX = 2 * root(x/4). So we could use that recursive algorithm or something like that in logN too Newtons method does something too

Problem Summary:

We have a list representing a longer number like [5, 3, 1, 0, 9] add 1 and return a new list

Notes:

Increment last one, carry while we have 10s

Problem Summary:

Given an NxN (N<=9) board find the # of boards we can place N queens with no two attacking

Notes:

standard backtrack(row) where we have a rowSet, colSet, two diagSets We could also do backtrack(r, c) with the sets

Problem Summary:

We have an NxN (N<=9) board, output all boards with N non-attacking queens on it

Notes:

standard backtrack(row) where we have a rowSet, colSet, two diagSets We could also do backtrack(r, c) with the sets

Problem Summary:

We have an avengers base. There are positions in the base each with some amount of avengers. The length of the base is a perfect power of 2. Thanos wants to destroy the base with minimum power. Starting with the whole base, he can: -If the length is at least 2, divide it into two equal halves and destroy them separately -Burn the base, if it has no avengers it takes A<= 1e4 power, if it has avengers it takes B * n_a * l power, where l is the length, B is <= 1e4, and l is the length of that base. What is the min power to destroy everything? 2^N is the length of the base, N <= 30, so the base is <= 1e9 length

Notes:

We can represent the problem as: recurse(l, r) The root level is (0, n-1) Second level is (0, n-1/2) (n-1/2 + 1, n-1) This forms 1 + 2 + 4 + 8 + ... + n at the bottom level. This is 2n-1 intervals. Think of it like adding binary: 0001 0010 0100 1000 (this is n) The sum is: 1111 Now this is too many because N <= 1e9. But the moment we have no avengers in a range we could early terminate. So how many ranges could contain an avenger? With M avengers each one could be in up to logN different sized subproblems so M log N which is tenable. We just need countAvengers(l, r). I did another binary search which gives us M log 2^N log M I don't know if we can drop that binary search (fractional cascading?), someone said something about master theorem: https://codeforces.com/blog/entry/64989?#comment-708754

worth a read

Problem Summary:

We have N <= 1e5 superheroes with powers <= 1e5. In an operation we can remove one superhero (if at least two) or increase the power of one by 1. We can do at most M <= 1e7 operations and at most K on a specific superhero. We want to maximize the average power.

Notes:

1/ We test every amount of removals. We remove 0, 1, 2, etc. We remove the smallest and see how many ops we can use for the remaining gain. 2/ I think we can binary search on a max average too, removing anyone below that average and incrementing the rest, but not sure if this works with the K per superhero cap?

Problem Summary:

We have S <= 1000 length string and T <= 1000 length. We want to transform S into T. We can change any vowel in S to any other vowl, and any consonant in S to any other consonant. Can we do it?

Notes:

Wording is unclear, so a->e and a->i are both possible at different positions. becomes trivial

Problem Summary:

We have N <= 10 doors and we want to pass through all of them, some are open and closed, if open we can pass in 1 second. Cannot pass through closed doors but we can use a special power once which makes all doors open for X seconds. Can we pass?

Notes:

Find leftmost and rightmost closed and see if it is small enough

Problem Summary:

Construct a permutation of size N <= 2e5 where we can do this operation the max # of times: -pick a non endpoint number that is bigger than its neighbors, remove it

Notes:

Put 1 and 2 on the ends now the max can always be removed

Problem Summary:

We have N <= 2e5 numbers <= N. We want to partition it. A partition is cool if for each segment b_j, all elements in b_j also are in b_j+1. So [1, 2] [2, 3, 1, 5] would be good. Find the max # of segments we can make.

Notes:

Observe the last segment must contain every number, I went right to left, my logic is a bit confusing in hindsight I think there might be some better ways with like distinct_prefix counts

Problem Summary:

We have M, N <= 1e6 rows and columns in a grid. The cost to enter (i, j) is (i+1) * (j+1). We began at 0,0. On odd moves we must go right or down, on even moves we must go left or up. Find the min cost to reach m-1,n-1 or -1 if impossible.

Notes:

It's basically almost ways impossible, I just did casework

Problem Summary:

Given a SQL table of cities find all cities in each state that have at least 3 cities, one city which starts with the same letter as the same

Notes:

Subquery where I aggregate cities together, get the count, check how many equal the state letter with SUM(CASE ...), then another query outside it

Problem Summary:

We have two arrays of length <= 1000 with numbers <= 1e5. Find the number of triplets (i, j, k) where nums1[i]^2 == nums2[j] * nums2[k], and the same for the other direction

Notes:

We can solve each array orientation separately. Many ways: 1/ O(n^2) For a number in nums1, loop through all numbers in nums2, find the other factor, get a count with a counter. Or loop on pairs and multiply them and look up the square in the other array. 2/ O(n * pollard rho on square) For a number in nums1, fast factorize the square with pollard rho, enumerate all D divisors and look them up in a counter in nums2 3/ O(n * d of square) For a number in nums1, fast factorize it, generate all factors of square by doing like (p1 * e1) -> (p1 * 2*e1) and generating the list, then look up LET'S UNDERSTAND POLLARD RHO AND FACTORIZATION TECHNIQUES: For a number N there are several sizes to keep straight: N - the value numDistinctPrimes(N) - the # of distinct prime factors, like 12 = 2^2 * 3 which has 2 distinct ones numPrimesWithMult(N) - # of prime factors multiplicity allowed, so 12 has 3 numDivisors(N) - just the number of divisors, so 6 numDistinctPrimes <= numPrimesWithMult <= log2(N) The first is obvious, the second is because all primes are >= 2 so it would grow faster numDivisors can be larger than logN but it grows slowly, for example N <= 10^10 has max divisors 6720 Pollard Rho: It is a randomized alg. Given a composite N it gives some non trivial factor d (1 < d < N) in N^1/4 per call expected, or N^1/4 * logN not fully sure on this We can use deterministic Miller-Rabin to check if prime in k log^3 N time where K=7 for 64-bit numbers. But since N is a 64 bit number two of those log factors are actually O(1) machine operations so we get k time logN, which is 7 log N. <-- also not 100% on these ideas So the full flow is something like this?: function fullFactor(N): if N == 1: return {} if isPrime(N): # Miller-Rabin return {N: 1} d = pollardRho(N) # some factor, 1 < d < N left = fullFactor(d) right = fullFactor(N // d) return merge(left, right)

re-read notes

Problem Summary:

We have N <= 1e9 seats that are all empty. When a student enters a room they want to sit as far as possible from other people, if a tie, they sit at the leftmost index. If no one is in the room they sit at position 0. Also support leave(i).

Notes:

Let us attempt to just store the free ranges in a SortedList, like ([0, n-1]). The issue is we need sizes too, as we must pick the biggest size. So we have a second sorted list holding sizes, like (size, left, right). But that sizes one is not enough because when they leave we need to find the interval they are in, so we need both. In general we can find the biggest size, place them in the middle, and handle the logic. But there's some edge notes: 1/ if empty we place at 0 -> can just code this logic in, check if we are fully empty e.g. we have one full range interval 2/ edge ranges like [0, 3] being free, despite being smaller, can score more than larger regions in the center like [15, 20] since placing someone at an edge puts them the full distance away, not a midpoint distance. To fix this, I found simplest way was to have all the bySize sorting assume we place in the middle and get that score, and in the seat() function we check the leftmost and rightmost intervals by position, see if they are at the edge, and theorize what we would score. Helpful to make helper functions like rem(l, r) and such This makes logN for everything

re-read notes, clean handling with helper functions and clean logic to deal with sitting at ends vs sitting in the middle, just always assume the sorted list sits us in the middle and check ends separately

Problem Summary:

We have two arrays source and target of length N <= 1e5 containing numbers. And a list of E <= 1e5 swaps (a, b) which means we can swap source[a] and source[b]. Find the minimum # of differences between source[i] and target[i] we can make after any amount of swaps

Notes:

1/ Gather components 2/ In a component, we can re-order those numbers however we like 3/ See how many elements we can match with those numbers from target

Problem Summary:

Given N <= 1e9, find the # of different consecutive positive sequences that sum to N

Notes:

Answer for a sequence of length 1, 2, 3, etc - we can sum 1...X and then check the remaining required values. This terminates at rootN since the sum grows squared.

Problem Summary:

We have an array of houses with money and can steal but not from 2 adjacent, and it is circular, max money?

Notes:

We could try two options including the first index and not last, or vice versa, or add another state

Problem Summary:

Given a column in excel like "ZYA" find its number

Notes:

Basically base 26, loop and multiply

Problem Summary:

Given a SQL table of people and addresses basically combine them

Notes:

just a JOIN

Problem Summary:

Given a SQL table of employees find those who make more than their managers

Notes:

Join and compare

Problem Summary:

Given a SQL table of Customers and Orders find customers who never ordered anything

Notes:

JOIN and then select from that

Problem Summary:

Houses have money, we cannot rob two adjacent, get the most money

Notes:

standard dp, can do bottom up space optimized

Problem Summary:

Get the right side view of a binary tree

Notes:

Either bfs and use the last node, dfs and track our position and update, or bfs right to left and use the first

Problem Summary:

We are given N < 2*31, find if it is happy. Take N, replace it with the sum of the squares of its digits, if it hits 1 (it stays there) it terminates, otherwise it is not happy

Notes:

At most a transformation turns a number of N into 9^2 * logN so I guess, I don't actually know a proof of the upper bound complexity of this but we see it reduces quickly, so we could just simulate it and hash set We could slow and fast pointer too to see if it has a cycle but do O(1) space There was some analysis about finding the biggest number with a next bigger value is 243 so any cycle must contain numbers smaller than 243 or something and we can deduce the finite list of cycles and use that

Problem Summary:

reverse a linked list

Notes:

iterative with prev is best

Problem Summary:

Given a linked list and an integer, remove all nodes that have that value

Notes:

standard linked list, dummy node, etc

Problem Summary:

Given a binary grid find the # of islands

Notes:

we can dfs, bfs, or union find

Problem Summary:

Given a SQL table of emails find all duplicates

Notes:

GROUP BY HAVING count

Problem Summary:

Design a data structure which supports add a number, and find(value) returns a boolean if any two numbers sum to value

Notes:

Don't think we can do better than O(n) find, either using a hashset or a SortedList and the sorted two sum, but that requires logN add (idk why I did it like this)

Problem Summary:

Given N <= 5e4 numbers find the majority, it always exists

Notes:

Giving a 3/10 difficulty for boyer moore version

Problem Summary:

Given a string of tokens like ["2","1","+","3","*"] evaluate it in reverse polish notation, hard to describe but could look at code

Notes:

Basically stack, when we hit an operator process it on the last 2 elements

Problem Summary:

Given a binary tree get its postorder traversal

Notes:

postorder dfs

Problem Summary:

Given a binary tree get its preorder traversal

Notes:

preorder dfs

Problem Summary:

Given a linked list, determine if their is a cycle in it

Notes:

Slow and fast pointer see if they meet

Problem Summary:

We have a string S <= 20 length and a dictionary of D <= 1000 words of length <= 10, add spaces to S so every word is in D, find all possible unique sentences. It is guaranteed the answer is <= 1e5 length.

Notes:

We could backtrack, which ends up being 2^n nodes (we put a partition or not between everything), and N work at the end to update the result. We do O(10) hash lookups to check if that word is in the word dict but even if it were O(n) it doesn't affect complexity because if we imagine a tree of 2^n nodes (regardless of for loop backtracking or not) then each node could do N work and not degrade complexity. N * 2^N for backtracking then For dp we have dp(i) is for ... and holds all those answers, for a given DP we loop through 10 sizes and update the result, DP doesn't improve things I think, we still have to generate the entire answer and build it out, since the DP result could be as large as n * 2^n size in a string 'aaaa...aaa'

review notes, mostly how DP doesn't actually improve complexity here because we are bounded by the length of the answer, but it's probably better on average, I mean if we have two different prefixes we build like "aa" "b" vs "a" "a" "b" and we can re-use work for the suffix after it, I don't think it matters that that suffix is cached in a DP or backtracked, because worst case the suffix could be a bunch of c's and the size of the cached value is the size of the # of states produced by backtracking

Problem Summary:

Given S <= 16, partition it such that every substring is a palindrome, find all ways

Notes:

We can loop at an index and check if that substring is a palindrome, I think the complexity does not degrade if we do a naive palindrome check inside the loop, the thought is there are 2^n nodes in a backtrack (Without a for loop) since we either place or don't place a separator between each two letters, and leaf nodes do O(n) work to place the result, so all nodes can do N work? not sure if it really translates though, I mean in the tree with for loop backtracking we still have 2^n nodes, every node should take on a different state uniquely, so doing N work at every node doesn't affect anything

re-read notes, I think complexity does not degrade with naive check

Problem Summary:

We have left, right <= 1e4. Calculate the product of all those numbers. Remove all trailing 0s. If the remaining number is <= 10 digits, do nothing to that part. Otherwise turn it into <first five digits>...<last five digits>. Add on e<number of trailing 0s> to the end. Return this.

Notes:

First we could try to calculate the product manually without trailing 0s. If it is <= 10 digits we can basically have our answer. To do this, start manually multiplying. However we cannot just keep manually multiplying and stop the moment we hit >10 digits, because some future ending digits might get stripped out due to trailing 0s. Instead lets multiply the numbers together but remove all their factors of 2 and 5. We terminate if the product is >10 digits. Now multiply by the remaining 2s and 5s factors that didn't produce trailing 0s and again check if we exceed 10. If we don't then we just take this final product + number of trailing 0s. If we do exceed 10 we need the last 5 and first 5 digits. Last 5: We could literally just track the product of the last 5 digits before any trailing 0. Multiply all numbers together, every number strip all trailing 0s, throw away anything above 5 digits. Remember to add on a 0 at the beginning like if we trail with 8192 we actually trail with 08192 at the end. First 5: One idea, we can actually do the same thing. Store the first 18 digits, multiplying each number and dropping digits off the end. Now we keep the top 5. We use 18 for more precision but I didn't precisely follow the math. This worked for me though. Another idea (which had precision issue in a test case, then I tried decimal but it TLEd): # any positive number P can be written in scientific notation P = m * 10^k # m is the mantissa and satisfies 1 <= m < 10 # EXAMPLE: # P = 7,219,856,259,000 # P = 7.219856259 * 10^12 # m = 7.219856259, k=12 # the leading digits of P come from P # take log_10 of both sides # log_10(P) = log_10(m * 10^k) # log_10(P) = log_10(m) + log_10(10^k) # log_10(P) = log_10(m) + k # since 1 <= M < 10, we know log_10(m) is in the range [0, 1) # and K is an integer # log_10(P) will then be some integer portion + fractional portion, remember log_10(P) is kind of like the # of digits of P # log_10(m) will be the fractional portion, and K will be the integer # we want to solve for M # log_10(m) = fractional part # m = 10^(fractional part) # now we compute log_10(P)

re-read notes

Problem Summary:

We have a string of N <= 1e5 letters and N shifts where shifts[i] means we shift the first i+1 letters forwards by that much (wrapping z->a), find the final string

Notes:

I did a sweep line version but I think something about a suffix sum works or also looping backwards for O(1) space

Problem Summary:

We have strings like this, we want to print it vertically Input: s = "TO BE OR NOT TO BE" Output: ["TBONTB","OEROOE"," T"] Explanation: Trailing spaces is not allowed. "TBONTB" "OEROOE" " T"

Notes:

Find the max word length, loop over that, loop over each word

Problem Summary:

We have 2 strings of length <= 1000 with only X and Y, like s1 = 'xx' s2 = 'xy', in an operation we can swap any digit from s1 with any from s2, min # of ops to make them equal, or -1 if impossible

Notes:

Note this configuration: XX YY Requires only 1 swap to become YX YX So we count XY and YX pairs. Each one contributes the floor of half of it to the final score. Like 2 YX pairs YY XX Contributes score 1 Obviously we ignore already matched pairs like: X X Now if we have something like XY YX We can fix this in two operations: YY XX -- XY XY But we basically only do this once, cause if we had 2 of those, we would have two XY and two YX which we fix in 2 total operations Only issue is if we had a single XY or single YX we cannot repair that, but we check that total Xs and Ys are both even and things work out

re-read, don't need to solve super in depth but just feels like one of those patterns that comes up a bit

Problem Summary:

We have a string S of length <= 1000 and D words <= 1000 (each word also <=1000 length), find the longest of the D words that is a subsequence of S, if multiple possible give the smallest lexicographical one

Notes:

No better way than to manually check, note that to avoid the sorting of D words (as we want a lexicographical answer) then we could just maintain our best answer, and for each word compare it against our best, capped at the length of the current best and the word we consider, which does not affect asymptotics

kind of a cool idea to avoid sorting

Problem Summary:

We have a grid of B and W cells, find the number of lonely black cells, a cell is lonely if that row and column don't have others

Notes:

Keep a counter for each row and column

Problem Summary:

Given a binary tree find the largest value in each row

Notes:

Can dfs or bfs

Problem Summary:

We have a matrix grid of water nad land, there is one island, find its perimeter

Notes:

For all land cells, look at all the sides

Problem Summary:

Genes are 8 letters and consist of A C G T. We have a start and end gene and a bank of genes. We want to go from start to end using only bank genes, find the min length path

Notes:

standard bfs

Problem Summary:

Given a space separated string find the # of words

Notes:

can do O(1) space by looping

Problem Summary:

We have an array of N <= 2e4 intervals [start, end] with coordinates >= -1e6 and <= 1e6, all starts are unique. The right interval for an interval i is another interval j where start_j >= end_i and start_j is minimized, find the right interval for all i.

Notes:

Basically for each interval we need to find the smallest start value that is >= our end, so we sort the intervals and binary search for start points someone also did a two pointers + sorting but I hate those

Problem Summary:

We are given S and T, T is S shuffled with an extra letter, find that letter

Notes:

two counters

Problem Summary:

We have a file system storing both files and directories, using \n and \t to help a string basically form the shape of the directory, find the longest length absolute path

Notes:

We can basically use a stack and check the length of it, a lot of annoying indexing / math

Problem Summary:

We need to support a data structure with O(1) average insert, delete, getRandom, and duplicates are allowed - random chance should relate to the % frequency of that element

Notes:

Standard easier version of the question, we maintain a counter of elements and an array, to insert we update both, get random picks a random one from the array, and to delete we look up the number in a num->list of indices map, look at the last index in that bucket (since O(1) to pop from it), swap with the ending element, and update the maps, think this should work For some reason in my initial submission I did a lazy delete, so I tracked lazy removals and when I call get random and it hits something with lazy removals I then delete it, I guess this is O(1) amortized but just seems weird

Problem Summary:

We need to support a data structure with O(1) average insert, remove, getRandom, no duplicates allowed.

Notes:

We maintain a set of elements and a list. And a map of element -> pos in list. Insert and getRandom are then easy. To remove, find that element, swap to the end, and pop.

Problem Summary:

We have an NxN board and we need to design tic tac toe which supports move operations and tells us if there is a winner after that move

Notes:

When we place a move we can linearly iterate, but there is even an O(1) approach per move Since we only win when we get N marks in a row/col/diag we can just maintain a counter for each of those

review notes because second part is genius

Problem Summary:

Given two arrays, return an array of their intersection but numbers appear based on the # of times they appear in the originals

Notes:

Two counters

Problem Summary:

Given two arrays, return an array of their intersection

Notes:

Two sets

Problem Summary:

We have N <= 1000 words of lengths <= 1000, find the max len(word1) * len(word2) where those words share no common letters.

Notes:

For each pair we check if they share letters, we precompute the set of letters and do a set intersection, or a bitmask for a single machine op

Problem Summary:

We have a binary grid of 1s and 0s representing land and water, we can perform a single add land operation turning water -> land, for each position in the grid, find the # of islands if we turned that into land

Notes:

Union find and now we know which of the 4 adjacent neighbors are connected, we could assign an ID to each node or I think easiest would be to just query the parent of each adjacent 4

re-acknowledge note we don't need an idx, we can just check parent reps

Problem Summary:

We have an array of nums and point updates and range sum queries

Notes:

Standard seg tree or sqrt decomp

Problem Summary:

We have a string of only + and -. We take turns flipping ++ into --, the game ends when the other person cannot make a move. Return all possible states after one valid move.

Notes:

Just enumerate all moves

Problem Summary:

We have an MxN (M,N <= 250) grid of walls, empty rooms, and gates. For each empty room find its distance to the nearest gate.

Notes:

Standard multi-source bfs

Problem Summary:

Given a SQL table of logins, find who should be banned, meaning two IPs were logged in at the same time

Notes:

Join the login table against itself querying for matching account ids, different ip addresses, and both logins occured before the other logout (clever)

Problem Summary:

Given a SQL table of drinks replace all null drinks with the name of the previous non-null row

Notes:

This is some classic "forward fill" problem, there are surely better ways but I basically learned about a hidden .ctid field which gives a physical location which I could use

Problem Summary:

We have 3 types of water, cold warm and hot. We want amounts <= 100 of each (different amounts). Every second we can fill two cups with one water, or one cup with one water. Find the min # of time to fill all

Notes:

Say the 3 amounts sorted are A <= B <= C We obviously must take at a minimum C time since we cannot go faster. We also must take a minimum of ceil((A+B+C)/2) time since we cannot subtract more than 2 at a time. The answer is the max of these two. See: If C >= A + B we take C time by pairing C with a and B and then the rest solo deplete C. If C < A + B we always pick the biggest 2, didn't airtight prove this never results in an [X, 0, 0] case though Obviously we can simulate but that is slow

review notes

Problem Summary:

We have N <= 1e5 pistons some are moving up and some down, the height at each piston is up to 1e6. As time flows they move 1 unit in their direction, reversing at the ends. Max area under a piston at any point in time?

Notes:

We could imagine a piston's space over time as X, X+1, X+2, ... hits the ceiling, goes back down to 0, then goes back up to X. This space of time is <= 1e6, and we have arithmetic progression range adds. We want the max after. To avoid T log T work to query each point we first push down all nodes in O(T) then we can query each leaf in O(1), so it becomes O(n log T). Other ideas: I believe some sort of version of two sweep lines should work, one for the step value and one for the constant value, I was testing some things with claude and it was pushing back on some of my ideas so I didn't fully explore I think we can consider this as a piecewise function with at most like 2*n breakpoints so there's some geometric intuition We can kind of simulate it at any time we gain the # of up pistons - # of down pistons and move them between two deques at most 2n times I think similarly we could use a heap and poll for things hitting the endpoints and bookkeep the # of up and down

re-read notes

Problem Summary:

We need to support range add in a...b 1, 2, 3, and so on. And range sum queries.

Notes:

It is an arithmetic progression segment tree. We can represent a lazy addition of (coefficient, constant) so if a node covers a range i...j and we have coeff=3 constant=2 it means the i-th element gains coeff*0 + constant, i+1th gains coeff*1 + constant, and so on We can compose these together just by adding the lazy coefficient with the new coefficient, and same for the constant factors also some sqrt decomp idea

review

Problem Summary:

We have two numbers L and R <= 9e15, and a string directions of length 6, basically we need to count # of numbers in the range L...R that follow this weird rule set, best to read the original problem

Notes:

Best is to precompute all the notable indices of the initial digit and then do dp(i, ltight, htight, prevDigit, notableI). I initially had a weirder implementation where I kind of rolled up the (r, c) logic inside the DP but I couldn't debug, realized my mistake was not considering the initial 0,0 cell as special, it's one of those things where I was sort of conflating the concept of entering a recursive call with the prior parameters

re-read notes first to remember the precompute special indices is better, stop and think clearly during contests, I guess mostly just that because it helps me not run into that annoying state / previous call / current call issue, but really the problem point was here: for d in range(low, hi + 1): ndigit = prevDigit if not isNext else d isNext wasn't being set to true in the first 0,0 call to my dp function which caused problems, because really what I wanted was "isImportant" not isNext

Problem Summary:

We have an MxN grid (M*N <= 1e5) and some set of initial cells with colors, every second they expand, and a cell becomes the max of the new flood-fill if multiple cells reach a new one at the same time, return the final grid

Notes:

Standard bfs but we have to allow multiple on a layer to overwrite, I did this by using both a seen and an lseen set I'm sure there's other ways. Lee also did some BFS but sorted by larger values first which I think simplifies it

Problem Summary:

We have N <= 1e5 numbers <= 1e9, find the earliest index i where the prefix sum - postfix sum is <= K <= 1e9

Notes:

prefix/postfix, I did sparse table since I was in contest

Problem Summary:

We have N <= 100 numbers we want to find the earliest index where the prefix sum - postfix sum is <= K <= 1e9

Notes:

Prefix/postfix, I used sparse table since I did it in contest

Problem Summary:

We have an MxN (M,N) <= 500 grid with a start and ending position, and some walls. We don't actually know the grid, we are given a class which we can tell if we can move a certain direction, if we are current on the target, and the ability to move our robot. Find the min distance to the target.

Notes:

PROBLEM: We have 1 robot only, so a BFS becomes untenable. We dfs to find the target, using a seen set to keep it O(m*n), and we don't terminate early when we hit the target, we enumerate all cells. Now in step 2 forget about the robot, seen cells indicate open cells. Run a standard BFS.

re-mindsolve

Problem Summary:

Given a SQL table of employees and bonuses get all employees who didn't get a bonus or got one <1000

Notes:

just left join

Problem Summary:

Given an array of N <= 2e4 elements find the longest subsequence where the difference between the max and min is exactly 1

Notes:

Check all pairs of number types (using the sorted array)

Problem Summary:

Given an N-ary tree, get the postorder traversal

Notes:

just postorder dfs

Problem Summary:

Given an n-ary tree, get the pre-order traversal

Notes:

just preorder dfs

Problem Summary:

Given 4 points, determine if they form a square

Notes:

Check equal side lengths, we can do this by finding the minimum 4 distances between all pairs of points, and the last 2 distances are equal, maybe some other ways too

re-read notes

Problem Summary:

We have a garden of size height x width (height, width <= 100) where there is a tree, a squirrel, and N < 5000 nuts, the squirrel wants to bring 1 nut at a time to the tree then end at the tree, find the min # of moves it can make

Notes:

Each nut is going to be a tree->nut->tree loop, except for the first which is squirrel->nut->tree, so find the most savings we get for any nut

Problem Summary:

We have 2N (N <= 1e4) numbers, group them into pairs (a, b), (c, d), ... such that the sum of the min of each pair is maximized. Return this max sum.

Notes:

We just sort and do it, could bucket sort too

Problem Summary:

Find the # of subarrays with sum equal to K

Notes:

Standard lop off method

Problem Summary:

Find the max depth of an n-ary tree

Notes:

just dfs

Problem Summary:

We want to find the # of attendance records of length N <= 1e5, consisting of A P L (absent, present, late) where there was at most 1 absence and at most 2 consecutive late attendances. Find how many valid sequences there are.

Notes:

We can do dp(i, absences, previousLate) for O(n) or use matrix multiplication for O(logN), there are at most 6 states (2 possible absent states, 3 late states) and we can define a 6x6 transition matrix

re-read, for matrix exponentiation

Problem Summary:

We have a string of A L P (absent, late, present), find if the student wins an award, they had <= 1 absences and never were late for >= 3 days

Notes:

O(n) 1 pass, can optimize out the 3n factor

Problem Summary:

Given a string make sure all letters are capitals, all are not capitals, or only the first is

Notes:

just do what it says

Problem Summary:

Given a binary tree, find the most frequent subtree sum

Notes:

Global counter, get sums

Problem Summary:

A perfect number is one equal to the sum of its proper divisors, return if N <= 1e8 is a perfect number

Notes:

rootN factorize or O(d) factorize work, there is also some logN euclid-euler proof in the editorial

Problem Summary:

We have N <= 1e4 unique scores <= 1e6, athletes are placed based on their scores, either they get gold silver bronze or their rank is their placement, return the ranks

Notes:

Just sort

Problem Summary:

We have N <= 1e9 balloons all off, every second we toggle every i+1-th bulb, find how many are on at the end

Notes:

Perfect squares have odd divisors, so we can count those in logN by binary searching, "O(1)" with sqrt math, or just rootN by testing increasing sizes

Problem Summary:

We have N <= 300 balloons and if we pop one we gain nums[i-1] * nums[i] * nums[i+1] coins, find the max # of coins. If an edge is popped then the left or right are an imaginary 1 balloon

Notes:

dp(l, r) and we enumerate the last balloon to pop in that range, if that is the last balloon, then it would be paired with the l-1 and r+1 balloons, why? Imagine we have a problem for l...r, we pick some last balloon, now we recurse to a sub problem, well it is guaranteed the edges of that subproblem were a last balloon from the prior state

re-read notes, particularly the edge logic of the last balloon

Problem Summary:

We have a secret string number (length <= 1000) and we ask our friend to guess. Then we give a hint, the # of bulls (correct position digit) and cows (right digit, wrong position). Given a secret and a guess, return the hint.

Notes:

we could do one pass

Problem Summary:

Support online range sum queries

Notes:

prefix sums is O(1)

Problem Summary:

We have an MxN (M,N <= 25) binary grid that follows the game of life. Living cells with <2 living neighbors die, living cells with 2-3 living neighbors live, and those with >3 neighbors die. Dead cells with exactly 3 living neighbors become a live cell. Output the next state.

Notes:

We can do it in-place by using intermediary values to represent "old state was X, new state is Y"

Problem Summary:

We have a string and a pattern, find if the string follows the pattern, basically the pattern maps a letter to an entire word, we need a bijection

Notes:

keep a mapping in both directions

Problem Summary:

We have N <= 300 points, find the max # of points that lie on a line

Notes:

1/ O(n^3) for each of n^2 pairs, check all other n points to see if they lie on the same line 2/ O(n^2), for each pair get a slope, ideally using some gcd or reducible thing, track slope -> count

implement the n^2 in the cleanest slope method, might have thoughts on this in another problem

Problem Summary:

We have N <= 1000 words of length <= 20 and need to see if we can form a string S <= length 300 from some arrangement (duplicates allowed) of them.

Notes:

Naive is dp(i) is if we can form i... in S and we loop over up to 20 lengths and check if that word is in the set, could drop a factor of 20 with rolling hashes I think any bitset/aho corasick attempts get worse complexity

Problem Summary:

Given a string of length <= 2000, partition it into the minimum # of palindromes, find that #

Notes:

dp(i) is for i..., we test all options, can precompute if substrings are a palindrome with dp there is some clever bottom up way to do O(n) space but we could also just use two rolling hashes for O(1) isPalindrome check with O(n) space

Problem Summary:

We have a linked list and a value X,t put all nodes < X on the left and others tw on the right, preserving their relative order

Notes:

Split into two sublists then connect them

Problem Summary:

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, slightly different from the first version of the problem where we leave 1 copy of each

Notes:

I'm guessing we can do it in a few ways but I basically checked if this is a duplicate then did a nested walk to find the new point

Problem Summary:

Given a sorted linked list remove duplicates

Notes:

Just keep removing while next equals the current one

Problem Summary:

We have a sorted list of numbers, find two indices where the sum of numbers adds to a target

Notes:

L=0 R=N-1 and increment or decrement

Problem Summary:

We have two versioned string numbers like 1.2.01.3, compare them

Notes:

Basically split them into groups and compare each group

Problem Summary:

Given a list of space separated words, get a string where the position of the words are switched, so "hi i am ishaan" becomes "ishaan am i hi"

Notes:

O(n) space to reverse a list, O(1) in mutable string is clever - reverse all characters and then for each word reverse them, maybe other ways too

re-read notes of clever idea

Problem Summary:

We have a tree and need a level order traversal but each other layer traverses backwards

Notes:

just a variant of bfs

Problem Summary:

Determine if a binary tree is symmetric

Notes:

dfs(node1, node2) but the mirroring is weird, we go left on the left half and right on the right half sort of thing

Problem Summary:

Get the level order traversal of a tree

Notes:

standard bfs

Problem Summary:

Given a string of words and spaces get the length of the last word

Notes:

Just loop backwards

Problem Summary:

Generate the Nth pascal triangle row

Notes:

Basically just build over and over which is n^2, there is also an O(k) version with math, think of it like this: at a given cell at the bottom row, maybe towards the left, we have to move A total moves left and B total moves right which are fixed, so that's like combinatorics of (A+B)!/(A! * B!)

re-read combinatorics notes

Problem Summary:

We have an N*M with N,M<=100 grid, find the # of unique paths from 0,0 to the bottom right, moving only down or right

Notes:

dp(r, c) works or we can find the # of ways to interleave the sequences of moves, which I think is just the (A+B)!/(A! * B!)

Problem Summary:

We have N <= 2e4 heights and water rains down, falling out the sides. Compute how much water is trapped.

Notes:

1/ We are limited by prefix and postfix min, so use that 2/ Extend to use greedy two pointers for O(1) space

Problem Summary:

We have two linked lists that are sorted, merge them

Notes:

standard linked list merging

Problem Summary:

We have N <= 200 numbers with abs(number) <= 1e9, find all unique quadruplets [nums[i], nums[j], nums[k], nums[l]] with i<j<k<l where the numbers sum to 0

Notes:

We can loop on n^2 first pairs then do the sorted 2 pointers method after, O(n^3)

Problem Summary:

We have N <= 500 numbers with abs(number) <= 1000. Find 3 distinct indices so the sum of those numbers is closest to target.

Notes:

1/ We can sort and do the two pointers method on the right, decrementing and incrementing L and R pointers if we are too big or too small, O(n^2) time 2/ I think we can do t^2 + n, maybe with binary search also, didn't look into it

Problem Summary:

Given N <= 3000 elements, find the number of triplets (nums[i], nums[j], nums[k]) where i!=j!=k and the three nums sum to 0. No duplicate triplets allowed.

Notes:

We can sort and for a first pointer we want to find how many j and k there are, we can do the sorted two pointers method for O(1) space

re-read notes

Problem Summary:

We have N <= 500 words with length <= 5, two words are adjacent if they differ by one letter. Output all minimum length paths from beginWord to endWord.

Notes:

We can just naively generate the adjacency list or do it faster with wild cards. A naive thought is we store a list of all paths of minimum length to all nodes, but I think this degrades in time (it MLEd). A more clever thought is each node stores a list of parent pointers that we could visit. At most each node could feasibly store 500 nodes so we get n^2 memory, and the input states the answer is bounded by 1e5 so we know we wont exceed that with our DFS building. I did this with a level-seen set that makes it so multiple things on the same layer able to consider the adjacent node as a possible connection (which we need to build all paths) but I think we could do it without a level seen, see my code At the end we DFS to build out the results backwards

re-read notes

Problem Summary:

We have N <= 5000 words with length L <= 10. Two words are adjacent if one character differs. Find the min # of moves to go from beginWord to endWord.

Notes:

A naive idea is to, for all n^2 pairs, check if there is an edge in O(L) time by counting the # of mismatches. Now we have a graph with at at most 26 * L * N edges (we cannot reach N^2 edges!) and we BFS on it. But the N^2 * L complexity kills us. So what if we, for a given node, generate 10 wild cards like ABC_EFG. This is done in O(n * L^2) time (or maybe faster with mutable strings?). Now for a given word we look at all L wild cards, and look at all other nodes that had that wild card, and pair them up. We create the same 26 * L * N sized graph but now the construction of the adjacency list was only N * L^2 time, which works.

re-read notes

Problem Summary:

We have N <= 2e4 rectangles on a plane, find if they form a perfect rectangle with no overlap

Notes:

1/ O(n * log^2 U) we can support 2d range add and 2d range sum using a 2d fenwick tree, so do that to check no overlaps, then standard individual areas added = total area checks. With the 2d fenwick tree we normalize all coordinates to the positive range also. 2/ O(n), clever observation, corner points should have even parities except for the outer 4 corners, this helps us avoid the bad case of the rectangles fitting into an outer rectangle, and areas being the same, but having an overlap and a hole, since the hole region would create odd parities 3/ O(n log n), sweep line of events on x coordinates, each event adds and removes a y-interval range, with careful bookkeepping and an interval tree I think we can ensure full Y coverage

re-read notes for all, all good ideas

Problem Summary:

We have N <= 1e5 numbers <= 1e9, we want to find the minimum distance between i,j (i < j) where the reversed nums[i] == nums[j], and we strip leading 0s when we reverse

Notes:

1/ We cant store i-numbers in a hashmap and then at j try to look up which ones reverse into it, for example [1200, 21] at the 21 we would need to look up 12, 120, 1200, ... (I guess technically we could...) Instead I reversed the array so I made it [21, 1200] and now we can reverse the j-numbers and look up the earlier one 2/ Basically functionally the same as 1, but when we get to an i-number, reverse it and store that in the hashmap, now at a j number just look up that number in the hashmap

Problem Summary:

Given two trees check if they are the same

Notes:

dfs(p, q)

Problem Summary:

We have a linked list and two values, we need to reverse the left...right positions

Notes:

I used the rev(L, R) where L is the node before reversed range, R is after, R can be null. We use a dummy node too.

Problem Summary:

We have N <= 10 numbers, return all subsets but now we can have duplicates in the input and we don't want duplicate subsets.

Notes:

Similar backtracking, either we skip from a list then skip all, or consider a frequency map and choose how many to list

Problem Summary:

We have an absolute file path and we need to simplify it, things like getting rid of unnecessary .. in the path

Notes:

We can just use a stack and do it

Problem Summary:

Given an MxN (M,N <= 6) grid of letters find if a word <= 15 letters can be formed from a path

Notes:

Backtrack starting from each cell

Problem Summary:

Given N <= 10 numbers output all subsets

Notes:

standard backtracking

Problem Summary:

Given K <= N <= 20 find all combinations of K numbers chosen from 1 to N

Notes:

standard backtracking either with and without a for loop

Problem Summary:

We have a binary tree constructed by taking in some array (not given to us) and following this procedure: -find the max element, it is the root -the left tree are the elements on the left -the right tree are the elements on the right Now take that hidden input array, add some given value V to the end, we need to output a tree produced by this

Notes:

Two steps: 1/ Go from binary tree -> array This simple recursion looks like it is O(n) but actually it can be O(n^2) worst case if we keep re-adding large arrays, and O(n log n) in balanced cases I think if we appended things to an array it would be O(n), this is literally just a global result and then inorder dfs Now append V to the end 2/ Go from array -> binary tree Find the max, and construct on left and right This is n^2 if the max is at the beginning or at the end always since we do a full scan, if the max happens to be in the middle we do a full scan initially but then split into two evenly sized subarrays and I think it ends up being logN layers of N sized scans so n log n (whereas worst case we keep descending to lopsided size subarrays and now its N scans of size N) If we precomputed maxes with sparse table or something it could be faster, true O(n) construction after n log n preprocessing There is also a true O(n) construxtion using monotonic stack + dfs or something I didn't look into it SOLUTION 2: We just insert into the tree directly which is O(h) time, something about just. walking down the right spine

re-read notes, particularly about the complexities of things

Problem Summary:

We have a linked list, we will treat is as groups of size 1, 2, 3, 4, and so on (up to the last group which may be truncated). Evenly sized groups need to be reversed.

Notes:

Best abstraction I think is to make a rev(pre, post) function which takes in boundary nodes, we need a dummy pre but the post can be null Also the part outside the abstraction I did a bit weird at first trying to sync prev and curr, maybe different ways to implement it but I found just doing curr = prev.next at the beginning to be best

re implement with my reversing abstraction

Problem Summary:

We have N <= 1e5 numbers, and a K, all abs() <= 1e5. We can change at most 1 element to K, and we want as many partitions of size 2 (meaning split array into 2 non-zero subarrays) with equal sums. Find the max possible.

Notes:

No change case is easy For a change case, we can check each element, we change it from some old value to K, accounting for a difference. I now want to see any prefixes that start >= i (so our changed point goes in the left) and ones that start < i (our changed point would be in the right subarray). We can basically just use prefix/suffix hashmaps for O(1) frequency lookups, not too bad there was some binary search solution didn't look into it but seemed worse

re-read notes, maybe peek at code

Problem Summary:

We have an array of N <= 100 elements <= 100, if a number is a local peak or a local valley it changes by 1, return the final array

Notes:

Naive simulation works, can do O(1) space since as we scan left to right we only need the previous value There is a faster n * log solution I saw but didn't understand it

Problem Summary:

Design a skip list (the stacked layer of linked list things) that supports add, remove, and search in logN

Notes:

Alex wice has a really clean implementation that re-uses an iter function Quick reminder of how a skiplist works: -We have different layers, I picked an amount such that it would never have a 0.5 coinflip N times in a row. So for instance 32 height was VERY safe for n = 5e4 adds. We never expect any node insertion to win heads 32 times in a row. Because we randomly flip to decide a level. This gives the natural layering of a bottom level with every node, the first layer with half the nodes, second layer with a fourth, and so on -Think of the top layers like express lanes, we start at the top and zoom right until we must drop down -To drop down we actually just re-use the same node and each node has a forward array for each # of levels it supports -To search, start at the top, walk right as much as possible, then down, repeat, don't worry about the implementation too much -To add, basically we need to find insertion points at every layer, I did it with an "updates" array -Delete is more complex because if we have multiple elements with the same value we need to make sure we don't just delete that value per row, but the actual same true node, you can reference the notes in my code which gave a diagram of a tricky case (thanks to claude) but in short it functions similarly to delete

just a mental re-note of how skiplists work

Problem Summary:

We have N <= 1e5 types of candies each with a count <= 1e5. We have Q <= 1e5 queries (favorite candy type, favorite day, daily candy cap). We begin eating candies on day 0, following these rules: 1/ At least one candy must be eaten per day 2/ We must finish all candies of type i before i+1 3/ We can eat many types in a day provided rule 2 is followed 4/ We cannot eat more candies in a day than the given daily cap, for the query For each query, can we eat our favorite candy type on our favorite day?

Notes:

1/ binary search O(n log n) For a given query we want to know what's the leftmost day (basically if we eat as slow as possible) we can eat the preferred type, and the rightmost day (we eat the cap per day), and see if our favorite day falls in that range We do this with two binary searches + prefix sums, the indexing was a bit weird, also note the edge case where our binary search value could stay None implying there were more candies than days 2/ O(n) Flip the problem, instead for the given candy type look up the range of candy quantity we can eat and have that type, sort of like a prefix, then look at the range of smallest candy number we can eat (1/day) and max we can eat (cap/day) and see if these two intervals overlap

re-read, #2 solution is clever and #1 indexing was weird for binary search

Problem Summary:

Alice and Bob have candies that are numbers, we want to swap 1 candy between alice and bob so they have the same weight, find a pair (guaranteed one exists in the inputs)

Notes:

Basically we find the current alice surplus then half of that is the diff and we use that

Problem Summary:

We have a special table of secret encodings for n=0,1,2,...7, given n <= 1e9 deduce the output

Notes:

n+1 in binary, then remove the top bit

Problem Summary:

We have M <= 17 and <= 2^M numbers (roughly 1e5) all <2^m. We want to, for each number, find the max hamming distance between it and any other number.

Notes:

Finding the max hamming distance from X to another number is like finding the min hamming distance from complement(X) to another number. We begin a BFS from all numbers in the array on a graph with all [0, 2^m] numbers in it, seeing how far each number in that range needs to travel to reach a number in our input. Now for each number in nums, we can check its complement, and the min hamming distance to some number in nums. The result then becomes m-minDist[complement]. There was also some DP I did not look into. Also note a trie won't work that degrades to N time

re mind-solve, noting the concept of hamming weights being invertible, and the right way to do a multi-source bfs (we start from numbers in nums)

Problem Summary:

We have N <= 1e5 numbers <= 1e9 all the same length. The digit difference of two numbers is the # of positions they have a differing digit in. Find the sum of all digit differences between all pairs.

Notes:

map[digitPos][digit] -> count and update Think we could also get all the counts up front and kind of do combinatorics from there

Problem Summary:

We have an array of N <= 1e5 distinct numbers. In an operation if the first element is smallest, remove it, otherwise put it at the end. How many operations to clear the array?

Notes:

1/ seg tree I want to know the index of the minimum which we can find with a seg tree. I have a virtual index to the "head" of the array based on the current rotation. I can count how many operations to cycle to that min. We can represent a deleted hole by setting it to infinity, so we also need to count the # of infinities in between the range. So our seg tree tells us the index of min and the # of infinities in a range, when we delete we assign to an infinity. 2/ sorted list Didn't look into it but I think we can do something loosely the above but with a SortedList 3/ plain sort Also didn't look into it but some tricky sort idea

re-read notes / re mindsolve

Problem Summary:

We have a binary tree, we need to layer traverse it, on odd layers left to right, even right to left. Each layer has a score which is the sum of nodes but we stop scoring once we hit a node lacking a child. Find the score for each layer.

Notes:

Many ways to do it, I just avoided a deque and used a list directly which I kept reversing, I think we could also just iterate over the list backwards

Problem Summary:

We have two binary arrays of lengths N, M <= 1000. We want the minimum possible largest number in either array. We must replace all 0s with even numbers and all 1s with odd numbers such that no number is duplicated (even between arrays) and they both are increasing.

Notes:

A super naive dp is like dp(i, j, lastInumber, lastJNumber) which was too slow Then I tried something like dp(i, j, lastNumber) and if we place at i then say its parity is even to our last number, that means we must place lastNumber+2, if it isn't even we can place lastNumber+1. This TLEd so it is likely more states than it looks and also looking back I'm not even sure how this worked because what if we last placed a 4 and the parity at i is odd, that means we could potentially place a 3 but we aren't sure? Probably missing something. These were also bad because we carried the last number through the state and then returned it at the end, but we can basically drop a dimension by just making the return value have the number Anyway I found the easiest to implement solution to be bottom up dp for i and j which solves for placing i and j numbers (NOT placing ...i and ...j, usually bottom up is easier this way). And this dp STORES the smallest number for that, so we stuffed it into the return value So dp[0][0] = 0 our single base case, now we loop on states We could have come from i-1 as our last placement and we look up the smallest number in that case and can infer a new placement using that result, same with j I think top down was kind of weird for me because I was solving like dp(i, j) and looking to future states i+1 j+1 but we actually need to look to previous states i-1 j-1, that makes sense because the array gets built left to right so our recurrence relationship should require solving 0...i-1 first, not i+1...n-1

should implement to practice the dp actually, like the bottom up indexing, and also reread notes

Problem Summary:

We have N <= 1e9 and need to pick a random number from 0...n-1 but we have M <= 1e5 blacklisted numbers. Build the class.

Notes:

We cannot just keep repicking because if we have N = 1e5+1 numbers and 1e5 are blacklisted we will never find it. We also can't prestore the non blacklisted numbers as there are too many. Also we can't binary search for a number, check how many are blacklisted <= it, and then say "okay actually that means we picked this new number", for instance if 5 6 7 8 are all blacklisted and we picked 5, 1 is blacklisted so we actually picked 6, but that means we picked 7, and so on so it degrades in time and also might not even working since all of 5,6,7,8 would map to 9 Two options: 1/ We have some range [0, n-m] which is like the "real" range of indices we could pick from (not exactly numbers). Say we have N=10 but 2 are blacklisted so we want to pick 0...7. We pick a random selection from that say 6. We want the 6th non-hole number. Let's find the smallest X in range 0...n-1 where (X - blacklisted<=X) is 6. Now this equation could evaluate to 6 at a blacklisted number, but that means if we drop X by 1 we drop both X and the blacklisted<=X by 1 changing the output by 0, so finding the smallest just ensures we skip all blacklisted ones. This is logN * logB time 2/ Split the universe into two ranges 0...m-1 and m...n-1 some numbers in 0...m-1 might be blacklisted, these are holes, we can't pick them (there could also be blacklisted ones in region 2, sure, but not the point) for every blacklisted number in region 1 there is an un-blacklisted number in region 2 consider numbers 0...999 with 20 blacklists so if all 20 are blacklisted in 0...979 then all 20 in 980...999 are free if 5 are blacklisted in the left, 5 are free in the right so we're just going to pick any number in region 1 and if it's blacklisted it gets mapped to a free one in region 2 So it's O(1) pick after O(B log B) (I sorted, think we can avoid) preprocess but note we have to be a bit careful with our looping / construction to not accidentally loop over N or N-B in any way

re-read notes for both solutions and code for the remapping version since I accidentally had some bad loops the first time I did it, also note I sorted blacklist which allowed me to safely just assign every blacklisted value -> some right position, including blacklisted ones in the region m...n-1 which we technically don't need, but if we remove the sort we could avoid this just by skipping those out of range blacklisted ones

Problem Summary:

We have N <= 1e5 numbers all < N. A number is good if it is <= its index. We can rotate our array left any amount of times. Find the best rotations index (max score) or if a tie the smallest # of rotations needed.

Notes:

A number X is good in the index range 0...X This corresponds to up to 2 rotations ranges but it's kind of confusing to make that mapping / handle the indexing. But if we use a sweep line on the # of rotations then we can easily handle. Easiest way: First put the element on the back with i+1 rotations., definitely good here See how many more rotations we can allow, this could make this new number > N Mod it by N, now we have some rotation range [A...B] but A could be > B, if so, apply 2 separate sweep line adds

resolve because indexing was hard

Problem Summary:

We have N <= 1e5 numbers, we will delete one number. If the sum of odd indexed numbers is the same as even ones, we gain a point. How many points do we get across all possible deletions?

Notes:

Prefix/suffix on odds and events, flip the parity for the suffix

Problem Summary:

We have an integer number line and N different segments [L, R, V] which describe painting that section with color V. If two paints overlap they form a new paint {V_1, V_2}. We basically want to describe the painting in the minimal form, see the description

Notes:

The notable points are at any painting ending or start, I did the event based sweep line, used a prev tracker and also made sure to skip when the sum was 0 indicating an absent segment

prob just peek at implementation again since some of these sweep lines get tricky

Problem Summary:

We have N servers with weights and M tasks that each take some amount of time. Tasks are processed one at a time, the first at time=0, second at time=1, and so on. When a task enter the queue the lowest weight server, and if a tie, lowest index, picks it up and completes it in the tasks time. If no server is available we wait until one is. Find the server that processes each task.

Notes:

Basically simulate, we store the available servers sorted by (weight, index) and the ones that get released back into availability in (time, weight, index). Maintain a time variable and use that in the bookkeeping too.

Problem Summary:

We have an NxM (NxM <= 1e5) grid of numbers >= 0. It is surrounded by a border of -1s. No two adjacent numbers are equal. Find any 2d peak (one that is greater than its 4 local neighbors) in faster than N*M time.

Notes:

The 1d version of this is simple, we search for a point, call the value in that 1d array V. The left value is L and the right is R. If L < V < R then we can safely go right and eventually find a local peak (assisted by the -1 on the edge) If L > V > R we look left If L < V > R then we found the peak If L > V < R then either direction has it This is logN We could try to apply this procedure to every row one at a time, and check if it is a 2d peak, but this fails, there isn't a guarantee that the first peak we find with our binary search is also a 2d peak. Instead think of it like this: We pick some column C and find its MAX manually with an O(n) scan. It's now bigger than top and bottom layers. Call those U (for up) and D (for down). If our element V is > L,R then we find a 2d peak if V < L,R we have a divot and a valid 2d peak is on both the left subgrid and right subgrid if L > V > R we look to the left subgrid to find some 2d peak if L < V < R we look right Basically say L>V>R it is safe to claim there is SOME 2d peak on the left (not necessarily a global matrix maximum). Why? Well L was bigger than V, and L is going to be bigger than anything in our column C too, since V was the max of that column. And no element can be the same as its neighbors, so obviously the global max in the left region is going to be bigger than what is above and below it, and too the left. We are only scared about its right neighbor, which could potentially be on our column C, but it must be bigger than that too because our direct value L was bigger than in, and our left global max is at least as big as that This is like n log m We can also do n+m using some sort of quadtree search I didn't look into it EDIT: navneet made a post about breaking this problem, he talks about the quadtree approach more but also a root(m*n) sample and climb solution: https://www.takeuhigh.org/explore/breaking-leetcode/find-peak-ii/cross-method

re-read notes

Problem Summary:

We have N <= 1e5 numbers <= 1e9. In an operation we can pick two non-zero numbers and delete them, and add nums[i] % nums[j] to the end. What is the minimum length array we can form?

Notes:

First if we pair A and B and A < B we can do A%B which just deletes those 2 and puts back the A, resulting in deleting B only. We can then delete any number not the minimum. And with minimums we pair them together forming a 0 (potentially leaving one last odd minimum out). But can we do better? If we can form a number less than the minimum we can use that single number to nuke everything else. We can do this as long as there is some number in the array NOT a multiple of the minimum.

re-read notes just because it's an awesome problem

Problem Summary:

We have N <= 1e5 operations where we will update the frequency of a given ID by some + or - delta <= 1e5. After each operation, find the max frequency of any ID.

Notes:

SortedList holds (freq, id) we discard old and add new using a hashmap to track id -> freq count

Problem Summary:

Given 3 triangle side lengths, find if it forms a valid triangle, and if so find the interior angles

Notes:

Law of cosines, it's a 2/10 difficulty if you look up the formula or recently worked in geometry lol

Problem Summary:

We have an input graph, find the max node degree

Notes:

Just check each edge

Problem Summary:

We have an array of N <= 1e5 numbers <= 1e9, and a target <= 1e9. Find the # of subarrays where the target element is a strict majority.

Notes:

First turn it into a binary array to simplify, we want arrays where 1 is the majority. We can do lop off method, where the prefix stores the SURPLUS of 1s over 0s. Now we know how many prefixes we can cut off. I used a sorted container. There is some really weird O(n) variant by lee which is essentially my idea but somehow he does O(1) updates and avoids the sorted container, one of those weird tricks I think where if we only do certain operations in certain orders we can leave data stale and allow for O(1) updates: https://leetcode.com/problems/count-subarrays-with-majority-element-ii/solutions/7335037/javacpython-prefix-sum-on-by-lee215-gf47/ There's also some stack idea I did not look into that was O(n)

re-read solution, I was riffing on ideas in the code and I think a lesson is to explore each idea more because one of them was the right idea I just didn't investigate enough

Problem Summary:

We have N <= 1000 blocks each of size <= 1e5. We have a worker who can build a block in its size time, or pay split <= 100 time to divide into two. Once we build a block that worker retires. Minimum time to build all blocks?

Notes:

Same as https://leetcode.com/problems/find-time-required-to-eliminate-bacterial-strains/description/ (and that had worse constraints) so I'm just leaving the notes there. Except someone also listed an n^2 dp for this one, I did not look into it

Problem Summary:

We have N <= 1e5 strains of bacteria that each take <= 1e9 time to kill. A single white blood cell can kill a single strain, then retires. We start with a single WBC. It can split into two in splitTime <= 1e9. What is the fastest we can kill all bacteria?

Notes:

If we binary search on answer we need to know "can we kill all of these in time <= X" We should basically greedily split over and over, but the moment a strain requires an immediate kill, we allocate one of our WBCs to kill it, and not split At most we split logN times since we don't ever need more than N WBCs. And we can simulate basically killing each of the N manually, so the checker function is linear, forming log(max) * N. We can make the checker take log^2 time like this: # Yes, the checker can be O(log² n) instead of O(n). The idea: at each split step (there are at most log n of them), instead of popping strains one-by-one, you binary search on the sorted array to find how many strains are too large to survive another split. # so that would make it log^3 n Note that most solutions are using a heap and no binary search on answer, I think it's some idea of building binary trees and finding the most shallow depth, like if we split then we are bottlenecked by the slowest of the two children, I didn't really explore it. Also this is the same question as 1199 so I didn't write the notes for that here.

just re-read notes to refresh idea of the greedy

Problem Summary:

We have N <= 1e4 villages with E <= 1e4 weighted bidirectional edges. Each village has cost to open a well there. We want every village to have water, either via its own well or a connected set of pipes to another well. What is the min cost to supply water to every village?

Notes:

I claim we must fill the cheapest well. If we didn't, that village must get water somehow. It would be part of some component, and one village in that component would supply water. But our well is cheapest, so we could swap that more expensive well for our cheaper one. It is never worse to supply water to the cheapest well. Once we do this, we now add all pipes from the cheapest well to other villages. Since those pipe costs are basically indistinguishable from opening new wells at those locations. We repeat the procedure. I think another way to think about this is to imagine a hidden village 0 which has water and the well costs at other villages are basically pipe costs. Now we just want to find the MST which we can do.

re-read notes just to keep the idea fresh, but not too difficult

Problem Summary:

We have N segments where each segment contains a_i 1s and b_i 0s. We want to construct each segment, and then re-arrange them all, to form the largest binary number possible. Return this mod 1e9 + 7. Also the sum of all segments is <= 1e5.

Notes:

Each segment should be all 1s then all 0s. We can sort them by putting segments to the left if they have more 1s. If a tie, fewer 0s goes to the left. Edge case is if a segment is all 1s though, like 11 goes to the left of 11110. Also if A+B is > B+A then we should do A before B. It's kind of similar to jiangly's observation that s1^infinity is < s2^infinity if s1+s2 < s2+s1. Also if we do the A+B vs B+A sort and actually construct those strings in the comparator, the sort time becomes (n+L) log n where n is the number of terms and L is the total length of all terms. After we sort we can find the contribution of each digit using modPow. int function should TLE since I think it degrades to n^2 on large binary strings. There may be a faster way with bitsets or something where we are not bound by L, lakkshyag was looking at some stuff

re-read notes, mostly: -jiangly s1^inf < s2^inf if s1+s2<s2+s1 -A+B before B+A is a way to sort things -remember sorting time is (n+L) log n

Problem Summary:

We have N <= 1e5 numbers <= 1e9. In an operation we can increment a number. Find the min # of operations to make all even indices prime and odd indices non-prime.

Notes:

Pre-compute a sieve. We could manually iterate every number and check since prime gaps are small, or binary search to find next prime. We could also precompute with a suffix "next prime" array.

Problem Summary:

Given a list of numbers, find how many times a specific digit appears.

Notes:

Loop over numbers then strings, or use math

Problem Summary:

Given a number, print a required string

Notes:

just follow instructions

Problem Summary:

We are at the bottom left corner of a box in a plane and need to move to the top right corner, but there are N <= 1000 circles on the plane (can be overlapping, outside the box, etc). Can we reach the other corner without getting blocked?

Notes:

In general this is not complex. We can union circles together and see if any chain touches the top+bottom, left+right, top+right, or left+bottom. This is done with union find where we also add a "touches" set per parent component. To check if a circle touches an axis-aligned line segment, we want to compare it to the closest point on the line segment. For instance on the top edge of the box, if we are already below or above it, the closest point is the first one directly above/below us, and we check if our radius is at least that big. But if we are out to the side, like out to the left side, we would compare our distance to the leftmost point on the line segment, which we can find the euclidean distance and compare to radius. Now another issue, normally we union two circles if they touch but we actually only want to union them if they touch INSIDE the box. Imagine something like this: -----\_________/-- | / ( \ | I don't know if this drawing made sense but essentially it's a really big circle at the top and at the right, leaving the top right corner actually accessible. But these circles are big enough they would intersect outside the box. Unioning them would then falsely indicate we have a top+right blocking chain. A proof that we only care about intersection points inside the box is imagine we were walking through a room with big circular floor-to-ceiling walls everywhere. If we got blocked it would either be by a single circle which covers 0,0 or the top right coordinate, which is handled by our union find already saying that chain was found, OR by some point those two walls intersect at. So we actually only need to check the up to 2 intersection points between two circles, not all overlap points. There can be 0 intersecting points if the circles are too far, 1 if the radiuses sum to the exact distance between centers, and 2 otherwise. To find 2 we basically find the chord line, get a perpendicular line, and walk up and down until we hit them, I kind of used a geometry template, it also returned floats so I guess could be imprecise. Only if at least one intersection point is inside the circle then we union them.

re-read notes, mostly takeaway is the union concept, circle touching line segment, and I guess awareness of two circles intersecting points template

Problem Summary:

We have N <= 1e9 sheets to paint. We also have C <= 1e5 colors where we have for each color c_i <= 1e9 paint meaning we can paint that many sheets. We want to find the # of ways to paint the N sheets, using exactly 2 colors, such that the colors each form two contiguous regions like BBBBRR.

Notes:

Say we have to paint 10 sheets. We consider all colors as if they were the left color (so we won't double count these). Say our color has 5 paint. We want to know how many other colors we could combine this with, but the actual # of combinations. Well some other colors could allow us to use all 1-5 quantities of our left color. For instance if another color had 20 paint we clearly have enough of that to fill out the rest no matter what if we use 1, 2, 3, 4 or all 5 of our left color. We find how many of these colors there are (it's just the # of colors that have >= n-1 paint) and we know we can combine those all with all 5 of our current color. Don't forget to exclude our current color 5 from the count, if 5 happened to be >= n-1, to prevent from pairing it with itself. Okay but what about colors that could only partially pair? For instance if we had 8 of another color, we could use 5, 6, 7, or 8 of it in junction with 5, 4, 3, or 2 of our left color. Well we know the min of another color we require is 5 (to pair with our left color 5) and the max is n-2. We find all the colors that exist in this range 5...9, say we have these other options: 5, 7, 7, 8 All of those form partial pairings with our 5 meaning we can use some quantity of our left color 5, but not all of them. For instance the 7 we could use our left color of 3, 4, or 5. The 8 could use our left color of 2, 3, 4, or 5. The actual amounts of these are just each of those colors, minus 4, and the 4 is derived from the minimum we require of another color (5), minus 1. We use binary search and prefix sums to handle this summing, also remembering to exclude our left color if it happens to fall into that partial l...r range too.

re-read notes, takeaway is for a color consider how many other colors we can pair it with, do some casework and probably write out cases to get a sense of how the math works

Problem Summary:

We have N <= 1e4 numbers <= 7e4. For any positive integer g, the beauty of g is (g * the # of strictly increasing subsequences with a gcd of g). Find the sum of beauties for all g.

Notes:

We want to know the # of strict increasing subsequences with a GCD of X, for all X. First let's actually find the # of strict increasing subsequences all divisible by X. If we do this for all X, we can do mobius inversion style inclusion-exclusion to convert it to GCD. For a given factor say 5, we will track the # of subsequences all divisible by 5, ending in [5, 10, 15, ...]. Across all factors X this is N log N size total due to harmonic series. We loop over numbers, for each number loop over its factors. Each factor would contribute to a different factor -> dp array bucket. We need to support range sum and point update to update the dp. I used a fenwick tree with the dp array. In total we do n * d * logn work roughly.

re-read notes, best parts were: -using fenwick tree to ac in python since my seg tree was slow constant factor (probably could be optimized) -maybe re-read the mobius inversion code at the bottom to see how I converted from "divisible by X" -> "gcd is X"

Problem Summary:

We have N <= 2e5 numbers <= 1e9. Find how many pairs (i, j) exist where a[i] * a[j] = j - i

Notes:

Heavy/light query processing: call B the ceiling of the square root of N If a number X is >= B it can only be multiplied by a number <= B. So we could just manually check all the previous indices in rootN time. We also should do a forward pass to look ahead. Note the edge case we don't double count pairs of (B, B). If a number is <B then it could multiply by a number >= B, or one <B. We already did the first case. For the second case we can just iterate on all numbers from 1...B-1 and check, also in rootN time.

re-read notes to keep idea fresh

Problem Summary:

Given a SQL table of posts we need to find all users who had a 7 day period in february 2024 with a posting frequency at least theirs in all of feb 2024

Notes:

A bunch of subqueries to get: -the posts from feb -all 7 day window starting dates with a generator -posts per user per window -average frequency per user in feb -now we combine all of these to find it

Problem Summary:

We have N <= 1e5 numbers <= 1e9. And Q <= 1e5 queries [l, r, k, v] where for all numbers in range l, l+k, l+2k, ... up to at most r, we multiply that number by v then apply a mod. Find the XOR of all numbers after all queries.

Notes:

For queries with a K >= root(N) it only takes rootN time to apply the updates manually, do so. For other queries, we might have things like [1, 4, 7, 10, ..., 100] which is more than rootN indices to update. Note we have different groups based on the jump size and the residue. So [0, 3, 6, ...] is the same jump size different residue. If we have rootN jump sizes (the small ones) each takes combined N indices so that's N root N. We could map (jumpSize, startingIndex) -> a sweep line of the size of the # of indices in that residue class. Then when we get a query, we use math to apply a mod mult at sweep[l] and a mod inv at sweep[r + 1]. A few notes about this: 1/ We don't need to precompute all the indices for each residue class, rather we can just have the sweep lines. We set sweep lines to all 1s (identity for multiplication). We can use a nested defaultdict(lambda : 1) or actually allocate the 1s. We apply the sweep gain at the corresponding index for `l` in the query, but r is not necessarily where we lose. Cause it might not be part of the residue class. Like go from indices 33 to 50, jumping by 5. We want to apply a sweep loss at 53 not 50. To find this we can take the difference which is 17, floor divide by jump size to get 3, then re-add 3*5 to 33 to get 48 which is the last position we actually gain. Then one more for the loss position (standard sweep line loses at r+1 type of thing). 2/ We could have the map I suggested above (jumpSize, startingIndex) -> sweep line of just those indices, or we could do a map of jumpSize -> sweep line of size N. Basically squishing all the sweep lines together. This was more performant and let me pass in python even though it's the same complexity. It just makes the aggregate trickier at the end. To aggregate we loop over jump sizes and starting indices and basically treat that N sized sweep line as a bunch of separate lines.

should re-implement to practice the nested sweep line stuff, some of the index math, and ability to understand the heavy/light child concept

Problem Summary:

We need to find customers that are churn risks which fits several rules, find those customers

Notes:

I think there are better ways but I used a distinct on trick to get the first value from a group (using our custom ordering) which helped

Problem Summary:

We have an MxN M,N<=50 grid of numbers and another one of a smaller size of numbers and letters. We want to find if the smaller pattern matches with the larger grid. We require a bijection of numbers<>letters for the pattern.

Notes:

Brute force, check all n*m top left cells and run another n*m sized pattern check. Bijection means we need both mapping directions enforced. Also numbers can be in the pattern instead of letters so handle those separately.

Problem Summary:

We have an H,W <= 1e9 grid. We jump right, then down, then right, ... and so on. The grid wraps in both directions. Our right jump is R and down jump is D. D, R <= 1e9. Do we cover all tiles?

Notes:

First the 1D variant. If we jump right by R and the width is W, do we hit everything? One way is to figure out when we first hit 0 again. We do this after lcm(W, R) steps. So width 10 and we jump right by 8, at lcm=40 total steps we return to 0. Divide lcm(W, R) by R to get the # of actual jumps we make. So lcm(W, R)/R is the # of jumps we make before we repeat. This must be = W to work (otherwise we cycle before hitting every cell). This is also transformable: gcd(a, b) * lcm(a, b) = a * b lcm(a, b) = a * b / gcd(a, b) ((W*R) / gcd(W, R)) / R = W W/gcd(W, R) = W gcd(W, R) = 1 I think this is also kind of intuitive, if our jump and width had a shared factor, we could never land on a number not divisible by the factor? something like that. anyway in the 2d variant we have separate right and down requirements to repeat. Say we need 10 right moves to return to column 0, and 8 down moves to return to row 0. We would think we need lcm(10, 8) = 40 pairs of moves to repeat (which is 80 moves). However this is the # of moves to repeat with the *same parity* meaning our first move after 0,0 is going right. We can actually repeat earlier: col0 col1 col2 col3 col4 col5 +-----+-----+-----+-----+-----+-----+ row0 | 0 | | | 1 | | | +-----+-----+-----+-----+-----+-----+ row1 | 3 | | | 2 | | | +-----+-----+-----+-----+-----+-----+ row2 | 4 | | | 5 | | | +-----+-----+-----+-----+-----+-----+ Move 1: right+3 → (0,3) Move 2: down+1 → (1,3) Move 3: right+3 → (1,0) (wraps) Move 4: down+1 → (2,0) Move 5: right+3 → (2,3) Move 6: down+1 → (0,3) ← REVISIT cell 1! Move 7: right+3 → (0,0) ← REVISIT cell 0! Why does this happen? We are revisiting 0,0 but at a different parity (next move will be down). It would take 2x moves to revisit at 0 with the same parity. But the issue is we are going to repeat the same set of cells, so we don't actually see 2*6 unique cells. I believe there is no closed form way to check when we hit 0,0 early but at the wrong parity. Remember when we get the full cycle with our 2 * lcm of both cycles, each step visits a unique STATE, not a unique cycle. A state is (row, col, parity). Two different states can land on the same cell. We also need the independent row and column cycles to enumerate the full width and height. I don't fully get why this is...

re-read notes, refresh: -how to compute if we loop on a 1d plane -ideas about the 2d variant, like checking the lcm of both individual lcms, times 2, equals a STATE re-visit not a cell revisit don't worry about fully getting it since I can't airtight prove at the time I solved

Problem Summary:

We have a binary string of length N <= 2e5 and a single position p. We can flip any range l...r as long as it contains p. Find the min # of moves to make the entire array into the initial value at p.

Notes:

We have a leftmost and a rightmost position number that are opposite from the number at p. We must flip those, inverting everything in-between (including the number at p). Every time we face a different number, we have to invert again. We can combine left and right sections so we take the max of those.

Problem Summary:

We have an array of numbers and take turns removing one from a single number at a time. The game ends when there are only 0s left (if you cannot move you lose). We also have a special power that replaces our turn and replaces every number with K, once. Can we win?

Notes:

either sum of all is odd or sum of n*k is even

Problem Summary:

We have N <= 100 nodes on a graph with E <= N^2 directed edges. Find how many paths from 1 to N exist after K <= 1e9 moves.

Notes:

Matrix exponentiation, state is the # of ways to end at each node, sized N, and we transition K times, n^3 log k

re-mind solve

Problem Summary:

We have N <= 1e5 houses, each house has a distance to go forward to the next house and backwards to the previous. Also the houses are circular. Answer Q queries for the min distance to visit each house in the specified order.

Notes:

We basically walk left or right, check both

Problem Summary:

We have N <= 1e5 numbers <= 1e9. And K <= N. We want to find the longest subarray length where at most K numbers occur more than once.

Notes:

Standard variable window, shrink while we have too many repeats

Problem Summary:

We have N <= 1e5 numbers <= 1e9. And K <= 1e9. Find how many subarrays have an XOR >= K.

Notes:

We can do this with a trie on prefix XORs. A trie is able to tell us, given a value, how many other values in the trie can we XOR this with to get a number >= X. We can also achieve the same complexity solution without a trie. I didn't fully look into the solution, but it is something along the lines of iterative over all log(max) bits, for each bit iterate over all numbers in the array, find some sort of "branching" point where we need a prefix starting with a certain thing, and count those up: https://leetcode.com/problems/subarrays-with-xor-at-least-k/solutions/7270450/iterative-solution-no-trie-by-westxrn-t5rm/

implement bit trie with the advanced function required

Problem Summary:

We have N <= 1e9 intervals from [L, R] <= 1e9. Find the max # of a subset of intervals such that at least one interval intersects with all of them

Notes:

For a given range, we can search how many touch it. Easiest way is to search how many do not touch it (their R is less than our L, and vice versa), so minor inclusion exclusion I think we could do some two pointers with sorting to check as well but not sure

quickly re-mindsolve and implement using bisects

Problem Summary:

We have a height x width (height, width <= 100) grid. We start at the bottom left as a robot. We need a move(steps) function which moves and if it hits a wall it turns left first, basically walking the perimeter. The # of steps can be big. Also we need to get the position and direction of the robot at various times.

Notes:

Cleanest way is O(1) everything. We track our position as a number along the perimeter. To move we move steps and then mod by perimeter. To get the position we can check if we are on the bottom strip, else right edge, else top edge, else left edge. For direction we could just use where we are too, with the edge case at 0,0 we face right if we just started and haven't moved yet, otherwise we face down

honestly the code is clean should look at it

Problem Summary:

We have N <= 1000 numbers all <= 1e9. And K <= N. The array is cyclic. We must partition it into at most K partitions. The score is the sum of max-min for each partition. What is the max score?

Notes:

1/ O(n^3 * k) super naive - TLE A naive version is to try all N rotations. Then for each rotation we can run a dp(i, partitionsTaken) and loop on N future options. This is n^3 * k. 2/ O(n^3) improved DP - TLE We note a better DP than the super naive one is dp(i, partitionsTaken, state). State is 0 1 or 2 depending on if we have scored the +max, -min, or neither. It's sort of like these open-interval DP ideas. But this is still n^3 time. 3/ O(n^2) improved DP + cycle trick - passes We note that our global minimum would only ever need to be on the boundary of a partition. Otherwise we stand to gain no extra minimum if we move past that. Seems a little bit not fully proven to me cause I have some concerns about how the max interacts with that. Also this observation should work for global max. So we do the normal state DP but only on two arrays. 4/ O(n^2 log MAX) alien trick - passes in C++ with bottom up We can alien trick this. We search for the largest y with >= k partitions. Our DP wants to maximize partitions in the event of ties. We update result every binary search loop, not taking the max of the res each time, just overwriting. For a given y then the dp becomes the same dp(i, state) which is O(n). We run this in N rotations. Note our alien trick here also requires an extra case where the natural DP with a given y penalty results in <k partitions. This is acceptable because we can use at most K partitions, so we should accept that answer too. Otherwise no matter the penalty we never find one that uses >= k partitions. 5/ O(n log MAX) alien trick - passes The above but we only run it on two key rotations. 6/ O(n^2 log MAX) alien trick - didn't test We do only the two key rotations but for each one we do the naive dp(i) and loop on N possible J's. 7/ O(n^2 + n k log n) dnc dp - passes in C++ A normal DNC dp on the array should be n*k log n. With n^2 to precompute all the costs l...r for max-min (can avoid this though with mo's trick I believe, or just sparse table and live query). We run this on only 2 rotated arrays. 8/ O(n*k) - advanced DP, passes in Python dp(i, partitionsUsed, state, wrapState). The same but we track the state of the first every partition too, so if we only took +max from there and -min from the end we can coalesce them. Basically n*k*3*3 Also note I think the way I'm doing aliens can be perfectly mirrored: This finds the smallest y where seg <= k. At termination, right is that value. Then res = f(right).val + right * k. It's the mirror of our approach: | | Ours | Theirs | |----------------|----------------------------|-----------------------------| | Tie-break | more partitions | fewer partitions | | Search for | largest y with seg >= k | smallest y with seg <= k | | Binary search | l = 0, r = max | left = -1, right = INF | | Record answer | when seg >= k, move l up | when seg <= k, move right down |

should re-read all notes, keys to remember: -cyclic problems often can have some smart rotation -crazy dp idea to track the state and wraparound state -probably re-read the code I wrote in python for dp(i, state) because it felt a bit too simple but worked -re-implement aliens + naive n rotations in C++, can use top down dp(i, state) should pass. Aliens make sure I can implement the dp tiebreaking and the binary search boundaries logically, understand when and how we update result in binary search, and also realize the "at most k partitions" causes a minor difference in how we aliens too

Problem Summary:

We have N <= 1e5 numbers <= 1e9. We want to have the max # of local peaks (0 and n-1 can't be). In an operation we can increase a number. Find the min # of operations to get max local peaks.

Notes:

If N is odd there's only one option for local peaks, at indices 1, 3, 5, ..., so just add those up. If N is even we basically can have a gap of 2 somewhere: # 56 | (97) 40 (79) 74 45 (101) 4 (84) | 102 56 and 102 can't be peaks as they are edges. We need to pick 4 out of the center 8. Also note the gap could go at the start or end, like 56-97 could be a gap or 84-102. We can do knapsack dp(i, skippedBool) and either we take and go to dp(i + 2, skippedBool) or we skip once and go to dp(i + 1, True) which feels a little bit too simple but it works. Just look at code and think about this skip concept. In contest I did it with a prefix and suffix though. pref[i] is we take i, i-2, and so on. suff[i] is we take i, i+2, and so on. Now I loop over all gapIndex positions. But not we can't start the gap at i=1 or i=n-3 because that would be like 56-97-40 is a gap which we cannot do.

re-read notes, I guess idea of the knapsack dp actually working and being elegantly simple, also be more careful cause in contest I assumed the gap could only go in two places but it can go anywhere

Problem Summary:

We have N <= 5000 numbers with abs(num) <= 1e5. The array is circular. In an operation we can increase a number by 1. We want to find the min # of operations to get K <= N local peaks (0th and last index wrap around for their peak checking). A peak is strictly greater than both neighbors. Or return -1 if not doable.

Notes:

dp(i, peaksLeft, didIncrementFirst) is n * k * 2. Worked top down in C++. We can optimize space by dropping the n dimension but it's annoying. We have two dp arrays to track and we need access to the previous 2 layers. Easiest way might be to use the mod trick lakkshyag talked about. Like the "rolling" trick to re-use dps. And instead of two arrays for didPickFirstIndex and didn't, maybe just combine everything. But still seems annoying to implement. We could also drop the 2 space dimension by just doing 2 cases, we allow the 0th to be used but not the last, and vice versa. We can also do alien trick in n log MAX. Observe f(k) is the cost to make k peaks. It is concave since each successive peak is at least as bad. Thus we use WQS binary search. Didn't implement or fully investigate. We can also do n log n with a backup algorithm. Didn't really look into this either: https://www.takeuhigh.org/explore/breaking-leetcode/min-ops-k-peaks/greedy-with-undo It uses heaps and a DLL

re-read notes, and re-read the top down C++ notes here: https://www.reddit.com/user/leetgoat_dot_io/comments/1scxgix/c_dp_ramblings_for_myself/ Pasted here: -global array goes into bss, zero-paging read only, allocation happens only when we try to write at a per-page level. note the 0 page trick only works for globals, on the stack an un-intialized array gets garbage vals -put an array into the function now its on the stack for that fn call = blow up -put a vector, thats fine, only struct goes into stack, big data onto heap -ordering of arrays matter as they are row-major contiguous, put the dimension that moves around a lot at the end. same thing matters with looping orders when we fill out arrays. matters for bottom up, top down to still be discovered -to reset the shared global we can: memset, but takes the entire flat array time loop over only the cells needed in the problem, takes time based on problem inputs use a generation counter, O(1) reset but takes 2n memory -nested vectors screw us. we are making n*m*... new calls which is lots of allocations. every access call is slow because now we're dereferencing multiple pointers. just lots of overhead.

Problem Summary:

We have N <= 1e9 and need to find how many numbers <= N are the sum of two triple powers a^3 + b^3, with at least two unique combos (a, b) and also a <= b

Notes:

a and b are at most N^(1/3) so loop on those combos for N^(2/3) total time, store achieved numbers in a counter to verify >= 2 combos