APIO 2013 - Codeforces

11 лет назад, # |

There is no Online-participation, right?

→ Ответить

11 лет назад, # ^ |

read about it in "regulations" tab in official website

→ Ответить

11 лет назад, # ^ |

"Submission of Site Information Tables: 28 February 2013" does it mean that I have no chance to compete, if i just got to know about the competition?

→ Ответить

11 лет назад, # ^ |

← Rev. 5 →

no, I don't think that it means this.

just a few days ago Syrian delegation registered us to APIO .

Each delegation registers its own competitors for the APIO.

If you are a student wishing to compete,

please contact your local informatics olympiad organisation.

quote from http://www.apio.olympiad.org/

→ Ответить

11 лет назад, # ^ |

Probably, I am blinded but I have not found any E-mail or something else I could use to contact APIO organizators.

You know, I live in a counrty, where nobody cares about online competitions, so I would be really happy if I can participate at least out of competition.

→ Ответить

11 лет назад, # ^ |

← Rev. 3 →

the only way to participate is to contact your local informatics olympiad organisation. and ask them to register you to APIO 2013

A list of some of these organisations is available here.

→ Ответить

11 лет назад, # ^ |

Imagine, I am a man from my local informatics olympiad organisation, where do I can write to register my team?

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

I've searched but cannot find the way to do that , I'm sorry for that.

→ Ответить

Xellos

11 лет назад, # ^ |

← Rev. 2 →

But I suppose that only applies for "officially participating countries", not just some random guys who want to try... it's called Asia-Pacific olympiad, so I doubt they'd just let any country join...

It's not that much of a catastrophe, anyway. Just try solving the problems when they're published, I guess

→ Ответить

https://www.facebook.com/download/538924552813015/APIO_2013.pdf

11 лет назад, # |

+23

The contest has finished in all countries. Let's discuss the problems here.

robots: first, make table like this: dst[y][x][dir]:=(grid of final destination of move whose direction is dir from the grid of (y,x))

second, use breadth-first search and get costs like this: cost[id][y][x]:=(the number of moving cost of robot(_id_) to the grid (y,x))

third, build dp[low][up][y][x]:= the number of moving cost of robot id in the range of [low,up) to the grid of (y,x)

building this dp requires Dijsktra ,but using dijkstra is too slow,so I managed to use breadth-first search.

also memory limit exceeded happened to me,so I cut half memory of dp by implementation. O(w*h + w*h*n + w*h*n^3 + w*h*n^2)

toll: too difficult to me :( I only got 16 points by using 2 hours....

tasksauthor: subtask 4 and 6 is difficult(make dijkstra get TLE by using negative edge,not use negative cycle)

I have little time to solve them...

→ Ответить

Pancake

11 лет назад, # ^ |

+10

Would you mind sharing the problems' statements ? I cannot find them on the official website of APIO.

→ Ответить

ig_dug

11 лет назад, # ^ |

+11

→ Ответить

11 лет назад, # ^ |

I can't understand dp[low][up][y][x] , because the cost to move (x,y) depends on initial position of robot [low,up) , and the initial position of this robot may be anywhere because robot [low,middle) and [middle,up) can met in many positions.

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

yes,that's right.

so I first, dp[low][low+1][y][x]:=cost[low][y][x]

and for each [low,up) dp[low][up][y][x]:=(minimum value of dp[low][mid][y][x]+dp[mid][up][y][x] , low<mid<up) in this range, I start breadth-first search from each states as vertexes(this process corresponds to the move after merging robots)

note that the dp of range [low,up) must be done after its subgroups is done.

→ Ответить

11 лет назад, # ^ |

so you doing reverse calculation you start from meet point and search for best initial positions?

→ Ответить

11 лет назад, # ^ |

?reverse?

I need to calculate dp smaller range at first,and larger range after that.

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

I'm not talking about order of calculating dp states, I'm talking about how to calculate each dp state ? how your BFS work?

what is complexity for claculating each state?

→ Ответить

bristy1588

11 лет назад, # ^ |

I don't understand something. hogloid , can you please tell me why a simple recursive DP with memoization will not work here?

→ Ответить

11 лет назад, # ^ |

I think my solution is too tiring,so there may be simpler solution about robots.

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

how much your solution scored? and how much time you spent to code it?

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

+16

I got 100 in robots.

It took me about 1 hour and 40 minutes.

→ Ответить

11 лет назад, # ^ |

← Rev. 2 →

I think you're going to gain gold medal, congratulations!

do you mind if you give me your code?

→ Ответить

11 лет назад, # ^ |

+15

thanks,I hope so :)

http://ideone.com/96vMcn

this is my "robot" code.

→ Ответить

bristy1588

11 лет назад, # ^ |

I don't understand something. hogloid, can you please tell me why a simple recursive DP with memoization will not work here?

→ Ответить

DEGwer

11 лет назад, # |

+10

I spend 2 hours on Toll but I could not solve it and I got only 16 points... Can someone explain the solution of Toll?

Anyway, I challenged to hack dijkstra, and I think I discovered the case, but it didn't work...

My solution　is following:

Let's define the Unit, which consist of 3 nodes, there is cost-0 edge from first point to second point, cost-enough-big edge from first point to third point, and (-(cost-enough-big)-1)-edge from third point to second point.

We can connect Units previous Unit's second point and current Unit's first point will be the same node.

When we connect them, the order of dijkstra algorithm will be O(2^(number of Units)) I think...

→ Ответить

hza

11 лет назад, # |

T_T,APIO 2013 was a sad trip for me. I mistaken the meanings of problem robots and toll and made them much harder.

→ Ответить

11 лет назад, # ^ |

You won't believe what happened to me, for problem robot I thought that blocked gird is donated by 'X' capital but it's actually 'x' small, I spent to much time debugging then I give up search where is my bug. after contest I discovered that it's 'x' small

→ Ответить

Hououin_Kyouma

11 лет назад, # |

Anyone knows, when the results will out?

→ Ответить

tiorted

11 лет назад, # |

← Rev. 2 →

+39

Results

Participants

→ Ответить

keivan

11 лет назад, # ^ |

Where did you find it ?

→ Ответить

tiorted

11 лет назад, # ^ |

Our delegation.

→ Ответить

11 лет назад, # ^ |

-8

is this official results?

→ Ответить

tiorted

11 лет назад, # ^ |

I had received letter from our delegation. Seems official.

→ Ответить

11 лет назад, # ^ |

thanks.

→ Ответить

11 лет назад, # ^ |

+16

according to this results,some strong contestants who I think be eligible for this contest (for example,havaliza and YuukaKazami) didn't participate for this contest. ??why??

→ Ответить

11 лет назад, # ^ |

+13

I talked to YuukaKazami he told me that he didn't participate in APIO 2013

→ Ответить

lsmll

11 лет назад, # ^ |

According to a rule made by Chinese delegation,the Chinese IOI 2013 team can't participate in APIO 2013....I also failed to participate because in China it is only one contest that decide who can participate in APIO 2013.....I did badly in that contest...Someone not stronger than me but did well in that contest can participate..So sad.

→ Ответить

11 лет назад, # ^ |

hmm,so if wjmzbmr or other delegations for IOI had participated,the results would have been different.

→ Ответить

lsmll

11 лет назад, # ^ |

← Rev. 2 →

+15

Yes,sometimes I think some Chinese rules are really strange.For example,one can't participate in IOI again if he has got a gold medal,and only one contest to decide APIO contestants-which I've mentioned above.

→ Ответить