CF #99, prob 138

problem B: given an integer n, find two permutations of the two copies of n such that the sum will end with maximum number of zeros. n has at most 10^5 digits.

I read the problem wrong and was thinking the sum needs to have maximum number of zeros which could be in any position. Then the problem becomes much harder as we now have to deal with sum of tens and sum<=8 to space out the tens, in addition to the trailing block of 0s, 10, and 9s.

Spent two days on it and couldn't find a way to implement the idea. Only after reading the solution did I realize the maximum is on trailing zeros.

problem C
there are n<=10^5 trees and m=10^4 mushrooms, all in one line. each tree has position a[i], height h[i], prob fall left l[i] and probability fall right r[i], both given as an integer between 1 and 100. Each mushroom has a position b[i] and a power p[i]. Each tree may fall left or right with the given probability, a mushroom would survive if no tree hits it. A tree will hit a[i]-h[i] to a[i]-1 with probability l[i], and hit a[i]+1 to a[i]+h[i] with probability r[i]. The problem asks for the total survival mushroom power.

After some thought it seems we need to sort trees and mushrooms. Each tree can be seen as two intervals. And we need to keep track of current probability of killing given what trees are covering this position. This can be implemented as a queue. Each new start will contribute to the current probability by multiplying (1-l[i]) or (1-r[i]). Each exit will remove that contribution. Each mushroom can then be calculate using current probability. However, there is a catch. When there are many trees, the accumulated probability can be very small and then never come back due to underflow. The rescue is from the probability being represented as integral percentage. So we can keep an array of [1..100] for counts of percentages. then we merely incr/decr counts as new start or exit occurs.