Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

Блог пользователя kingofnumbers

APIO 2013
Автор kingofnumbers, 13 лет назад, По-английски

APIO 2013 (Asia-Pacific Informatics Olympiad) will take place in 11 may 2013 , I wish good luck to all participants.

here is the official site: http://apio.comp.nus.edu.sg

here is the competition rules: http://apio.comp.nus.edu.sg/APIORules.pdf

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
13 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

There is no Online-participation, right?

→ Ответить
»
13 лет назад, скрыть # |
 
Проголосовать: нравится +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...

→ Ответить
»
13 лет назад, скрыть # |
 
Проголосовать: нравится +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...

→ Ответить
»
13 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    13 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

    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

    → Ответить
»
13 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Anyone knows, when the results will out?

→ Ответить
»
13 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +39 Проголосовать: не нравится

Results

Participants

→ Ответить
»
12 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

Hi, It seems the official website of APIO (http://apio.olympiad.org) is down. Also the statements aren't available in the official site of APIO 2013. So could anybody please upload the statements somewhere?

Edit: I forgot to mention that the link given in comments above doesn't work neither.

Edit2: I didn't notice that the solution file contains the statements as well. I'm sorry.

Thank you very much.

→ Ответить