Page 2 of 3

Posted: Sun Jul 15, 2007 6:59 pm
by Parleen
sunny wrote:I did greedy.

My solution is O(n) without any extra memory(not even an array to store all numbers).
then what is this?

Posted: Sun Jul 15, 2007 7:39 pm
by sunny
Whatever you call it DP or greedy, I think the idea of the O(N) solution with O(1) memory is same.

It seemed to me that 'Greedy' would be the appropriate term to define the solution(as when i thought this solution DP wasn't in my mind).

Posted: Sun Jul 15, 2007 7:47 pm
by Parleen
thanxsunny ,
can anybody see my code in page 1, i did it without using array and dont know why i got wrong answer , otherwise please provide some input output

Posted: Sun Jul 15, 2007 8:02 pm
by jan_holmes
Try this test case :

Code: Select all

1
5 8 9 7 6 10
The answer should be 3.

Posted: Sun Jul 15, 2007 8:36 pm
by trulo17
Robert Gerbicz wrote:
here is a dp solution using O(n) time and O(1) memory, and it is trivial to prove that the algorithm is correct. It's a little surprising.
Find this really surprising. Always think of dp as a trade of space for time.Could someone shed some light on this?

Posted: Sun Jul 15, 2007 9:38 pm
by KirllButin
O(n) solution:

Sequence starts at first maximum point (fred, fred>fred[i+1]) (result=2)
after that increase result at each extremum point

Posted: Sun Jul 15, 2007 11:39 pm
by klopyrev
How the hell are people getting such fast times? My solution is O(n) and it doesn't even store the input. All it does it one comparisson per number. It runs in 0.447 seconds. Then there are people that do it in <0.200 seconds. How the hell is that possible?

Posted: Sun Jul 15, 2007 11:42 pm
by klopyrev
Can someone tell me the technique for super fast input reading? I'm already using C input and its taking 0.439 second just to read it all, without even running any algorithm on the data.

Posted: Mon Jul 16, 2007 12:07 pm
by Adrian Kuegel
You can use low-level I/O functions like read / write. I guess this is how Rio gets his fast runtime. When the algorithm is O(n), most of the time is spent on I/O, so you can really optimize a lot there. Ignore Ghalib who is listed on first place, I am quite sure he just prints the output without reading the input.

Posted: Mon Jul 16, 2007 9:42 pm
by Darko
I submit in Java and I/O is very slow, so I read all at once and then process the input. Same for the output - I put all in a buffer and flush it at the end. That's why my solutions usually have large memory usage.

You can do the same thing in C, I saw a post somewhere around here about it, you should do "man read".

And yes, I am about to post something about Ghalib in Bugs and Suggestions, that is just silly.

Posted: Tue Jul 17, 2007 1:37 am
by Robert Gerbicz
Darko wrote:I submit in Java and I/O is very slow, so I read all at once and then process the input. Same for the output - I put all in a buffer and flush it at the end. That's why my solutions usually have large memory usage.

You can do the same thing in C, I saw a post somewhere around here about it, you should do "man read".

And yes, I am about to post something about Ghalib in Bugs and Suggestions, that is just silly.
And see also the new records:
in 0.002 sec. Raquel Mendez
0.002 sec. Loiane Groner
That's surely cheat, because I've reached 0.070 sec. using O(n) time, O(1) memory and using fread and fwrite for fast I/O. It' impossible to get so fast time without cheat, I don't understand them why they cheat on the site.

Posted: Tue Jul 17, 2007 4:47 am
by sclo
Well, the only way to avoid cheating is to not post sample solutions and judge input/output, but I believe there are always people that will learn something when they look at sample solutions. We're all here to learn and practice. That's especially true for harder problem like problem E (problem 11243) on the contest.

Posted: Tue Jul 17, 2007 5:07 am
by Darko
Simon, I agree with you. That is why I suggested to slightly change I/O from the published one, so people don't just send the output in. That still does not prevent them from sending in judge's solution - but I am not sure that they would bother doing that if it does not get them the fastest time or something like that. I really don't understand what their motivation is.

Need guide

Posted: Wed Jul 18, 2007 1:24 pm
by H_Hima
Ivan wrote:
2. To reduce the complexity we use a common technique to reduce the inner loop.
Instead of iterating through every j in order to find the above mentioned
maximum we can do a range maximum query (RMQ) - which can be easily done in
logarithmic time leading to overall complexity of n * log(n).

In the above context the query is done over a range of VALUES (not indexes)
of elements of A looking for such a VALUE whose index i corresponds
to the largest H (or L). The mentioned query can be easily answered
using an appropriate data structure such as segment tree, binary indexed
tree or whichever you prefer.

So we can replace the inner loop with something like this:

L = get_max_H(A + 1, n) + 1; insert_new_L();
H = get_max_L(1, A - 1) + 1; insert_new_H();

may you make it more clear or send me a code used this method.
or send me a reference to learn it.I understand the O(n) algorithm but not this one.
I think that I need a help in the trees mentioned above. :-?
I need your help because it can be used in LIS problems too.
thanks.

Posted: Fri Jul 20, 2007 2:53 pm
by WingletE
little joey wrote:You can look at the sample solution at the Waterloo site (google for it). It is a quadratic time complexity solution. They missed a crucial observation to make it linear, but it is not very hard to find.
Can you give me the address of the website? There's so much websites called "Waterloo"...

Thanks