Codeforces
덤프버전 :
1. 개요[편집]
경쟁적 프로그래밍 대회를 주기적으로 개최하는 사이트이다. 2009년부터 십수 년 간 수백 번의 대회를 개최했고, 현존하는 경쟁적 프로그래밍 사이트 중에서 가장 큰 사이트라 볼 수 있다. 주로 올림피아드에 참가하는 사용자들이 다수 이용하고 있다. 러시아에서 만든 사이트지만 러시아어뿐만 아니라 영어도 지원하고 있어서 기본적인 영어 실력이 갖춰진다면 문제를 이해하고 푸는 데 지장은 없다.
사이트에서 문제를 푸는 방법은 크게 두 가지가 있다.
- 대회에 참가한다. 이 경우에는 제한 시간이[2] 주어지고, 이 시간 안에 최대한 많은 문제를 풀어내야 한다. 대회에 참가하면 사용자의 레이팅이 변하는데, 처음 몇 개의 대회에서는 레이팅을 추가로 어느 정도 주기 때문에 빠르게 올라갈 수 있다.
- 지난 대회의 문제들을 열람한다. Contest 메뉴에서 Contest History로 간 뒤, Virtual Participation을 누르면 대회에 모의로 참가가 가능하다.[3] 또한 Problemset 메뉴로 가면 그동안 Codeforces 대회에 출제된 문제들을 시간 제한 없이 풀 수 있다.
2. 대회[편집]
2.1. Codeforces Round[편집]
Codeforces의 유저들이 직접 문제들을 만들고 개최하는 대회이다. 보통 일주일에 한 번 이상 열린다. 참가 신청은 대회 시작 약 2일 전부터 할 수 있으며, 순위 결정 방식은 대회 종류에 따라 달라진다. 자세한 내용은 아래 참조.
2.1.1. Series[편집]
Codeforces Round 중에는 시리즈 대회들이 존재한다. 아래에 설명한 시리즈 외에 다른 시리즈 대회가 열리는 경우도 있다.
- Hello: 2018년에 생긴 시리즈로, 한 해의 시작을 기념하는 대회이다. Combined Round이다.
- Goodbye: 2013년에 생긴 시리즈로, 한 해를 마무리하는 송년 대회이다. Combined Round이다.
- Global Round: 2019년에 생긴 시리즈로, 1년에 6번 열리며 높은 등수를 차지하면 티셔츠를 받을 수 있다. Combined Round이다.
- Technocup: 러시아 올림피아드로, Elimination Round 1~4와 Final Round로 구성된다. Round마다 시작 시간이 제각각인 경우가 많다.
- VK Cup: 챔피언십의 하나로 Codeforces에는 2012년 대회부터 존재한다.
- Moscow Olympiad in Informatics: 모스크바 학생들의 올림피아드 대회을 Codeforces에서 동시에 개최하는 것이다. 문제들의 어려운 난이도에 대한 논란이 비교적 많은 편이다.
- Codecraft: 매년 4월경에 열린다. 2015년 대회부터 존재하며 2017년부터 2019년까지 세 번 연속으로 Pretests가 매우 약해서 FST의 대명사로 불리기도 했다.
- April Fools Day Contest: 만우절 대회로 일반 대회와 다르게 위트 문제들로 구성된다. 2012년부터 해마다 열렸으며 2015년에는 없었다. Unrated Contest이다.
- Testing Round: 사이트 점검을 목적으로 여는 대회이다. 대체로 기간이 짧으며 Unrated Contest이다. 현재는 Testing Round #17까지 열렸는데 Testing Round #17만 대회 접근이 불가능하고 나머지는 가능하다.
- Kotlin Heroes: 제출할 수 있는 언어가 Kotlin으로 제한되는 Unrated Contest이다. Practice와 Episode로 구성된다.
- CodeTON: 상위권 참가자들에게[4] TON이라는 암호화폐가 주어진다. Combined Round이다.
2.2. Educational Round[편집]
Codeforces의 특정 유저들이 주기적으로 개최하는 Div. 2 대회이다. 한 달에 두 번 정도 열리며, 순위는 ACM-ICPC 방식으로 정해진다. 자세한 내용은 아래 참조.
2.3. Division[편집]
대회에는 Division(줄여서 Div.)이라는 시스템이 있는데, 이는 참가자의 실력에 따라 대회를 나누는 기능이다. Division에 따라 대회에 참가 신청을 할 수 있는지와 그 대회가 자신의 레이팅에 영향을 주는지의 여부가 달라진다.
Div. 1과 Div. 2는 초기부터 존재했다. Div. 1 + Div. 2는 Combined Round라고도 하며, Div. 1과 Div. 2가 따로 열리거나 Div. 2만 열리는 대회보다는 드물게 열리는 경향이 있다. Div. 3과 Div. 4는 나중에 생긴 Division이다.
이런 이유로 레이팅이 음수가 되면 레이팅 변화에 큰 제약을 받게 된다.
2.4. 순위의 결정[편집]
2.4.1. Codeforces 방식[7][편집]
Codeforces Round 중 Educational Codeforces Round, Div. 3, Div. 4를 제외한 대회에서 따르는 점수 계산 방식이다.
각각의 문제에 얻을 수 있는 최대 배점[8]이 있고 패널티에 따라 점수가 줄어든다. 대회 시작 후 1분이 지날 때마다 문제를 풀었을 때 얻을 수 있는 점수가 0.4%씩 줄어든다. 또한 제출한 코드가 테스트 케이스에서 실패한 경우 제출 1회당 50점이 차감된다. 너무 많은 페널티로 인해 문제를 풀면 오히려 손해를 보는 상황이 발생하지 않게 하기 위해 문제를 풀면 최소한 그 문제의 배점의 30%를 얻을 수 있게 되어 있다. 즉, 어떤 문제를 풀었을 때 얻는 점수는 다음과 같다.
max(문제 배점 × 0.3, 문제 배점 - 시간 페널티 - 제출 페널티)
시간 페널티는 다음과 같은 방법으로 계산된다.
(대회 시작 후 해당 문제에서 마지막으로 "Pretests passed" 판정을 받기까지 걸린 시간[9]
) × 문제 배점 ÷ 대회 시간[10] ÷ 125
제출 페널티는 다음과 같은 방법으로 계산된다.
(그 문제에 한 제출 중 Pretest 1을 통과한 제출의 수 - 1) × 50
Codeforces Round에는 Pretests라는 것이 존재한다.[11] 대회 중에 제출된 모든 코드는 Pretests로만 채점되며, 모든 Pretests를 통과한 경우 Pretests passed 판정을 받고, 그 문제를 푼 것으로 간주한다. 대회가 끝나면 System testing이 진행되는데, 이때 대회 중에 Pretests passed 판정을 받은 마지막 제출을 Pretests를 포함한 전체 테스트케이스로 다시 채점한다.[12] Pretests를 통과한 코드가 System testing을 통과하지 못하는 경우를 Failed system test(FST)[13]라고 한다. 이렇게 되면 그 문제는 풀지 못한 것으로 간주한다. 코드가 System testing을 통과하는 경우는 Passed system test라고 한다.
Codeforces에는 Hack이라는 기능이 존재한다. Codeforces Round의 경우, 자신이 어떤 문제를 해결했을 경우 대시보드로 가서 그 문제를 Lock할 수 있다.[14][15] 그렇게 했다면 같은 Room[16]에 있는 참가자들이 그 문제에 제출한 코드들을 볼 수 있다. 만약 Pretests를 통과한 어떤 코드를 틀리게 할 수 있는 유효한 입력을 알아냈을 경우 그 입력으로 해당 코드에 핵 시도를 할 수 있다. 핵 시도가 성공했을 경우(Successful hacking attempt 판정이 나온 경우) 핵을 시도한 참가자는 100점을 얻는다. 핵을 당한 코드는 틀린 것으로 바뀌고, 그 코드를 제출한 참가자에게 자신의 코드가 핵을 당했다는 알림이 간다. 핵 시도에 사용된 입력은 그 문제의 테스트케이스의 뒤쪽에 자동으로 추가되어 System testing에 사용된다. 핵 시도가 실패했을 경우(Unsuccessful hacking attempt 판정이 나온 경우) 핵을 시도한 참가자는 50점을 잃는다. 그밖에 핵 데이터가 잘못되었을 경우(Invalid input, Generator crashed 등의 판정이 나온 경우)는 점수가 변하지 않는다.
System testing이 종료되면 자신이 해결한 문제와 핵 시도에 의해 얻은 점수들의 총합을 기준으로 순위를 매긴다. 동점인 경우 같은 순위로 간주한다.
2.4.2. ICPC 방식[편집]
Educational Codeforces Round와 Div. 3, Div. 4에서 따르는 점수 계산 방식이다. 문제별 배점이 존재하지 않으며, 대회 중에 문제를 해결하면 해결한 문제 수가 1 증가하고 페널티가 추가된다. 더해지는 페널티는 다음과 같은 방법으로 계산된다.
(대회 시작 후 해당 문제에서 마지막으로 "Accepted" 판정을 받기까지 걸린 시간[17]
) + 제출 페널티
제출 페널티는 다음과 같은 방법으로 계산된다.
(그 문제에 한 제출 중 Test 1을 통과한 제출의 수 - 1) × 10
ACM-ICPC 방식으로 진행되는 대회에는 Pretests, Room, Lock이 존재하지 않는다. Hack은 대회가 종료된 후에 할 수 있는데, 대회 종료 직후부터 12시간 동안 Open hacking phase가 지속된다. 이때 모든 참가자의 코드를 자유롭게 핵할 수 있다. 단 핵에 성공하거나 실패하더라도 핵을 시도한 사람의 페널티는 변하지 않는다. Open hacking phase가 끝나면 성공한 핵에 사용된 입력을 포함한 테스트케이스로 System testing을 진행한다.
ACM-ICPC 방식에서 참가자의 순위는 해결한 문제가 많은 순서로 정해지며 해결한 문제 수가 같으면 페널티가 적은 순서로 정해진다. 해결한 문제 수와 페널티가 서로 같으면 같은 순위로 간주한다.
System testing이 끝난 이후 치터[18]가 처리되고[19], 이후 Elo Rating에 기반해서 참가자들의 새 레이팅을 계산한다.
2.5. Editorial[편집]
대회와 채점이 모두 끝나면 에디토리얼이 공개된다. 에디토리얼은 모든 문제의 풀이와 소스코드를 간단히 적은 글로 대회가 끝난 뒤에 에디토리얼을 보고 업솔빙할 수 있다. 대회 출제자의 블로그에 올라오고, 문제 페이지에 에디토리얼 링크가 뜬다.
3. Rating[편집]
3.1. 사용자의 레이팅[편집]
대회를 참가하면 대회 성적에 맞게 레이팅이 바뀐다. 레이팅이 자신과 비슷한 사람보다 잘 보면 오르고, 그렇지 못하다면 레이팅이 떨어진다. 레이팅에 따라 참가할 수 있는 대회가 다르다. 레이팅을 등급 이름으로 부르는 경우는 많이 없고, 대부분 색깔로 부른다. 오렌지 이상부터는 Master와 International Master, Grandmaster와 International Grandmaster을 구분하기 위해 오렌지/찐렌지, 레드/찐레드로 부르거나, 약자인 IM, GM, IGM 등으로 부르기도 한다.
Codeforces에 처음 가입하면 레이팅은 0부터 시작한다. 과거에는 1500부터 시작되었으나, 라운드 한 번만 치르고 Specialist 등급에 이름만 걸어놓는 유저가 많아 그 아래 등급의 유저 분포가 극도로 적어져 하위권 변별력을 확인할 수 없는 문제가 발생해 2020년 초부터 0부터 시작하는 것으로 바뀌었다. 이도 실제로는 1400으로 간주되는데 처음 6번의 대회에서 레이팅 500, 350, 250, 150, 100, 50을 각각 추가로 주기 때문. 이 때문에 자신의 정확한 실력을 확인하려면 라운드를 최소 6번 쳐야 한다. 레이팅이 음수가 될 수도 있다.[24] 주기적인 점수 초기화도 없고 휴면 페널티도 없기에, 라운드를 치르지 않으면 한없이 그 레이팅을 유지시킬 수 있다.[25] 다만 마지막 라운드를 치른지 6개월이 지나면 순위표에서는 빠진다.
한국에서 IOI 국가대표, ICPC 월드 파이널 출전 팀의 코드포스 레이팅이 레드인 것을 생각하면, 레드 이상의 레이팅 등급을 가진 경우 국가대표급의 굉장한 실력자로 생각할 수 있다.
3.2. 문제의 레이팅[편집]
대부분의 문제에는 레이팅 태그가 달린다. 문제의 레이팅은 대략적으로 다음과 같은 의미를 갖는다.
레이팅이 x인 사용자가 레이팅이 y인 문제를 대회 중에 풀 확률은 다음과 같다:
<math>P=\dfrac{1}{1+10^{\tiny\dfrac{y-x}{400}}}</math>
문제의 레이팅은 2018년에 생긴 기능으로, 원래는 상한과 하한이 존재하지 않았지만 2020년 레이팅 계산 방식이 개편되면서 하한과 상한이 각각 800, 3500으로 설정되었다.
4. 문제점[편집]
4.1. 양민학살 문제[편집]
양민학살은 보통 고 레이팅 유저의 부계정이 div2나 div3 등 낮은 Division에서 높은 순위를 차지하는 행위를 말한다.[26] 공식적으로는 다중 계정의 사용이 금지되어 있지만,[27] 대놓고 치팅을 하지 않는 한 거의 단속되지 않고 있는 실정이다. 특히, div3/4에서는 Trusted Participant 제도가 있어서 대회에 5회 이상 참여하지 않은 계정은 순위표에서 제외되지만, 레이팅이 반영되는 것은 여전하다.
4.2. 수준 낮은 커뮤니티[편집]
코드포스에는 여러 게시판에 글과 댓글 작성이 가능하고, 이러한 곳에 자신이 추천/비추천과 비슷한 Vote, Downvote을 할 수 있는 기능이 있다. 문제는 이곳에서 특정 네임드 유저의 친목질 및 찬양, 비난과 무지성 Vote/Downvote 몰아주기가 난무하다는 것. 특히, 레이팅(색깔)에 따른 차별, 이른바 Ratism(Rating과 Racism을 합친 말)이 극심하다. 비슷한 발언을 해도 그레이는 Downvote 폭탄을 받고 작성한 댓글이 숨겨지는 반면[28], 퍼플/오렌지 이상의 고티어 유저는 다운보트를 적게 받는 일이 많다. 이러한 커뮤니티의 낮은 수준 때문에 정상적인 유저는 커뮤니티 사용을 하지 않고, 그렇지 않은 유저들만 남아 수준을 더 떨어뜨리는 악순환이 발생한 상태이다. 이 상황이 빠른 시간 내에 개선되는 것은 어려워 보인다.
이와 별개로 사용자의 문제가 아닌 시스템의 문제도 있는데, 게시글/댓글에 Upvote/Downvote를 하면 두 번 다시 Vote를 수정할 수 없고, 관리자에 의한 강제 삭제를 제외하면 댓글 작성 후 첫 2분 동안만 삭제가 가능하다.
5. 사건사고[편집]
5.1. 문제 표절[편집]
2022년 7월 24일, Round #810 (Div.1)의 E번 문제가 다른 코딩 사이트의 문제를 의도적으로 베낀 것이 드러났다. 해당 문제는 매우 어려운 문제이지만[29] 중국의 대회에서 출제된 적 있어 중국 유저들 사이에서 매우 유명한 문제였고, 한 유저가 대회 도중에 관련 자료(Contest Materials)에 문제 원본의 링크를 올려 중국 유저들에게는 날먹이나 다름없는 문제가 되어 버렸다.[30] 결국 해당 대회는 Unrated 처리되었다. 동시에 열린 Div.2는 정상적으로 레이팅이 반영되었다.
이로부터 단 47일 후인 9월 8일 열린 Round #819에서도 또다시 표절이 발각되었다. 이쪽은 여파가 크지 않았지만, 당연히 대회가 Unrated 처리된 것은 물론이고, 해당 세터는 영구 출제 금지 처분을 받았으며, 도용된 문제는 현재 채점이 불가능해졌다.[31]
6. 확장앱[편집]
코드포스에서는 유저가 만들어놓은 유용한 크롬 확장앱이 많다.
6.1. Carrot[편집]
대회 중 실시간으로 레이팅 변화, 퍼포먼스를 알려준다.
대회창의 Standing에 들어가면 원래는 순위, 점수 푼 문제 항목밖에 표시되지 않지만, 이 확장앱을 깔면 퍼포먼스, 레이팅 변화, 다음 레이팅까지 남은 점수가 대회 중 실시간으로 표시된다. 또한 대회가 끝나면 다음 레이팅까지 남은 점수 대신 이 대회를 통해서 발생한 등급 변화를 보여준다.
퍼포먼스는 Π 문자로 표시되고, 퍼포먼스가 x점이라는 것은 레이팅 x인 사람들이 평균적으로 이 정도의 등수를 받는다는 것이다. 퍼포먼스에 따라 레이팅이 결정된다.
이 문서의 내용 중 전체 또는 일부는 2023-10-22 16:34:45에 나무위키 Codeforces 문서에서 가져왔습니다.[1] Codeforces Contest Rules[2] 일반적으로 2시간[3] Virtual Participation은 한 대회 당 한 번밖에 할 수 없다.[4] 1023위 이내[5] 첫 대회는 2020년 5월에 있었다. 그리고 다시는 안 열리는 줄 알았으나 거의 2년 만에 두 번째 대회가 열렸다.[6] 0 ~ 1399라고 표시는 되어 있으나, 음수 레이팅도 레이팅에 영향이 있다.[7] Codeforces Contest Rules[8] 단위는 250점이다.[9] 단위: 분[10] 단위: 시간[11] 앞쪽 문제들의 Pretests 수는 대부분 10개 이하이며, 뒤쪽 문제들의 Pretests는 대체로 조금 더 많다.[12] 만약 어떤 참가자가 한 문제에서 Pretests passed 판정을 여러 번 받았을 경우 가장 나중에 제출된 것만 채점한다. 그 전의 제출은 모두 "Skipped" 처리가 되며, 마지막 제출이 System testing을 통과하지 못하더라도 그 전의 제출을 다시 채점하지 않는다.[13] 한국어로는 줄여서 시스페일이라고 한다.[14] 문제를 해결해도 Lock을 할 수 없는 한 가지 경우가 있는데, Subtask 문제 중 Easy와 Hard가 있는 경우 모든 버전을 해결해야 그 문제를 Lock할 수 있다.[15] 문제를 Lock하면 대회 중에는 더 이상 그 문제에 제출을 할 수 없다.[16] 대회 시작과 동시에 40명씩 모아서 구성된다.[17] 단위: 분[18] 부정행위자[19] 대회 이후에 레이팅이 일시적으로 롤백되는 경우도 있는데, 이 역시 치터를 처리하기 위함이다[20] 2022년 8월 17일 기준 6개월 이내에 Rated 대회를 한 번이라도 치른 순위표 등재 전체 유저 122,289명 기준. [21] 이 등급의 유저는 대회에 참가할 수 없지만 일반 유저가 중간에 관리자 권한을 얻은 경우 레이팅이 존재하기도 한다.[22] 일반적으로 누텔라라고 한다. 국내에서 이 등급을 달성한 유저는 단 7명이고, 전 세계로 범위를 넓혀도 100명 정도이다.[23] Rated 대회에 한 번도 참가하지 않은 계정. 한 번이라도 참가했다면 레이팅이 0 또는 음수라도 Newbie 등급이 된다.[24] 현재 Codeforces의 최고 레이팅 기록은 3979, 최저는 -89이다.[25] 위 그래프는 6개월 이상 라운드를 치르지 않은 유저는 제외시킨 그래프이기 때문에 등급 첫부분에 턱걸이로 걸치고 잠수한 유저의 수는 훨씬 많을 것이다.[26] 실제로 많은 div2 대회에서 1위를 Unrated, 즉 대회에 한 번도 참여하지 않은 계정이 가져가는 경우가 많으며, Top 5를 모두 현지인들이 가져가는 경우는 아예 없다고 봐도 된다.[27] 적발 시 횟수에 따라 대회 참가 무효화, 0점 처리, 일시적 또는 영구적으로 계정 정지 등의 페널티가 있다.[28] Downvote 10개를 받으면 반투명 상태가 되며, 25개를 받으면 숨겨지며 클릭해야 내용을 볼 수 있다.[29] solved.ac 기준 난이도가 Ruby III이다.[30] 대회 도중 D번을 푼 사람 수는 9명인 반면, E번을 푼 사람은 무려 171명이었다.[31] 제출 자체는 가능하지만, 정답 코드를 제출해도 3번째 테스트케이스에서 반드시 틀리게 되어 있어 더 이상 해당 문제를 맞힐 수 없다.