11402 - Ahoy, Pirates!

[tobby]

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

[rio]

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

EDIT: Got AC using segment tree.
-----
Rio

[tobby]

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

[Hadi]

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]

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

[chengouxuan]

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]

@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]

@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]

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

[devashishtyagi]

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]

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]

Don't double post. http://uva.onlinejudge.org/index.php?op ... &Itemid=31

[darkstallion]

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]

Don't use getchar() and count on it to be a newline. Maybe there is extra whitespace at the end of a line.

[darkstallion]

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.