Task "Brojanje", Regional Competition

Admin, my program does 6/10 test cases .. I get TLE on the rest. Time limit is 0.2 sec. I have test examples (from dms.com) and when I count time passed for those 4 test cases every goes under 0.16 sec, can you look at my code or maybe extend the time limit for that task .. It's not a hard task, however there are more people whose code haven't passed than whose have passed ...

Hmm idea that will pass in C++ won't pass in pascal. I had the same problem, constantly TLE in pascal and then I rewrite the same code in C++ and it passed. I think that only way to solve this task in pascal is using BIT...

Sorry, Alex but I really don't know what BIT is?

Binary Indexed Tree. You have pretty nice tutorial when you can learn from. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees Btw do you have MSN or something like that so I can explain it to you better. :)

Thank you, Alex, my e-mail is mprekajski@hotmail.com, if you can post me an e-mail?

I can, but can you log in to windows live messenger. It would be easier to chat. I can explain to you both of my ideas.

Sorry, I have little problems with msn, will you be on z-trening tomorrow, and if you will, when?
I'll try to fix some things on my computer .. :)

Ok i have sent you e-mail, i will be here in let's say 8pm or later.

tnx, Alex ..

np

Check your e-mail.

Thank you, Alex .. However, I've already used that idea, but with binary search in a part where you add new number (I think it is faster) and it didn't do ... you can look at my code: http://www.z-trening.com/submit.php?submit=7100091791&subm_code=1

I'll try without binary search ...

:\ Maybe test cases are bad... I gave you the code that passed. If you can't make it to work I can explain solution with BIT.

Can you explain idea with BIT, what to memorize and how do you find k-th element?

Ok when ever I have in input command 1 I read val and update with value 1. When I have command 2 I binary search for that val that get ( val ) will be K. Can you give me your MSN it will be easier to explain ;)

Thanks for explain, and sorry for not responding. When I saw your post I immediately began to code and I forgot to reply. My msn is boris.vukojevic@hotmail.com.

it is impossible to solve it without BIT in pascal...
does someone happen to know what was the time limit for the contest?

i think it was 1 second...

than it was possible:D

is it possible to solve it this way
if the nubmer is already in the array thatn increase the number of it appearing for 1 else add that nubmer to the array but keep the array sorted.and then when u need to output u add the number of appearances of each nubmer until it becomes more or equal to K.i have seen this that they also used this idea in the contest solution on yuoi but no matter what i do it just wont pass the first test

Yes, it's right idea but it won't pass on Z-Trening because Pascal is too slow, you need to write it in C++ if you want that idea .

Hey, now it will pass ... I tried! Time limit is risen to 0.5 sec instead of 0.2 sec. And if time limit is problem for your code in pascal for one or two test cases, try submit your code in GPC, but instead of longint use integer and instead of int64 use longint ... :)

ok matijazzz will try.
but what are other ways of solving this aleksandar?
edit:when i replace integer with longint i pass all test with TL but i get wrong result:(
what are the limits for integer?

Other idea is using Binary Indexed Tree... Google it for more info about how it works, there is a nice tutorial on TopCoder written by boba5551.

ok:D
i really dont get what to do in order to improve my current algorithm
replacing longint with integers doesnt work
aleksandar what are the limits for integer

In FPC ( don't know in GPC ) integer limit is ~32000 and longint limit is ~2000000000.

in GPC integer is longint and longint is int64