Блог пользователя kostka

Автор kostka, 8 лет назад, По-английски

It's almost here! KickStart rounds kick off this Sunday, March 24 with Round A at 4:00UTC. Get ready and register now at g.co/kickstart.

 .

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

The URL is appended after codeforces/blog/entry, please fix that : )

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

What would be the difficulty of the round ?

»
8 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +30 Проголосовать: не нравится

I can't see/view the problems/scoreboard :(

EDIT: Now it works

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится
»
8 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится +26 Проголосовать: не нравится

Codeforces finally works... Didn't even have a place to complain about the competition...

Failed to submit C small... should've get a better rank. We even cannot say, "Hey, please make this unrated." like what we usually do when such things happen in Codeforces.

»
8 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Oh boy, I can't wait to see all the rants when codejam also transits into this UI and judging system. Good luck on dealing with all the lagging issues.

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +16 Проголосовать: не нравится

What was your approach on problem C?

  • »
    »
    8 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +1 Проголосовать: не нравится

    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)

  • »
    »
    8 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +5 Проголосовать: не нравится

    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?

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +16 Проголосовать: не нравится

how to solve B ?

»
8 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

In question B, if we take all zeroes except 1 at one corner, one of the accepted solutions will have a complexity of 10^9 and another code 4*10^8 for this test case. How does 100 test cases with similar test data doesn't give his/her code a TLE?

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Hints for B and C?

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

Editorials were published and are available in the problem view.

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please tell why I am getting Run-Time error for training Problem, My code : "https://ideone.com/e.js/oRGkWq

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Why does my B WA?

I've done what the editorial said, it passes samples but fails the main tests

https://ideone.com/iDlNtN

I think there might be something wrong with my check function if I misunderstood the editorial

In my check function, I take maximum and minimum over all x+y and x-y for all points where their current distance from a post office is >k

Then I individually check each of these 4 values to see whether it can lie within the square with centre (i,j)

to do this, each of the precomputed values — (i+-j) must be less than or equal to k

Shouldn't this work?

»
8 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +4 Проголосовать: не нравится

Can someone please explain that in second question in binary search function, how do we find optimal cell which can give maximum distance atmost K in O(RC). I could not figure it out from editorial. They said it is.

dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 — (x2 + y2)), abs(x1 — y1 — (x2 — y2)))

How do we get this?

»
8 лет назад, скрыть # |
← Rev. 7  
Проголосовать: нравится +47 Проголосовать: не нравится

Since there are a few people PM-ing for clarification about the problem C editorial I think I might as well create a short summary here:


Why does picking the min order in the forward direction doesn't work

The issue here is that you are not doing dynamic planning here. While I can't give a formal argument in disproving if this approach is correct with some special tie-breaking method, I cannot prove it is correct either, due to the fact that min(jth request) is dependent on the subset available for the jth request. While it is guaranteed that the order shall generate less seats if they come later, you might not care about the decrease if K is significantly smaller than it.

If this is your first time dealing with min max stuff and you can't see why does such plan causes a bad K in the future, a problem that I would recommend on top of my head is "HDU 6000 Wash".

Why does picking max backwards works here

Before I continue I must clarify the editorial's approach as it is proven to be confusing to multiple readers.

Consider the corner test case provided by Errichto.

N=8 Q=3
2 8
1 4
5 8

What the editorial meant by picking the max segment is that you must imagine that the other segments have been picked prior to the concerned request, for example, the first iteration would be:

[2, 8] : Imagine that [1, 4], [5, 8] has been occupied, and picking [2, 8] last must yield 0 seats.

[1, 4]: Imagine that [2, 8], [5, 8] has been occupied, and picking [1, 4] last must secure 1 seat.

We shall pick [1, 4] as the last request processed (we skip [5, 8] as an exercise for the reader).

On the second iteration, you will prioritize picking [2, 8] as it yields 3 seats. Note that you should imagine [1, 4] as not processed as you are considering [2, 8] as the 2nd request and [1, 4] is chosen to be the 3rd request, which is satisfied after picking [2, 8].

Now we may apply a similar argument: If the request was satisfied after processing only a set of request S, it must yield more seats as it would after processing the set (S union T).

As an informal proof, consider that the request i was picked on time j is the bottleneck of the ordering, i.e. it secures only k seats, let's see what happens if we attempt to process it in another time.

If request i swapped place with the request processed on time jg > j: It will then yield even less seats so the new k must be decreased.

If request i ... time jl < j: Note that we picked request i on time j because it yields the most seats at the time. Swapping it with any other picks must yield less than k seats on that iteration, resulting a worse allocation.

To generalize the proof above, one must show that k is non-increasing even for arbitrary swap. This is left as an exercise to the reader.

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +27 Проголосовать: не нравится

I don't think I've seen anyone else mention it here, but the new "search bar" is incredibly laggy, and the lack of a friends list adds to the annoyance as it was there in the 2018 UI. I'm sure that a good number of other people feel the same way about these features...

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

My solution to problem B was O((RC)^2) and it passed the hidden tests. The key was to randomly order the squares with 0 before checking each of them. I didn't do formal math (just convinced myself with some examples) about this but it seems to work. Did somebody do the math?

My submission

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Would anyone like to point out what I'm doing wrong in my simple solution Problem B's visible tests? I feel like I'm following the analysis properly.

https://codeforces.me/contest/1141/submission/51800899

»
8 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +16 Проголосовать: не нравится

Could someone help me understand the editorial solution to the large test for C? I don't understand how we can quickly determine which seats are covered by exactly one interval. Is this operation provided by the interval tree, or does this need to be determined in some other way?

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Analysis: The number of possible orderings of the requests is Factorial(Q), which would not be fast enough for either of the test sets. We can observe that for a chosen ordering of the requests, the number of seats that we can book in the last request does not depend on the ordering of the previous Q - 1 requests. 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.

I think it's not a right greedy approach to chose a request with maximum possible bookings of seats. Consider a case for 2 intervals: [1,4] and [1,2]. According to this approach[1,4] will be chosen first and then no seat for [1,2]. Hence ans=0 but in the opposite way, we can get ans=2. It is possible that I didnt understand what the statement means. If that is the case please let me know.

  • »
    »
    8 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain in detail how the greedy approach in working in problem C.

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Can someone post the Code(preferably Cpp) for second question that uses the binary search as discussed in editorial? I have cannon figure out how to calculate maximum distance from the location to a square in constant time for all locations that have greater than k values.

  • »
    »
    8 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

    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

»
8 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +3 Проголосовать: не нравится

Please explain this part in the analysis of problem B: "Hence, we can compute the maximum and minimum values of both x1 + y1 and x1 — y1 for all squares with a delivery time greater than K."

why do we need to compute max and min of x1+y1 and x1-y1? why do we want the distance of x2,y2 maximized?

I am having a hard time understanding the analysis :'(

  • »
    »
    8 лет назад, скрыть # ^ |
    ← Rev. 5  
    Проголосовать: нравится +4 Проголосовать: не нравится

    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).