11240 - Antimonotonicity

[Parleen]

I did greedy.

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

then what is this?

[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).

[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

[jan_holmes]

Try this test case :

Code: Select all

1
5 8 9 7 6 10

The answer should be 3.

[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?

[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

[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?

[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.

[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.

[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.

[Robert Gerbicz]

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.

[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.

[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.

[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.

[WingletE]

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