Round 15: K Consequal

Maintain a stack with letter and current count, update the stack on each new letter

Round 15: Base K Xor

Idea 1 ——- We consider each digit independently, i.e. sum becomes an operation under mod k, i.e.,we can apply the partial sum trick. Note that we can delay the mod operation as much as we can, until the final step, since it doesn’t affect value, not presentation of digits.

at i > 1 th digit from right to left, the answer is sum(num/base) * base - base + digits to the right. All these happens in base 10, but mod k. However, note that for ith digit, it changes every k^i times, i.e., every complete change is a multiple of k already => so we just need to worry about the last digit!!!

So the answer is d * (x % k^i + 1), +1 is for the x0000..0 case

Idea 2

As the title suggests, it is essentially XOR in a different base. When k = 2, (4 * x) ^ (4 * x + 1) ^ (4 * x + 2) ^ (4 * x + 3) = 0

So we can expand on this idea, and just calculate the XOR from a to nearest k^2 * k , and from nearest k^2 * k to b

Round 14: Surrounded Rectangle

Official solution ——– Idea is similar but simpler. For each point, we look for the first 0 to the right of it, and to the down of it. So that we know the rectangle must be bound for that. Given this candidate, we can do a validation check via 2D prefix sums. Note we need to calcualte on prefix sum of 1, as 0-case can be inferred already.

Alternative solution

Flood-fill on 1s, and keep track of the max, min x and ys. In the end, check if the size of the component matches equal to the product.

Round 14: Subarrays Xor Sum

  1. For each bit, we calculate the prefix sum - odd or not on the count of it.

  2. The partial sum of xor is similar to regular addtional, except the difference in the interval is XOR too !!!

  3. For each [j - B, j - A +1] interval, we need to keep track of how many XOR sums are 0 or 1, to handle to case of xorSum(j) is 0 or 1

Round 13: Balanced Min Pairing

Do a greedy pairing - sort A, B, and match a[1…N/2] with b[N/2 + 1… N] , and run validations

Round 13: Num Cube Sets

We know a,b must be of form n1 * n2^2 * n^3, therefore, we group each number by n1 * n2^2, n1^n2 can not be n^3. and in the end we brute force on all possible group counts. Note that elements from within the smae subset should have the same normalization

Round 12: Independent Rectangles

Build a graph and then calc components

Official solution

Sort by (w, h), we also keep track of min height we have seen so far. It is independent, if it is the min height we can seen so far. Alterantively, sort by (-w, h), and keep track of the max height we have seen so far

Round 12: Bitwise And Queries

So for y, if x has a bit 0, can be 1, if x has a bit 1, the corresponding bit has to be 1. We assume x < b.

At each bit of y, we try to keep a prefix of b

  1. x = 1, b = 1, do nothing

  2. x = 1, b = 0, invalid

  3. x = 0, b = 0, do nothing

  4. x = 0, b = 1, add 2^remaiing free bits to answer

The final answer is answer + 1 to include x itself.

The range in [a, b] is calucated by the delta approach

Round 11: Connect the Graph

during DFS, we can find the edge that would introduce cycles, and then we save them to add all other components to the first node

Round 11: A Single One

Naive approach is to use a BFS. # of nodes are good, but there are too many edges.

To optimize it, we can not include potential edges explicitly. Instead, we find that the nodes it tries to expand to form a CONTINOUS band with the same oddity!!!

Therefore, we keep track of two node lists, one for odd, one for even, when we BFS to expand on the next node, we use set::lower_bound to infer the neighbors instead of using explicity edges