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

Автор hogloid, 12 лет назад, По-английски

JOI(Japanese Olympiad in Informatics) will hold JOI Ninja Contest,a training contest for IOI(International Olympiad in Informatics). Contest site is here -> http://joiopen2012.contest.atcoder.jp/

The contest will begin at 4:00,September 17th,2012(GMT) (in Japan,it will begin at 13:00 in the same day)

The contest duration is 5 hours,the same hour as IOI,and the number of the problems is 3,this is also same as IOI. I guess other features are like IOI. However, we use stdin/stdout for input/output. Submitting is similar to ordinary Online Contest(not release tokens like IOI,just submit source code)

(actually the problems were made for APIO(Asia-Pacific Informatics Olympiad) 2012,so the problem level is not low)

The problem statements are in Japanese and English.

I hope many contestants will attend this contest,and raise their level together!! (of course,those who aren't contestants of IOI 2012 also can attend it :) )

UPD1: JOI also hold the same contests that begin at 9:00and at 15:00,Septenber 17th(GMT).(of course their duration is 5 hour,too)

**contest sites of other times: http://joiopen2012b.contest.atcoder.jp/ http://joiopen2012c.contest.atcoder.jp/ **

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

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

04:00 GMT? That's 07:00 in Riga, too early for me :(

Just in case I decide to drop in, what are the rules? Is there anything like release tokens available?

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I updated the entry.

    " However, we use stdin/stdout for input/output. Submitting is similar to ordinary Online Contest(not release tokens like IOI,just submit source code) "

    also ,the same contest will be hold another time,so I guess you can enter it :)

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

I liked this contest, thank you for announcing it very much. Is there any online archives (or may be, test archives) of other Japanese olympiads (I've solved APIO 2012 and liked it as well)?

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

Can anyone share some hints about problem A (Codes)? I came up with an approach of iteration by diagonals and storing information about same strings between each pair of cells. But the implementation happened to be so tricky.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I couldn't solve the problem A , so I can't share idea. You can see other contestants' code by clicking magnifying glass button on the standings. (at present,there is no official editorial)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    It can be solved using dynamic programming. d[x1][y1][x2][y2] is a count of pairs of shortest paths (not necessary different) to corresponding points such that their messages are equal, each such pair is counted pA·2N + M times, where pA is probability of going along path A (let's say, the first path in a pair).

    It's not hard to understand that the answer is d[N - 1][M - 1][N - 1][M - 1] and this function has O(n3) non-zero states (it's zero when x1 + y1 ≠ x2 + y2). Transitions are straightforward, you can view my code as hogloid said above.