### zoooma13's blog

By zoooma13, history, 17 months ago, , IOI tasks are now available on IOI Website.

Live Scoreboard Comments (17)
 » Can someone elaborate how to solve the third subtask in seats problem.3. (20 points) H <= 1000, W <= 1000, Q <= 5000Thanks in advance.
•  » » SpoilerMy approach: Let Bk be the bounding box of all numbers from 1 to k. If area(Bk) = k, then Bk is beautiful. Conversely, if R is a beautiful rectangle and area(R) = k, then area(Bk) = k. And finally, if area(Bk) = k, then area(Bk + 1) > k, because if R = Bk is beautiful, then either Rk + 1 or Ck + 1 is outside of the bounding box Bk. Without loss of generality let it be Rk + 1. It follows that k + 1 is the first contestant at row Rk + 1. So, all we need to remember is the contestant with the lowest id that is in the row i, and the contestant with the lowest id that is in the column j. We can do this by simply maintaining an ordered set of the indices of contestants for each row and column. This can be maintained in per query. Using this, we obtain H + W candidates on the beautiful rectangles in O(H + W) time and we simply check all of them.To check a candidate for a rectangle, we have a segment tree for calculating the minimum/maximum row/column on a range. This gives us time algorithm to process one query.Combined together, this is .
•  » » » To check a candidate for a rectangle, we have a segment tree for calculating the minimum/maximum row/column on a range. -> we can improve it to O(H+W) easily. (update r1, r2, c1, c2). Overall time complexity is O(HW + Q(H+W)).
•  » » » » Can you explain more on how it can be improved?
•  » » » Would 10^7 segtree operations really pass?
•  » » 17 months ago, # ^ | ← Rev. 4 →   My solution involves just iterating all the positions and recomputing for each query. You will get a total of 37 points with this. SolutionLets define a beautiful box Bk as a box containing only numbers 0 to k-1 I would sore in array arr[id] = {r, c} the position of each contestant. Then for a bounding box Bk to exist the prefix arr[0..k] should form a rectangle. For that I get the min/max for column/row in the prefix of size k and check if the rectangle is exactly of area k. If yes then that is one box. So I compute this in O(HW) and build an array stating if Bk is a bounding box or not. When each query arrives I will update positions a and b and recompute the positions of the array in the range a and b in O(|a - b|).
•  » » » how can this pass in TL ? isnt it O(q*HW) ?
•  » » » » THe thing is you first do $O(HW)$ to compute all good prefixes (the ones which form a rectangle) when you do a swap $O(|a-b|)$ only $10,000$ prefixes can change and hence you only need to check those to update your total count of good prefixes and answer the query.
•  » » » » » I am talking about the 20pnts stask. there, the (|a-b|) = 10K constraint was not there.
•  » » » » » » Oh, I see. It is right it doesnt work for the 20pts, I might have missed that. For the 20 points the number of rectangles is less than 4000 and you can compute them iteratively starting from the 1x1 rectangle and then expanding it to include the [MEX](https://en.wikipedia.org/wiki/Mex_(mathematics)) of the current rectangle. For that you only need to have the MIN in each column and each row which can be updated on every update.