C - Candles

ans = dist between ends + min distance from either end

C - Strange Bank

  • No need for memorization. Note in knapsack solution, we just need >= and A[0] instead of checking >
  • Note that 6 coins and 9 coins they don’t intersect, so we just brute force on the 6s amount, and the remaining will be shared by 9s, followed by 1s

C - String Transformation

We can prove that the transformation retains the isomorphism if it starts with one. so we can just verify that final mapping is an isomorphism

C - K-th Substring

  • Brute force won’t work because it will be s ** 2 substrings
  • K no more than 5 means that the top K answer will not be longer than 5 anyway. Otherwise, we can reduce the length of the answer and improve it
  • So we just sort all 25000 strings, each with length 5

C - Factors of Factorial

Calcuate the prime factorization of each number and then build the divisor by the PRODCUT of numbers

D - Rain Flows into Dams

Since it is odd, we can do the odd - even trick and sum up together

C - AB Substrings

Corner cases:

  • no BA

  • no BX and AX

    The general theme is that every time you see a counting formal with minus component, have a dicussion on the cases where the sum could be negative and when the positive item could be 0

C - String Transformation

Every swap will keep the isomorphism, and we can transform to any isomorphism by swapping. Therefore, we just need to ensure the final isomorphsim is good, because it is always reachable

C - Snuke Festival

Good for coding excercise

D - Flipping Signs

Simple problem, but similar to two segment insight

D - DivRem Number

N = q * m + q = q (m + 1), with q LT m. Just need to find all divisor pairs

D - Remainder Reminder

Similar to divisor finding, iterate on all possible divisor b >= max(2, K + 1) to generate a, check how many full b “bands” we have and calculate mod >= K in the last partial band. Note that mod band start at 1! so the partial bond contributes to N % b - K + 1 pairs