then what is this?sunny wrote:I did greedy.
My solution is O(n) without any extra memory(not even an array to store all numbers).
11240 - Antimonotonicity
Moderator: Board moderators
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
Try this test case :
The answer should be 3.
Code: Select all
1
5 8 9 7 6 10
-
- New poster
- Posts: 6
- Joined: Mon Feb 26, 2007 10:42 pm
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
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.
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.
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.
-
- Experienced poster
- Posts: 196
- Joined: Wed May 02, 2007 10:12 pm
- Location: Hungary, Pest county, Halasztelek
- Contact:
And see also the new records: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.
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.
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.
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
Ivan wrote:
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.
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.
Can you give me the address of the website? There's so much websites called "Waterloo"...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.
Thanks