헤헤 결과 나왔나요?

카이스트 1등팀은 G나 H 중 적어도 하나는 풀었을 것 같네요.

대회 종료후 프리징 기준 대학생 프로그래밍 경시대회 입상 예상 입니다.

대상: KAIST - [A-za-z0-9]+ (9/838,BGH)

금상: 서울대 - gcc (8/653,DF), 고려대 - Opportunity (8/670,BDFH)

은상: 서강대 - PurpleNoon (6/388,G), 연세대 - TackHeeHyeonJong (6/449,HK), UNIST - Saram (6/449,G)

동상: 아주대 - Coding Ajou Jalham (6/474), 성균관대 - kriii lovers (6/544,C), 부산대 - Geumjeong Mt Simmani (6/600), POSTECH - ChocoJam (5/364,C), 한양대학교 - dailyCoding (5/368,C)

은상과 동상은 크게 변동이 없을 것 같으습니다. 대상과 금상에는 변동이 있을 것으로 예상되나, 개인적인 예상으로는 KAIST가 이번 대회 우승을 할 것으로 예상합니다.

upteamisup팀

프리징 전 I만 풀었었는데 프리징 후 ACEGHJKL제출했습니다!!

오사카가 F를 맞추며 다시 1위가 됩니다.

1위와 2위팀이 지금까지 푼 문제가 두개나 다르네요.

f는 dfs tree에서 기우성이 안바뀌는 edge 홀수개를 지나는 cycle이 존재하는지 찾는데 존재하면 그러한 edge 1개만 사용히는 cycle이 존재함을 알 수 있고 각 정점에 대해 기우성 바뀌는 efge만 이룡하여 도달 가능한 가장 먼 조싱을 찾으면 해결 가능한 것 같습니다

현재까지 순위로 한국 대학생 프로그래밍 경시대회 순위를 예측하면 다음과 같습니다.

대상(1팀): KAIST - [A-Za-z0-9]+

금상(2팀): 서울대학교 - gcc, 고려대학교 - Opportunity

은상(3팀): 서강대학교 - PurpleNoon, 연세대학교 - TackHeeHyeonJong, UNIST - Saram

동상(5팀): 아주대학교 - Coding Anjou Jalham, 성균관대학교 - kriii lovers, 부산대학교 - Geumjeong Mt Simmani, POSTECH - ChocoJam, 한양대학교 - dailyCoding


[03:30] [A-Za-z0-9]+ 최초로 F를 성공하여 1위를 탈환합니다!

[03:21] 오랜 침묵을 뚫고 카이스트가 D를 성공하며 2위로 올라섭니다.

[02:30] 대회가 절반 지난 지금 안풀린 문제는 B,D,F 입니다. 특히 F번의 경우 몇팀이 제출을 한 상태인데 아직 성공한 팀이 없습니다.

지금까지 대회 스코어로 봤을때, 대학생프로그래밍 경시대회 입상권으로는 조심스레 6문제 예상해봅니다.

[02:25] 오사카가 K를 한번에 성공하며 다시 선두를 굳건히 유지합니다.

[1시간 45분] 오사카가 A를 풀면서 7문제로 단독 선두로 질주합니다. 카이스트 [A-Za-z0-9]+ 팀은 K를 First Solve 하면서 단숨에 2위로 올라가네요.

[01:42]오사카 chikOkU가 A를 풀면서 7문제 1등으로 올라섭니다.

서울대 CompCert가 6문제 2등, gcc가 5문제 3등입니다.


쉬운 문제: E, I, J, L

중간 문제: A, C, H, G? F?

[1시간 20분] 오사카 chikOkU가 H를 First solve하면서 6문제로 1등으로 올라섭니다. 서울대의 CompCert가 A를 풀면서 6문제로 2등.

A는 정점과 코인을 잘 두고 거리를 가중치 삼아 가중치 매칭을 하면 될 것 같네요.
G는 stack을 이용해 convex hull을 구한 후 풀면 됩니다.

플로우 문제가 2문제(A, C)나 보이는군요 ㄷㄷㄷ

현재 서울대의 gcc가 AEIJL로 1등, KAIST의 [A-Za-z0-9]+가 CEIJL로 2등을 차지하고 있습니다

A는 그래프의 정점에 흰색 또는 검은색이 칠해져있고, 각 정점은 흰색 또는 검은색 코인을 가지고 있을 때 edge로 연결된 정점끼리 코인 swap operation이 가능합니다.

이 operation을 최소화해서 정점과 코인의 색을 같게 만드는 문제입니다

스코어보드2: https://www.acmicpc.net/daejeon2015

x분때의 스코어보드, 코포/탑코더 레이팅, 순위 변동, 제출 기록 등등을 볼 수 있는 스코어보드 입니다. 공식은 아니에요

C는 n*m 보드에 숫자가 있을때 인접한 2개의 숫자를 1씩 빼는 오퍼레이션(숫자가 1이상일때만 1씩 빼는)을 반복해 모든 숫자를 0으로 만들 때 필요한 최소 횟수를 구하는 문제입니다.

인접한 두 숫자라는 점을 이용해 보드를 체스판처럼 흑과 백으로 나눈 후 정점분할을 이용한 networkflow로 풀릴듯 합니다

대회 시작 30분정도가 지난 가운데 서울대와 KAIST가 4문제로 선두권을 유지합니다.

앞에서부터 보면서 하나씩 양쪽끝에 번갈아가면서 넣으면 풀릴듯합니다

E는 주어진 수를 잘 배열해 인접한 수들의 차의 최댓값을 최소화 시키는 문제입니다.

증가 후 감소하는 모양을 가지도록 수를 배열하면 해결할 수 있을거 같네요

L은 brute force 문제로 보입니다. E는 DP로 해결할 수 있을 것 같은데...

I, J, E 문제가 대체로 쉽네요. J는 세 소수를 더해 주어진 홀수를 만들 수 있는지 검사하는 문제, I는 수열을 한번 뒤집어서 max를 저장해둔 후 정방향으로 보면서 푸는 문제가 되겠네요.

2문제로 EeveE팀이 앞서갑니다.

현재 두문제를 푼 EeveE가 1등입니다

0cb2202e223ce22f7fdde2a02e4eb285.jpg

Run ID 1번은 서울대 CompCert팀이 가져갑니다.

대회 시작했습니다.

문제 http://143.248.204.182/problemset-2015.pdf

스코어보드 http://143.248.204.182/scoreboard/

대전에 와있습니다