Betlista's blog

Betlista's TopCoder SRM 647 editorial
By Betlista, 9 years ago, In English

In SRM there were 1413 registered participants — DIV1 570, DIV2 698 + 145 newcomers

DIV2 — easy (250)

(link)

Not so difficult, max number of children with same age can be at most half (rounded up, so for example 2 for 3 chidren) of the count of all — . Len say that max age is 1, for even count of children we will arrange the line as 1 a 1 b 1 c ... 1 z for odd number of children 1 a 1 b ... 1 z 1 where a-z are different ages...

To find max number of children we can use array, while the age is at most 25, or in general Counting Map.

DIV2 — medium (500)

(link)

Greedy is fine. Everytime we visit the city, we remove the item with max profit we can still sell in such city. I maintained heap (one per city) and removed the sold item (if heap is empty simply do nothing).

DIV2 — hard (1000)

link

First step is to find the real possible max height of the buildings. We can see that in test case #2, where in input there were values {8,22,1,55,42}, but height of the second building can be at most 17 (height of the previous building is 8, and distance is 3 => 8+3*3 = 17). One can do that in while loop, checking whether heights are reachable, if not, decreasing the height for most reachable at the moment and run the check again...

When we have this, we have to find for each pair of the buildings the max height between those two, using for example binary search (described in deeper detail in comment).

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

Comments Comments (20)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

This editorial is the largest I've ever seen :D

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hard was not there yet, if no one complaint about such brief notes, there is no need to describe in deeper detail, there was nothing tricky in easy and medium...

    @all: feel free to ask if something is not clear enough ;-)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      In the editorial for div2-easy(250) I could not understand the first line max number has to be atmost half of the count of all

      What does max number refer to.. the maximum age of some child or the maximum number of occurrences of some particular age? and count of all means the total size of the vector ages?

      Could you help me with that?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I modified it to max number of children with same age can be at most... is it better?

        So if ages of children are let say 10, 11, 12, 12 this max number of children is 2 = there are two children with age 12 and there are is not bigger group of children with same age...

        → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Perhaps I am missing something important, but for the question with heights {8,22,1,55,42} how the maximum height is not greater than or equal to 55?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You cannot reach the number 55 if this is your question...

    Max heights of the buildings are 0 8 17 1 7 16 22 (I added the building for x=1 and x=n). From previous building with height 1 (x=13) the max height of next building (x=15) is 1 + 2*3 that's why 7 and not 55...

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

How do I go about checking if a height can be reached between 2 buildings during the binary search?

I did try some arithmetics, but didn't work out. As for using a for to check if it's possible that would just give me a TLE.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    My favourite "template" for binary search is:

    int ok = ...  // ok value
int nok = ... // not ok value
// for integers the difference have to be 1
while ( ok + 1 < nok ) {
    int mid = (ok + nok) / 2;
    if ( isOk(mid) ) ok = mid;
    else nok = mid;
}
return ok

    Now, one have to define 3 things:

    • ok value
    • nok value
    • isOk(mid) function (can have more parameters needed for decision)

    We have 2 buildings, we know lowerHeight, greaterHeight and distance d (x[i] - x[i-1])...

    So our ok value (the one we can reach for sure) is greaterHeight (can be also lowerHeight, but logically greaterHeight makes more sense). nok should be some value we cannot reach for sure. While distance is d so max height we can theoretically reach is lowerHeight + d * k, so we can set nok as lowerHeight + d * k + 1.

    And finally isOk(mid) function... We can reach the height h (mid) from lowerHeight in roughly (h - lowerHeight) / k steps, if (h - lowerHeight) % k is > 0 one more step is needed, what can be written in one formula as (h - lowerHeight + k - 1) / k, we can count the number of steps from greaterHeight same way, so we have s1 and s2, we now need to check only, that s1 + s2 <= d.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thnx a lot :)

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is lowerHeight in this? And greaterHeight will be the height that is given as t[i], right?

      Please explain the terms a bit.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Imagine, you have two neighboring buildings:

          *
  *
  *
* *
*_*

        heights are 2 and 5, so lowerHeight is 2 and greaterHeight is 5 (distance d is 2). Initially the heights are set to t[i], but we need to modify this to what height is really achievable...

        See the discussion below with Roberio about how we are doing this — two iteration in array from 1 to n and back (from n to 1)...

        → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

Writing editorials seems to be a really motivating way of getting ideas right. Awesome work.

By the way, in the hard problem, in the process of redefining the maximum heights of the buildings, you loop over the array checking whether heights are reachable and decreasing the height multiple times until them stabilize? I was wondering if number of restricted buildings(size of x) was huge this solution would be feasible, just out of curiosity.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    Yes, your understanding of the process is correct. Rough estimate of the process time is O(N2) where N is length of x, which is up to 500. It's because in each iteration one element can change so we have to iterate the array again.

    My idea during the contest was to use tree (but when item is changed, it has to be removed and added again to reorder) and process buildings by increasing max height, so for example in test #2 — 0,8,22,1,55,42,48 (I added first — x=1 and last x=20 buildings):

    1. start with height 0
    2. modify the neighbors 8 and mark building with height 0 as final
    3. continue with height 1 and change 22->19 and 55->7, mark that building as final — 0,8,19,1,7,42,48
    4. continue with 7: 0,8,19,1,7,16,48
    5. continue with 8: 0,8,17,1,7,16,48
    6. continue with 16: 0,8,17,1,7,16,22
    7. continue with the rest, but no height is changed

    This is O(n * log(n)).

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 7   Vote: I like it 0 Vote: I do not like it

      Really nice approach. After thinking a little bit I came to an O(n) solution for the first part of the problem.

      We can impose all the needed restrictions with at most 2n operations, with one normal scan and one reverse scan.

      In the first scan, we will process, from left to right, every pair of height-restricted buildings (i - 1, i) such that i and i - 1 are valid height-restricted buildings and hi - 1 < hi. Then we will impose the restriction to the i-th. Let d be the distance between these buildings.

      h'i = min(hi, hi - 1 + d * k), then we set this as the new restricted height of building i.

      Now we move to the second scan, going backwards this time. We will process every pair of restricted buildings (i, i + 1) such that i and i + 1 are valid and hi + 1 < hi. Then we will impose the restriction to the i-th building in a similar way to the first scan.

      With this process ordering the heights stabilize after one single iteration. I'm having a hard time to prove it formally so I will leave this way for now.

      This does not change the overall solution complexity because of the binary search, but it was interesting to think of since it can be useful in a problem we might stumble upon in the future.

      ( Code )

      EDIT:

      We can actually prove it. Let (i, j) be a pair of "adjacent" restricted buildings. If this pair was not processed in the scans or it was processed in only of them, we are okay. We de not have any dependency cycle for it. But if the given pair was processed in both scans, we have to be careful.

      We know that if (k, i), such that k ≠ j, was processed in the first scan, it was certainly processed before (i, j) (since we process from left to right). So, if (k, i) processing imposed any modification to the i-th building, it was certainly taken into account when processing (i, j).

      Now let's analyze the second scan. If (j, l), such that l ≠ i, was processed in the second scan, it was certainly processed before (i, j) (since we are now going from right to left). So we can think in a similar way of the previous paragraph.

      If (i, j) was processed at both scans, it means that some building b such that b ≠ i modified j in such a way that its height became lesser than i's height and, certainly, this building was already restricted (if needed) at both scans. So we just want to prove that we will not need to execute the first scan again. We can see that hi will become, at least, (hi, hj + k) so the pairs will not need to be processed again.

      So, after all, the order that the buildings are processed is the important thing here.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        Edited. "Proof" added. It is.. weird.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          Thank you for your effort, here is my payback ;-)

          We can replace binary search with this "formula" (function is probably a better word):

              	long minh = ... // minHeight
    	long maxh = ... // maxHeight
    	long d = ...    // distance;

    	long tmax = minh + d*k; // theoretical max height in d steps
    	long hd = tmax - maxh;
    	long nmax1 = tmax - ((hd / k + 1)/ 2)*k; // height in the middle from minh

    	long s1 = (nmax1 - minh)/k; // number of steps from minh
    	long nmax2 = maxh + (d - s1)*k;
    	return Math.min(nmax2, nmax1);

          Which makes the algorithm completely in O(N) ;-)

          It's too late here (00:30), I'll try to find out a good description for why and how is this working soon. It was accepted in arena.

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Hi Betalista, can you please explain your approach a little bit?

            I am unable to understand the Div 2 1000 problem. Can't find official editorial for that.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              There is no official editorial (typically those are very delayed), that's why I'm writing my own editorials... And community is helping to make it better...

              Can you be more specific what is not clear?

              There are two steps: 1. adjusting building heights (O(N)) 2. finding the maximum between two building in distance d (easier is binary search — O(N * log N) for N buildings — O(log N) )

              → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Betlista , can you please explain how this function works in place of binary search

            → Reply