540C: Ice Cave

If there is a solution, we know that

  1. there a path from (r0,c0) to (r1, c1) without touching existing Xs

  2. (r1, c1) must have at least 2 . neighbors if it is . itself, one for the incoming edge, one for stepping out and back

  3. note that we do not need more than 2, because we can always reorganize our paths to use only 1 . neighbor, if there exists any path

Special case is r0 = r1 and c0 = c1, where you just need one . neighbor

463C: Gargari and Bishops

There are only 2 classes of diagonals:

1. captureable from (1,1), by only going diagonals

2. captureable from (1,2), by only going diagonals

proof: induction on the size of n, base case n = 2 and 3, each time n -= 2

Therefore, we go through each point, calculate which class it is from sum of the value it captures, and update that class maximum

A point is in class 1 in if abs(y -x) is even, otherwise when abs(y-x) is odd, it is class 2

pre-calculate all 2 * n diagonal sums for quick retrival. For all left leaning diagonals, cells with same i-j are on the same diagonal. For the right leaning, cells with i+j are on the same diagonal

552C: Vanya and Scales

Consider the number in w-nary representation, from the smallest digit form.

if it is 0, do nothing

if it is 1, we put our only weight on the RHS

if it is w - 1, we put our only weight on the LHS,

if it is other digit, we can do nothing

Note that we go small > large instead of the other direction is because we are doing additions and advancing a digit will affect downstream ops

329A: Purification

Consider with out E

Claim: we need at least n spells

Proof: induction on n, n =1 obvious n = i, if it can be done with < i spells, we can move those points to within the i-1 range, thus contradicts the inductive hypothesis

If we have n spells, how should we cast?

if we can find a X or T of Es, then we know there is no solution, otherwise, one must exist, because we can fill into that x or T hole and remove those Ts

if there is a row of E, consider the final solution, we know we should cast spell on each column once, and conversely such will satisfy a solution, since and X or T do not exist, we know that each column has a cell we can fill, we just fill it. After n rounds, all n columns are filled.

if there is a col of E, then we go after each rows with steps similar

543A: Writing Code

Note that we are actually looking for a O(n^3) solution

way[i][j][k] : 1…i to write j lines of code with total bug k

ways[i][j][k] = sum of (ways[i-1] [j - j1] [k - j1 * a(i)) => This gives O(n^4)

Alternativly, it is equal to

ways[i-1][j][k] + ways[i-1][j - 1] [k - a(i)] //i doesnt write a single + i writes at least one line

Notice this recursion is really similar to how you calculate binomial coefficents

Note that although O(n^3) run time is ok, but space is not ok. Therefore, we need to reuse the overwrite dp state trick, i.e., we use a 2-d array, and on calculating each ways, ways[i-1][j][k] is actually the cell we are about to update, and ways[i][j-1][k-a] is the (j-1, k-a) cell we updated in this i round, i.e., i should be the outmost loop

703C: Chris and Road

Idea 1:

The two moving against each other is equivalent of tourist moving in diagonal against static object. Therefore, he has to wait if that diagonal cuts into polygon. If it does, then tourist has to wait until the line just meets a single point of the polytime. The amount of time to wait is equal to v/(horizontal shift to make the diagonal tangent).

Note we can use bsearch to brute force the shift

Idea 2:

We hold at the origin, until polygon passes a certain point, and then we go full speed toeard to end

If we may crash into the bus, then the final time >= (w - y)/u + x/v, for any point in the polygon.

Claim : the optimal way is the MAXIMAL value.

Proof: we will get better overall time if and only if we start earlier given our schedule. but it will hit the polygon, because we will have a case where final time < (w -y)/u + x/v, directly violating our conditions

What I did wrong during the contest

  1. upon realizing that the man has to wait and it is hard to describe it, I should transform the problem into something more approachable,e.g. , the tangent approach or
the hold-release approach

  2. the lastT < passTime check did not consider the case of points on the same y-axis, and therefore, need to introduce a max filter

354A: Vasya and Robot

consider the final solution, 1…m will be picked by left, m + 1…n by right.

Therefore, we need to brute force on the m. To minimize cost, we need to alternative L and R as much as we can.

if m <= n/2, total cost = staticLeft(1…m) + staticRight(m+1….n) + (n - m - m -1) * rc else total cost = staticLeft(1…m) + staticRight(m+1….n) + (m - (n -m) - 1) * rc

22D: Segments

Consider the left most seg, just need to be greedy to nail at its right end, and then take out all segs starting to the right of that end

282C: XOR and OR

Idea 1

If they have different lengths, then of course we can not transform

Difference between XOR and OR: only difference is at 11, one is 0, the other one is 1

len = 1, can do only if they are same already

when len = 2

  1. 00 <=> 00

  2. 01 <=> 11 <=> 10

Claim: we can transform => we can start fixing from the tail (if side is obvious). Notice that each step is reversible, so we can force direction from a to b

proof: n = 1 or 2, obvious

for case n, if 0-0 or 1-1 case, then we can follow inductive hypothesis, with nop at the end

if 0-1 case, the only way to transform, if possible, is to use rule 2,i.e, change the tail to 10, for all possible ways.Therefore, we can fix the order of application

Idea 2

Claim: any non-zero string can be converted to each other

Proof: any string can be converted to 10…0. From right to left, just keep applying 01 => 10, 11 => 10

493D: Vasya and Chess

n = 2, w wins immediatley

n = 3, all will go down until reach the bottom, and then white got captured by black

n= 4, white goes down, not sure how that work…

but if white goes right, then from the black perspective it is same as n = 3 case, where both have to reach the bottom first. i.e., black will lose for sure!

n = 5, if white goes left, black should go right, so that we have similar case to n = 3, i.e. black will win

if white goes down, black will go down as well, since now it appears that, the width matters most instead of heights, and this reduces to the first case of n = 5

i.e., when n is even, we can always devise a strategy for white to win, when n is odd, we can always design 1 strategy for black to win

534C: Polycarpus Dice

  1. max value can be reached  = min(d(i), A - (n - 1))

  2. min value can be reached = max(1, A - (sum - d(i)))

469C: 24 Game

  1. n = 4, just multiple them together

  2. n = 5, possible the form a solution

  3. for all n >= 6, we can reduce to case n < 6, just keep multiply with i - (i -1), where i >= 6  

236C: LCM Challenge

  1. obviously, there is an optimal solution where the any of the gcd(i,j) should be 1, so that the answer is a * b * c. Otherwise, we can reduce a solution into a format with this pattern

  2. if n <= 2, just pick n

  3. we know gcd(n,n-1, n-2) = 1, and n * n-1 * n-2 is maximal, if n is odd

  4. But if n is even, then we should pick n-1 * n-2 * n-3 

318C: Perfect Pair

  1. if any number is negative, then we can not make from an non-perfect to perfect

  2. if any is posivite, just brute force it => if x <= y, turn into (x+y, y), we know the lower end increases by at least double 

578A: A Problem about Polyline

  1. since polyline can not be higher than x, then we know b <= x

  2. if a < b, that is impossible to get the line

  3. if the point is on the rise,  a - b will be on the axis, i.e, (a-b) = 2k * x

  4. if the point is on the fall, a + b will on the axis a+b = (2k + 1) * x

  5. try both and take minimum

456C: boredom

Consider each number appears only once

If we have 3 consecutive numbers, we should take 1st and 3rd

If we have 4 consecutive nubmers, we shoud take 2nd and 4th

i.e., if there no repeats, start the biggest, and we take every other numbers

If there are repeats,

best(n) = max(score(n) + best(n-2), score(n-1))

so sort the number, then

best(n) = max of

  1. score(n) + best(n-1), if a[n] > a[n-1] + 1

  2. score(n) + best(n-2), if a[n] = a[n-1] + 1 

  3. best(n-1), if a[n] = a[n-1] + 1
      

269A: Magical Boxes

Sort (k, c) pairs

start from 1 to n-1, calculate, how many box of this size can fit all previous sizes. Set balance to max(boxes to fit all, a[i])

if balance =1, we are done. Otherwise, the final answer is kmax + log(4, balance) + 1

204A: Little Elephant and Interval

Standard transformation: calculate all such pair < R

for numbers with m digits , all possible number is 9* 10^(m-2)

For numbers with same number digits as R,

if first digit <= last digit, (fd - 1) * 10 ^(m-2) + middleDigits + 1

if first digit >= last digit, same answer, (fd -1) * 10 ^(m-2) + middleDigits

437C: The Child and Toy

What will an optimal solution look like?

Consider the vertex with biggest value, since all edges must be brokean, we want they to be borken from the higher end, i.e., the highest value vertex should be removed first, to satisfy the conditions.

Repeating this process, we can form a sequence of actions, where for each edge, we guarantee that the edge is broken from the bigger end, i.e., the smallest possible cost is incurred

599C: Day at the Beach

Suppose we find our first segment s with length l, what property will that have?

  1. it will contain the l smallest numbers. Conversely, if we find the first l smallest numbers, we can declare a segment

  2. any remaining numbers >= any numbers in the s,i.e., the min of the remaining segment >= max of s. Conversely, having this property
means s must have the smallest numbers,i.e., can form a segment

This leads to 2 ideas

Idea 1

We keep track of a balance of numbers as we scan through the array from the left, every time we hit with balance 0, we announce that we detect a segment

Idea 2

We scan from left to right, every time we detect i s.t. max(1…i) <= min(i+1…n), by property 2 we can declare a segment

123A: Prime Permutation

Consider the target string:

By induction, we know for all prime <= n/2, i | prime will share the same letter. Moreover, if a composite number <= n/2, it must have a prime fact <= n/2, i.e., all number in [2, n/2] must share the same number

Conversely, if prime > n/2, it can appear only once as factor, i.e, at i = prime itself. if composite > n/2, then it must be a prime factor <= 2/n, which means it will share char with previous steps

So the algorithm is

  1. scan string to keep track of counts, and which letter is the most popular

  2. all number in [2, 2/n] must be same

  3. for numbers in 2, use a process similar to sieve to generate composite numbers > n/2 that has to share the same char

  4. scan through the answer again to fill in whatever left

297B: Fish Weight(!!!)

Idea 1

Consider the delta between A and B, it is possible for A to win if and only if

  1. delta of the biggest fish is in the favor of A

  2. first continous positive delta in the favor of A > sum of continuous positve delta previously in the favor of B.

But coding this is not the easiest thing

  1. sort <weight, count> pair in decreasing order for A and B

  2. if top weight (A) > tw(B) || top weight(A) = tw(B) && count of tw(A) > count oftw(B), done

  3. if top count and weight same, progress both indeies 

  4. progress B indice, until conditions 2) is statisfied, update the top most count for B

  5. now progress A index until 2) is violated, update the + balance for A

  6. compare if + balance is > - balance

Notice here we need to iterate through map <int, int> which is often sigh of flawed algorithm

Idea 2

just sort all fishes caught, on the first difference, if A is winning we are done. If B is winning, we need to keep scanning until we find a position where A is winning

Claim: A is winning in at least one postition <=> it is possible to find a solution

  1. (<=)  if A is not winning at any position, obviously impossible 

  2. (=>) we can make the delta arbitarily large to cover all potential balances

343B: Alternating Current

After looking at smaller cases, we can see that we can reduce consecutive ++ or – pairs, until the whole string is reduced to empty string.

Therefore, we can scan from left and right, and eliminate all ++ or – as we scan through. However, we can not afford to modify the underlying strng. Therefore, we have to maintain a prev[i], i.e., a linked list

as we scan through , if s[i] = s[prev[i]], we set prev[i+1] = prev[prev[i]], i.e., we remove i and prev[i] from the linked list

Init prev[i] = i-1 in [0, n], linked list will be empty if prev[n] = -1, i.e., the init value for prev[0].

198B: jumping on walls

Consider the subproblem by dropping the condition: what if without the rising water, how to solve it?

We can reduce to a graph connectivity problem, which can be solved with DFS

  bool visit(height, side)

      mark (height, side) as visited

      canEscape = height > n - k

      canEspace = canEscap || visit (height + 1, side) if it is not visted yet.

      canEspace = canEscap || visit (height - 1, side) if it is not visted yet.

      canEspace = canEscap || visit (height + k, !side) if it is not visted yet.

      return canEscape

But with the rising water, how to prove the existance of a solution?,

 1. we know the time arriving at a spot must be before water reaches that level. 

 2. Therefore, we look for the earliest time to arrive at a spot. A solution exists iff we can find an earliest time to escape

 3. This transforms the problem into a shortest path in a unit length edge graph problem -> a BFS would do

 4. note that since if we go up, we go at least 1 unit up, we do not even need to worry about water in that case
  
 5. However, if we go down, we need to ensure water level is not high enough yet,i.e., earliest time at the spot = water at that time <
height of the spot

350C: Bombs

Standard greedy problem

Idea 1: group bombs by rows, sort each row by cols.

Idea 2: If A is on the path to B, then we know mahatann distance of (A) < MD(B), i.e., if we process bombs in the order of MD, we know that all potential blocking bombs are cleared already

334C: secrets

For the optimal solution, we need to use as many small denomincations as possible in the place of large ones,i.e., the optimal solution have only the smallest denomination, because for any other solution, we can replace larger coins with smaller one and improve the result.

Consider any potential solution, the smallest denomination can not divide n, because otherwise, we can take out that denomination, and the sum is either still greater than n, or < n, which implies the sum = m.

Therefore, in the optimal solution, the smallest coin should not divide n

525C: Ilya and Sticks

Suppose we have 4 pairs a < b < c < d, c * d + a*b > a * d + b * c, i.e., we need to be greedy, and form the first pair we can

Idea1

Saw as you go. Start scanning len from max to min,

  1. push all evens to the result list
  
  2. if there is 1 remaining left, and count[len-1] > 0, push an additonal pair

  3. In the final run, iterate through pairs and output

Idea 2:

Do all sawing first, and then look for the matching pairs. Scan len from max to min

  1. if count[len] is even, no need to saw

  2. if count[len] is odd and count[len-1] > 0, saw one. Note that since we saw at most one stick at each length and only when there already exists a stick with len - 1, we know that we are not re-sawing the same stick twice

  3. if count[len] is odd and count[len-1] == 0, count[len]--

  4. Now our scan handles only even entries, and we need to keep track of only the outstanding pair

272C: Dima and Staircase

Notice that the first block always get covered for each drop. So we need to keep track of height of the first block, when there is a drop, the answer will be max(right anchor, first block), and we need to update first block height afterwards

Note that without the covering first w(i) requirement, this needs to be solved with a segment tree

66D: Petya and His Friends

Obviously, a(i) can not be a prime, otherwise, it will violate 2nd constraint

One construction would be a(i) = product of first n primes / ith primes

Another construct is to look at case of N = 3 (N = 2 obviously gives no answer), can you expanding to N with a known solution at N = 3

353C: Find Maximum

Note that m <= 2^n - 1

Notice that all a[i]s >= 0, so we should be greedy and include as many #s as possible. So we should interate through the prefix of m

at each i, if m[i] = 1, update suffix sum, update result with prefix sum + suffix sum , update prefix sum

343A: Rational Resistance

Note that this problem does not allow joining 2 elements. Therefore, we can just backtrack.

  1. we are done if a = b

  2. if a/b > 1, then we reverse n steps so that a/b - n <= 1

  3.  if a/b < 1, then we reverse n steps so that b - n * a <= a

  4. Note that at recursive call we backtrack n steps, in the spirit of GCD algo

316B2: EKG

  1. if prev[a] = b (b != 0), populate next[b] = a;

  2. for each prev[a] = 0, go through the linked list to find its length, add it to a vector size if it does not have the target

  3. possible [v][i] = possible[v] [i - 1] || possible [v - size[i]][i - 1]

  4. iterate through all possible[v][size.lenght], print v + pos if it is true

150B: Quantity of Strings

if k = 1, any string would do

if k = n, any string of length l/2 would do

Claim: if k is even, then the string can have only 1 letter

Proof: suppose k = 2* j. Consider the substring starting at 1

  1. a[j -1] = a[j] because they are the inner most pair

  2. a[j -2] = a[j], 2nd inner most pair

  3. a[j-3] = a[j -1] = a[j], 3rd inner most pair
  
  ....

Claim: if k is odd, then the string can have only 2 letters, all odd chars are the same, and all even chars are the same

Proof: suppose k = 2 * j + 1, Consider the substring staring at 1

  1. a [j + 1] = a[j +3] =  = a[j - 1] , inner most pair


  2.a [j] = a[j+4] =  a[j - 2]

  3. repeat steps for substring staring at 2..... n -k

384C: Milking cows (!!!)

This is type of the problem where we decompose by classification, and hopefully the target function is a simple composition of each class, without each class overlapping of each other’s cases question is: how do we classify?

We can just focus on the cases of 2 cows, 4 cases

1. >< : we will lose 1 regarldess of which side we pick

2. >> : we should try pick the left most one first

3. <>: we will not lose any regardless of which side we pick

4. <<: we should try picking the right most one first

since case 1 and 3 gives constant cost, if we can just need to minimize case 2 and 4 AT THE SAME TIME, we can reach the minimal cost

Fortunatly, we can decompose the target string into »»> and ««< : even the two interleaves, how they interleave doesn’t affect the final target functions

So we just need to calculate the total cost of case 1 => do a linear scan with state update and we are good

118D: Caesars Legions

Consider the compliement of the problem: how many ways to have no more than k1 consecutive Fs or K2 consecutive Cs?

  ways(nF, nC, F) = ways(nF-1, nC, C) + ways(nF-2, nC, C) + ..... ways(nF-k1, nC, C)

  ways(nF, nC, C) = ways(nF, nC - 1, F) + ways(nF, nC-2,  F) +....ways(nF, nC - k2, F)

  ways(1, 0, F) = 1 and ways(0, 1, C) = 1

answer is 2^n - ways(nF, nC, F) - ways(nF, nC, C)

207-A: Knight Tournament

Easy problem with c++ set and it O(logn) upper_bound. But it can be solved with the parent[x] array, plus the path compression trick in union-find data structure

265-A: no to palindromes

Suppose we know the first index to flip the first letter is not same and prev and prev - 1, then we can keep generating, with this rule from a, knowing that it will not introduce new palidromes. Otherwise, the inner part would have a palindromes already

One thing to notice is that since we are looking for the next one, we should try from the tail, so that we can break immedately upon finding one

336-A: Chain Reaction

The first idea is to DP by index i, i.e., ans[i] = 1 + ans[j] where j is larget num s.t. a[i] - a[j] < b[i], but this requires a bsearch

Can we avoid the bsearch?

Consider the value is within 1 mil range, at distance d

  ans[d] = ans[d-1] if d is has no lamp

  and[d] = ans[d - b[l[d]]i - 1] + 1 if d has lamp

334 A: Alternative Thinking

Flipping a substring can be decomposed into 2 prefix flips. Easy to prove each flip increase the score by at most 1, and if there is an optimal solution (i.e., can increase), there is one that flips at the first 00 or 11. Therefore, we just look for total number of 00s and 11s, cap it at 2

112 C: Another Problem on Strings

Similar to the problem above, substring can be decomposed into delta of 2 prefixs. This means substring with k 1s = prefix with n 1s and a smaller preifx with n-k 1s

Therefore, num of substrings with k 1s = sum of ( # of prefixs with n 1s * # of prefixes with n-k 1s) where n is from k to n

211 C: Fixing Typos

Easy problem, but can you solve it with one pass only.

Consider the inductive steps: if my current string is valid, and I try appending new one, what should I do to ensure it keeps valid?

9C: Hexadecimal Numbers

Need to know how many numbers < n that has only digit 0 and 1?

Idea 1: recursive computation

  num(n) =
    if (n = 1) return 2

  if top digit is 1
    num(n - 10s) + num(10s - 1)

  else if top digit is not 1
    num(n - remainig + 10*)

Idea 2: Generation-Filtering Generate all numbers with digit 0 and 1 that can possibly be less than < n, i.e., 9 digits, then filter out those >= n. This works, because we generate < 2^10 = 1024 numbers

372A: Counting Kangaroos is Fun (!!!)

since max answer <= n/2, we can partition the data into 2 halves, each with size n/2.

Claim: there always exists an optimal solution where all big ones are in the right half, while small ones are in the left half

  Proof: suppose we have a pair (a, b) in the same half. 

  If the other half has empty space, we can move a or b to that space, while preserving the max value

  If the other half has no empty space, and  no pair exist in the other half, then overall count > n/2, contradiction.

  Thus, there must exist a pair (c, d) in the other half, with a < b < c < d, i.e., we can just swap b, c to form (a,c), (b,d) and the optimal
value still preserves

So we can use a two pointer approach, start from one side, and search for the matching other side

567C: Geometric Progressions

So we need to find a(i), a(j), a(k) which forms a geometric sequence. Similar to the problem where you find a longest increasing subarray with one odd point, we can focus search for the middle point, the benefit is that we can break down the solution into 2 parts, we can easily bsearch on each part

475B: Strongly Connected City

Given the constraint, a DFS on each node would do in O(n^2 * m^2), but can we do better?

Consider base case: 2 rows, 2 cols, the for edeges must form a cycle (cw or ccw)

If add a a new row or col, it would do as well

Claim: as long as the outer sell forms a cw or ccw cycle, we can form a SCC

  Proof: by induction
  When we all a a new row, any new point can reach any old point, and any old point can reach any new point, and any new point can reach any
  new point

Notice that we can always construct an optimal solution with simple greedy approach, i.e., if a(i) < a(j), we know there exists an optimal solution where numberOfLeader(i) >= numberOfLeader(j). Reason: we can force a(i) to be leader until a(j) is reduced to a(i), and then each of them takes turns to be leader.

Also notice we are looking for the minimum number, i.e., the answer is monotonic, i.e., if m satisfies conditions, so does m + 1

Make unknown known, and invent a new problem related to the existing one

Suppose we know final answer m, given the greedy insight, we can find the solution as follows,

  1. a(1) is leader for m - a(1) games

  2. a(2) is the leader for (m - a(1)) - (a(2) - a(1)) games = m -a(2)

  3. a(3) is the leader for (m - (a(1) + a(2))) - (a(3) - (a(1) + a(2))) games = m - a(3)...and so on

Since m also is number of games a(i) being leaders, we know m <= m - a(1) + m - a(2) + m - a(3)….. Solve it and we get lower bound for m

This is the type of the problem that looks at its inverse - i.e., instead of finding out what moves, find what did not move and its extreme values.

Focus on the unknown, what properties can you infer from the unknown?

  1. The unmoved parts, after moves, will be collapsed together, i.e., they must be consecutive numbers

  2. Therefore, # of unmoved <= # of items where consecutive numbers have increasing indices, i.e., max(# of unmoved) <= max(# of consecutive numbers with increasing indices) 

  3. Can the upper bound always be reached? i.e., does that longest sequence give the answer we need?

  4. Then we need to prove max(# of unmoved) >= max(# of consecutive numbers with increasing indices) 

  5. To prove 4), we can argue that we can always construct a solution around that subsequence, easily prove by induction

  6. Therefore, by 2) and 4), we just need to find longest consecutive value sequences with increasing indicies => use the inverse index

Option 1:

len(i, lastChange, hasChange): longest strictly increasing subsegment ending at i

when we move to i + 1

len(i+1, false, false) = a[i+1] > a[i] ? len(i, false, false) : 0 + 1 len(i+1, true, true) = len(i, false, false) + 1 len(i+1, true, false) = invalid case len(i+1, false, true) = max of ( a[i+1] > a[i] ? len (i, false, true) : 0 + 1 a[i+1] > a[i-1] + 1? len(i, true, true) : 1 + 1 )

and then check all (i, bool, bool) combos for max answer base case= len(0, false,false) = 1, len(0, true, true) = 1

Option 2:

Calculate all lenEnd(i), Calculate all lenStart(i)

for all i, compute lenEnd(i) + lenStart(i), and get max

Techinique: Find all potential solutions and get the max value. This means looking at the unknown and try to infer from its properties,i.e., one out of order means we need to search based on which entry is out of order

357C - Heap operations

The simple greedy approach would work. I TLEed because I did not include ios_base::sync_with_stdio(false);

Consider the first invalid case we run into. Options

  1. removeMin() on empty heap,

  2. getMin() > current min on heap

  3. getMin() < current min on heap

We can fix the heap on the spot, and repeat this step, by induction, our result will be consistent.

  1. we missed an insert, the value does not matter
  
  2. we missed removal

  3. we missed insert

In contest I spent more time proving the greedy approach is optimal than writing code!

358C - Alyona and the Tree

These types of problems introduce a speical definition, so we need to focus on that definition and infer conditions out of it.

From the perspective of a node, it must be removed if path to any of its ancestor > value of this node,i.e., we need to keep track of the max path from ANY ancestor to the node itself

MaxPath(node) =  E(parent, node) +  max(0, MaxPath(parent))

Also, since we remove from leaves, we need to go from root, and remove the subtree rooted at the first bad node

To make implementation easier, instead of calculating how many are removed, we calculate how many nodes are saved, the result is N - saved. (Inclusion-exclustion principle)

357C - Heap operations

The simple greedy approach would work. I TLEed because I did not include ios_base::sync_with_stdio(false);

Consider the first invalid case we run into. Options

  1. removeMin() on empty heap,

  2. getMin() > current min on heap

  3. getMin() < current min on heap

We can fix the heap on the spot, and repeat this step, by induction, our result will be consistent.

  1. we missed an insert, the value does not matter
  
  2. we missed removal

  3. we missed insert

In contest I spent more time proving the greedy approach is optimal than writing code!

358C - Alyona and the Tree

These types of problems introduce a speical definition, so we need to focus on that definition and infer conditions out of it.

From the perspective of a node, it must be removed if path to any of its ancestor > value of this node,i.e., we need to keep track of the max path from ANY ancestor to the node itself

MaxPath(node) =  E(parent, node) +  max(0, MaxPath(parent))

Also, since we remove from leaves, we need to go from root, and remove the subtree rooted at the first bad node

To make implementation easier, instead of calculating how many are removed, we calculate how many nodes are saved, the result is N - saved. (Inclusion-exclustion principle)

359C: Robbers’ watch

Typical complete search problem with generate-filter pattern. Because we have 2 constraints (uniqueness and value upperbound), we can generate to-be-filtered data set in 2 different ways. The basic idea is to generate according to one constraint, and then filter generated with another.

  1. generate all permutations of 0-7 with next_permutation, and check it first dn + dm digits to make sure the number formed < n and m. In the end, divide by
(7-dn-dm)! to filter out duplications. You can also use a set to maintain it, but it is more cumbersome to code

  2. generate all possible (n, m) pairs, and check this pair has no duplicate. I find this is easiler to code.

Notice that each node has exaclty 1 out edge. The graph would be a tree, with children pointing to the parent, and root pointing to some random child

Also notice that this n node, n edge is composable structure, so potentially there are multiple components

Now assume only 1 component in the graph.

The graph can be broken down into 2 parts

  1. a directed cycle
  
  2. directed trees with roots on that cycle

Proof: Induction on the number of vertices, when we add a new edge, which node should it point to?

  1. if it points to a vertex on the cycle, it has 3 choices, no incoming edge, incoming edge from cycle, incoming edge from tree

  2. If it points to a vertex on the tree, these 3 choices either introduce more branches, or break the old cycle and introduce a new one

Now if the component is just a cycle, then any subset would do => 2^n

If the component is cycle + branch

  1. if branches do not change, any subset from cycle will do =>  2^ size(cycle)
  
  2. if branches change, then any non-empty subset from cycle will do => (2^size(branches) - 1) * (2^size(cycle) -1)

  3. sum it up, we get 2^size(component) + 1 - 2^size(branches)

Now lets consider the multiple component cases

  1. for each component, the argument above still holds, because of the n vertice, n edges structure is composable, except that we have to
exclude empty set case, because each component needs to contribute something to the n node

  2. Therefore, the total # of ways is the product of each indiviual componenets ways - 1 (-1 to exclude empty set case)

  3. therefore, we should DFS the graph to discover the component size and cycle/branch size, and then product result of each component together

Implementation notes

  1. to calculate size of component, need to convert it to undirected graph

  2. to find the length of the cycle, need to use the directed version, and keep a DFSish clock (See Floyd cycle finding).

  3. 1L << shift to calculate power for long

1.Definition of partial ordering

2.if C(a) > C(b), can I say a → b? Why or why not?

3.How the partial order maintained during processes and send/receives?

4.How is total order defined based on partial order?

5.Why the paper says total order is not defined only by the system of events?

6.Describe the distributed sync problem

7.Why a central process alone approach will work?

8.Describe the distributed sync algorithm and its assumptions?

9.Why do we need physical time to detect failure?

10.What is the “anomalous behavior”? What are the 2 solutions proposed by the paper?

11.Why the strong clock condition physical lock only sets forwards?