(Codeforces) Intel Code Challenge Final Round

http://codeforces.com/contest/724

B (14분)
N^6 짬. 이거 별로 안쉬웠다... 그냥 글러먹은듯 ㅠ

D
B를 풀고 친구 스탠딩을 봤을 때(=14분) 정우형이 AC를 받은 걸 확인했다. 그래서 잡았다. 그 때까지만 해도 내가 이걸 한시간 이상 잡을 줄은 몰랐다..

문제를 처음에 보고 lexicographically라는 조건을 보고 내가 처음 한 생각은 "길이를 최소화해보는게 좋겠군!" 이었다. 대충 이 때부터 망한 듯 하다. 길이를 최소화한 상태에서 lexicographically smallest를 구했더니 예제가 안 나왔다.

앞에서부터 안 뽑힌 것중 가장 character가 작은 걸 뽑아가는 그리디를 생각했다. 세그먼트 트리를 하나 짰다. 예제 안나왔다. 또 하나 이상한 그리디를 생각했다. 조금 더 쎈 세그먼트 트리를 짰다. 예제 또 안나왔다. 아....

문제가 있다고 생각해서 다 밀고 다시 생각했다. character가 작은 것부터 순서대로 넣는데, 다만 "쓸데없이 많이 넣는 일이 없도록" std::set을 사용해서 그리디를 구현했다. 예제가 다 나왔지만 pretest 5에서 안 나왔다. 코드가 짧아서, 코딩 실수는 아니고 알고리즘 문제라고 생각했다. 이때 체념하고 C로.

C (79분)
반사시키지 않고 뒤집어서 펴주니까 식이 대충 나왔고, 좀 써보니까 합동식 두개가 나왔다. 중국인의 나머지 정리를 쓰면 될거 같은데 문제는 내가 그게 뭔지를 잘 모른다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ x망...

a1 = b1 (mod p1) / a2 = b2 (mod p2) 두 식이 있을 때, gcd(p1,p2) == 1이어야 CRT를 적용할 수 있던 걸로 알고 있다. 난 p1 = 2n, p2 = 2m이라 글러먹... 은 줄 알았으나, 식을 전개해보니 -1인 경우를 걸러내면 서로소 케이스로 환원할 수 있음을 깨달았다.

질의당 O(min(n, m))을 짜니까 예제 3개가 잘 나왔다. 풍악을 울려라! 구글에 chinese remainder theorem cpp를 검색했고, 괜찮은 코드를 베껴서 AC를 냈다.

D (106분)
그래서 내 D의 문제점은 뭐일까? 코드를 더 봤지만 답이 없었다. 한참을 생각해도 모르겠어서 데이터를 여러개 만들어서 손으로 넣어봤다. 음 맞는거 같아. 음....

어쩌다가 알았는지 모르겠지만, 대부분의 경우 "쓸데없이 많이 넣어야" lexicographically smallest라는 걸 깨달아버렸다. 다 지우고 다시 짰다. AC.

G
E F G를 봤는데 F는 풀기 싫게 생겼다. G가 많이 풀려서 그걸 잡았다.

XOR에 대해서 얘기를 하는데, 엄청 어려워 보였다. 그럴 때일수록 비트를 쪼개면 쉽게 풀릴 거라고 생각해서 비트를 쪼개는 쪽으로 생각했다. 에지 가중치가 0과 1이면 음... 어렵지 않았다. 열심히 짰다. 예제 1이 나왔다. 그리고 예제 2가 이거였는데

4 4
1 2 1
2 3 2
3 4 4
4 1 8

이건 안 나왔다.

뭐가 문제인지는 알았다만 그걸 생각하니까 비트가 잘 안 쪼개졌다. 한참을 고민하다가 결국 사이클의 xor 값으로 샤바샤바하면 쪼갤 수 있다는 것을 깨달았다.

문제는 샤바샤바였다. 결국 N개의 원소 중에 부분 집합 XOR의 경우의 수인데... gaussian elimination을 쓰면 당연히 N * 64^3이니 TLE가 날 거고, 음... 잘 모르겠지만 N * 64^2 dfs를 짜서 10분 전에 냈는데 틀렸다. 뭐 틀린거 같다....

대회 이후 슬랙 그룹챗에서 나왔던 얘기가 충격적이었는데, 가우시안으로 row echelon form 구하는 게 맞고 그게 O(N * 64) 라고 한다. 나 저거 배운지 2주밖에 안됐는데;; 결국 풀 수 없는 문제였던 것. 학교에서 분명히 세제곱으로 배웠기 때문에 가우시안으로 푸는 게 말도 안된다고 따졌으나, 지금은 대충 이해한 거 같다. 가우스! 그 위에 ainta~~~

총평

10등하니까 unrated + 알람 못맞춰서 코포 놓친 후 버쳘돌렸더니 10등 + 20등하니까 상수 sysfail 크리를 맞은 이후라, 그동안의 업보를 봐서라도 잘 보겠거니 생각했는데 싸대기를 제대로 맞았다. 280등 정도면 최근 10달 내 최악이다. 그래도 뭐 다시 돌아갈 수 있겠거니 한다. 아직은...

나에게 있어 오늘 대회의 핵심은 D번이었는데 (....) 이렇게 막히면 도대체 어떻게 해결해야 하는지 잘 모르겠다. 답이 없다...

XOR로 가우시안 하는 거는 오늘 처음 배웠다. 찾아보니까 XOR 부분집합 최대화 같은 것도 똑같이 하는 듯. 선대를 배우니까 정보 할 때 확실히 편한 거 같다.