Ups, sorry, already fixed!

It's hard to estimate... You can check previous rounds to have some grasp on the difficulty. I'd say it's easier than the Code Jam, but this is my personal opinion.

its still not working.scoreboard is loading....

I see 2 people on the scoreboard, but where are the problems??

codejam 2018: Guys we don't think it's a good idea to use the new UI kick-start 2019: GUESS WHAT

I was about to post the same comment here about 15min before the round was to end.

But even CF was down. Lol you won the race :P

Observation:

1. If A >= B (A fully contains B), there must exists some OPT ordering where B is ordered before A. (If A is committed before B then B will get 0 seats so obvoiusly no)

2. If two order does not share a seat then their relative order does not matter.

Construct a DAG from the >= relationship. We shall try to place "smaller" orders before larger ones, in a toposort fashion. Pick any order that does not contain a unprocessed order(segment), Pick all other orders which do not have an unprocessed >= relationship in the toposort and overlaps with the current order (recursively), call this a group. We binary search for k on each group (and take min of all afterwards), use two pointer to check if all order got at least "mid" seats (two pointer from i-th order in the group to j-th order in the group, the starting point of the i-th order is only affected by the ending point of the (i-1)-th order), while using some range query data structure to query the amount of unprocessed seats in the range.

Time complexity: O(n lg^2 n)

First binary search the answer. Let the current answer be $$$k$$$.

Consider the intervals in the reverse order (i.e. from the last interval in the schedule.). For example there are three intervals $$$[1,5], [2,4], [3,6]$$$, and $$$k = 2$$$ now. We know that $$$[1,5]$$$ cannot be the last interval since we know that if so, $$$[2,4]$$$ and $$$[3,6]$$$ already covers some range and $$$[1,5]$$$ can only have seat $$$1$$$. $$$[2,4]$$$ cannot be the last interval for the same reason, but $$$[3,6]$$$ can be the last interval. As long as there are intervals that can be put in the last position, we put them and the problem becomes a smaller one. If there are none, then the current $$$k$$$ is not possible, and we switch to smaller value.

Different implementations of this can lead to different complexity. It will be easy to get the small with the idea above, but I am still thinking about how to use data structure to solve large.

From problem C editorial:

"Another observation is that at every step we can always choose this request greedily from the remaining set: the one where we can book the maximum number of seats."

Shouldn't we pick the request which yields the min number of seats as it will only drops when we allocate more and more seats?

In C, does the editorial simulate the process from the end?

"Another observation is that at every step we can always choose this request greedily from the remaining set: the one where we can book the maximum number of seats. ... At every step we intend to find the request where we can book the maximum seats, remove this request from the set and recalculate the number of seats we can book for the remaining requests. "

During the contest, I implemented a solution where we greedily take an interval with the smallest number of available seats. Got WA and then found a countertest :(

the submit button is not worked in last hour, I cant make submission for B and C then, what will be the solution of that? there is also a public announcement regarding this

Even I want to know. What is the procedure of submitting there. Not close to codeforces way of submitting.Found this: https://code.google.com/codejam/resources/quickstart-guide but still unclear

Line 43, not necessary you are going to put a delivery office if the distance is greater
than K , besides that there is another bug that neither I don't know yet.

010

000

if you skip distance 1 cooridinate, you get answer 2. but it's 1 selecting the (2,2) point

Consider the four corners of a box, the first term is "dist(top right, bottom left)", second term is "dist(bottom right, top left)". With the bottom left corner as (0, 0).

In the last line , did you mean non-increasing?

Thanks. Your answer is crisp and clear. But after reading your answer, I still don't understand following in their editorial: "the number of unique ranges that the requests cover is at max 2 * Q, which would make our solution run in O(Q^2) for every test case." — From where did the factor of 2 come in 2*Q? I don't understand this line. Shouldn't the maximum unique ranges be Q if we are given Q queries?

Interesting. It sounds like you are using similar concept behind randomized trick Radewoosh mentioned?

In this case the answer is 1 and your code gives 2 as result:

1
2 3
010
000

It is because the farthest point is not necessarily the optimal.

Do a parallel binary search on a min segment tree.

Since we are considering a query to be the last query in remaining set, maximum possible seats means the number of seats requested only by this query, as if a seat is requested also by another query, it would have been already given to that query. So, for 2 intervals[1,4] and [1,2], seats available to [1,4] is 2 and seats available to [1,2] is 0, so we select [1,4] as last query. Now, seats available for [1,2] is 2 and so we select it as 2nd last query/first query. And since both queries has 2 seats, our answer will be 2.

Someone already did. Just read the comments.

Here is what I did: first calculated distance of each node from the current delivery office using multisource bfs then do a binary search on the answer k. For a valid k, we have all distance less than or equal to k so adding a new position (let it be a,b) as delivery offices only affects the positions x,y within the rhombus: abs(x-a)+abs(y-b) <= k so you only need to verify that does there exist a point in which all > k current distance nodes are all inside the rhombus which can be calculated easily using maximum x+y, maximum x-y, minimum x+y and minimum x-y of all the points with distance > k. CODE : https://ideone.com/uBTBJx

For two points (r1, c1) and (r2, c2) we have four possible cases.

1. r1 < r2 && c1 < c2. So distance here is D = r2 — r1 + c2 — c1.
2. r2 < r1 && c1 < c2. So distance here is D = r1 — r2 + c2 — c1.
3. r1 < r2 && c2 < c1. So distance here is D = r2 — r1 + c1 — c2.
4. r2 < r1 && c2 < c1. So distance here is D = r1 — r2 + c1 — c2.

Now lets fix (1). Its equal to D = (r2 + c2) — (r1 + c1).

Also lets fix (4). Its equal to D = (r1 + c1) — (r2 + c2).

This means that case (1) and case (4) is equal in absolute value. These cases stand for the first term in the tutorial. With similar method you can take that (2) and (3) stand for the second term in the tutorial.

So if we use abs() we don't have four cases but two cases. The team of (1)-(4) and the team of (2)-(3). Also the real distance is the maximum of these. You can convince yourself with an example, because if you use the 'wrong team' it will give you less than the real distance. So taking the max() of these is optimal.

Now that we are convinced that the formula works, between two points (r1, c1) and (r2, c2), if we build an office at point (r2, c2) we would like to iterate over all other points. But for every pair of points we will use the same equation. Each term of the equation is of the form:

T = max(a — b, b — a). (because of the abs())

So if we have fixed 'b', isn't better to take 'a' as large as possible or as min as possible ? Intuitively we want 'a' to be as far as possible from 'b'. So having the minimum and the maximum possible 'a' is enough, because for EVERY 'b' its always better to pick the maximum or the minimum 'a' rather than one in between (you can visualize it with a line).