2014 Asia Jakarta Regional Contest

Codevore 001 Institut Teknologi Bandung가 처음으로 J를 풀어냅니다.

BerinGAS University of Indonesia가 처음으로 C를 풀어냅니다.

Java# VNU University of Engineering and Technology가 E를 풀어 3문제 3등이 됩니다

B는 그래프가 주어졌을 때

connected component에 대해서

1) 각 component의 vertex가 disjoint set P, Q로 쪼개지고 두 set의 크기가 같음

2) P, Q는 완전 그래프

3) P와 Q 사이에는 1개의 edge만 존재해야 함

을 만족하는 개수를 출력하는 문제입니다

현재 2등인 BerinGAS 를 조사해보니 인도네시아 예선 1위, 방콕 리저널 23위를 한 전적이 있습니다

Codevore 001 Institut Teknologi Bandungㄱㅏ J를 풉니다?!

ThanQ+ National University of Singapore 가 F를 풀면서 3문제 1등으로 올라갑니다.

H번 풀이를 정정합니다

순서가 번갈아가면서 진행한다가 아니고

입력으로 주어지기 때문에

grundy number가 아닌 sliding window를 이용한 O(N*M) DP가 될듯 합니다

Taipei-Hot National Taiwan University 이 E를 포기하고 B를 먼저 푸네요. 아직 12등입니다

Team X가 Kuala Lumpur Regional을 돌면서 그런디 넘버 문제를 풀었고, 공부했으므로 언젠간 H를 풀겠군요!

H는 O(N*K)로 grundy number를 쓰면 쉽게 풀릴듯 합니다

K번 법 997이 소수이므로 뤼카의 정리를 사용하지않고도 풀 수 있을 것 같습니다..

뭐 루카스 안쓰더라도 997가 몇번 곱해지는지만 카운트하면 그냥저냥 되지 않을까여... ㅠ

BerinGAS University of Indonesia 가 가장먼저 C를 풀어 유일한 3문제 1등이 됩니다

Java# VNU University of Engineering and Technology 가 H를 가장 먼저 풉니다!

H는 베스킨라빈스31게임을 응용한 버전으로

A,B팀이 있고, 각 팀에 팀원이 N명이 있는 상태로 숫자를 1~K까지 부를 수 있을 때 마지막 M을 부른 사람이 있는 팀이 이기는 게임입니다.

각 팀이 최선을 다해 플레이 한다고 했을 때, 이기는 팀을 구하는게 목적입니다

DELAPAN.3gp Institut Teknologi Bandung 가 B를 풀었습니다

그런데 K번 NM제한이 백만이라서 Lucas Theorem을 알지 못하면 하기 힘들겠네요!

Chord(FPT)가 아직 아무도 못푼 F를 풀어서 4등으로 올라갑니다

F는 각 용을 잡기 위해서 정확히 a_i의 능력치를 가진 칼과 b_i ~ c_i사이의 능력치를 가진 칼 2개가 있어야 하는데

칼의 능력치를 마음대로 만들 수 있을 때 칼의 최소 개수를 찾는 문제입니다.

a_i의 set에 들어있는 원소들로 전부 칼을 만들고,

b_i ~ c_i에 a_i를 제외한 원소가 하나라도 그 범위에 들어가 있는 경우에는 이 범위를 고려하지 않아도 되므로

이를 제외한 list들을 모아서 greedy하게 minimum cover를 하면 될듯 합니다.

K번은 포함배제로 O(K^2)에 풀립니다.

Team X 가 31분에 E를 풀었습니다! 3등으로 올라가네요

10개 이하군요

K번은 N*M 그리드가 있을 때에 (1,1)에서 (N,M)으로 (x+1,y) 또는 (x,y+1)로만 움직여서 갈 수 있는 경우의 수를 카운팅하는 문제입니다.

단 문제에서 '나쁜 점'들이 10개 미만 주어지는데, 그 점들의 좌표를 (X1, Y1) ... (Xk, Yk)라 한다면 각 좌표를 중심으로 3*3 정사각형 영역은 지나가면 안됩니다.

N, M 제한은 1,000,000입니다.

10개 미만인 것에 착안해서 좌표를 압축한 다음, dp식을 행렬 곱셈으로 하면 되지 않을까하는 생각이 듭니다.

E번은 tree의 간선을 잘라가면서 두 노드가 같은 forest에 있는지를 판단하는 문제인데

query를 앞부터 보면서 해결하는 것이 아니라 뒤에서부터 보면서 union&find를 하면 풀립니다

와이 파이를 얻었어요 ㅋㅋㅋ

A번은 주어진 수열을 정렬해놓고 인접한 것의 차이가 K보다 큰 것의 개수를 세어주면 되는 것 같습니다.

Team X 가 F를 시도했으나 Failedㅠㅠ

제출이 있어야 Scoreboard 가 업데이트되는 pc2특성상 대회는 43 혹은 44분에 시작한 듯 하네요

Badak Timur 팀이 E 를 풀었습니다

Taipei-Hot National Taiwan University가 처음으로 Problem E를 시도했지만 Failed...

문제가 공개되었네요.

와 같은 형식 혹은 http://competition.binus.ac.id/icpc/ 에서 보실 수 있습니다

BerinGAS University of Indonesia solved A first in 3 minutes.

Team X ranks 4th place now.

7분 전쯤에 시작한 걸로 보입니다. 시간 수정 요망...

The scoreboard is a little bit slow. Last Update: Fri Dec 05 13:31:45 ICT 2014

10분이 지났는데 스코어보드가 아직 조용하네요

필승 전승 압승~!!

화이팅!

문제가 올라오는 대로 해설을 해 볼 예정입니다.

화이팅이요 !_!

ThanQ+(NUS)랑 Chord(FPT) 팀이 Kuala Lumpur Regional(Danang) 을 같이 출전했었는데 Div. 2 3, 4등의 성적을 거두었었습니다

Team X가 자카르타 리저널에서 최소 3등을 한다면 월드파이널을 나갈 수 있게 되는 것으로 알고 있습니다.

2014 자카르타 리저널 Reservations

National Taiwan University	Taiwan	Taipei-Hot	ACCEPTED
National University of Singapore	Singapore	ThanQ+	ACCEPTED
Tokyo Institute of Technology	Japan	katou	ACCEPTED
FPT University	Vietnam	Chord	ACCEPTED
Korea University	South Korea	Team X	ACCEPTED

위의 5팀이 순위권 접전이 되지 않을까 조심스래 예상해봅니다.

Taipei-Hot은 올해 월드파이널에서 4등으로 금상을 수상하였습니다.

katou의 경우 올해 일본 도쿄리저널에서 6문제를 풀어 12등을 하였습니다.

ThanQ+의 경우 Danang 리저널에서 많이 말렸지만 코드포스 3레드의 강팀입니다.

Team X는 @myungwoo , @wclee2265, @functionx 님으로 구성된 올해 대전리저널 3등 금상을 수상한 팀입니다.

개인적으로는 Team X가 1등은 힘들더라도 평소 실력대로라면 2, 3등은 무난하지 않을까 예측해봅니다.

대회가 생각보다 늦은 시간 ㅋㅋ 현지 시간 오후 1시, 한국 시간 오후 3시에 시작하네요