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

### DIV2 — easy (250)

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)

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)

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

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

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

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?

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...ya it's much better to understand now...

Thanks

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?

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

My favourite "template" for binary search is:

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`

.Thnx a lot :)

What is

`lowerHeight`

in this? And`greaterHeight`

will be the height that is given as t[i], right?Please explain the terms a bit.

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

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.

Yes, your understanding of the process is correct. Rough estimate of the process time is

O(N^{2}) 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):`0,8,19,1,7,42,48`

`0,8,19,1,7,16,48`

`0,8,17,1,7,16,48`

`0,8,17,1,7,16,22`

This is

O(n*log(n)).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 2

noperations, 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 thatiandi- 1 are valid height-restricted buildings andh_{i - 1}<h_{i}. Then we will impose the restriction to thei-th. Letdbe the distance between these buildings.h'_{i}=min(h_{i},h_{i - 1}+d*k), then we set this as the new restricted height of buildingi.Now we move to the second scan, going backwards this time. We will process every pair of restricted buildings (

i,i+ 1) such thatiandi+ 1 are valid andh_{i + 1}<h_{i}. Then we will impose the restriction to thei-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 thatk≠j, was processed in the first scan, it was certainly processedbefore(i,j) (since we process fromleft to right). So, if (k,i) processing imposed any modification to thei-th building, it was certainly taken into account when processing (i,j).Now let's analyze the second scan. If (

j,l), such thatl≠i, was processed in the second scan, it was certainly processedbefore(i,j) (since we are now going fromright 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 buildingbsuch thatb≠imodifiedjin such a way that its height became lesser thani'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 thath_{i}will become, at least, (h_{i},h_{j}+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.

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

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

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

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.

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.

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

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

can someone please dumb down the div2 1000 solution