Editorial for Just Eat it! and Washing Windows

Problem Discussed Today:

Interview Problem ( From LeetCode )
  1. Delete Node in a Linked List

No editorial will be provided for the Interview Problem.


Editorial



Idea:

If there is at least a prefix or a suffix with non-positive sum, we can delete that prefix/suffix and end up with an array with sum ≥ the sum of the whole array. So, if that's the case, the answer is "NO".

Otherwise, all the segments that Adel can choose will have sum < than the sum of the whole array because the elements that are not in the segment will always have a strictly positive sum. So, in that case, the answer is "YES".

Solution Link: Solution



Idea:

For each window (x,y)(x,y dirty water may reach it through windows (x1,y1)(x-1,y-1 or (x1,y)(x-1,y) or (x1,y+1)(x-1,y+1).
For each window (x,y)(x,y) let’s denote by dpx,y=t the latest moment tt such that some window (p,q) was cleaned at moment tt and the dirty water reached (x,y)(x,y) from (p,q).
We previously stated that dirty water may reach (x,y only from its neighbors. Quite frankly:
t=dpx,y=max(dpx1,y1,dpx1,y,dpx1,y+1)
Because these are the only possible ways such that the dirty water may reach (x,y)(x,y).
Now that we have found tt for our window (x,y). If tt is later than Ax,yA_{x,y} then it will be dirty by the end of the process, otherwise it will be clean.
After determining the answer for (x,y)(x,y) (clean/dirty) we should update dpx,ydp_{x,y}:
dpx,y=max(dpx,y,Ax,y)
Because dpx,y denotes some moment where dirty water reaches (x,y)(x,y) and it will be propagated to windows below (x,y). At the moment, Ax,yA_{x,y} the window will be cleaned and dirty water will start flowing, so we must update dpx,y such that Ax,yA_{x,y} would be propagated as well.

Solution Link: Solution

If there is an error or want to discuss your approach, then please feel free to drop in the comment section.

Comments