how to solve the last one?
GRUMPMA could be solved using Basic DP.
Click here to view previous answer
Traverse the rectangles in reverse order.
Observe that computing answer for only first quadrant is sufficient.
Now you will have to add contribution of area of one rectangle when you add that rectangle.
The final figure after adding any rectangle will always be like ladder.
So keep track of upper right corner of each rectangle which are involved in ladder using a set/map.
( Maintain convex hull type shape (which will be ladder in this case) in a set/map and keep removing points which are not necessary/involved for ladder after adding upper right corner of current rectangle)
Only points which are being removed after adding current rectangle will contribute in calculating area of current rectangle. So you can iterate them linearly.
You can find the starting point of set of points which should be removed using lower_bound.
( They will be in subarray of given set)
As set will be sorted according to x coordinate.
Reframing my answer.
Let’s count area only for first quadrant and then we can multiply it by 4.
Add rectangles in reverse order. And count area which will be visible after adding it.
The shape after adding any rectangle will always be like a ladder.
Keep track of ladder by upper right corner of each rectangle.
Maintain the ladder using a set ( sorted by x) (insertion/deletion) You can use that ladder to count the area as well.
The points which are to be removed will only contribute in counting area of current rectangle.
Use lower bound on set/map to find points which should be removed after adding current rectangle.
2 Likes
can you elaborate how to solve the problem. I tried but was not able to come up with a solution
can you provide the editorials? by the way nice contest
clash between codeforces div 2 contest and codechef dcode and codechef code war.
how can one person can be at 3 place at same time!
I think codechef itself should manage this!!
pls explain the solution of this problem GRUMPMA
Code war was unrated and Codechef do not force any unrated contest to change timings unless it’s very much necessary.
You should have requested code war’s organizers for the same.
About D’code you can ask D’code’s organizer’s.
but there is contest on codeforces too
Codechef should consider that platform at least if codechef is not for profit
It was really great to be able to compete! Please provide editorials for the question ! that way it could help us improve !
According to some discuss post organizers of this contest finalized date 1 month ago when codeforces contest was not declared.
It doesn’t make sense if Codechef denies taking contest on this date after approving it one month ago just because of a contest on another website.
Non profit kaha se Aya isme ?
From 3 idiots : kehna Kya chahte ho ?
1 Like
I have posted an unofficial editorial on that. You can refer to that.
1 Like
Thanks @roll_no_1 for your feedback. Sure, next time we will try to scale the event further up and get it rated for all.
Yeah, maybe the background stories (Theme: Fullmetal Alchemist) did make the problem statements somewhat long. However, we added illustrations wherever required to make the problem very clear. We will work on improving this in the next iteration.
1 Like
@sachin_yadav
The contest was a brilliant one, an ideal one for guys like me atleast 
. Keep up the work and try to get it rated for all next year. 
1 Like
Thanks @teddysphotos for the wonderful feedback for the contest.
Sure, we will work on keeping the problem statement more concise in the next iteration.
Thanks @chaos . We will work on keeping statements concise next year.
For the corner cases, CodeChef team did really help us a lot for strong test files in the contest.
When will it be rated?
1 Like
After long challenge ends. Next to next Monday
2 Likes