Hard contest, I made mistake in every single problem I tried !!!

767B: The Queue(!!!)

1. I didn’t consider the case that other arrival time may be out of the range already

2. My code didn’t consider the case where the queue is empty by the time next client arrives

767C: Garland(!!!)

I did realize that one to decompose the problem is to consider the 2-cut is one cut in the child link + link to the parent itself. But I have to exclude root node from this case, i.e., there are 3 cases to find 2 cuts from a linked tree, notice our focus is link here

1. 2 single cuts in two child siblings

2. 2 cuts from the same child, may include the link from child to the parent (recursive case)

3. a sinlge cut in a child, may include the link from child to the parent, plus the cut on the link from current root to its parent, need to
   exclude the link 

767D: Cartons of milk(!!!)

The more we buy, more likely we have to throw a carton, so we just bsearch the target number, of course, we will at each try, we will do a 2 pointer scan to move k cartons each day (sorting will be too expensive)

Mistakes I made

1. should sort store milk increasingly, and then take the last size blocks. During iteration, we should go from block start to m, since we
     want to consume ealier milk sooner, but overall, take the latest milks

2. Use scanf insteand of cin, or otherwise TLE

765D:Artsem and Saunders

If h and g exist, what properties can we infer?!!!

f(f(x)) = h(g(h(g(x)))) = f(x)

i.e., for all values of f(x), it must be a stable point, i.e., f(vfx) = vfx

Now we just need to construct a solution to prove that as long as f(vfx) = vfx for all vfx presented, we can find g, and h

m >= number of distinct f(x), otherwise, we will have 1 m mapped to 2 f(x)

m <= number of distinct f(x), because for each stable point we discovered, we can assign an m value

Therefore, m = distinct values of vfx. So we define g1(vfx) = index(vfx), and h(index(vfx)) = vfx at that index, i.e. g1 is the inverse of h, and then g = g1 * f

h(g(x)) = h * g1 * f(x) = f(x) 

g(h(mx)) = g1 * f(h(mx)) = g1 * f(vmfx)  = g1(vmfx) = index of(vmfx) = mx

When implementing, we can just interation all vfx values from 1 to n, if f[vfx] = vfx, we know it is a stable point, and thus we can safely include that in the final answer, because our condition requires only vfx are stable points of f.

768C: Jon Snow and his Favourite Number

I realize that XOR itself is reversible operation, so I spent too much time finding a sequence of actions than can save some sorting work!!!

Instead, if you pay attention to the input constraint, the values are only 10^3, therefore, instead of sort the input array directly, we can just keep track of distinct values and their numbers, and brute force simulate the process. Overall run time is O(k * 10^3 * 2), which is enough is for its 4 sec run time bound

768D: Jon and Orbs

Consider p=1000, q =1000, this is the max number of days we possible need to calculate

Pr(day, collected) = Pr(on day -1, pick within collection) * Pr(day - 1, collected) + Pr(outside collection) * Pr(On day -1, pick outside collected - 1, collected - 1)

When p, q = 1000, we can calucate to know day <= 1000 for sure!!!

Therefore, we just calculate all probablilites with DP (standard coupon collector problem), for each queries, we can just do a linear search on Pr(day, k)

721D: Maxim and Array(!!!)

1. If we have 0, we need to mark them +1 or -1 to ensure final product is negative. Thus, we need to keep track of the number of negs we have so far. If there is not enough k to fill 0s, return 0;

2. If final product is still positive, we need to pick minimal abs(value) and try flip the sign

3. Now we enlarge them one by one with a PQ in a greedy way. Note that to answer the final queries, in PQ we need to keep track both value and original index

724D: Dense Subsequence(!!!)

Insights

1. If the final answer has more than letter a, we should list ALL a in the string
2. If the final answer has only a, we should list a few as as possible. Morever, each a should not be separate by more than m. If not, we
   know that the answer must exist some letter other than 1, then by 1 we have to take all as
3. Therefore, the only letter that we don't take all is the last one, all we need to do is the find the biggest letter in the answer, and
  keep track of that count.

743D: Chloe and pleasant prizes

From the root, we have a few options,

1. take the root, and the whole subtree 

2. don't take the root, and take the best subtree from it 

3. don't take the root, and take the best two subtree from it

So the state we keep

best2(node) = best choice of having 2 cuts from tree rooted at node 

best(node) = best choice of having only 1 cut from the tree rooted at node

Note implementation wise, we need 3 DP, best2, best , and rootSum

742D: Arpa’s weak amphitheater and Mehrdad’s valuable Hoses

Union-Find to group Hoses into groups, the state we keep is best[gn][w] = best score we can get with group 0…gn, with total weight w;

options we have

1. pick the whole group

2. pick anyone from the group. note that for each w, we go through all n only once, so the overall time is still O(n^2)

3. ignore the group

Note implementaion wise, it is similar to a knapsack problem, i.e., bottom-up with exactly same recurrsion as top-down. However, we do not trigger the DP step until we know Find(i) = i. Otherwise, we just let best[i][w] = best[i-1][w], i.e., no op on this step

738C: Road to Cinema

bsearch on the min fuel capacity, and try to spend all gas before the next station

738D: Sea Battle

scan from left to right, find the first cell that the subarray 1..l can hold k ships, must hit that cell, after that , every time we have enough to hold a ship, we need to hit it once.

749D: Leaving Auction(!!!)

707D: Persistent Bookcase (!!!)

If only operation 1,2, and 3, we can keep track of the inverse, and twist the operation as we go. This also means we need to maintain the whole state.

I was having problem handling the 4th operation, because I wasn’t sure how to handle the memory and run time requirement when it comes to revert. Turns out because we have all entries there already, we can do a full pre-computation and store the result, to avoid the case of re-computing a single node many times => i.e., we cache it as part of computation progress!

Idea 1 (Offline)

Instead of calculate the result online, collect all queries and but a dependency graph, DFS it once and fill the cache, and then print out the result

Note that because we try to apply changes at each step, the revert may be a noop because the application didn’t go through in the first place!

Idea 2 (O(nq) space and time)

Becasue we have only 10^5 queries, max of 10^5 lines are modfies, therefore, we store those 10^5 lines explicits, along with the which version they represent. To make op 4 calculate quickly, we have a cache of state[version][i] to keep track of the version of a single row i of at the overall version.

On operation 4, we just interation through all n and sum up (with the help of count cache)

711D: Directed Roads(!!!)

In a sunny graph, find the edges in the center circle. The final answer will be (2^|size of cycle| - 2) * (2^|edges outside the cycle|)

Note that by the given input, each node has exactly 1 outgoing edge, failed to realize this makes my solution and reasoning much harder

Also, we can use dfs’s depth to calculate the cycle, but we have to watch out for the case where other edge from the branch hitting the cycle and thus will mess up the cycle size based on depth!

To defend against that, we have to mark which visit the discover is from, and allow only the visit from the same discovers. Note that this secondary discovery will not affect our count of ways, because of our forumla - only each individual cycle length matters

735D: Taxes

If n is prime, we pay only 1.

Otherwise, if n is even, by goldbach’s conjecture, we can find 2 primes

If n is odd, then it can be the sum of a prime and an even number. Note the speical case of that even number = 2 (!!!), otherwise, the answer will be 3.

What I did wrong during contest

1. I did realize that similarity grows much quicker than instability. Therefore, we need to somehow max the instability while minimizing the
similiarity

2. I also realized that because we have only 26 letters, adding 1 letter after the first 26 ones will increase the instablity by at most 1,
   and yet increase the similarly at by at least 3 when N = 100 (pigeonhole principle) 

3. From here on, I lost the idea

Solution

1. since we need to max instability and min similarily, let's solve them one by one, we will separate the alphabelt into 2 groups, 1 group
   just for contributing to instability and does not add to similarity, and the other just for similarity but not instability

2. Therefore, we choose pairs of letter AB, CD, EF...etc, such that first P words will be ABAB...,
CDCD..., and EFEF...

3. The remaining letters will go with single letter, G, H, I...., i.e, they will add to similarity among themselves (pigeonhole principle),
   but not to the first group , nor will they add to instability
  
4. Where to draw the line? We can brute force search for the size of group 2, but if we calculate the rough number, we can see that just
   take (A, B), (C, D) as part of the first group is enough

5. Reason: first group instability : up to 99 * 2 = 198, second group similarity < 22 * 5

What I did wrong during the contest

I didn't run the second example by hand, or read the second example in text. Therefore, I didn't realize that if two words are both oppsites
of the third word, they will be equivalent.

In the end I spent too much time reasoning about the how to update the hate state efficiently. By the way I realize my mistake it is too
late.

To keep track of hates, we just need to keep track of each UF components roots, and note that each member can not have more than 1 hate. This makes answering relationship query easier, compared to keeping track of hate at the non-root level

When we try adding (a op b)

1. OppositeA and b will be merged => addEq(OpA, b)

2. OppositeB and a will be merged => addEq(OpB, a)

3. The root of the two's group will be marked as oppsite

4. if any of the above step is invalid, revert the changes

When we tray adding (a eq b)

1. we need to add equal to addEq(OpA, OpB) as well

2. each check is to ensure that they do not hate each other already

For addEq, we just need to look up in the oppsite array and make sure their parents are not against each other

761D: Dasha and Very Difficult Problem

My Idea: bsearch

We can bsearch on the max value in C, since we know it will be <= 1e9

For each maximum C value, we can try from n-th biggest to 1-th,

	1. current c entry value, cv < previous c value
	2. b = a - cv, and b is in [l, r], i.e., we set cv = min(prev cv -1, a + l)
	3. If cv < a - r, we know our guess is too slow

Official: greedy

we know that for each c, it must be within the range of [ac-r, ac-l], also, it must be within the range of [aPrevC-r -1, aPrevC-l -1], just iterate through n to 1.

The solution exists if no bound overlaps. Once we have c, we can easily get b.

762C: Two strings

For each prefix of a, calculate longest b prefix that it can form a subsequence

For each suffix of a, calculate longest b suffix that it can form a subsequence

calculate max(prefixL[i] + prefixL[i+1]), buy checking all i in [0, n-1)(!!!)

Note

1. the offical calculates in the other direction, i.e., given a prefix of b, what is the minimum prefix of a we need? And it will do a two pointer scan from the B side, until the total length of A required less than A.size()

2. The problem with my approach is that I have to worry about cases 1. b is a substring of a, and 2. only a prefix or a suffix is needed, but not both 

754D: Fedor and coupons

sort the start and end points, and keep track of how many levels we have at each event. Update the start and end segment when level becomes k and k - 1, respectively.

Note we should process the leave events first before start events at the same point

In the end, scan through segments for the first k that has start <= seg start and end >= seg end

Consider we go from top left to the bottom right. Given a 50 * 50 board, the min step k is 98. If during our traversal, for each left or up turn the final answer increases by 2: 1 to go left/up, and 1 to go right/down to cancel that

The key mistake I made during contest is that I didn’t pay attention to k <= 1000 constraint!!!

Now how to construct k = 1000 path on a 50 * 50 board? We can create a zig-zag pattern, the maximal zig-zag pattern gives k > 1000 already!

Proof

1. every 4 rows, we make c left turns, i.e., increase the k by 2 * c

2. For a 50 row board, we will have  (50 / 4) * 2 * c, i.e., the final k is around 25 * (c = 50) = 1250 

3. Thus, we can satify our k = 1000 constraint

Note that for each left/up we take out, we reduce k by 2, i.e., we have a way to construct all paths with even k in [100, 1000]

Now what if k is odd number between [99, 999]? By our proof, we just need to change c to an odd number, e.g., 49, so that the maximal k is odd, and by our “reduction by 2” rule, we can construct all odd k >= 99

757C: Felicity is Coming (!!!)

Key question: how to detect that across groups, the 2 types should be in the same permutation?

Answer: if and only we compare the groups in which the type appears, they should be exactly same

Therefore, for each type, we have its group appearances, sort them, and scan through the while keep track of each group

760D: Travel Card (!!!)

Implementation details to watch out for

1. When try expanding the suffix, handle the case where the next digit is 0

2. If the longest suffix is just 0

3. We have to limit the length of suffix. Otherwise, the result will overflow

4. Use a temp index to try the longest suffix, so we can update the state/result only when we have discovered better result

Easy problem, but there is a bug in my code that I was not able to fix it within 10 mins

What I did wrong during contest

1. should use upper_bound() on vector or sets , instead of implementing my own bsearch

2. Alternatively, should do bottom-up construction, so that we can update pointers to either neighbors in a while loop => added only linear cost

Idea 1: Fenwick tree

Having problem understanding the solution. Namely Why need to set k = min(k, n-k)?

assume k * 2 <= n for now…

If we connect from x to x + k - n, How much diagonals do we cross?

1. Because each diagonal has a gap of k, then any diagonal originated in (x - k, x + k), will cross our new diagonal

2. Therefore, we need to maintain prefix sum of number of digaonals from the point. Note that we keep the 1 count only for the starting , but not for ending point

3. For each new diagonal, we can calculate the interval sum with the fenwick tree, and add 1 to the point sending out to the new diagonal

Now consider k * 2 > n, the above formula, stops working, because the from and to points swapped sides clockwise! Therefore, we set k = n - k in this case, as each step, the new “shape” remaings same, except it is an mirror image, node-wise!

Idea 2

We follow the sequence of actions, every time the next index is less than the current one, we know we have rotated one round around the polygon. Therefore, from then on, the number of of polygons we will cross will be increaded by 1 compared to the previous cycle

Need to watch out the case where we first cross the cycle, and when we end up in 0 again, which is the final step.

750C: New Year and Rating

Idea 1: Math (My approach)

Maintain an upper and a lower bound. Initially they are set to (-INF, INF), as we go through the rating change in the reverse order, apply the delta to upper/lower bound as long as they are not INF. If we run into a band change, we will do a hard reset if the current value after the rating change is inconsitent with the new band

Idea 2: Bsearch

Since the problem asks for the max possible value, and input size is 20k, we can try binary search the answer directly, i.e., just use the bsearch to introduce the final answer, and run through the sequence of actions in the reverse order, and see if it is consistent with the band before the contest

750D: New Year and Fireworks(!!!)

Why I was stuck during the contest

1. I realize that the input size is small enough that I can keep states to avoid recomputing, but my upperbound is too much, in fact, each direction needs only 150 cells, but my bound is too loose at 300. Therefore, I spent much time reasoning about memory usage 
 - I calculated one more 0!

2. I was not sure about how to implement the starting point in the middle of the map. Should it be at (160, 160) or (0, 0) ? In retrospect this doesn't matter much.

3. For the state to capture, I failed to identify the depth itself is enough to uniquely identify a state

Code-wise, I had problem how to handle the start of the whole sequence. It turns out I should do all the step iterations within that step call, because the state [curStep] we capture is unique, so we don’t have to worry about other steps overriding our curStep=0 case, that is , it represents at (x, y), we are about to start at step i, with direciton heading at d

The overall memory = 300 * 300 * 8 * 30 < 25 mil, each cell in memory is filled once only => the running time is same

722D: Generating Sets

Since we care about the max number, we can bsearch on that number, and reduce it to the prefix to fall under that, if there is no space, they we know the lowerbound is too low.

Note that my first idea is to be purely greedy: highest number try reducing to the lowest number, but I had difficulty proving it, and it actually failed one of the test cases

682D : Alyona and Strings(!!!)

Idea 1: Greedy (My approach)

Calculate LCS at (i, j), and then for the best(i, j, k), it is the best of

1. best(i-1, j, k) => pass the current pair

2. best(i, j-1, k) => pass the current pair

3. best(i-lcs(i,j), j-lcs(i,j), k-1) => try using the current pair

Idea 2: Pure DP (Official answer)

I realize the kernel of the problem is that need to know if the tail of the string pair is used, so that we can know when we glue the new pair if it is a new segment. This means the best(i, j, k) state is not enough, and we need to introduce another flag to mark if the end pair is used

Note that to handle the “previous” index nicely, we will use then length as state instead of index

When s[i] = t[j], best(i+1, j+1, k, 1) = max(best(i,j, k, 1) , best(i,j, k-1, 0)) + 1

the base case is best(i, j, k, 0) = max of

1. best(i-1, j, k, 0) => ignore the current end pair

2. best(i, j-1, k, 0) => ignore the current end pair

3. best(i,j, k, 1) => use the current end pair

The final answer will be best(n, m, k, 0)

1. Why does F1 support Protocal Buffer as table column?

2. Why schema change in F1 is non-blocking?

3. Give use cases for lock column feature

4. Why F1 decides to move change history to its owm level?

5. What is the role of Spanner in F1?

6. Why perssimistic transactions requires stateful F1 server?

7. Why the user should always try to use single-root transcation

8. When we design schemas, when we use repeated fields in protocol buffer, and when to use child table?

9. What is the cost of using global index, what is the usage practice, and why is that?

10. why it is not practical to update schema atomically across all servers?

11. F1 applies schema change asyncly, how does it handle/prevent conflicting changes?

12. What is the difference between Snapshot, Pessimistic, and Optimistic transcations?

13. What is the insertion phantom problem?

14. How is the change history inside F1 implemented?

15. Why disk latency is not a huge problem for F1 queries, unlike traditional DBs?

16. What are pros and cons of streaming result immediately?

17. In deploymnet, why do we need read-only replicas?

18. Multi-region replicas means higher latency, how do they mitigate it?

Consider the number of spare balloons we can spare

while we can spare more, give more to the next rank, and then delete ones that can be floated, keep going until we have no more to spare, and keep track of the best rank in the mean time

Implmentation-wise, using a double pointer style for-loop is way easier to reason than a while loop, even though while loop seems more intuitive - took me an hour to figure it out.

This is similar to the first version. However, this approach failed on test 10!!!

The key insight I was missing is that we should only try getting rid of the teams ahead of us. Otherwise, our final rank can not be improved regardless

Algorithm

	1. Add all t > k to the priority queue

	2. while we can remove from the PQ, we remove, and update the current k count.

	3. Since now we reduced k count, we need to move pointer further to include more entries > current k

724C: Ray Tracing

Claim: the ray will always hit a corner

Proof: If not, then we will form a closed loop, however, since we start at a corner, such loop is impossible

Claim: the ray hits each point only once Proof: If not, then we will have a case where it comes in the oppsoite direciton to where it is from. Since the whole sequence is reversible, this means it will come from a corner and to a corner

Algorithm

	1. For each 2 * n * m points, keep track of when it is first hit
	2. Simulate the process by calculating the next point to hit, and the hit time
	3. For each point, calculate from which x or y axis it is hit, take the earlier point, and add the distance to the answer

Note that map<PII, LL> can fit in all cached answers, if we use it to store only reached points

706D: Vasiliy’s Multiset

Maintain a set for inserted numbers and its count to handle type 1 and 2 request

For type 3 request

	1. Use set.lower_bound() to decide if there is entry for the best prefix + 1, with this we can know if it is possible to put 1 bit or 0 bit on that position 

	2. look at the requested number, and pick the opposite number

	3. start with 2^30, all the way to 2^0

Note the bitwise operation is a bit tricky. Took me some time to think it through. On our bit search, we have the assumption that this search will yield a number in the set, by induction.

735C: Tennis Championship

n = 2 , answer = 1

n = 3, answer = 2

Given the max number of games the winner plays, what is the min number of players we need?

g(n +1 ) = g(n) + g(n - 1) => this is the fibonacci sequence starting at n = 2

So we can calcuate fib until the answer > n, and the previous number is the answer

note that we need to keep track of the answer x as well, since we are calculating f(x)

740C: Alyona and mex (!!!)

When the subarrays have no overlap, trival case, just plug in into each gap, i.e., ans LT min length of the subarray, i.e., there is no point putting more than that number in that array

	0. Int final answer to 0
	1.  Get all subarrays, and sort by the start index, we also keep track of min gaplength
	2. For each subarray, scan it first to get what elements are populated, and then fill in the blanks with misssing ones

What if the input is n = m, and each l = 1 and r = n? This means we can not scan all entries for segment

Therefore, we just construct the array as 0,1,…,ans, 0, 1,…ans. This will make sure any segment of length ans in the answer will have the exact set we need

734D: Anton and Chess

For all 8 differnet lines, keep track the closest one to the king, and its type, and finally decide if it is possible

732C: Sanatorium(!!!)

Idea 1: Formula

min number of missing meal means number of days stay = highest number of on the list

If all 3 numbers are same, no missing.

If only 1 number has highest value:

number of full days = highest number - 1, and then the other 2 meals have 3 * number of days

if two numbers has highest value, 3 possiblilies,

	1. (b, d) = full days? not really! consider the zig zag pattern!
	2. (b, l) = full days, in the final answer, --dinner
	3. (l, d) = full days, in the final answer, breakfast--

Idea 2: brute force

brute force the tuple of (arrival, departure)

732D: Exams

Start from the tail, keep track of which exams we have to pass.

If it is a new exam, add days to the budget

If it is idle or seen example, budget–

Then we bsearch on the position of tail

733C: Epidemic in Monstropolis(!!!)

Obviously, before sum = after sum

so given the first item, we can calculate which items that final item is made of

if no such index exists, or if all items scanned are the same, it is not possible. Otherwise, start with the first heaviest monster in the left, and then eat all the way to the left, and finally eat all the way to the right

repeat for each item segment

What is wrong with this algorithm?

	1. I got WAed because my first biggest monster approach does not work in the case of [2, 2,1 ] => 5.

	2. To fix it, we just need to find the first maxI that can move, and then be greedy and try to each as much as we can
	
	3. My checks of two arrays having the same sum is implicit. Therefore, it didn't catch the case where a's sum > b's sum

733D: Kostya the Sculptor(!!!)

A lot of implementation details in the answer

1. Should separate the case of alone and combined, i.e., the map we use should handle the combined case only

2. Because we are looking for the best of 2, we need only to store the best bottom only. Storing the best two makes the implementation complicated => this is what gave me WA

3. To avoid adding to itself, at each item, we hold on all update to the state until all quries related to the 3 choices of bottom are done

727C: Guess the Array

Consider n = 3 case, we can just a1 + a2, a2 + a3, and a3 + a1 to solve it. We can use it as the seed for the n > 3 case

1. a1 + a2, a2 + a3, a3 + a1, solve a1, a2, a3, as per n = 3 case

2. a1 + a4, a1 + a5....., all the way to a1 + an

697C: Lorenzo Von Matterhorn (!!!)

since node id < 10^18, each path has at most 64 nodes on the path i.e., there is at most 64 * 1000 entries we need to update for each node, we just record its edge length

When operation is update

start from the tail, update the edge cost one by one

When operation is query

start with the bigger number, because child id > parent id, calculate the path all the way to the LCA. Do the same thing for the small number

if small number is prefix of big number, return num1 - num2, otherwise num1 + num2

The bug I made in the code is that I used root instead of LCA! There were also function parameters where I used int instead of LL.

This problems shows again that in a tree, for the two nodes, the importance of LCA

723C: Polycarp at the Radio (!!!)

Idea 1 (my approach)

Assume all bands are within the m, then just take the average, that will be the target number, then swap until all counts are either floor(average) or floor(average) + 1

when some numbers are outside the 1..m range, we will replace them only if n - oor < average * m < n

Algorithm:

	1. count number of appearance for each number, and target

	2. scan through the array, if the band is oor, replace it with the next avaialbe one. If the band is one of the bigger ones, replace it with one of the underbudget ones. Note that we reduce oversied item to target + 1 instead of target at this step 

	3. scan through the array again, if there is any uninserted left, reduce the target + 1 to target

The mistake I made during coding is that the 2 rounds checking condition is inconsistent. One checks if the queue is empty, the other checks if the number is OOR. We need to check both in both places!

Idea 2 (official)

Notice that we just want to minimize the number of total operations, therefore, we can replace all overbudget ones first with under budget ones first, and then in a second loop, repalce out of the range ones.

This works because total # of operations is determined the total count of budget deficits, and has nothing to do the the order or selection of which over budget band to reduce

The main benefit of this approach is that we don’t have to worry about the nasty n+1 case, i.e., the final shape will have as many bands m with songs as possible, as a comparison, the shape of my solution is to have lowest highest count

723D: Lakes in Berland

DFS to find all connected waters, also for each water, mark if it is a lake or not, add it to the set of ids. Finally, scan through all cells, and fill the cells with marked ids

719C: Efim and Strange Grade

Suppose we have an optimal rounding plan, it should be applied from right to the left, because a rounding operation will kill off all digits to the right.

So we calculate c[i] = min cost to change d[i] to d[i] + 1

1. if d[i + 1] >= 5, c[i] = 1

2. if d[i + 1] < 4, c[i] = -1

3. if d[i + 1] = 4, c[i] = c[i+1] + 1

In the end, we scan from left to right, and find the first c[i] <= t

747D: Winter Is Coming

What I did wrong during the contest

1. Forget the impossible / -1 case, but the fact that have that check for the turing postive tail into negative case suggests such inconsistency is checking of calls means problem.

2. My approach to the problem is slightly different. Instead of focusing on the negative segaments, and dirve formula based on that, and I just assume gap + 1 as number of segments, but this formula is wrong when there is no segments at all!

I realized that the special case of last element being negative or not, but instead of using the “last one positive” as base case, I used “last one negative”, but this one does not affect the code complexity

749C: Voting

• What I did wrong during the contest
  1. I thought about simulation, but I was not able to prove it will terminate quickly given 200k input size
  2. I was not able to prove the optimal strategy is indeed optimal

Why simulation run time could work

For each vote, the total # of voters is decreased by one. Moreover, if a person is denied,we will remove that person from the line anyway. This means we will iterate through denied person O(n) times, and undenied person O(n) times

Why the official stragety is optimal

For the first element, assuming R, obviously need to deny one D before the next R.

Now suppose we have RDRDR as we go, with the first D ready to vote,

1.If veto the first R, then any D can be vetoed by the next R. Similar argument goes for vetoing the third R

2.If veto the second R, then any D has a chance to not get vetoed, because later D MAY deny further Rs

3. If there is no D after the first D, then it doesn't matter which way we choose, i.e., as long as we pick a strategy and we know it is optimal for this case

675: ShortestPathWithMagic(!!!)

Hint

Naive way would be to use the city graph as is. However, the potion makes the graph variable, but most graph algo we know requires constant graph. This suggests we should transform the problem so that the existing graph algorithm can handle it. Note that all common graph algorithm we know does not handle varaible length of edge

Algorithm

Instead of using city as node, we use (city, number of potions left), and construct graph. (c, n) to (c, n) keeps the same length, and (c, n) to (c, n-1) uses the half size.

Finally we run dijkstra from (0, k), and find the best by scanning all (1, i)

675: TreeAndPathLength3

Note that s can be 10000, but node can be no more than 500. So what is the construction that gives most 3-simple path?

So x * y + y + z - 1 is the max construct, so we set x, y both to floor(sqrt(s)) - 1, and append the remaining nodes as a single line to node 1

676: BoardEscapeDiv2

good(r, c, s) = false if any of the following is true

	1. s = 0
	
	2. grid(r, c) is an exit

	3. all of good(r+ i, c + j, s -1) is true, |i| + |j| = 1

Otherwise, good(r, c, s) = true

676: WaterTank

Just bsearch R, and make sure with R set, the residual never exceeds C

The classic transformation: instead of asking what to delete, we calculate what to keep.

We can use dijkstra to grow the tree, if the node is included via a railroad as part of expanding process, then we know we have to keep that railroad, otherwise, the shortest path to that node is increased. Conversely, if we reach that node without using the railroad, we can get rid of it.

Pseudo code

	1. add (0, (1, 0)) and all (yi, (node, 1)) to the PQ 

	2. take the top member from PQ, if the node has been discovered, ignore

	3. Otherwise, set top member as discovered, and add (curdist + xi, (v,0)) to the PQ

	4. if the top member is marked as type 1, i.e., uses railway, mark that railway is used 

	5. repeat 2-4 until PQ is empty

	6. scan through to get # of rail roads used, and return k- total

149C: Division into Teams

Sort the players by score, then biggest one goes to team A, and next one goes to team B.

Claim: This arrangement satisifes the conditions

Proof: Obviously condition 1 and 2 hold, and obviously s(B) < s(A)

Can also proved in a geometrics way

107A: Dorm Water Supply

Since each house has at most 1 in and out edges, for each node, we can keep track of prev and next node, and start with nodes where prev[node] = node, and find the most narrow pipe

255C: Almost Arithmetical Progression

Case q = 0 ———- just just the element with highest count

Case q != 0

For each element, try it as p

Linear scan, for each p, maintain 2 length[i], current subsequence length, state[i], min index of p needed to increase the subsequence length

If a[i] = p, update lastPI

If a[i] != p

	1. get the id for current value
	
	2. check the needPI[id], if it is >= lastPI, do nothing, note that needPI is init to -1

	3. otherwise, length[id]++, and needPI[id] = i + 1 

Then scan from the tail, find the position of the last p and second last p, for all number between them, length[id]++

and then find the highest length

148D: Bag of mice

Pr(p, w, b) = Pr(white) + (1 - Pr(white)) (1 - Pr(d, w, b-1))

Pr(d, w, b) = Pr(white) + (1 - Pr(white)) (Pr(white jumps) * (1 - Pr(p, w - 1, b-1)) + Pr(black jumps) * (1 - Pr(p, w, b-1))

Pr(p, 0, i) = 0

Pr(p, i, 0) = 1

Pr(d, 0, i) = 1

Pr(d, i, 0) = 1

616D: Longest k-Good Segment

When we try adding the current element to the segment

	1. If a[i] is in the set already, move the right pointer, update the right most index for that value, and the current best length

	2. Otherwise, move the left pointer, until the left pointer is greater than the right most index of that value. Also, remove that value from the set, and add a[i] to the set

271C: Secret

for group ki, just assign 2(ki)-1, 2 * k to that group, and then the next k element to the group 1 to k, and remaining elements to group 1

444A: DZY Loves Physics(!!!)

Claim: that highest density subgraph can have only 2 nodes and 1 edge

Proof: suppose the target subgraph has more than 2 nodes, then for each (u, v) pair, in the graph , the density is sum(U) + sum(V) / sum(e(u, v)). However, we know that there exists u + v / e(u, v) >= that density. Otherwise, the equation is no longer possbile

140C: New Year Snowmen(!!!)

Solution 1: bsearch on the final answer with construction algorithm

Claim: we can form k snowmen, if and only if then there exists an arrangement takens from sorted number array, (1, k+1, 2k+1), (2, k+2, 2k+2), on condition that no number appears more than k times

Proof:

Construction => result : obvioius

result => construction

	1. at least 3 * k snowballs. 

        2. no number appears more than k times

	3. Therefore, if we sort all snowballs, this arrangement can still work, because of 2) 

Solution 2: greedy

Claim: all quantities are < k and total >= 3 * k <=> we can form k snowmen with min number of snowballs

Proof:

Condition => result

	1. if there are >=3 numbers appearing more than k times, obviously

	2. if there are one or 2 numbers appearning more than k times, take these 2, and another random one, and do induction

	3. if there are no number appearing more than k times, we just take any 3 numbers, and do induction

Result => condition: obvious

700A: As Fast As Possible(!!!)

I failed to solve this problem during contest. I thought the bus had to take students to the end and then head back

Insights

1. To be able to minimize the time, all students should arrive at the same time. Otherwise, the bus could have headed back earlier and helped the slowest one

2. Since input is 10k max, we can do a bsearch on number. Because we have the insight 1), the related search would be the final time every one arrives. Note that our epsilon is 10^-6

3. Because each group arrive on the same time, and v1, v2 are constatnt, that means each group spend on the bus for the same amount of time. This furthur suggests the time spent to meet the bus heading back is same across all groups

4. Therefore, we can calculate by multiplication, how much time bus has been running, and as long as bus run can conclude within t, the answer is possible

Remember to setprecision to display required number of precisions

645A: Amity Assessment

The DFS-state approach is too complex to code for this problem. For this problem, we notice that no matter how we move, the relative clockwise order of tiles remain same.

Therefore, it is enough just to form a 3 element string from inputs (minus the x), and see if we can rotate the from to form to

592C: The Big Race

If it will be a tie if, L is within the range of (i* lcm(w, b), i* lcm(w, b) + min(w, b))

So total # = (t / lcm(w, b) - 1) * min(w,b) + min(w,b) - 1 + tailBand

Note that need to handle the case where min(w, b) > T

53C: Little Frog

n = 3, 1 -> 3 -> 2

n = 4, 1 -> 4 -> 2 -> 3

n = 5, 1 -> 5 -> 2 -> 4 -> 3

The pattern is obvious now

717C: Potions Homework

Sort the student by laziness

Claim: the optimal is achieved when lowest lazyness is paired with highest difficlutiles

Proof: Exchange proof. Suppose we have l1 LT l2 and d1 LT d2, we can improve the solution by pair l1 with d2 and l2 with d1

l1 * d1 + l2 * d2 - l1 * d2 - l2 * d1 = (l2 - l1) * (d2 - d1) > 0

12C: Fruits

Sort the fruits by numbers

Max total = max # of fruit is most expensive

Min total = min # of fruite is most expensive

Exchange proof, note that the swap works for both ways

616C: The Labyrinth

Flood fill on each passable cells, for each passible cell assign the component number, and then for each wall, get the set of its neighbor component numbers and add up

635A: Orchestra

Calculate n(r, c) = number of vs in the rectangle with bottom right corner at (r, c), note that n(i, 0) = 0, and n(0, i) = 0

n(r, c) = n(r-1, c) + n(r, c-1) - n(r-1, c-1)

Then brute force on all (prevTop, prevLeft, br, rc) combos, find all combons such that n(br, rc) - n (prevTop, rc) - n(br, prevLeft) + n(prevTop, prevLeft), note that prevTop < br and prevLeft < rc

1. Why does raft use randomized timout values?

2. “GFS and HFDS use a seprate replicated stat machine to manage leader election and store configuration”, what does the author mean? Give concrete examples.

3. What is the max # of servers that can fail while raft is still avaiable? what is the min # of servers that can fail while raft becomes unavailable?

4. Descript the seqence of actions when a CANDIDATE handle an incoming AppendEntries call?

5. How can a candidate discover current leader or a new term? Why it becomes a follower upon such discovery?

6. During election, it is possible that no one is elected, how can that happen? How does raft deal with that?

7. consider the cases of leader/follower crashes, where can these scenarios happen?

        a. follower may have missing entries
   
        b. follower may have extra uncommited entries
   
        c. follower may have both missing entries and extra entries
   

8. When and how will raft fix the inconsitences in Figure 7)?

9. Why we need to ensure that any elected leader for an given has ALL of commited entries from the previous term? Why this property is satisfied in raft?

10. Describe the scenario in Figure 8

        a.replicated on majority of servers but not commited entry
    
        b.such entry in a) got overwritten
    

11. What if broadCastTime « electionTimeout is violated? what if electionTimeout !« mean time between failures (MTBF)?

12. Describe the disjoint majorities problem, how they can be triggered during membership changes, when each server just switch directly

13. What happened when cluster leader itself is not included in the new membership?

14. Give a scenario where removed cluster members can trick the new leaders into a follower, if without the remedy done by the raft.

15. What kind of metadata should snapshot include?