11402  Ahoy, Pirates!
Moderator: Board moderators
11402  Ahoy, Pirates!
Do you have a very fast algorithm? Do we need some advanced data structure? Please give me some ideas.
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.tobby wrote:Can you tell me how to do the "inversion" fast with segment tree?
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.

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

 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)) rowrecord operations and O(2) rowprocessing 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.

 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.

 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.
Thanks in advance.
Thanks in advance.

 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.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11402  Ahoy, Pirates
Don't double post. http://uva.onlinejudge.org/index.php?op ... &Itemid=31
Check input and AC output for thousands of problems on uDebug!

 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 !
Thanks a lot !

 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!

 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.