simp1eton's blog

APIO 2011 Problems
By simp1eton, 14 years ago, In English

Hi all,

I am trying to solve the APIO problems. The problems and the contest data can be found here:

 http://apio2011.inoi.ir/?page_id=132

I can't seem to find the editorials anywhere, so I hope that you can help me out. Thanks!

Q1:

I am not sure how to solve this problem. I was able to find the solution in this thread:

http://apps.topcoder.com/forums/?module=Thread&threadID=707486&start=0

However, it did not state how to solve invalid cases. Can someone help me?

Q2:

I was only able to solve the 60% case with a BFS. I think that to get 100%, you need to do some line sweep, but I am not sure how you can do so. Can someone help me?

Q3:

I really do not have much ideas for this problem. I could only solve the case for strings up to 3 letters long by bruteforce.

Thanks in advance! =D

  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I used Dijkstra for task 2. Vertices of graph are start point, end point, corners of rectangles and some more points on rectangle sides you have to initialize.
→ Reply