2014 Asia Jakarta Regional Contest

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

ThanQ+ National University of Singapore가 K를 풀어 1등이 됩니다ᅲᅲ

현재 2등과의 패널티차가 346인데 ThanQ+ 는 이미 K를 3번 틀렸으니 K를 286분 - 20 * (앞으로 틀릴 횟수) 까지 맞느냐가 1등의 기준이 되겠습니다.

타이완 코치가 갑자기 나에게 달려와서 월파 가는걸 축하한다고 하네요 ᄏᄏᄏᄏᄏ 그러면서 보라색 information security 고려대학교 재킷? 한자로 고려 써있는거가 정말 멋지다고 하네요. ᄏᄏ ᄏ그래서 제가 한국가서 보낼 수 있으면 보내볼라구요 ᄏᄏᄏᄏᄏ

현재 ThanQ+ 가 지금 Contest 200분이고 페널티를 보아 90정도 앞서있는 것으로 보입니다

올솔브!!!!!

Team X Korea University의 올솔브!

Java# VNU University of Engineering and Technology가 D를 풀어 유일한 9문제 3등이 됩니다

3등인 Java# 가 D를 시도합니다.

Team X 의 두번째 D시도!

현재 풍선룸에선 Team X와 ThanQ+ 중 누가 우승할 것인지에 대해서 베팅을 한다고 합니다..?

ThanQ+ National University of Singapore의 K 3번째 시도!

Team X 담당 스텝이 명우가 지금 담배를 펴야 할 것 같다고 하네요. ᄏᄏᄏᄏᄏᄏᄏᄏ

Team X Korea University가 G를 AC! 10문제 2등! 누가 올솔브를 먼저 하는가가 문제네요.

ThanQ+ 가 K를 다시시도!

ThanQ+가 K를 틀린 것으로 보입니다.

ThanQ+ National University of Singapore가 K를 시도하네요!

BerinGAS University of Indonesia가 J 를 풀어 8문제 4등이 됩니다

Team X가 D를 시도!

타이완 코치가 어제 저에게 싱가포르 팀이나 Team X가 우승할 것으로 보인다는 멘트를 남겼습니다.

Team X가 푼 K번은 이번 대회에서 가장 어려운 문제라고 현지 스텝이 갑자기 페이스북 메신저로 말해줬습니다

현재 1위 ThanQ+ National University of Singapore 코드포스 정보 : http://codeforces.com/team/6491

레이팅이 2300, 2303, 2208 이네요

ThanQ+ National University of Singapore가 G를 풀면서 10문제가 되고

Team X Korea University가 K를 풀면서 9문제가 됩니다.

ThanQ+ National University of Singapore가 D를 풀면서 9문제가 되고

Team X Korea University가 I를 풀면서 8문제가 됩니다.

Java# VNU University of Engineering and Technology는 B번을 풀면 8문제가 곧 되겠군요

Java# VNU University of Engineering and Technology가 G를 풉니다! 3등이네요

ThanQ+ National University of Singapore가 J를 풀어 8문제 1등이 됩니다!

Team X Korea University가 J를 풉니다! 하지만 페널티로 2등이네요ᅲᅲ

Java# VNU University of Engineering and Technology 가 3번만에 J를 맞아 3등이 됩니다. Team X가 페널티에서 아직 앞서네요!

Taipei-Hot National Taiwan University이 뒤늦게 H를 풀며 5등까지 올라오고 있네요

ThanQ+ National University of Singapore가 B를 풀어 7문제 1등이 됩니다

현지 특파원입니다..

코치룸은 4층, 대회장은 7층에 있어서 대회장을 볼 수가 없습니다 ᅲᅲ

참고로 저는 KFC에서 닭불고기를 먹고있습니다. 사진은 제 페이스북에서.... 페이스북만 빨라요 ᄏᄏᄏᄏ

어 근데 I번 풀렸네요 ᅲᅲ

ThanQ+ National University of Singapore가 I를 풀어 6문제 1등!

동시에 Team X 도 C를 풀어 6문제 2등이 됩니다

여기 스코어보드는 Pending도 빨간색인 것 같은..

Team X가 H를 풉니다! 순위는 그대로 3등이네요

STL 없이 구현해야 하는 이 대회에서, J번은 fenwick tree로 min(a[i]..a[j]) 를 구하게 짜는 것이 multiset에 밀어넣고 smallest를 찾는 것보다 승산이 있어보입니다.

다른 문제들은 그렇게 어려운 문제가 없으므로, 승부는 I번에서 갈린다고 봐야겠습니다.

최종적으로 상위권들이 A,B,C,D,E,F,G,H,J번은 풀 거 같습니다.

D번도 카운팅 문제인데 다른 문제들보다는 훨씬 straightforward하게 풀립니다.

G번 한 가지 까먹은건 제곱수들인데 그냥 안켜지는걸로 생각하는게 편할겁니다..

G번은 과거 코드포스나 지니어스아인타컵(...) 에 나왔던 문제와 유사하게 풀 수 있습니다.

31 이하의 소수 (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31) 11개에 대해서는 모든 램프의 경우를 다 만들어본 뒤에,

나머지 소수들은 램프 하나를 조종할 수 있는 소수의 수는 많아야 한 개이므로, 그리디하게 처리할 수 있습니다.

G번 문제는 다음과 같습니다.

N개(N≤1000)의 전구들이 처음에 다 off 상태입니다.

K개(K<N)의 스위치를 누를 수 있습니다. 각 스위치는 X(i)라는 소수(prime number) 한 개를 가지고 있습니다. i번째 스위치를 누르면 X(i) 배수들의 상태를 모두 바꾸게 됩니다.(on->off, off->on) 한번에 스위치는 하나만 누를 수 있습니다.

이럴 때, on 상태로 만들 수 있는 전구의 수 최댓값을 구해야합니다.

I번은 어려운 카운팅 문제로, 각 행에 대해서 처리하면서 '현재 열려있는 칸들, 각 칸들의 위쪽에서의 연결상태' 를 정보로 가지는 상태공간을 만들어서 처리하는 문제입니다.

월파 기출문제에 비슷한 문제가 있긴 한데, 그것보다는 쉽습니다.

Team X 가 K를 시도했지만 틀렸네요ᅲᅲ

ThanQ+ National University of Singapore와 Java# VNU University of Engineering and Technology가 모두 C를 풀면서 5문제를 푼 팀들이 되었습니다.

Java# VNU University of Engineering and Technology가 F번을 맞추어 4문제를 풀면서 2등으로 올라섭니다.

J번은 단순한 슬라이딩 윈도우 문제 같아 보입니다.

C번 그냥 쉬운 DP인듯 하네요..

Team X 가 B를 풀어 3문제 2등으로 올라갑니다!!

우선 각 connected component들을 구하고, 각각에 대해서

degree count를 해서

component size = X라고 했을 때 (X는 짝수여야함)

X/2-1가 X-2개

X/2이 2개인지 체크하고

실제로 앞의 조건을 다시확인해보면 풀릴거 같네요

Team X가 B를 시도했지만 틀리네요ᅲᅲ 화이팅ᅲᅲ