319B: Psychos in a Line (!!!)

This problem is not easy even though it appears so.

Idea 1

Observe that we definitely want to know something about the number that

1. j < i

2. a[j] > a[i]

3. j is the biggest about all that satifies 1 and 2

if a[i] < a[i - 1], then time[i] = 0;

if a[i] > a[i - 1], then

1. if time[i - 1] = -1, i.e., always alive, then time[i] = -1; 

2. if time[i - 1] >= 0, and there exists j that satifies the conditions we mentioned above,  time[i] = max(time [(j...i)] + 1. Note that this upper bound is achievable and thus is the optimal answer

3. Otherwise, time [i - 1] = -1, it is always alive;

To calculate j, we can use a stack to keep track of numbers, and popping until we reach the one that is greater than the current one, and then add the i onto the stack

Note that number of steps = time to kill + 1

Also note that, the answer for case 3 2 1 is 1 instead of 0!

Idea 2

Consider a brute force O(n^2) solution

1. For each turn, we maintin the state of the array, and we add new item one by one to all turns

2. If end of the list > current to add, we mark current dead at turn i + 1, and add it to all at turn 0 to i 

3. The final answer is the max of all kill times

Now we need to optimize it to O(n)

1. For space, obviously, we need to keep track of only the right most entry

2. For time, instead of iterating all entries, we just put it on the stack, and remember them top to bottom 

3. each interval got put on stack at most once.

359D: Pair of Numbers(!!!)

My idea

Assume they are all distinct Suppose we have one such collection, it must be of V shape in terms of values

So we start with each local minimal points, and try expanding, because of that v shape-thing, we know we cover each point at most once So we try calculating longest right-expanding sequence, and then reverse and calculate the longest left-expanding sequence, and then sum it up

Note the corner case where all values are same, we will have multiple entries

Official solution

Binarly search on the value of r-l, use a data structure to answer GCD(l,r) and min(l, r),e.g., a segment tree-ish DS

358D: Dima and Hares(!!!)

Brute force DP seems to be O(n^3). How can we improve that?

Notice that we have a lot of overcalculation here: place 1 and then 3 is same as placing 3 and then 1,i.e., we need to find a different angle.

Consider the leftmost entry. We have two choices

1. Fill 0 with 1 is empty => equivalent of totalCost(1...n, leftFilled) + cost(0, single)  
2. Fill 0 while 1 is filled already => equiavlent of totalCost(1..n, leftNotFiled) + cost(0, double)

For easier coding, we can reason the same thing but start with the rightmost