Betlista's TopCoder SRM 647 editorial

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	djm03178	152

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 — $\text{[math]}$ . 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).

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

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

Комментарии (20)

Показать архивные | Написать комментарий?

allllekssssa

10 лет назад, # |

← Rev. 2 →

-11

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

→ Ответить

Betlista

10 лет назад, # ^ |

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

calmhandtitan

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

orsenthil

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

taigi100

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

sahildua2305

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

Please explain the terms a bit.

← Rev. 3 →

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

Roberio

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

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

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

← Rev. 7 →

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 h_i - 1 < h_i. Then we will impose the restriction to the i-th. Let d be 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 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 h_i + 1 < h_i. 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 h_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) )

sidak

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

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

DIV2 — easy (250)

DIV2 — medium (500)

DIV2 — hard (1000)