Hello Codeforces, my name is C137 and starting from today I'm gonna try to write regularly in this blog:

The idea is, every 7-10 days i am gonna select a problem that i really found it useful and interesting, and then i will talk about the way i solved this problem, with long editorial and analysis, by this way of sharing my thoughts i hope that grey, green and cyan contestants will benefit from it and learn something new, also i am hoping that top rated contestants will also add their notes to my solution, and suggest some more optimized code.

As a start i choose the following interesting problem, I hope you will like it :D

P.S: if you are familiar with the Segment tree data structure, then i strongly recommend you to try with this problem at least for two hours before reading this blog, otherwise as a start you should check this and this, also for more advanced Techniques you can check this amazing article .

Before I start, I would like to thank NourAlhadi for solving this problem after reading this blog, and adding his notes and suggestions to make it even more clear.

problem name: Billboard

Source: 2008-2009 ACM-ICPC, NEERC, Northern Subregional Contest

Link: this

type: Data Structures

Difficulty level: Medium

Short Description:

You are given a Billboard with width w, and height h, also you are given n ads, each ad has height 1 and width w_i and for each ad you must decide in which row you will put it, you start putting ads from top and going down if there is enough width in this row, if you can put the ad, then print the number of the row, otherwise print  - 1

Example:

w = 6, h = 3, n = 5

ads widths: 3 3 5 2 5

answer: 1 1 2 3 -1

after putting the first ad, the remaining width will be: 3 6 6

after putting the second ad, the remaining width will be: 0 6 6

after putting the third ad, the remaining width will be: 0 1 6

after putting the fourth ad, the remaining width will be: 0 1 4

there is no row with width 5, so you cant put the last ad.

Problem Analysis:

The first thing that came to my mind when I read this problem was to use set<pair<int, int> > the first parameter of the pair is the row index, and the second is the remaining width in that row, I spent nearly 30 minutes trying to get something useful out of this idea using lower_bound but I only ended with a piece of useless code, so I erased the whole code, cleared this idea from my head, and started thinking in something else.

lets say that the current ad width is x I am interested in the first row with remaining width greater than or equal to x, then I should update the value in that row and decrease it by x, the word "Update" took me to think about Segment tree, what if i used a segment tree, and in each node of the tree I can store the max value in it's range?? now initially i will build the tree, and for each node i will put the value w which is the width of the Billboard, now I can know for each range in the array whether I can put the ad in it or not only with log h time=30, that's great, I started to make some progress, now how can I know the index of the first row greater than or equal to x ??? or there is no answer???

Let's first talk about the no answer case:

if quer (1,1,h) < x then there is no answer, because in the whole tree there is no node with remaining width greater than x.

If there is an answer, but it's not in the range (1, ind) then for sure it will be in the range (ind+1, h) this is so familiar to binary search, actually it's a binary search, so now I can get the first row (the answer) in only log h * log h time =30*30=900 for each ad.

now my pseudo code was something like this:

for each ad 
read x
if(quer(1,1,h)<x)print -1
st=1, en=h
do binary search
if(quer(1,1,mid)>=x)en=mid
else st=mid+1
print st
update(1,1,h) // decrease the value at st by x

OK, now most of the work is done, Or that's what I thought, two big problems were about to make me change the whole idea, and give up solving this problem...

First problem, the time complexity n* log h* log h=200000*30*30=180000000 too big!! and needs optimizations

Second problem, Memory, h is too big, it can go up to 10^9 so I can't use a segment tree array of size 3*h

After five minutes, I noticed that i am not interested in the whole billboard, I just need to use the first n rows of it, because in the worst case, I will but one ad in each row, using only n rows.

About the time,I needed to get rid of one of the log n the query or the binary search, After drawing some trees, I noticed something so important, I can use the structure of the tree to do the Binary Search !!!

Each node of the tree has at most two children, the left child, and the right child, the left child might take me closer to to the answer, and to the lower row, and the right child also might take me closer to the answer, but to a higher row, so when I can go to the left child, I must go straight to it, otherwise go to the right child, finally return the index of the leaf I will reach, and now my pseudo code was something like this:

for each ad 
read x
if(tree[1]<x)print -1
ind =quer(1,1,n,x)
print ind
update(1,1,n) // decrease the value at ind by x

and the quer function will be:

int quer(int pos, int l, int r, int x){
	if(l==r)return l;
	int mid=(l+r)/2;
	if(tree[2*pos]>=x)return quer(2*pos, l ,mid,x);
	else return quer(2*pos+1, mid+1, r, x);
}

Now all the ideas were clear to me, my time complexity is n*log n, the memory is 3*n, and everything was ready on paper, it took me 10 minutes to write the code, and you can't imagine how sad and depressed i was when i got TLE, I checked my code again, and found a stupid bug in the update function, fixed it and got the beloved green light, after a very interesting and amusing two hours of thinking :D

This is all I can say for this problem, I hope you liked my analysis and you benefit from it, I am not gonna post my code, because I think you can code it now after reading the analysis, If there is still something unclear, then fell free to ask me in the comments below, or send me a message...

If you liked the idea, then I will try to post the next blog about the next problem in the following week...

Happy coding, and have a nice day :D