kostka's blog

By kostka, 5 weeks ago, In English,

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.

 .

 
 
 
 
  • Vote: I like it  
  • +18
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What would be the difficulty of the round ?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +4 Vote: I do not like it

      yes , , but you said easier than code jam .

      which round you are considering , QR , R1 , R2 or ,WF ?

»
5 weeks ago, # |
Rev. 3   Vote: I like it +30 Vote: I do not like it

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

EDIT: Now it works

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's okay, even Googlers are humans. But they should still ensure such things don't repeat in the future rounds.

      But yeah, we got something after Codechef to criticize xD

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, I tried to hold my rants.... My temper have limits and I figured out that I should let some of it out after waiting for almost a year since last year's codejam.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It shows for me, 6 minutes before round starts, and I can also see the problems. What is happening??

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Google contests have the shittiest UI. This happened in hashcode as well. Now I see 90% people have already submitted A.

    How long ago did the contest start? I took a screenshot.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      likely some timezone issue in their system xd

      the contest started an hour ago

»
4 weeks ago, # |
Rev. 4   Vote: I like it +26 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

What was your approach on problem C?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      I am sorry but I cannot understand this. Did you try submitting it?

      If so, can you share the code?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I submitted it after the editorial is released but it doesn't work, also fails in Errichto's test case :/

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 4   Vote: I like it +6 Vote: I do not like it

      Just to add. I had similar idea for solving small. Instead of binary search always take the max length segment as the last segment.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Do you think flows will work? Source to each seat has capacity 1. Seats to bookings are edges of capacity 1. We can compress the seat ranges, and change capacity from source to seats but maybe not needed. Then you add edges from bookings to sink with capacity k. And finally you find maxflow here, and check that all incoming edges have flow = k. Then you binary search on k.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          No, because we are given each person takes all the seats available and not the amount he just needs

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nice observation! Sounds like a way to help us solve large.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +22 Vote: I do not like it

          I think we can also say that there will atmost sqrt(n) distinct values possible for the max segment at each stage throughout but I still do not know how to use this and solve the problem fast.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Will it not fail for test cases like:
        1
        20  3
        1  10
        11  20
        4  17

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      I thought so and found a countertest:

      N=8 Q=3
      2 8
      1 4
      5 8
      
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Great test case, max(min) always get me screwed...

        Then picking max backwards do makes sense, picking max(min) in each iteration whlie allowing other requests to grow does construct an impeccable greedy solution.

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

how to solve B ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm really not sure about my idea, bcz I didn't really do this round seriously, but maybe like this : First find the best values for each cell with parallel bfs from all available centers. Then binary search on the answer and find the point which you can make as a center for the new building for each value > bin_search_value.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      okay bs the answer,now how can we find out the position of the cell in n*m for each mid in bs? bcz mine n*n*m gives tle

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        So, this is the part I didn't think about, because I was so done with kickstart by that time.

        But n^3 * T for 15sec should not TLE, right?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          i also think it will pass, but sad, it did not passed in my case..u tried n^3?

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            well n*n*m == n^3 in terms of complexity :|

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              yep

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Actually, mine isn't Tn^3, it's Tn^2logn.

                You do 2D partial sums per binary search, and if there's a cell having a number equal to all cells you must reach from the new building, to get that bin_search_value as your answer, you know what to do from there.

                The problem is that, partial sums is not on a proper rectangle. It's on a tilted rectangle. I faced a similar problem once. https://www.hackerrank.com/contests/hourrank-27/challenges/moving-the-kings

                But I didn't do anything after submitting A, and reading B and C during contest. But now that I thought about the problem, I think I don't like problems that require specific knowledge than using a nice observation. I didn't like that hackerrank problem as well, but oh well((

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        How to solve in O(n ^ 3) , I could not think better than O(n ^ 4). Can you explain your solution a bit ?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          .

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Will there be always n + m maximum these "X" maximum cells as a input matrix something like this would give precisely (n * m) / 2 cells which are maximum .

            1 0 1 0 1 0 ... 1 0
            0 1 0 1 0 1 ... 0 1
            1 0 1 0 1 0 ... 1 0
            0 1 0 1 0 1 ... 0 1
            1 0 1 0 1 0 ... 1 0
            0 1 0 1 0 1 ... 0 1
            1 0 1 0 1 0 ... 1 0
            0 1 0 1 0 1 ... 0 1
            

            So wouldn't it result in O(n ^ 4) solution ?

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              good point at that time i think about 100000 100000 100000 ...... 100000

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hints for B and C?

»
4 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

Dedicated to all the shitty false positives of Google's hiring process:

Imagine staying awake since 1am in the morning for a contest that starts at UTC 4am. You check with your timezone, and see that 4am UTC = 5am CET. You feel like spending the next 4 hours just looking up some tutorial here and there. Who knows, it might just be in the contest right? At 3am UTC, you check the website, and see 2 hours before contest begins, and you're like, huh, how can I make such a stupid calculation mistake, so you recheck your math. Your math checks out. So you think to yourself, did they shift the contest by 1 hour? Maybe they did. Anyway, it's on their website, so it must be true. It's Google. It's "trustworthy".

So you don't bother firing them an email asking what's going on. You completely forget that this is something very similar to what happened to you in Hashcode 2019, unfortunately. Had it been recalled at the right time, you would've refreshed the page every 5 minutes.

So now, when 1hr 50 minutes are up, you come ready for the contest to see that there is 10 more minutes remaining, but wait a minute! why are the problems "open"? You click on it and see "3hour 10 minutes" ticking at the top of the contest. Wait what? Was it a 4 hour contest? Did it actually start at 5am CET, like you calculated? You go back and check the email. It says, 4am UTC, 3 hours long.

And the memories of Hashcode come flashing back. There's nothing to do but go to codeforces and see if everyone else is equally screwed up. You start solving A, and then come back to see if anyone replied to you on cf, but cf is down. You refresh cf every 15 minutes, and you've fully understood never to trust Google's highly skilled engineers and their products again. And you carry on. Fortunately, the problems are hard, so it's okay, you won't do well anyway.

But after the contest is over, you see the final scoreboard along with "45 minutes remaining in contest". You lol, and write an email to Google appreciating how awesome the engineers are, and how wonderful your experience with Google contests have been this year so far. You send them all the screenshots, but you leave out the detail that you were awake since 1am for this disaster, because they don't really care. Meanwhile codeforces is still down. You're in jet black about wtf is happening.

Finally, you make peace with the fact that shit happens, and there are more rounds, and swear to never trust Google again, while writing a rant about it on cf, hoping one of Google's highly skilled engineers reads this and feels proud of themselves.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    When Code Jam is right around the corner, and there are more Kickstart rounds coming months, losing sleep in order to participate in this round sounded like a super bad idea for me.

»
4 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Editorials were published and are available in the problem view.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Please don't make us play treasure hunt on your website, please give the link.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      See if this link works for you.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Beautiful! It's on the codejam website. Did they forget it's kickstart?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wow, nice link. I thought we must enter a problem and then hit "analysis" hidden in the middle (really, it's there).

        In your link, the scoreboard is broken in an unusual way. Looks like problems A and C have a subtask worth 0 points and because of that nobody solved the last subtask.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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 :(

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am thinking about to choose smallest segment and delete that from set and go ahead, is there any counter test case for this?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, I pasted it a few comments above. Intervals $$$[2, 8], [1, 4], [5, 8]$$$.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          correct output and what is the order?

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            [5, 8], [2, 8], [1, 4], k = 1.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +21 Vote: I do not like it

            Come on, you could check brute force it yourself in seconds. You must take the last interval first. The answer is $$$1$$$.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              got it,thanks

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Why in this case the answer is 1? in first segment 4,5 in second segment 7,8 in third segment 1,2 Could you explain what I'm missing?

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I think you misunderstood the statement. A query takes all the available seats in the interval.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes we simulate from the end, the previous line states

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Any proof for the observation stated above?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I'd imagine they will end up inviting more contestants than usual and tell everyone better luck next time.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    010

    000

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 7   Vote: I like it +47 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think "equivalence class" is a better word for "unique range". Whenever you add a new query.

      For example, if you have [1, 100], [2, 101], and you add [3, 102], two classes will be cut by the new query, namely [2, 100] is cut into [2, 2] and [3, 100], and [101, N] is cut into [101, 101], [102, N].

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok got it. We have to traverse a max of 2 * Q points.

»
4 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Other issues majorly affected participants negatively. Compared to them, this one was much smaller and forgiven (

»
4 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yes, you are right. Actually, I learned about this concept reading that post and I find it really interesting. I usually think about applying this idea when I don't find a way to improve the asymptotic complexity and I see that the worst case somehow depends on the order you process some data.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.com/contest/1141/submission/51800899

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see now, thank you for that!

»
4 weeks ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

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?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I want little consultation here. I solved A problem in 24 minutes and could not think of a solution for B and C. Finally I submitted O(n^4) brute force solution for B which passed smaller test cases.

So, to perform well in Kickstart I have to focus mainly on implentation and adhoc type ? And, were coders of DIV1 on codeforces able to solve 2nd and 3rd question correctly ?

Can anyone provide an analysis of what type of problem they ask and how to be good at them ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Someone already did. Just read the comments.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

»
4 weeks ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

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 :'(

  • »
    »
    4 weeks ago, # ^ |
    Rev. 5   Vote: I like it +4 Vote: I do not like it

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