## 11402 - Ahoy, Pirates!

Moderator: Board moderators

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

### 11402 - Ahoy, Pirates!

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

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
Can you tell me how to do the "inversion" fast with segment tree?

Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
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
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

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

@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

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

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

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.

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

### Re: 11402 - Ahoy, Pirates

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

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

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 !

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

### Re: 11402 - Ahoy, Pirates

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

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.