Chairs

Daniel can you increase the time limit by 0.01s. I've got TLE on 8-th test case and i've tried the original solution and it too gets TLE on 8-th test case? :-)

I don't know what to use to optimize my solution. :-(

I set the TL so because you should use something smarter. Here is a hint "Sweep line".

If there are any other problems, or you need more help just ask.

Ok. I'll try it now in C++ . I think I can pass the TL now. ;-) Tnx

Can I read like this.

scanf("%d:%d:%d %d:%d:%d",&a1,&b1,&c1,&a2,&b2,&c2);

Yes you can.

Ok.

Can you give me some text about "Sweep line" , I didn't found anything that might help me. :-(

If you are looking for some algorithm take a look here:

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index

Maybe this can help you:

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep

Okay, thanks a lot. ;)

Well here is a short info.
If a person comes in a certain time "T1" in a room, then you note in an array "room" like this ( room[ T1 ]++ ) And if the person leaves the room at time "T2", then you are decreasing it like, ( room[ T2 ]-- ) So if you are now going trough the array rooms, you exactly know when a person comes, how much persons and when they leave. I think that would help,

well, here is another idea :) This is how I done it...

When you have intervals, like T1-T2 ( T1 = time in, T2 = time out ), then you just sort them, and the just go through array, and if that element of array is TIME IN then you increase some value, else you decrese it, and each step you check is that value best result :)

Aleksandar, try using same algorithm like for Z-policajac :)
It's identical task, the only difference is the input.

I know, but i got TLE on 8th test case. ;(

Use efficient sort and that's all u need to do?

Sorry for asking a lot of questions, but I am still pretty much new to the world of programming. What is the "efficient sort". :)

well, to begin with, you have those slow sorts, like bubble, selection etc.Complexity: n*n
On the other hand, you have quick sort, heap sort, merge sort...etc. Their complexity is nlogn.

But, as n=1000 here, I don't know why you get TLE, I'll check your code....

Meh, Pascal, :D, I can't understand this :D

Aha , now i get it. I think that it was some kinda new sort. I know about quick sort and merge sort. I didn't use any sort. I just loop through the time wizard came in and out and increase some value x[i] and after i found the maximum in the array x[1..24*60*60], but that's too slow. Daniel told me to use sweep line and I am trying to find the solution.

I've wrote it in c++. Here you go. :)

http://al3ksandar.pastebin.com/m54cba4c8

EDIT:

Same idea as in Pascal.

I suggest you to take a look at my code for Z-policajac ;)
It should teach you how to do this task properly :)

Thanks, it helped. ;)

@Aleksandar: Well, that's one way of doing it :) Making events and sorting them is better :)

And also, always declare arrays outside of main() because arrays declared in functions are allocated on stack memory which is less than heap memory (in most cases, stack is 8 mb and heap 32mb).

Ok, I'll keep that in mind when I code in C++. Thanks. ;)