🧠 Mindsolves

Problem Summary:

We have N <= 2e5 numbers A[i] <= 1e9. And a k <= 1e9. We need to create a set of numbers B such that all multiples of each B[j] that are <= k are in A. And all numbers in A contain a divisor in B.

Notes:

The smallest in A that has no divisors in B, must be chosen separately. We choose that to put in B and loop over all multiples marking them as accounted for in A. Also if one of those multiples doesn't exist in A we have an impossible situation. We repeat this process for all smallest numbers over and over. WRONG: Remember we mark multiples until we fail to have that multiple in A, so at most we can mark up to |A| times. Because we might be marking multiples that were already marked. A loose bound looks like we would try all numbers 1, 2, 3, ... N and their multiples up to 1e9 but somehow the complexity amortizes I don't have an airtight argument for this Some other ideas that failed: All primes must be chosen (unless 1 can be chosen). Then go small numbers to large. If the first number had no prime factors picked then this number must be picked. But future numbers could have no primes picked but still a normal factor picked. Like [4, 8] we pick 4 but at 8 it's not enough to just check primes we must check factors so this does not work.

Refresh on the amortized idea of harmonic series here and think about failed ideas

Problem Summary:

Given a tree with a weird structure / format, return the sum of all root<>leaf paths.

Notes:

Use the root=1, left child = 2*i and right child = 2*i + 1 system to handle the weird format. I did dfs(node, prefixSum) as we descend and I used a global result to update the answer when I hit a leaf. We can avoid the global by making the DFS return a value, GPT: "Yep. You can make DFS return “sum of all root→leaf path sums in this subtree, given that we start at this node”." Like this: def dfs(i, prefixSum): if i not in idxToNode: return 0 val = idxToNode[i] % 10 prefixSum += val left, right = 2*i, 2*i+1 if left not in idxToNode and right not in idxToNode: return prefixSum return dfs(left, prefixSum) + dfs(right, prefixSum) return dfs(1, 0) So I guess the DFS returns the "this node to leave path sums" We can do it without the prefixSum parameter too: GPT: If you really want DFS to not carry a prefix, you can return two things from each node: leafCount: how many leaves are in this subtree sumFromHere: sum of path-sums from this node down to leaves including this node’s value Then parent can combine without needing a prefix: def dfs(i): val = idxToNode[i] % 10 left, right = 2*i, 2*i+1 hasLeft = left in idxToNode hasRight = right in idxToNode if not hasLeft and not hasRight: return (1, val) # 1 leaf, sum of paths (just val) leafCnt = 0 childSum = 0 if hasLeft: c, s = dfs(left) leafCnt += c childSum += s if hasRight: c, s = dfs(right) leafCnt += c childSum += s # every path below gets +val once return (leafCnt, childSum + val * leafCnt) leafCnt, total = dfs(1) return total

Re-read the concept for DFS returning a value instead of using a global and understand the implementation Re-read the second solution without the prefix sum parameter too

Problem Summary:

We are given X, Y <= 1e9. We need to find a K <= 1e18 where (x + k) + (y + k) = (x + k) ^ (y + k) or show it is impossible.

Notes:

This is saying A + B = A ^ B. This only happens when A & B = 0, no bits can be shared. If A=B we cannot do anything as they will always be the exact same. Otherwise, set the bigger one to some higher power of 2 which will share no bits with numbers below it.

Remember the clean solution and your struggle with trying to greedily iterate from msb or lsb. Remember the simple A + B = A ^ B when no two set bits are shared.

Problem Summary:

We have a SQL table Triangle with columns x, y, z that are numbers. Report all rows that can form valid triangles + an extra column Triangle with "Yes" or "No"

Notes:

-Triangle inequality: (x + y > z) and (x + z > y) and (y + z > x) -To add a column we use CASE / WHEN / THEN / ELSE / END AS

remember triangle inequality

Problem Summary:

We have a tree of <= 2e5 nodes. We need to make all edges directed. An ordered pair of nodes (u, v) is good if we can reach v from u. Is it possible to make the edges directed and have exactly N good pairs? Construct a solution if so.

Notes:

Note that by default all N-1 edges add 1 reachable section, so we just need one more. Structures like A>B>C>D add a lot of good pairs (too many) since we can reach things. Our tree must alternate directions, like: A v. v B. C ^^. ^ DE. F To prevent ever having too many good pairs. However we need one more good node than normal, so a single connected chain like A-B-C would become A>B>C, provided B cannot reach any other nodes. It is okay if C has other children and A connects to other things too. D < A > B > C < F v E So we just need to identify a node C by checking if any node has 2 edges. Then make another node next to it like A, the root, and construct the solution.

Remember the idea

Problem Summary:

We have a string S of size <= 1e6 and up to Q <= 2e5 other strings (with total length at most 1e6). For each string answer how many more letters we need to append so that it is not a subsequence of S.

Notes:

To quickly check if a string t is a subsequence of s we use nxt[i][char] to only spend O(t) time. Now if we are a subsequence we know where we ended and then we use worst[i][c] to find the furthest right character to jump to. My implementation for worst[i][char] was easier if it corresponds to a suffix, not including `i`. Same with nxt[i][char]. Then I compute an O(26) size first[char] array to figure out where to start. But we also need a dp[i] to stack on top of the worst chains so that a query is O(1) after the O(t) portion.

Refresh mindsolve on this

Problem Summary:

Check if 3 points are distinct and not on the same line

Notes:

We can compare slopes and to avoid fractions, we want to simplify X/Y. This can be simplified while they share a factor, so divide both by their GCD.

Mind-solve the slope hashing

Problem Summary:

Call f(num) the number of trailing zeroes on num!. How many numbers X, have f(X) = a given K? K <= 1e9.

Notes:

Binary search on answer, use legendre's

Just remember how to solve this

Problem Summary:

Find the # of trailing zeroes in N!. N <= 1e9.

Notes:

A trailing 0 is formed by a 2*5. There will be fewer 5! than 2! so how many factors of 5 are there. Amount of #s divisible by 5 we add 1 to result for each. Repeat for 25s, 125s, and so on. log(n) time

Remember legendre's formula

Problem Summary:

We are given K <= N <= 1e6. Construct a sequence of at most length 25, where no subsequence adds to K, but we can create subsequence sums for all other 1...N.

Notes:

A standard summing problem would give 1 2 4 8 ... until our total sum is >= N. First construct up to K-1: 1 2 4 8 16 ... then some number that puts us at K-1. Now we can make 1 to K-1. We need K+1, the only number that can be placed is K+1. Now we can make 1 to K-1 and K+1 to 2K. We need 2K+1 so we place that. We might think we can place all numbers up to 4K+1 now, but we cannot make 3K+1 as it is a hole. We place 3K+1 and we might think we can make up to 7K + 2 but we cannot make 6K + 2. I kept doubling the hole and placing that and it worked but also needed some edge case handling. Wasn't the cleanest solution.

Stay vaguely aware of how I solved this

Problem Summary:

We have a string s of size <= 5000. We need to form a string of size k <= 5000. We can delete the last letter of s, or do s = s + s. After infinite operations, find the smallest lexicographical string we can form.

Notes:

My claim is that we should delete some amount of letters, duplicate until we exceed size K, then trim the remaining edges. If we were to remove some letters, duplicate, and remove more, then duplicate again I think it would be provably worse, need to think about it more requires some focus. But Jiangly pointed out a good equivalence, s1^infinity < s2^infinity means s1 + s2 < s2 + s1: https://codeforces.com/blog/entry/91381?#comment-805703 Consider ABCD (don't worry about the actual letters for now), if we cut off D then duplicated: ABCABC And if we claimed we wanted to cut off more and duplicate again: ABCAB ABCAB It's sort of like claiming AB is better than ABC we should have just cut off more to begin with. So our string s with some ends chopped off, plus more of the start of s, is better as an infinite sequence if that is less than s itself. With jiangly's observation we can just test all prefix lengths duplicated and see which is the smallest. Since constraints are small we can do n*k.

Remember the string equivalence

Problem Summary:

Check if a 9x9 partial filled sudoku board is valid (not necessarily solveable),

Notes:

Scan over rows, columns, and boxes. Use box hashing const rowGrouping = Math.floor(rowNumber / 3); // rows 0-3 -> 0, 4-6 -> 1, 7-9 -> 2 const colGrouping = Math.floor(colNumber / 3); // cols 0-3 -> 0, 4-6 -> 1, 7-9 -> 2 // if we are in rowGrouping 0, we know we are in boxes 0, 1 or 2 // if we are in rowGrouping 1, we know we are in boxes 3, 4, or 5, etc // our first possible box we could be in, based off of the rowGrouping, is (rowGrouping * 3) // the colGrouping then provides an offset to increment by const boxNumber = rowGrouping * 3 + colGrouping;

refresh box hashing (for interviews)

Problem Summary:

Return true if the number X is a palindrome

Notes:

To do with just math we can "pop" the last digit by mod 10 and build out a reversed number, then compare those 2

Mindsolve the math reversal technique

Problem Summary:

We have numbers, N, A[i] <= 1e5, can we split them into groups of size K where every element in each group is distinct?

Notes:

First, make sure the most frequent number occurs <= groups times (otherwise it is impossible) and also make sure n % k == 0. Imagine the frequency of our numbers is like a histogram, taller bar means a more frequent element. O OOO OOOO Frequencies are [1, 2, 2, 3]. Say we are trying to make 4 groups of size 2. The slots will look like this. X|X|X|X X|X|X|X Simply lay the most frequent element (3) into three groups: X|X|X|X O|O|O|X Now lay the next most frequent (2). Here I use lowercase o to show the second layering. o|X|X|X O|O|O|o And repeat. Of course we can fill out all the slots, because no frequency is >4.

Mindsolve and review the notes

Problem Summary:

Given a number n, we have 1, 2, 3, ... n. Partition into 2 sets of equal sum and print them, or determine not possible

Notes:

Keep taking from the left until we overflow, then subtract We are guaranteed to be able to make all sums of 1 using just 1 So when we add a 2, we can make 2, and all previous sums added (up to 3) Now when we add 3, we can add it to all previous ranges, so up to 6, and so on Eventually we will overflow the target by some amount < the number we just added at the end, so we can remove that single number

Mindsolve this

Problem Summary:

Given an array of numbers, A[i] <= 1e5, N <= 3e5, and Q queries, Q <= 3e5, support point updates and find the largest alternating subsequence sum A + B - C + ... The input array is a permutation.

Notes:

A segment tree where each node stores the largest sum where the first and last elements were added, added and subtracted, subtracted and added, and both subtracted. Note the subtracted then subtracted base case for a leaf node is -1 * value, not NINF. There is another perceptive solution. Given the input is a permutation all numbers are local maximums or local minimum (bigger or smaller than both neighbors, ends of the array count as -inf). The length of our sequence should logically be odd. Odd index should always be local maximums, if not, it implies there is an adjacent neighbor bigger, we should take that instead. If we had an odd index not be a local max we could basically take its adjacent neighbor instead as an odd index and gain more. If that neighbor were an even index we should delete that and our current odd index to not lose to our contribution (need to think about this more). But essentially all local maxes and local mins should be taken. (also need to think about this). And to support swaps we can do bookkeeping on this.

Remember this application of segment tree, also stay vaguely aware of the local maximum and minimum idea

Problem Summary:

We have N ranges [L, R]. N <= 3e5 R <= 1e9. We need to select K ranges that all overlap, how many ways can we do this? K <= 3e5.

Notes:

First note trying to pick a range and see how many ranges touch that, doesn't work, as if two ranges touch our selected range, that doesn't mean those 2 overlap. Instead we go by coordinate point, starting left to right. We can pick some amount of ranges that already started, but need at least 1 new range starting here to avoid double counting. We can try taking 2 ranges starting here, 3, and so on, as it amortizes. Combinatorics. We pop from a heap or multiset on the left as well as we slide, for ranges that already ended.

Mindsolve this