Round 39: Reconstruct Sum

Consider each column independently. we just analyze the 4 cases, i.e., a combination of

  1. when there is a carry from last col
  2. there is a carry to the next col

Implementation-wise, we reverse the digits, and scan from 1 to n. Note we can just brute force to to calucate ways, with 10 added to carried digits

Round 39: Seven-segment Display

To be smallest, the # of digits must be smallest Therefore, we can calcuate greeidly, given K, what is the min # of digits we can have.

0, 1, 2,3,4,5,6,7,8,9 needs 6,2, 5,5,4, 5, 6, 4, 7, 6 segments respectively

But note that even though we know max # of digits, we need to find a way to max # of 0s, and then 1s,and then 2s. I got stuck findng an efficient way of solving it!!!

Note that 9 can never appear in the solution => we can use 6 instead. Therefore, 8s must form a suffix

Now we consider bruteforce search all potential non-8 prefixes, because of minimum length requires, the total # of segments in the non-8 part can be more than 7, otherwise, we will just add a new 8, i.e., at most 3 segments

so we brute force search 1 to 999, and caluate # of 8s need to fill all k segments, and keep track of the best number. Note that 9 can not appear in the solution

Round 38: Bounded Difference

  1. find the total # of violations, if # > 4, impossible to fix
  2. swap a[i - 1] with a[0], a[1]…., and calculate # of violations afterwards
  3. swap a[i] with with a[0],a[1]…., and calcualte # of viodlations afterwards

We break only if total # of violations is reduced to 0 in any cases.Note that we must swap one of a[i] or a[i-1], so we don’t need to check other cases.

Round 38: Tree Antichain (Easy)

A tree can always turned into a bipartite graph by coloring nodes alternatively in a DFS fashion. So we have two half permutations we can build on already!!!

Obviously, if tree is a star, we can not find solution. If it is not a start, we can find a path with length >= 3. Then the first and last vertices of opposite colors will not share a vertex for sure

Implementaion

  1. we can use a nested loop to detect the connection points => LTE 25 mil
  2. we can use swap(item, vector.back()) in c++ to change the connection point

Round 43: Bad Triplet

if all deg LTE2, then we must find a cycle with length % 3 = 0

if exists V deg >= 3, then either we find a cycle with length 3, or the V and neighbor itself is good enough!!!i.e., all passes through the central V.

Round 41: Tennis Tournament

if player wins M matches, then the first 2^M -1, must be worse then him, and 2^M + 1.. 2^(M+1), must have at least one that is better than him

Round 41: BFS-DFS

We need to satisfy both BFS and DFS. So to satify DFS, a trivial answer will be D1 -> D2-> D3 -> D4… To satify BFS, a trivail answer will be B1 -> B2, B1 -> B3…. Turns out these 2 can be satified AT THE SAME TIME!!! if we just add edges together!

The invalid case will be the that B1 -> B2 is different from D1 -> D2

Round 40: Switch the Lights

We need to toggle the first one, and keep a switched bool for each i

for each i, if i dark, continue. Otherwise, switch the current swtich flag, and add one at bool[R(i)], and then add apply the exsting switch flag. Alternatively, we can use a counter

Round 40: Restricted Permutations

ways(1, 1) = 1 calculate totalWays(N-1, i) ways(N, i) = totalWays(N-1, i - 1) if a[N - 1] = 1 Otherwise, ways(N, i) = ways(N-1, i) + ways(N-1, i + 1)…ways(N-1, N -1) = (N-1)! - totalWays(N-1, i - 1) Instead of inverse, we can just calculate partialSum(i, j)!!!