Interesting Problems
Given a set of N < 10^5 points (no three collinear), find the kth (k < N choose 2) smallest slope between any two points.
— USACO Camp Lecture
Point-line duality is super cool. Convert points (a, b) => lines y = ax - b. What do the intersections of the lines represent?
Binary search for the k leftmost intersection. How can you count the number of the intersections to the left of a given vertical line?
If we want to count the number of intersections to the left of the vertical line x = m. To do this, evaluate all the lines at x = m, and then find the number of inversions in the list when compared to the initial order. This is O(N log^2 N).
There is a pile of N < 10^100 stones and two players. Each player can take a palindrome number of stones from the pile on their turn. The player to take the last stone wins. Figure out who wins if both players play optimally.
— Palindrom Game, USACO Bronze
Think about small values first.
What happens with N=1, 2, 3, etc.?
Look for a pattern in winning/losing positions.
Consider that all single-digit numbers are palindromes.
Given a Nx1 matrix A, 1xN matrix B (N < 10^5), and integer K (< 10^9), find the sum of the elements of the NxN matrix A x B raised to the Kth power (modulo 1e9 + 7).
— Just Visiting Relatives, HPI