티스토리

......!

검색하기

블로그 홈

......!

evenharder.tistory.com/m

Evenharder 님의 블로그입니다.

구독자: 3

방명록 방문하기

주요 글 목록

13. Invocation Invocation은 countercase를 찾으려는 Stress와는 달리, 이쪽은 실제로 test를 돌려보는 쪽에 가깝습니다. 실제 Time limit과 Memory limit을 가지고, 입력한 testset, validator, main solution, checker를 이용해 solution이 예상한 verdict가 나오는지 확인하는 과정입니다. Invocation을 돌리려면 우선 Invocation 탭에 들어가 'Want to run solutions?'라는 링크를 누르면 해당 화면이 나옵니다. 이 경우 크게 3가지를 결정해야 합니다. 어떤 test set을 돌릴지를 결정해야 합니다. 한 Invocation 당 한 test set밖에 못 돌리기 때문입니다. 어떤 solution을 돌릴지 결정해야 .. 공감수 3 댓글수 0 2015. 9. 18.
12. Stress Tests, Validator, Main solution, Checker까지 다 만들었다면 문제의 90%는 만든 것이라고 볼 수 있습니다. 이제 필요한 것은 알고리즘의 검증도 있겠지만은, Polygon에서는 이렇게 만든 것을 가지고 자유롭게 테스트를 해볼 수 있도록 했습니다. 그 중 하나가 Stress입니다. Stress는 generator를 이용해서 test를 일정 시간동안 random하게 생성해내면서 혹시 있을지도 모르는 countercase를 찾는 것이 목적입니다. 어떤 soultion이 시간 제한이나 메모리 제한 등을 준수하는지 확인하고자 하는 것이 아님을 명심하시기 바랍니다(이는 Invocation이 담당합니다). Stress 탭에서 Add Stress를 누르면 다음과 같은 화면이 나타납니다. .. 공감수 0 댓글수 0 2015. 8. 18.
11. Checker Checker는 어떤 주어진 test에 대해(input), 제출한 답안이 출력한 답과 모범 답안이 출력한 답을 비교해서, verdict를 내는 프로그램입니다. 기본적으로 input data와 output data(모범 답안이든, 타인의 답안이든)을 제공받습니다. 이는 Validator에서 inf라는 Instream 타입 전역 변수를 이용하여 readInt 같은 함수로 입력을 받았던 것처럼, 제출한 답안(즉 participant's solution)이 낸 답은 ouf을 통해서, 모범 답안(즉 jury's solution)이 낸 답은 ans를 통해서 받을 수 있습니다. Checker는 기본적으로 inf를 통해서 답의 양식이 어떻게 될 것이다라는 것을 파악한 다음에, 이를 토대로 ouf와 ans에서 값을 불러.. 공감수 1 댓글수 0 2015. 8. 17.
10. Solution Files 문제의 input을 만드는 generator와, input이 합당한지 확인하는 validator를 만들었으니, 이제 input을 토대로 답을 내는 solution을 올릴 차례입니다. Solution files 탭에 가면 다음과 같은 화면이 우리를 반겨줍니다. Add soultion을 누르면 자주 봐왔던 파일 업로드 창이 보이며 여기에 업로드할 때도 파일명에 사용할 수 있는 문자들은 다음과 같습니다.알파벳 소문자 및 대문자숫자.(Period, 0x2E)_(Underscore, 0x5F)-(Hyphen, 0x2D)이런 식으로 파일을 선택하고, Language를 선택해서 올리면 solution이 추가됩니다. 밑에 있는 'Check solutions for compilability'는 solution이 컴파일 .. 공감수 0 댓글수 0 2015. 8. 12.
9. Validator Validator는 지금까지 고생하면서 만든 input 파일이 올바른 양식(이는 whitespace도 포함합니다)을 지니고 있는지, 또 문제 input 조건을 어기는 test가 invalid한지 등을 판별하는 프로그램입니다. 이런 프로그램이 따로 있는 것은 기본적으로는 test가 말 그대로 valid한지 판별하는 목적도 있겠지만, Codeforces의 Hack 등을 걸러내는 것에도 목적이 있습니다. Validator 역시 testlib.h를 사용하여 만드는 것이 강력하게 권장됩니다. 우선 Polygon의 Validator 탭에 들어가 봅시다. 각 항목을 설명하자면 다음과 같습니다.Select: Files 탭에서 'Source Files'에 업로드된 파일들을 선택할 수 있습니다. 기본적으로는 저렇게 'No.. 공감수 0 댓글수 1 2015. 8. 11.
8. Tests (2 - Generator with Freemarker) 일러두기 : 제가 정작 generator를 만드는 것 자체를 간단히 넘어간 면이 없지 않아 있지만 우선 이는 문제에 따라서 그 양상이 너무나도 다르고(input이 자연수 한 개뿐인 문제도 있는 반면, 그래프 상태를 입력을 받고 추가적으로 쿼리까지 받는 복잡한 문제들도 존재하기 때문입니다), 거기에 여러 커팅등을 방지하는 corner case를 만드는 것까지 고려하면 이건 문제를 만드는 사람이 해결해나가야 하는 일입니다. Codeforces Round에서도 '이거 정해는 O(n^2*m)인데 왜 O(n^3)이 통과되나요' 등의 일이 자주 발생하기 때문입니다. 그래서 problem setter가 여러 분들의 도움을 받는다는 것을 알 수 있습니다. 이와 별개로, 가끔씩은 test case를 만드는 것 자체가 하.. 공감수 1 댓글수 0 2015. 8. 9.
7. Tests (1 - Generator with testlib.h) 6. testlib.h에서 이미 적었듯이 Tests에서 test, 즉 문제의 input들을 만드는 것을 우선 포스팅하겠습니다. Tests 탭에 들어가면 다음과 같은 화면이 나타납니다. 순차적으로 위에서부터 설명하겠습니다.Tests(0): 이는 Tests라는 test set에 문제가 0개 있다는 것을 의미하여, Tests라는 test set에 이동하라는 하이퍼링크입니다. Tests는 기본적으로 생기는 test set입니다.Delete Current: 현재 자신이 있는 Test set를 지우는 링크입니다. 이를 만족하려면 다음과 같은 조건을 만족해야 합니다.Test set이 Tests가 아닐 것이며test가 하나도 있지 않아야 합니다. 즉 모든 test를 삭제한 상태여야 합니다.Create Current: .. 공감수 2 댓글수 0 2015. 8. 2.
6. testlib.h testlib.h는 5. Files에서도 잠깐 설명했지만, Codeforces와 Polygon의 설립자 Mike Mirzayanov가 만든, 문제를 검증하는 프로그램을 짤 때 사용하는 C++ 헤더 파일입니다. testlib.h는 test를 만들거나(Generator), test가 유효한지 판별하거나(Validator), 출제자의 답과 문제를 부는 사람의 답이 일치하는지 판별하는 등(Checker)에 사용됩니다. 실제로 testlib.h를 이용되는 경우가 많다고 이 링크에 적혀 있습니다. testlib.h의 장점은 기본적으로 안정적으로 정수가 사용되는 문제이든, 문자열 문제이든, 실수 문제이든 Generator, Validator, Checker 등을 만들 수 있으며, 실시간으로 verdict를 알 수 있.. 공감수 1 댓글수 0 2015. 7. 29.
5. Files 이번에는 기능적인 역할을 수행하는 곳은 Files입니다. 말 그대로 파일들을 저장하는 곳입니다. 그러나 Polygon의 Files는 파일들의 용도에 따라 분류가 되어 있기 때문에, 그리고 여기에 올리는 게 아니라 다른 데 올리는 파일들도 있기 때문에(ex. Statement에 첨부되는 사진 파일들), 그런 것들을 설명하겠습니다. Files의 모습은 다음과 같습니다. 크게 3개의 탭으로 나누어져 있는 것이 보입니다. 각각을 설명하자면 다음과 같습니다. Resource Files: Polygon 시스템에서 자동으로 추가해주는 기본적인 파일들이 있으며, 전체적인 토대를 이루는 파일들을 저장하는 곳입니다. 아무것도 하지 않아도 생기는 4개의 파일들의 역할은 다음과 같습니다. olymp.sty: TeX가 만드는 .. 공감수 2 댓글수 0 2015. 7. 28.
4. Statement Statement는 문제의 내용를 기술해놓는 곳입니다. 문제의 기술은 이미 General Info에서 하지 않았느냐고 말할 수 있겠지만, Statement에서는 TeX을 통해서 기술해야 한다는 점이 가장 큰 차이점입니다. 일단 TeX에 관한 설명은 뒤로 미루고 본문으로 들어가겠습니다. Statement 탭에 들어가면, 아직 하나도 만든 것이 없기에 다음과 같은 화면이 나타납니다. 언어를 하나 선택해야 하는데요, 기본적으로는 English와 Russian이 권장됩니다(언어 선택 탭을 누를 시 그 둘이 맨 위에 있는데는 이유가 있습니다. 기본적으로 Codeforces Round에서 그 두 언어만 공식적으로 지원하기 때문입니다). 개인적으로는 유니코드 충돌 문제 같은 것을 방지하기 위해 English를 우선시.. 공감수 1 댓글수 0 2015. 7. 28.
3. General Info Polygon의 첫걸음은 General Info를 적는 것에서 시작한다고 해고 과언이 아닙니다. 실제로 General Info(일반적인 정보)가 의미하는 것처럼, 문제의 기본 골격을 설정해놓는 것이 General Info의 역할입니다. 이는 다음 포스팅 때 설명한 Statement와 겹치는 감이 없잖아 있지만, 분명한 차이점이 존재합니다. General Info의 모습입니다. 여기에는 문제의 프로그래밍적인 부분보단, 문제 자체를 설정하는 부분이라 보시면 편할 것 같습니다. 하나하나씩 뜯어보도록 하겠습니다. Input file: 입력 방식을 결정합니다. 입력 데이터는 물론 파일로 존재합니다만, 이를 파일을 통해서 입력할지, 아니는 표준 입출력 방식을 사용할 지 결정합니다. 물론 그 이외의 선택지(ex. O.. 공감수 1 댓글수 0 2015. 7. 22.
2. Make a problem & Commit Changes Polygon 계정을 만들고 Login하면 View Problem 창에 있을 겁니다. 물론 방금 전에 계정을 만드셨으니 등록된 문제는 없겠지요. 그때는 간단히 New Problem 버튼을 누르면 됩니다. 이 때 문제의 이름을 설정하게 됩니다. 문제의 이름은 간단한 명칭으로 통용될 정도여야 합니다. 일반적인 문제 제목이 아니라 간단하게 'brackets' 'bang' 'flip' 이런 식으로 말입니다. 문제 제목에는 알파벳 소문자와 대시(-)만을 사용할 수 있습니다. 참고로, 문제 이름 가지고 깊은 고민하지 않으셔도 됩니다. 왜냐하면 문제 제목은 언제든지 바꿀 수 있기 때문입니다. 아무튼 문제 자체를 만드는데 성공하셨다면 Edit session에 왠지 누르고 싶어지는 Start가 나타나며, 이를 누를 경우.. 공감수 2 댓글수 0 2015. 7. 22.
1. Register Polygon에 일단 계정을 만들어 봅시다. 보시다시피, Polygon의 계정은 Codeforces와는 별개입니다. 뭐 입력해야 할 게 보이지요. 이 글을 읽는 분들이라면 당연히 영어를 잘 하시는 분들이겠지만 굳이 해석을 하자면 다음과 같습니다. First Name: 이름을 입력하시면 됩니다. 영어로 입력하시든 모국어로 입력하시든 별 상관은 없습니다. Last Name: 자신의 성을 입력하시면 됩니다. Email: 자신의 이메일을 입력하시면 됩니다. 이메일은 나중에 문제를 변경하였을 때, 알림을 받는 용도나, Polygon 계정을 까먹었을 때 임시 비밀번호를 받는 곳으로 사용됩니다. 한 이메일 계정은 한 Polygon 계정에만 사용 가능합니다. 이름, 성, 이메일은 로그인 후 자유롭게 변경이 가능합니다... 공감수 1 댓글수 0 2015. 7. 22.
0. Introduction 'Professional way to prepare programming contest problem' (프로그래밍 대회 문제를 준비하는 전문적인 방법) 세상에는 수많은 정보 문제들이 있습니다. 간단한 연산 문제부터 복잡한 알고리즘이 필요한 문제들까지, 다양한 문제들이 있지만 이들도 근본적인 공통점이 있습니다. 기본적으로 '문제'이기 때문에, description, input, output, 그리고 (주로 deterministic한) 정해 solution이 존재한다는 것이죠. 풀라고 만든 것이 문제니까요. 다만 이러한 정보 문제들이 잘 만들어졌는지는, 출제자의 책임입니다. 대체로 국제적인 대회에서는 팀으로 서로 의견을 나누고 지적해가며 문제들을 만들어내겠지만, 혼자서 문제를 만드는 경우도 생기기 마련이죠.. 공감수 5 댓글수 0 2015. 7. 22.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.