안녕하세요, 오늘의 중계알바 ainu7입니다.

허접하나마 해설을 포함한 문자중계를 시작하도록 하겠습니다.

순위
http://static.kattis.com/icpc/wf2013/
http://ahmed-aly.com/ICPC.jsp
http://myicpc5.icpcnews.com/

문제
http://icpc.baylor.edu/download/worldfinals/problems/icpc2013.pdf

온라인 저지
https://icpc.kattis.com/problems

중계
http://icpc2013.ru/competition/live.xml

21:49 SJTU가 아시아 챔피언, SPb가 유럽 챔피언을 차지합니다. 이상으로 중계를 마칩니다! (근데 B 어케 푸는거임요? ㅠㅠ)

21:47 결국 G는 아무도 풀지 못했지만, B를 풀면서 St. Petersburg National Research University of IT에서 10문제째로 우승을 자축합니다.

21:45 Shanghai Jiao Tong University가 9문제째를 풀면서 2위를 기록합니다.

21:43 아.. University of Tokyo 8문제에서 멈춥니다. 3위로 확정되는 순간, 2위와 1위도 자동적으로 결정되고 맙니다. 나머지는 tourist의 왕좌등극이 얼마나 화려한가만 남았군요.

21:41 우선 National Taiwan University가 8문제로 굳었고, 4위를 차지합니다.

21:39 이제 남은것은 금메달리스트들로 St. Petersburg National Research University of IT, Mechanics and Optics, Shanghai Jiao Tong University, The University of Tokyo, National Taiwan University 이렇게 4팀입니다. 현재 9, 8, 8, 8문제이고 각각 2, 1, 3, 1개의 펜딩이 남아있습니다.

21:38 Belarusian State University가 7문제로 8위, Taras Shevchenko Kiev National University가 8문제로 7위, University of Warsaw도 8문제로 6위, St. Petersburg State University도 8문제로 5위를 차지합니다.

21:31 Jagiellonian University in Krakow가 마지막 1시간동안 2문제를 풀고 9위를 차지합니다. 여기까지가 동메달!

21:29 Moscow State University가 10위를 차지합니다.

21:27 Carnegie Mellon University가 11위로 북미 챔피언을 시상합니다. 북미 죽었구나 ㅠㅠ

21:25 Perm State University가 13위, Tsinghua University가 12위.

21:20 30등대도 5문제인 가운데 라틴 아메리카 챔피언이 시상됩니다.

21:17 카이스트 4문제 55위, 성균관대 4문제 59위로 확정됩니다.

21:15 일단 카이스트 3(1펜딩) 성균관대 4(최종)로 올라갑니다. 아프리카/중동챔피언과 남태평양 챔피언 시상중...
.
21:08 이제 발표 프리젠테이션 시작합니다.

20:59 무려 ICPC의 역사를 처음부터 상세히 발표하는중...

20:54 드디어 빌 파우처 올라와서 본 시상을 시작하려는... 기미를 보입니다.

20:51 이어서 각 문제별 가장 빨리 푼 팀들이 시상을 받습니다.

20:48 NTU가 First solution award를 받습니다.

20:46 ICPC Challenge에 대한 시상이 있었습니다.

20:35 시상식으로 중계가 넘어갑니다.

20:33 B번은 중간 정도의 난이도로 예상했다는 러시아 해설진. 대체 어떻게 하는거냐!!!

20:22 아직 문제 해설중입니다.

20:01 상위권에서는 동경대와 NTU가 G 서밋으로 대회를 마무리했습니다. 결과는 어떨까요?

20:00 성대 D 12회 서밋으로 대회를 마칩니다. 카이스트는 계속 조용했던 것을 봤을 때, 일단 펜딩인 2문제는 맞았을 것으로 추정됩니다. 성균관대도 마찬가지로 4문제로 생각됩니다. 일단 HM은 면하기를...

19:58 성대 계속 D 서밋중.

19:57 성대는 여전히 D를 서밋하고 있습니다. 동경대와 NTU가 G를 (여러번) 서밋합니다.

19:56 막판 서밋이 폭주하는 와중에 SPb는 G를 6회 추가 제출합니다.

19:53 SPb G 3회 추가제출. 동경대 K 추가제출. 카네기 멜론도 7문제 가기 위해서 E 2회 추가제출(총 5회) 입니다.

19:50 SPb G 다시 제출. 동경대 갑자기 E와 K 동시제출??? 가히 점입가경입니다.

19:48 SPb G에 이어 B도 제출합니다. 과연? - 성대는 D, 카이스트는 H를 다시 제출합니다.

19:45 성균관대는 D를 2회 제출했습니다.

19:44 SPb와 NTU, G를 다시 제출합니다. 최소한 그동안 맞았던 것은 아닌듯.

19:42 상위권 추가 제출 없습니다. 펜딩인 문제들을 다 맞아서 그러는건지 모르겠네용..

19:36 SPb가 G를 2회 제출하긴 했는데, 맞았는지 아닌지 여부는 알 수 없습니다. NTU는 E를 다시 제출한 상황.

19:32 HM을 면하려면 4문제를 풀어야 할 것 같습니다. 한국은 두 팀 다 위험합니다.

19:29 성균관대는 H, 카이스트는 J 시도중.

19:25 다들 펜딩이라 잘 알 수는 없지만, 7문제를 풀어야 메달권이 될 것으로 보입니다. 6문제면 25위권 정도로 보입니다.

19:10 성균관대 3문제로 올라섭니다. 이제 아마 스탠딩 freeze 되었을듯...

18:57 99.99/49.99는 수렴이 참 느리군요. 정말 느립니다.

18:45 얼마나 시뮬레이션을 해야 하는지 알기 위해서 실제로 짜보기로 했습니다.

18:43 B번은 결국은 시뮬레이션을 해야 하는 것 같습니다만, 어떻게 해야할지 모르겠네요.

18:32 가장 흉악한 문제라 생각되는 B, G 중 하나를 Tokyo Univ에서 푼 상태라서, 다른 팀들보다는 희망은 있는 상태라고 생각됩니다.

18:29 SPb가 K를 풀어내며 9문제가 됩니다. 8문제 팀보다도 페널티가 적어서 상당히 유리한 위치를 차지했네요.

18:28 이제 억셉이 나오지 않은 문제는 G가 유일합니다. 전 다시 B번을 좀 더 생각해보겠습니다.

18:27 참고로, 성균관대 팀은 F를 풀지 않은 2문제 이상의 유일한 팀입니다.

18:26 개인적으로, tourist는 petr/acrush와 같이 콩라인인 2회 연속 2위가 적당하다고 생각하고 있습니다.

18:25 성균관대, A, J를 거의 동시에 풀어내면서 2문제가 됩니다. 6문제 중 어려운 축의 2문제를 풀었네요...

18:24 해설진에서 대략적으로나마 해법이 나오지 않은 문제는 B번이 유일합니다. 다행히도 most two digits가 있기 때문에, 99.99 49.99가 가장 흉악한 경우가 됩니다.

18:17 이 사이 Tokyo Univ가 처음으로 B를 풀어내고 7문제 끝자리인 4위에 위치합니다. NTU와 SJTU가 같은 7문제 2, 3위, 1위는 여전히 8문제의 SPb입니다. NTU I, SJTU K, SPb EI. K도 풀렸네요.

18:13 다만 이 과정에서 n^3 log n도 25억으로 아직 너무 큽니다. 물론 /2를 해야 하지만 12.5억인데, 어떨까요? - 정렬 과정을 O(n)에 수행할 수 있습니다. 즉, 정렬된 1x?짜리 블럭 두개를 2x?로 합칠 때, 둘 중 최대치를 선택하게 되는데, 어느 쪽 블럭의 수치를 선택하는가에 따라서 두 개의 시퀀스로 분리해낼 수 있습니다. 양쪽은 이미 정렬된 상태이므로, 머지 소트처럼 합치면 깔끔합니다.

18:10 잘 들여다보면 이 문제가 1D 문제로 변한 것을 알 수 있습니다. 즉 M[i]들에 대해서 n log n 이내의 시간에 풀면 됩니다. M[i]들을 내림차순으로 정렬하고 하나씩 들여다봅시다. 첫 위치에 등장하는 아이가 전체 바다를 둘로 쪼갠다고 생각할 수 있습니다. 쪼개지는 순간 그 세그먼트에 대한 답도 결정됩니다. 이 오퍼레이션을 O(1) 안에 하려면 쪼개진 세그먼트 중 작은 것들에 대해서만 업데이트해주면 됩니다. (전체 과정을 union find의 역방향으로 생각하면 됩니다)

18:07 좀 더 시간을 줄여보려면, M[i][j]들의 최소값이 1x1에 대한 해가 되고, M2[i][j] = max(M[i][j], M[i][j+1])들의 최소값이 1x2에 대한 해가 됩니다. M3[i][j] = max(M2[i][j], M2[i][j+1])들의 최소값이 1x3에 대한 해가 됩니다. 2x1을 구해두면 여기서 2x2, 2x3 등등도 유도됩니다. 이렇게 하면 500^4가 됩니다. 꽤 줄긴 했지만 이걸로는 안됩니다.

18:05 I번 해법 찾은 것 같습니다. 해설 들어갑니다. 우선 가장 나이브하게는 a*b 사이즈의 경우의 수가 500^2, 각 사이즈에 대해 검색 시간이 500^4가 드므로 총 실행 시간은 500^6이 됩니다.

17:48 동경대 겨우 마지막 조각인 C를 찾아내어 6문제가 됩니다. 6문제 팀이 총 5팀입니다.

17:39 이 방법으로 SPb가 E를 풀어낸 것 같습니다. 헌데, Spb는 I도 풀었습니다. 2위권과 다시 2문제 차이가 납니다.

17:38 경우의 수를 더 줄일 필요는 없습니다. 프로그램을 preprocessing해두면 됩니다. 즉 Vi 뒤에 Vj를 access하는 경우가 몇 가지이다 라는 정보들을 기억해두면 됩니다. (i!=j) 5625620*156 < 10억이니, 충분히 시간 제한 안에 나올 수 있습니다.

17:32 제가 쓴 조건에 가장 작은 bank들의 크기를 합해서 s(bank size) 이하면 안된다는 조건을 추가한 결과, s=3일때 5625620개로 가장 경우의 수가 많습니다. 5625620*1000 = 56억 정도이니 10초 안에 나올 수도 있을 것 같습니다. 경우의 수를 좀 더 줄여보도록 하겠습니다.

17:18 저도 백트래킹 참 좋아하는데요... 한번 구해보도록 하겠습니다.

17:14 E번 계속 갑니다. 우선 이 파티션의 경우의 수를 세어야 합니다. 일단 13^13이나 13!보다는 작은 것이 명확합니다. 또한 bank size가 13이라면 그냥 한 곳으로 몰아넣으면 되니 경우의 수는 1가지가 됩니다. 두 bank를 하나로 합쳤을 때 bank size보다 작거나 같다면 그냥 합치면 됩니다. 즉 bank size/2 이하의 bank는 2개 이상일 수 없습니다. 다만, 0번 bank를 뭘로 할지는 정해야겠지요. 나머지는 순서에 상관이 없습니다.

17:12 E번. 일단 13이란 숫자가 중요합니다. 즉 13개의 variable이 있다고 할 때 bank에 어떻게 배치할지가 중요합니다. 배치한 뒤에 프로그램을 실행하는 것은 어려운 일이 아닙니다. (1번째 반복 * 1 + 2번째 반복 * (n-1)을 하면 되니까요) 배치... lol 배치고사만큼 중요합니다.

17:04 해설진으로 이도경, 김진호님이 수고해주고 계십니다. BEGIK를 놓고 고민중이십니다. 현재까지는 K가 가장 할만한 것 같고, G는 해법은 있지만 이 해법이 참으로 고통스러운 문제입니다. offset이 arbitary inclination으로 나올 수 있어서 구현이 좀 짜증날 듯 합니다...

16:57 Spb와 SJTU가 같은 문제들을 풀고 6문제가 됩니다. 각각 1, 3위. 2위가 NTU입니다.

16:55 C번은 출발 시점만 다르면 길 하나를 여러명이 공유해도 되는군요. 이 조건을 못봤습니다. 일단 shortest path를 돌린 뒤에, 동시점에 출발하는 아이들과 이 아이들에 대해서 shortest path에 해당되는 길들만 모읍니다. 그러면 어떤 길에 대해서도 2명 이상이 같은 길을 이용할 수 없습니다. 따라서 각 길의 capacity를 1로 두고 maximum flow를 돌린 뒤 이것들을 합하면 됩니다. 차 수가 1천명이고 길의 수가 최대 5만이니 어떻게든 될듯 합니다...

16:50 NTU 바로 이 6문제로 1위로 올라섭니다.

16:49 A, C, D, F, H, J번 문제가 푼 팀이 있는 문제들이고, 모두 8팀 이상이 풀었습니다. 좋은 성적을 거두려면 이 문제들은 반드시 풀어야 하고 (전 아직 C번 해법을 모르겠습니다만) 다른 문제들도 하나둘 정도 풀어야 합니다.

16:48 카이스트가 A를 풀어서2 문제, 성대는 J번 reject로 여전히 0문제입니다.

16:42 K번은 pre/post 조합이 있을 때, 백트래킹으로 해결하면 될 듯 합니다. 경우의 수가 폭증하지는 않은 것이 memoization으로 최대 26*25/2개의 경우가 나옵니다. 가능한 경우 중에서 진짜 preorder로 가장 작게 나오는 것을 찾아서 잘 메모이제이션을 하면 되겠습니다. 자세한 설명은 생략한다...

16:41 A번은 reflection이 되므로, 구부러질 경우 자기쪽으로 돌아올 경우 항상 반대쪽으로 구부러지게 하면 겹치는 일이 없습니다. 즉 무한히 연결되는 경우가 있는지만 체크하면 됩니다. 한 receptor 안에서 가능한 조합들에 대해 edge를 연결해두고 cycle 체크를 하는 간단한 문제로 바뀌게 됩니다.

16:33 현재 Spb, NTU, SJTU가 5문제, Tokyo U.가 4문제, St. Petersburg, Moscow State, Fudan이 3문제입니다. 상위권 대학교들이 굉장히 빨리 치고 나가고 있습니다. 전반적으로 문제 난이도 조절이 잘 된 것 같습니다.

16:31 H번은 DP 문제로, [i..j]와 [j+1..k]를 합체하는데 필요한 open의 갯수를 amortized O(1)에 구하는 것이 관건입니다. 그래요님의 말에 따르면 가장 작은 수가 n이고 n+1, ..., n+k까지 연속해서 나올 때, n+k를 초과하는 것들은 모두 open해야 한다고 합니다. 이 방법이라면 i와 j를 고정시키고 k를 증가시켜가면서 업데이트하는 것이 가능할 것 같습니다.

16:28 K번은 가능한 코드의 수가 90가지입니다. 각 경우에 대해서, preorder's first = postorder's last = root가 되고, inorder에서 이것이 위치하는 자리를 찾아서 좌우를 분리할 수 있습니다. 그리고 recursive하게 풀면 되는데, 문제는 코드에 따라서 이것이 pre/post/in 중에 2개만 제공이 될 수 있습니다. pre/in이나 post/in의 경우는 여전히 유니크하게 루트가 결정되므로 괜찮은데, pre/post가 제공되는 경우가 문제입니다. 어떻게 해야할까요?

16:19 Spb 5문제로 무려 2문제 앞서갑니다.

16:14 I번도 모든 사이즈를 다 찾아보는 500^5에서 500^4까지 줄이기는 그리 어렵지 않은데, 그걸로는 곤란합니다. 어떻게 할 수 있을지...?

16:03 KAIST F를 44분만에 풉니다. 한편 tourist의 Spb 4문제가 됩니다. 13위까지 아시아/유럽팀.

15:55 B번은 문제는 간단한데 어렵습니다. 특히 p가 50으로, x가 100으로 근접해갈수록 더욱 어려운듯 합니다. 얼마 이상을 따거나 얼마 이상을 잃으면 멈춘다는 것은 명확합니다만 그것을 어떻게 결정할지..?

15:52 tourist 치고 나갑니다 3문제입니다.

15:50 A번은 주어진 molecule type들을 가지고 이것들의 무한한 라인이 만들어지는지 체크하는 문제입니다. 중간에 구부러져도 상관없지만 인접해서는 안됩니다. molecule type은 최대 4만개이나 receptor 종류는 최대 26*2개입니다. 어떻게 푸는 걸까요?

15:42 G번도 기하 문제로, 각 타일에 대한 plane sweeping 문제로 보입니다. 즉, 가장 왼쪽 오른쪽 아래 위 범위는 일단 구해두고, 오른쪽 위쪽으로 최대 한 타일만큼만 움직여보면 되니까, 각 타일에 대해 독립적으로 이 타일이 필요하게 되는 offset set을 구해둔 뒤에 모두 합쳐보면 됩니다. n이 작은 편이라 구현하면 될 것 같은데, 정확한 Time complexity가 어떻게 될지...

15:37 J번은 기하 문제인데 다행히 기하 문제치고는 쉬운 편입니다. 과거 알고스팟 DART 문제를 충실히 복습했다면 쉽게 풀 수 있는 문제입니다. (...) 특이점이 일어나는 x좌표들을 찾아서 line segment와 circle segment들로 뼈와 살을 분리한 뒤, 사이의 넓이를 계산해내면 됩니다.

15:33 D번은, 어떤 수=a^b * c^d * e^f 등으로 표현된다고 할 때, different arrangement의 갯수는 (b+d+f)!/b!/d!/f!개 입니다. 가장 작은 수를 찾으라고 했으니, a, b, c는 2, 3, 5 순서대로 올라가고 b>=d>=f인 것이 적절합니다. 답조차 2^63-1 이하라고 하니 딱히 경우의 수가 많을 것 같지 않습니다. 오버플로우를 조심하면서 백트래킹을 하면 되겠습니다.

15:30 그사이 A, J번도 풀렸네요. 이른 시간이지만, 동경대와 Spb가 빠르게 1, 2위를 달립니다.

15:24 F번은, 주어진 2nk개의 수들 중 2n개를 골라서 각각의 pair들의 수의 차이의 최대치를 최소화하는 문제입니다. 이 때 작은 순서부터 i번째 수는 전체에서 ki+1번째 수보다 작거나 같아야 합니다. 이 조건을 따라서, 답에 대해서 바이너리 서치하면서, 앞에서부터 그리디하게 검색하면 됩니다.

15:18 문제 올라왔네요. F번을 6팀, D번을 1팀이 풀어냅니다.

15:14 대만대에서 F번 첫 Accept를 가져갑니다.

15:13 ICPC에는 Topcoder rating으로만은 측정할 수 없는 다른 포스가 존재하는 것 같습니다만, 어느정도 성적과 비례관계가 있다고 할 때, 올해는 tourist의 SPb NRU ITMO 1 팀과 rng_58/lyrically/wrong의 동경대 The University of Tokyo 팀과의 2파전이 예상됩니다. 여느때와 같이 한국팀의 메달권 진입 여부도 관심사가 되겠지요. 이 팀들이 실력 향상이 빠른 팀들이었다는 것을 감안해보면...

15:06 문제는 A-K까지 11문제가 있는 모양입니다. 최근 몇년처럼 아주 쉬운 문제와 아주 어려운 문제가 확 갈리지는 않았으면 좋겠는데요...

15:05 아직 문제가 올라오지 않았군요...