11240 - Antimonotonicity

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Parleen
New poster
Posts: 5
Joined: Wed Jun 20, 2007 8:27 pm
Location: DreamTown

Post by Parleen » Sun Jul 15, 2007 6:59 pm

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?
Somebody help me

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » Sun Jul 15, 2007 7:39 pm

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
New poster
Posts: 5
Joined: Wed Jun 20, 2007 8:27 pm
Location: DreamTown

Post by Parleen » Sun Jul 15, 2007 7:47 pm

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
Somebody help me

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sun Jul 15, 2007 8:02 pm

Try this test case :

Code: Select all

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

trulo17
Learning poster
Posts: 62
Joined: Mon Jan 24, 2005 6:12 am
Location: Lima,Peru

Post by trulo17 » Sun Jul 15, 2007 8:36 pm

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
New poster
Posts: 6
Joined: Mon Feb 26, 2007 10:42 pm

Post by KirllButin » Sun Jul 15, 2007 9:38 pm

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
New poster
Posts: 8
Joined: Tue Dec 26, 2006 10:37 am

Post by klopyrev » Sun Jul 15, 2007 11:39 pm

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
New poster
Posts: 8
Joined: Tue Dec 26, 2006 10:37 am

Post by klopyrev » Sun Jul 15, 2007 11:42 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Jul 16, 2007 12:07 pm

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Jul 16, 2007 9:42 pm

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
Experienced poster
Posts: 196
Joined: Wed May 02, 2007 10:12 pm
Location: Hungary, Pest county, Halasztelek
Contact:

Post by Robert Gerbicz » Tue Jul 17, 2007 1:37 am

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.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Jul 17, 2007 4:47 am

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Jul 17, 2007 5:07 am

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
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

Need guide

Post by H_Hima » Wed Jul 18, 2007 1:24 pm

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.

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Post by WingletE » Fri Jul 20, 2007 2:53 pm

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

Post Reply

Return to “Volume 112 (11200-11299)”