Here are a few notes breaking down how I approached each problem. I’m mainly sharing these to document my thought process and the logic behind the code. It’s also a way to test myself — as the saying goes, ‘If you can’t explain it simply, you don’t understand it well enough.’ Plus, if I come back to this in three months, read my own notes, and they don’t immediately jog my memory about the problem, then I definitely didn’t understand it as well as I thought. Spoiler alert ahead if you haven’t solved these yet.
I am forcing myself to solve the problems in ascending ID order now, so I won’t just fool around with easy problems and trying things here and there without diving deeper.
Current progress: solved 458 / 988 | at: #229
(I really like these level icons before it refactored to those polyhedrons on the card)
228
Let \(v_k\) and \(v_{k+1}\) be the polar angles of two vertices of the regular polygon \(S_n\): \[v_k=\frac{\pi(2k-1)}{n}, \quad v_{k+1}=\frac{\pi(2k+1)}{n}.\] For a regular polygon centered at the origin, the outward normal angle of the connecting edge is the average of these vertex angles: \[\text{Normal Angle}=\frac{v_k+v_{k+1}}{2} = \frac{2\pi k}{n}.\] Since a full circle is \(2\pi\), the direction of the \(k\)-th edge is uniquely identified by the fraction \(k/n\).
By the properties of the Minkowski sum for convex polygons, the boundary of the resulting shape is formed by the union of the original edges. Edges sharing the exact same normal direction merge into a single extended edge, while edges with distinct directions form separate sides. Therefore, the total number of edges in the resulting Minkowski sum is exactly the number of strictly unique fractions \(k/n\) across all given polygons.
227
Let \(d\) be the shortest distance between the two dice, where \(0\leq d \leq 50\). In a single round, the change in distance \(\Delta d\in \{-2, -1, 0, 1, 2\}\) occurs with probabilities \(1/36\), \(8/36\), \(18/36\), \(8/36\), and \(1/36\), respectively.
The expected number of remaining turns to reach the absorbing state, \(E(d)\), satisfies the recurrence: \[E(d) = 1 + \frac{1}{36}E(d-2)+\frac{8}{36}E(d-1)+\frac{18}{36}E(d)+\frac{8}{36}E(d+1)+\frac{1}{36}E(d+2).\] Multiplying by 36 and rearranging the terms yields the linear equation: \[ E(d-2)+8E(d-1)-18E(d)+8E(d+1)+E(d+2)=-36.\] Applying the absorbing state \(E(0) = 0\). The final expected value, \(E(50)\), can then be computed by reducing the matrix via standard Gaussian elimination.
224
Similar to 223, we could try finding the divisors for \(a^2+1\). However, since \(N\) is larger and \(a^2+1\) doesn’t factor cleanly like 223’s \(a^2-1\), we can bypass factorization entirely by utilizing Barning’s matrices.
These are three specific matrices that generate the “Tree of primitive Pythagorean triples” from a single root. For instance, the root for \(a^2+b^2-c^2=0\) is \((3, 4, 5)\). For barely obtuse triangles, the equation is equals \(-1\) instead, giving us a starting root of \((2, 2, 3)\).
Here is the nice thing: the matrices do not care what the equation equals; they only preserve the left side. Therefore, we simply start at \((2, 2, 3)\), generate new triangles using the three matrices, and stop when the perimeter exceeds the limit. Remember to normalize sides and track what we have seen.
Last question: Can we do this to 223? Theoretical, yes; practical, no. Problem 223 does not have a single node as the root of the tree. If you plug in \(a=1\), the equation becomes \(1+b^2=c^2+1\), meaning \(b=c\). This creates an infinite family of valid starting points \((1, b, b)\). Because of this, it forms a massive, disconnected forest, making a simple graph traversal impossible.
Though, if you really want the \(a^2+1\) factorization approach, note that for some prime \(p\), \({a^2\equiv -1 \pmod {p}}\) gives us \(a^4\equiv 1\pmod p\). That is, all the prime factor of \(a^2+1\) must be either 2 or in the \(4k+1\) format.
223
Rearrange the given equation: \[a^2+b^2=c^2+1 \Longleftrightarrow (a + 1)(a - 1)= (c + b)(c - b).\] Let \(u=c+b\) and \(v=c-b\), Then \(uv=a^2-1\). Solving for \(b\) yields: \[u-v=(c+b)-(c-b)=2b \Longrightarrow b = \frac{u-v}{2}.\] For \(b\) to be an integer, \(u\) and \(v\) must have the same parity.
Given the perimeter limit \(N\), our bounds become:
- Perimeter constraint: \(a + b + c \leq N \Rightarrow u \leq N - a\)
- Side constraint: \(a \leq b \Rightarrow 2a+v\leq u\).
Finally, iterate \(a\) up to \(N/3\). For each \(a\), generate the divisor pairs \((u,v)\) of \(a^2-1\) utilizing the combined prime factorizations of \(a-1\) and \(a+1\), counting the pairs that satisfy the constraints.
222
I realized this is actually a 2D packing problem, because it reminds me of this Suika Game that went viral a few years ago. Intuitively, we just place the balls in a zig-zag order.
Spheres with size 30 mm, 39 mm, and 49 mm inside the tube.
Let’s consider two vertically adjacent spheres with radii \(r_1\) and \(r_2\), respectively. They stack inside a tube of radius \(R\), each touching the opposite wall. The Euclidean distance between their centers is \(r_1 + r_2\), and the horizontal distance is \(2R - r_1 - r_2\). By the Pythagorean theorem, the vertical distance \(v_{1,2}\) between their centers is: \[v_{1,2}=\sqrt{(r_1+r_2)^2-(2R-r_1-r_2)^2}= 2\sqrt{R(r_1+r_2-R)}.\] The total tube height for \(n\) sphere is the sum of these vertical distances plus the top and bottom radii: \[Tube\ Height=r_{bottom} +\sum_{i=1}^{n-1} v_{i,i+1} + r_{top}\]
I was not entirely sure what the optimal stack order will be. So I checked all the permutations of a small subsets of spheres, and spotted the pattern.
219
Every item in this size \(n\) collection must be a leaf node to the prefix-free tree. An internal node cannot be included because, by construction, it acts as a prefix to its children. Letting the current cost be \(C\), every split destroys that node and creates two new nodes with costs \(C+1\) and \(C + 4\). To minimize the skewed pricing, we must greedily split the cheapest available node.
A priority queue (PQ) simulating this until the tree size reaches \(10^9\) would work, but it will take around 20 to 30 minutes. That’s good enough for me.
Alright, here is the optimization: instead of splitting every node individually, we track the count of each cost. For instance, if there are currently ten nodes of cost 4 at the top of the PQ, we do not need to process ten separate splits. We simply add 10 to the frequencies of cost 5 and cost 8, bounding the bulk split by the exact number of operations remaining to reach \(n\). With this optimization, we bypass simulating individual strings and can find the solution instantly, even for \(Cost(10^{4000})\).
210
For any point \(B = (x, y) \in S(r)\), \(\triangle OBC\) has at most one obtuse angle. The valid regions for these angles are strictly disjoint:
- Obtuse at \(O\): Occurs iff \(OB\cdot OC < 0\). This simplifies to the half-plane \(x+y<0\), cleanly bisecting \(S(r)\). Calculable in \(\mathcal{O}(1)\) time.
- Obtuse at \(C\): Occurs iff \(CB\cdot CO < 0\). This simplifies to \(x +y > r / 2\), defining a triangular region in the first quadrant. Calculable in \(\mathcal{O}(1)\) time.
- Obtuse at \(B:\) By Thales’s Theorem, \(B\) must lie strictly inside the circle with diameter \(OC\). With center \((r/8,r/8)\) and \(R^2=r^2/32\), the boundary is \((x-r/8)^2+(y-r/8)^2<r^2/32\). Computable in \(\mathcal{O}(r)\) time.
Lastly, points collinear with \(O\) and \(C\) need to be subtracted explicitly from the totals in all three regions.
199
To find the exact starting curvatures, let the outer enclosing circle have a radius of \(1\), giving it a curvature of \(k_0=-1\). The three inner circles are congruent, so let their curvatures be \(k_1=k_2=k_3=k\). Plugging this into Descartes’ Theorem, we get: \[(-1+3k)^2=2(1+3k^2) \Longleftrightarrow 3k^2-6k-1=0.\] Solve for \(k\) to get our beginning curvatures. Next, Descartes’ Theorem also shows how to find the curvature of a fourth circle if we already know the curvatures of three mutually tangent circles: \[k_4=k_1+k_2+k_3\pm2\sqrt{k_1k_2+k_2k_3+k_3k_1}.\] Finally, we just need to implement the recursion to fill in the gaps.
198
- Find two fractions \(a/b\) and \(c/d\), such that the ambiguous number \(x\) sits exactly halfway between them. That is, \[x=\frac{p}{q} = \frac{ad+cb}{2bd}\] subject to the constraint \(2bd<10^8\).
- The Stern-Brocot tree can be used to systematically generate these fraction pairs.
- However, because the tree traversal is initiated strictly within the target interval, the pairs straddling the right boundary of \(1/100\) need to be handled explicitly.
195
- These are Eisenstein triples. Similar to Pythagorean triples, but for 60-degree triangles, and they have their own Euclid formula as well.
- This paper shows that if \((a, b, c)\) is a primitive triple, then \((b - a, b, c)\) is one too. Also any \(k>0\) multiple like \((ka, kb, kc)\) is an Eisenstein triple.
- Finally, we can use the Euclid’s formula to generate the \((a, b, c)\) sets, then pull \({(b - a, b, c)}\) from them. Find the inradius \(r\), and \(k = 1053779 / r\).
194
- Just brute-force the number of configurations for units \(A\) and \(B\) across a few small values of \(c\). Then use polynomial interpolation to get their respective chromatic polynomials.
- Searching around for “clique sum” and “chromatic polynomial”, bring up a paper detailing how to glue graphs along a shared complete subgraph.
- Because the specific sequence of \(A\) and \(B\) units in the chain doesn’t change the base number of colouring, the total is just the colourings for a single arrangement multiplied by the number of possible permutations, which is \(\binom{a + b}{a}\). Can also just use DP.
189
- Let \(0, 1\), and \(2\) represent colour red, green, and blue, respectively. Thus, we can use ternary to represent a row pattern. For instance, \(212_3 = 23_{10}\) represents the second layer from the given example.
- Then pre-compute all the valid rows by checking whether any two adjacent ternary digits in a number are the same. Hint: the \(n\)-th digit of a pattern is \(\lfloor pattern / 3^n\rfloor \bmod 3\)
- For each valid row pattern \(x\), pre-compute the set of all compatible next-row patterns \(y\) that satisfy the constraints between the two layers. This gives a transition list \(next[x]\), which tells us exactly which states can follow \(x\) in the DP.
- Finally, let \(dp[x]\) represents the number of valid colouring of all remaining lower layers, given that the current layer’s pattern is \(x\).
LeetCode 1931 is very similar to this problem.