11402 - Ahoy, Pirates!

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

Moderator: Board moderators

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

11402 - Ahoy, Pirates!

Post by tobby » Sun Jan 20, 2008 4:11 pm

Do you have a very fast algorithm? Do we need some advanced data structure? Please give me some ideas.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Jan 20, 2008 4:23 pm

I haven't tried this problem yet, but I think segment tree would work.

EDIT: Got AC using segment tree.
-----
Rio
Last edited by rio on Sun Jan 20, 2008 7:48 pm, edited 1 time in total.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby » Sun Jan 20, 2008 5:46 pm

Can you tell me how to do the "inversion" fast with segment tree?

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Sun Jan 20, 2008 6:29 pm

tobby wrote:Can you tell me how to do the "inversion" fast with segment tree?
You don't need to do the inversion to all nodes in the subtree. Storing some information in each node: At query time, you can decide what extra actions you should do for a node to find the correct result for that node based on the information stored at its ancestors.

EDIT: I think last problem of contest #3 of http://www.hsin.hr/coci/ has a similar solution, although it is simpler than this one.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby » Sun Jan 20, 2008 6:44 pm

It sounds not easy. I think I will come back to this problem later. :)

chengouxuan
New poster
Posts: 10
Joined: Wed Dec 15, 2010 12:32 pm

Re: 11402 - Ahoy, Pirates

Post by chengouxuan » Tue Apr 26, 2011 1:15 pm

can any one explain how to solve it using segmen tree in more details? i solve it by compress all pirates into a table of sqrt(n) X sqrt(n) with time O(sqrt(n)) and my algorithm runs 3.8 seconds.

patsp
New poster
Posts: 12
Joined: Tue Sep 21, 2010 8:51 pm

Re: 11402 - Ahoy, Pirates

Post by patsp » Fri May 13, 2011 12:48 pm

@chengouxuan

I tried it with segment tree but got TLE. I don't know how to do the inversion fast.

Can you explain how you solved it with sqrt(n) X sqrt(n) table??

chengouxuan
New poster
Posts: 10
Joined: Wed Dec 15, 2010 12:32 pm

Re: 11402 - Ahoy, Pirates

Post by chengouxuan » Mon May 16, 2011 9:00 am

patsp wrote:@chengouxuan

I tried it with segment tree but got TLE. I don't know how to do the inversion fast.

Can you explain how you solved it with sqrt(n) X sqrt(n) table??

this is my algorithm's outline.

there are O(sqrt(n)) rows. at each query, you shouldn't process all elements in all rows that are included in this query. just record this operation on each "totally included" row. there are at most two not "totally included" rows, you can process all elements on these two rows.

there are O(sqrt(n)) row-record operations and O(2) row-processing operations. since recording a single row costs O(1) time, and processing all element in a row costs O(sqrt(n)) time, each query costs O(sqrt(n)) X O(1) + O(2) X O(sqrt(n)) = O(sqrt(n)) time.

i'm asian, sorry for my poor english, here is my email: chengouxuan@21cn.com, i'm willing to send you my source code(400+ lines). btw, finally i solved it with segment tree, but this solution runs about 4.0 seconds.

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am

Re: 11402 - Ahoy, Pirates

Post by howardcheng » Fri May 27, 2011 6:38 pm

It looks like there are cases in which M > 100, violating the problem statement.

devashishtyagi
New poster
Posts: 2
Joined: Sun Sep 30, 2012 12:59 pm

11402 Ahoy Pirates

Post by devashishtyagi » Sun Sep 30, 2012 1:08 pm

I tried solving problem number 11402 (Ahoy Pirates) using segment trees but I am recieving runtime error on submissions. I have gone through the code and haven't found any obvious mistakes as of yet. My code can be found here http://pastebin.com/ZVVRvj8s.
Thanks in advance.

devashishtyagi
New poster
Posts: 2
Joined: Sun Sep 30, 2012 12:59 pm

Re: 11402 - Ahoy, Pirates

Post by devashishtyagi » Sun Sep 30, 2012 4:59 pm

I am getting a runtime error on submission of my solution. Any reason why this could happen? My code can be found http://pastebin.com/1VhpiUDp.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11402 - Ahoy, Pirates

Post by brianfry713 » Mon Oct 01, 2012 11:31 pm

Check input and AC output for thousands of problems on uDebug!

darkstallion
New poster
Posts: 3
Joined: Fri Jul 05, 2013 9:07 am

Re: 11402 - Ahoy, Pirates

Post by darkstallion » Fri Jul 05, 2013 9:21 am

Hello guys! I need help for this problem. I made a solution for this problem but I keep getting WA. Can someone give me the test case that make my solution fails or can someone show me where my code flaws are. Here is my solution http://pastebin.com/M7h109Cx

Thanks a lot ! :D

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11402 - Ahoy, Pirates

Post by brianfry713 » Fri Jul 05, 2013 11:13 pm

Don't use getchar() and count on it to be a newline. Maybe there is extra whitespace at the end of a line.
Check input and AC output for thousands of problems on uDebug!

darkstallion
New poster
Posts: 3
Joined: Fri Jul 05, 2013 9:07 am

Re: 11402 - Ahoy, Pirates

Post by darkstallion » Mon Jul 08, 2013 6:29 am

Thanks for your response! I have tried your suggestion and use getline instead of getchar. But the result is still WA. I think the problem is in my segment tree. But I can't find it.

Post Reply

Return to “Volume 114 (11400-11499)”