kingofnumbers's blog

APIO 2013
By kingofnumbers, 12 years ago, In English

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

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is no Online-participation, right?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    read about it in "regulations" tab in official website

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        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/

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

                → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              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

              → Reply
»
12 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          ?reverse?

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

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
            ← Rev. 2   Vote: I like it +5 Vote: I do not like it

            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?

            → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Anyone knows, when the results will out?

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +39 Vote: I do not like it

Results

Participants

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Where did you find it ?

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    is this official results?

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it +15 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          maybe this rules to allow as many as possible people to has a chance to participate in IOI/APIO

          → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I'm reading this blog now. Actually I was eager to participate in APIO this year. But I was on a two weeks trip which interfered APIO. :(

      → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    Thank you for the information. I didn't notice that.

    → Reply