'Polygon'에 해당되는 글 14건

  1. 2015.09.18 13. Invocation
  2. 2015.08.18 12. Stress
  3. 2015.08.17 11. Checker
  4. 2015.08.12 10. Solution Files
  5. 2015.08.11 9. Validator 1
  6. 2015.08.09 8. Tests (2 - Generator with Freemarker)
  7. 2015.08.02 7. Tests (1 - Generator with testlib.h)
  8. 2015.07.29 6. testlib.h
  9. 2015.07.28 5. Files
  10. 2015.07.28 4. Statement

13. Invocation

Polygon 2015. 9. 18. 15:24

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을 돌릴지 결정해야 합니다. 모든 solution을 시험할 필요는 없습니다. 다만 그 solution이 verdict를 만족해야겠지요.

  • 어떤 test를 돌릴지 결정해야 합니다. test set 중에서 sub-task가 있어서 그것만 돌리는 경우도 있기 때문입니다. 이 경우 test 창에서 group으로 해당 test를 묶으면 일일히 test를 선택할 필요 없이 해당하는 group만 바로 선택하면 됩니다.
선택한 다음에 'Run judgement'를 누르면 Invocation이 돌아가기 시작합니다. 여기서 다시 한 번 Solution의 종류(type)을 재고하면 다음과 같습니다.
  • Main correct solution: 일명 'jury's solution'입니다. 이 풀이는 무조건 AC를 내야 합니다.

  • Correct: 이 풀이는 무조건 AC를 내야 합니다.

  • Incorrect: 이 풀이에 대해서 Incovation은 Verdict를 따지지 않습니다.

  • Time limit exceeded: 이 풀이는 AC 또는 TL(Time Limit Exceeded)가 나와야 합니다.

  • Wrong answer: 이 풀이는 AC 또는 WA(Wrong Answer)가 나와야 합니다.

  • Memory limit exceeded: 이 풀이는 AC 또는 ML(Memory Limit Exceeded)가 나와야 합니다.

  • Failed: 이 풀이는 AC 또는 RE(Runtime Error)가 나와야 합니다.
Invocation을 돌리다가 나올 수 있는 다른 Verdict(2글자)는 다음과 같습니다.
  • RJ : Rejected입니다. 어떤 풀이가 예상된 verdict와 달리 나올 경우, 그 이후의 test는 실행되지 않습니다. RJ가 나왔다는 것은 Invocation이 실패했다는 뜻입니다.

  • IL : Idleness Limit Exceeded입니다. 일부 함수들은 입력을 받을 때까지 대기하는 경우가 있습니다(ex. scanf, getch()). 이런 함수들이 호출되지 않고 프로그램이 계속 idle한 상태일 때 이런 verdict가 나옵니다. 사실 이 verdict는 사실상 거의 나타날 일이 없습니다.

  • FL: 뭔 뜻인지는 모르겠지만, 파일 입출력으로 test가 생성되어 있는데 표준 입출력으로 test를 받을 경우 해당하는 verdict가 나옵니다.

  • PE : Presentation Error입니다. 공백 관련 문제가 아니라 int형을 예상했는데 long long int형으로 출력을 했을 때 이 Verdict가 나옵니다.
Invocation을 돌린 예시는 다음과 같습니다.

몇 개의 예시를 보면 다음과 같습니다.

  • 검은색 글씨로 나오는 경우는 '이 solution의 verdict는 신경쓰지 않겠다'는 것을 의미합니다.

  • 파란색 글씨로 나오는 경우는 Correct 이외의 Verdict 중 예상되던 Verdict(ex. 느린 코드면 TL, 속도는 괜찮은데 틀리면 WA)가 나오면 파란색이 됩니다.

  • 초록색 글씨는 Correct를 의미합니다.

  • 여기에는 없지만, 볼드체 쳐진 붉은 글씨는 예상된 Verdict가 나오지 않았다는 것을 의미합니다.

  • 각 경우에 적혀있는 x / y의 숫자는 각각 걸린 시간(ms)과 용량(MB)를 의미합니다.

  • 파란색으로 표시되는 test는 다음과 같은 조건을 만족합니다.

    • 그 solution에 대해서 가장 시간을 많이 소모한 test일 때(실제로는 Time Limit의 2배까지 돌려봅니다)

    • 100ms보다 더 오래 걸린 test일 때

  • 이에 비해, 주황색으로 표시되는 test는 Time Limit 안에 돌아가지는 않았지만 Time Limit의 2배 안에는 성공적으로 수행된 경우입니다.
Invocation은 결국 준비된 test에 대해서 모든 solution들이 예상된 결과를 보이는지 확인하는 마지막 절차라고 볼 수 있습니다.


'Polygon' 카테고리의 다른 글

12. Stress  (0) 2015.08.18
11. Checker  (0) 2015.08.17
10. Solution Files  (0) 2015.08.12
9. Validator  (1) 2015.08.11
8. Tests (2 - Generator with Freemarker)  (0) 2015.08.09
Posted by Evenharder
,

12. Stress

Polygon 2015. 8. 18. 16:28

Tests, Validator, Main solution, Checker까지 다 만들었다면 문제의 90%는 만든 것이라고 볼 수 있습니다. 이제 필요한 것은 알고리즘의 검증도 있겠지만은, Polygon에서는 이렇게 만든 것을 가지고 자유롭게 테스트를 해볼 수 있도록 했습니다. 그 중 하나가 Stress입니다. Stress는 generator를 이용해서 test를 일정 시간동안 random하게 생성해내면서 혹시 있을지도 모르는 countercase를 찾는 것이 목적입니다. 어떤 soultion이 시간 제한이나 메모리 제한 등을 준수하는지 확인하고자 하는 것이 아님을 명심하시기 바랍니다(이는 Invocation이 담당합니다). Stress 탭에서 Add Stress를 누르면 다음과 같은 화면이 나타납니다.




각 항목을 설명하자면 다음과 같습니다.


  • Script pattern: Generator의 script를 쓰면 됩니다. Generator의 기본적인 인자까지만 써도, Polygon이 내부적으로 추가적인 인자를 더해 seed값을 바꾸기 때문에 random한 test가 생성됩니다. 

  • Memory limit: 각 test당 사용할 수 있는 메모리의 제한입니다. 일반적으로 General Info의 것과 동일하게 설정되어 있습니다.

  • Time limit: 각 test 당 사용할 수 있는 시간의 제한입니다. 역시 일반적으로 General Info의 것과 동일하게 설정되어 있습니다.

  • Total time limit: Stress를 얼마나 돌릴 것인지 설정하는 항목이며, 5초, 15초, 30초, 60초, 90초, 120초가 가능합니다.

  • Solutions: Stress를 통해 돌릴 solution을 의미합니다. 직접 타이핑하는 수도 있으며(이 때 프로그램명과 확장자를 써야 합니다), 옆의 Add 버튼을 이용해 solution을 선택해서 올리는 수도 있습니다.

  • Description: 이 Stress가 무슨 의미를 가지는지 적는 비고란이라고 보면 되겠습니다.
이 때 Save를 누르면 Stress가 저장됩니다. 이렇게 만든 Stress는 탭에서 Run을 통해서 실행을 할 수 있으며, View를 통해서 설정 사항을 볼 수 있고, Edit을 통해서 그 사항들을 수정할 수 있으며, Delete를 통해 삭제가 가능합니다.

Run을 할 경우, Stress가 돌아가면서 random한 test를 각 solution에 집어넣습니다. Stress의 종료 조건은 다음과 같습니다.

  • 사용자가 탭에서 Cancel을 누른 경우입니다. 이 때 Stress는 무효 처리 됩니다.

  • Stress가 어떤 solution에 대해서 countercase, 즉 반례를 찾아낸 경우입니다. Stress가 성공한 것입니다. 이 때는 추가적으로 해당 Stress가 파란색으로 나타나며, Add to test를 통해 원하는 test set에 집어넣을 수 있습니다.

  • Stress가 지정된 시간만큼 random한 test case를 집어넣었으나, 반례를 찾지 못한 경우입니다.

  • Stress를 돌리다가, 어떤 solution이 Correct나 Wrong answer 이외의 verdict(ex. Time limit exceeded, Runtime error)를 낸 경우입니다. 이 때는 solution 자체가 잘못된 것으로, 해당 Stress가 빨간색으로 나타납니다.
Stress는 이렇게 잘못된 알고리즘으로부터 도출된 일부 solution의 wrong answer를 집어내서 countertest를 쉽게 만들 수 있다는 장점이 있습니다. 특히 실수 할 법한 코드를 걸러내는 역할을 수행하는데 제격입니다. 


'Polygon' 카테고리의 다른 글

13. Invocation  (0) 2015.09.18
11. Checker  (0) 2015.08.17
10. Solution Files  (0) 2015.08.12
9. Validator  (1) 2015.08.11
8. Tests (2 - Generator with Freemarker)  (0) 2015.08.09
Posted by Evenharder
,

11. Checker

Polygon 2015. 8. 17. 16:19

Checker는 어떤 주어진 test에 대해(input), 제출한 답안이 출력한 답과 모범 답안이 출력한 답을 비교해서, verdict를 내는 프로그램입니다. 기본적으로 input data와 output data(모범 답안이든, 타인의 답안이든)을 제공받습니다. 이는 Validator에서 inf라는 Instream 타입 전역 변수를 이용하여 readInt 같은 함수로 입력을 받았던 것처럼, 제출한 답안(즉 participant's solution)이 낸 답은 ouf을 통해서, 모범 답안(즉 jury's solution)이 낸 답은 ans를 통해서 받을 수 있습니다.

Checker는 기본적으로 inf를 통해서 답의 양식이 어떻게 될 것이다라는 것을 파악한 다음에, 이를 토대로 ouf와 ans에서 값을 불러내 비교하는 것이 그 역할이지만, 이 때 readSpace(), readEoln() 등의 함수는 일반적으로 사용하지 않습니다.


다음 함수들은 Checker에서 유용하게 사용할 수 있습니다.

  • void registerTestlibCmd(int argc, char* argv[]):
    이 프로그램이 Checker라는 것을 알리는 함수입니다. main 함수의 인자인 argc,argv를 그대로 인수로 전달해야 합니다.

  • void quit(TResult verdict, string message): void quit(TResult verdict, const char* message): void quitf(TResult verdict, const char* message, ...):
    Checker가 내린 결론을 verdict에, 관련된 멘트(ex. ok 4 numbers 1 4 2 3)를 message의 형태로 적어서 알린 다음, 프로그램을 종료합니다.

  • void quitif(bool condition, TResult verdict, const char* message, ...):
    bool형 조건인 condition을 만족할 경우, quitf(verdict, message......)를 호출합니다.

  • void setName(const char* format, ...): Checker에 내부적으로 이름을 주는 함수입니다.
  • 이 외에도 디버깅 용으로 ensuref를 사용할 수 있습니다.
저 TResult verdict로 나타나 있는 인자에는 다음과 같은 값을 집어넣을 수 있습니다.
  • _ok
    Verdict는 OK. 즉 맞았다는 뜻입니다. 문제에 따라서는 최적의 해이다라는 뜻일 수도 있습니다(답이 하나가 아닌 Special Judge인 경우).

  • _wa
    Verdict는 Wrong answer. 답이 틀렸거나, 최적해가 아니라는 뜻입니다.

  • _pe
    Verdict는 Presentation error. 직접적으로 사용하기 보다는, testlib.h에서 내부적으로 이 매크로를 많이 사용합니다. 예를 들면 readInt()를 했는데 읽은 값이 숫자가 아닐 때 이는 _pe로 처리되지만 실제 verdict는 wrong answer로 대체됩니다.

  • _pc(score)
    Verdict는 Partially correct. score에 점수를 넣어 사용합니다. 주로 Sub-task를 구현한 문제일 때 사용하면 좋겠으나 흔하진 않습니다. Codeforces Rounds부터 sub-task를 사용하지 않으니 말입니다.

  • _fail
    Verdict는 Fail. 역시 testlib.h에서 프로그램에 내부적으로 문제가 있을 때 많이 사용하는 매크로이지만(ex. readInt(1,5)를 했는데 return값이 0일 때), 때로는 최적해를 구하는 문제에서 모범 답안보다 더 훌륭한 답을 구했을 때 사용되기도 합니다. 이런 경우에 Wrong answer를 줄 수는 없으니까요. 실제로 이런 상황이 일어나면 문제 출제자가 Main solution을 재검할 필요가 있습니다.

이것과 Validator에서 사용한 함수들을 그대로 이용하면 Checker를 작성할 수 있습니다. 이번에는 testlib.h에 있는 checker 폴더의 ncmp.cpp 파일을 예로 들겠습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include "testlib.h"
#include <sstream>
 
using namespace std;
 
int main(int argc, char * argv[])
{
    setName("compare ordered sequences of signed int%ld numbers"* sizeof(long long));
 
    registerTestlibCmd(argc, argv);
 
    int n = 0;
    string firstElems;
 
    while (!ans.seekEof() && !ouf.seekEof())
    {
        n++;
        long long j = ans.readLong();
        long long p = ouf.readLong();
        if (j != p)
            quitf(_wa, "%d%s numbers differ - expected: '%s', found: '%s'", n, englishEnding(n).c_str(), vtos(j).c_str(), vtos(p).c_str());
        else
            if (n <= 5)
            {
                if (firstElems.length() > 0)
                    firstElems += " ";
                firstElems += vtos(j);
            }
    }
 
    int extraInAnsCount = 0;
 
    while (!ans.seekEof())
    {
        ans.readLong();
        extraInAnsCount++;
    }
    
    int extraInOufCount = 0;
 
    while (!ouf.seekEof())
    {
        ouf.readLong();
        extraInOufCount++;
    }
 
    if (extraInAnsCount > 0)
        quitf(_wa, "Answer contains longer sequence [length = %d], but output contains %d elements", n + extraInAnsCount, n);
    
    if (extraInOufCount > 0)
        quitf(_wa, "Output contains longer sequence [length = %d], but answer contains %d elements", n + extraInOufCount, n);
    
    if (n <= 5)
        quitf(_ok, "%d number(s): \"%s\"", n, compress(firstElems).c_str());
    else
        quitf(_ok, "%d numbers", n);
}
 
cs


파일을 분석하자면 다음과 같습니다.


  • setName으로 Checker의 이름을 내부적으로 설정합니다.

  • registerTestlibCmd로 이 프로그램이 Checker라는 것을 알립니다.

  • while (!ans.seekEof() && !ouf.seekEof())로, ans(jury's solution) 또는 ouf(participant's solution)가 끝날 때까지 읽어들입니다. 이상적인 결과는 둘 다 동시에 EOF를 만나는 경우이겠지만, 그러지 않는 코드를 제출하는 사람들이 존재합니다(괜히 pretest 1에서 틀리는 사람들이 있는 게 아닙니다).

  • 참고로 ans에서 나오는 답과 ouf에서 나오는 답을 각각 vector에 집어넣은 다음에 하나씩 비교해나가는 방법도 있습니다. checker 폴더의 uncmp.cpp 파일을 참조하세요.

  • n은 inf로 직접 코드에서 받을 수도 있으나, 본 코드에서처럼 while문 안에서 내부적으로 계산하는 수도 있습니다. 후자의 경우 본 케이스가 몇 번째인지 알 수 있습니다. 물론 inf에서 받아서 for문을 돌려도 마찬가지입니다.

  • j와 p를 각각 ans.readLong(), ouf.readLong();으로 받았습니다. 이 때 j와 p가 같지 않을 때 quitf를 사용하는데, 이때 사용하는 함수들을 분석하면 다음과 같습니다.

    • englishEnding(n). 1st, 2nd, 3rd, 4th......등에 오는 2글자짜리 영어 서수를 std::string으로 return하는 함수입니다. testlib.h에 전역으로 정의되어 있는 함수입니다.

    • c_str(). <string>에 선언되어 있습니다. 역할은 해당 std::string에 대해 string이 저장하고 있는 값을 가리키는 char* 포인터를 return합니다. 이 경우 %s로 바로 출력할 수 있습니다(이 경우는 quitf를 통한 stderr로 말입니다).

    • vtos(n). n를 std::string으로 바꾸어 return합니다. n의 타입은 일반적인 연산자 <<(std::ostream::operator<<)로 받아들일 수 있는 타입에 한합니다.

  • 이런식으로 한 쪽이 EOF를 맞이한 경우, 나머지도 EOF를 만날 때까지 계속 빼냅니다. 이 때 extraInAnsCount, extraInOufCount로 추가적인 원소의 개수를 계산합니다.

  • extraInAnsCount이나 extraInOufCount이 양수일 경우 어느 쪽이 길이가 얼마이며 더 길다는 것을 quitf를 통해 알립니다.

  • 그렇지 않을 경우, 올바른 답을 출력했다는 뜻이므로, quitf(_ok, "%d numbers", n);를 부릅니다. 다만 n이 5 이하일 때는 모든 element를 firstElems라는 std::string에 담아 보관하고 있다가 같이 출력합니다. 이 때 사용되는 compress 함수의 역할은 다음과 같습니다.

    • compress(str): testlib.h에 전역으로 선언되어있는 함수입니다. 역할은 str의 길이가 64 이하일 경우 그대로 str를 return하고, 그보다 길 경우 처음 30글자와 마지막 31글자만 남기고 사이에 "..."를 삽입하여 return합니다. 함수명대로 압축하는 함수입니다.

간단해 보이지만, 실제로는 Checker 역시 상당히 조심스럽게 만들어야 합니다. 왜냐하면 그 어떤 output(쓰레기값이 나오는 코드라든지, 일부러 이상한 값을 출력하는 코드라든지)에도 제대로 작동해야 하기 때문입니다. 그래서 일반적으로는 값을 읽을 때도 주어진 범위가 있다면 그에 따른 범위를 주어야 합니다.


또 '읽어내는 역할'을 수행하는 readAns 함수를 만드는 것 역시 추천합니다. 그 이유는 간단한 output이라면 모르겠지만, output이 복잡하면 ans 따로, ouf 따로 출력하는 것이 비효율적이기 때문입니다. 더 자세한 것은 이 링크를 참조하시기 바랍니다.


이렇게 만든 Checker를 Polygon에 올리는 방법은 Validator와 흡사합니다. 한번 볼까요?



Select하는 부분은 Validator와 동일하므로 넘어가겠습니다.


Checker test를 만드는 방법을 설명하자면, 기본적으로 Add test를 눌러서 문제를 만드는 창으로 이동할 수 있습니다.



각 항목을 설명하자면 다음과 같습니다.

  • Checker test #: Checker test의 번호입니다. 항상 그렇듯이 번호는 1부터 1000까지의 자연수만 가능합니다.

  • Input: 한 test의 input입니다. 물론 Validator가 통과시킬 수 있는 test를 작성해야겠지요.

  • Output: 이 output은 밑에 적혀있는 것처럼, 'participant'의 답안입니다.

  • Answer: 이 항목은 밑의 Generate Answer를 누르면, Main solution이 출력한 답을 창에 생성해줍니다. 물론 직접 입력할 수도 있습니다.

  • Verdict: 채점 결과입니다. 4가지 결과 중 하나를 선택할 수 있으며, 이는 다음과 같습니다.

    • OK: Output과 Answer가 같거나, Output이 여러 최적해 중 하나일 경우 해당합니다. Correct인 셈이죠.

    • WRONG_ANSWER: Output과 Answer가 다르거나, Output이 최적해가 아닌 경우를 의미합니다.

    • PRESENTATION_ERROR: 여러 번 강조하지만, 이 결과는 (일단 Codeforces에서는) 일반적으로 사용하지 않습니다. whitespace 관련된 규격을 맞추고 싶으시다면 뭐 어쩔 수 없지만 말입니다. 다만 testlib.h 함수를 호출했는데 값이 범위나 형식이 맞지 않으면 이 verdict가 내부적으로 호출되는 경우도 있습니다.

    • FAILED: 이 경우 프로그램 내부적으로 무언가 틀린 경우를 의미하는데, 위에서 TResult verdict 관련해서 설명했던 경우 중 'Output이 Answer보다 더 최적인 경우'가 해당됩니다. 물론 이런 경우가 있으면 해당 부분에 대한 수정이 필요합니다.
이 경우 Create를 누르면 Validator처럼 다시 원래 탭으로 이동하는 것이 아니라, 다음 test를 만드는 창으로 저절로 이동하게 됩니다.

만들 수 있는 test의 종류를 몇 개 추천하자면 다음과 같습니다.
  • Correct한 답안을 판별하는 경우. 이 경우는 특히 답안이 여러 개가 나올 수 있는 Special Judge의 경우 더욱 더 부각됩니다.

  • Wrong answer를 걸러내는 경우. 그 어떠한 output이 들어와도 Checker는 Runtime Error 등의 오류를 내면 안 됩니다.

  • Checker 등에 있는 ensuref, quitf 등의 작동. 형식이 틀렸으면 왜 틀렸는지(ex. 같은 수가 두 번 나온다든지, 그래프가 트리가 아니라든지)
Checker는 결국 직접적으로 participant와 소통하는 프로그램이라는 사실을 명심하시길 바랍니다.


'Polygon' 카테고리의 다른 글

13. Invocation  (0) 2015.09.18
12. Stress  (0) 2015.08.18
10. Solution Files  (0) 2015.08.12
9. Validator  (1) 2015.08.11
8. Tests (2 - Generator with Freemarker)  (0) 2015.08.09
Posted by Evenharder
,

10. Solution Files

Polygon 2015. 8. 12. 00:38

문제의 input을 만드는 generator와, input이 합당한지 확인하는 validator를 만들었으니, 이제 input을 토대로 답을 내는 solution을 올릴 차례입니다. Solution files 탭에 가면 다음과 같은 화면이 우리를 반겨줍니다.



Add soultion을 누르면 자주 봐왔던 파일 업로드 창이 보이며 여기에 업로드할 때도 파일명에 사용할 수 있는 문자들은 다음과 같습니다.

  • 알파벳 소문자 및 대문자

  • 숫자

  • .(Period, 0x2E)

  • _(Underscore, 0x5F)

  • -(Hyphen, 0x2D)

이런 식으로 파일을 선택하고, Language를 선택해서 올리면 solution이 추가됩니다. 


밑에 있는 'Check solutions for compilability'는 solution이 컴파일 가능한지 확인하는 버튼입니다.

표에 있는 문구들의 의미를 하나씩 해석하면 다음과 같습니다.

  • Author: 해당 solution을 업로드한 사람입니다. 혼자 하면 자신의 id가 나타나겠지만 Polygon의 문제는 타인과 공유가 가능하다는 사실을 잊지 마세요.

  • Name: solution의 이름입니다. Rename을 통해서 이름을 바꿀 수 있습니다.

  • Language: solution의 언어입니다.

  • Length: solution의 크기(용량)입니다. 참고로 Codeforces의 상한은 64kB입니다.

  • Modified: 최근 수정 날짜를 의미합니다.

  • Type: soultion이 어떤 종류의 풀이인지를 의미합니다. 창을 보면 8가지 중 하나를 선택해야 합니다. 이 Type는 나중에 Invocation이라는 것을 할 때 매우 중요해집니다.

    • Main correct solution: 일명 'jury's solution'입니다. 기본적으로 '맞는 풀이' 중 하나이나, 이 풀이는 Codeforces의 Hack이나, Checker 등을 통한 test에 대해 답을 출력하는데 사용됩니다. Main correct solution은 한 문제에 하나만 있을 수 있습니다.

    • Correct: 그냥 맞는 풀이입니다.

    • Incorrect: 여러 가지로 틀린 풀이입니다. 이 경우 test에 따라서 Runtime Error가 날 수도 있고, Time Limit Exceeded가 날 수도 있고, Wrong answer가 날 수도 있고, 맞을 수도 있고......

    • Time limit exceeded: 알고리즘은 맞는데 문제가 요구하는 것에 비해 느린 풀이를 의미합니다.

    • Wrong answer: 답이 틀린 풀이입니다.

    • Presentation error: 이 경우는 whitespace 관련해서 output이 이상한 경우입니다. 예를 들면 정수 2개를 공백으로 구분해서 출력하라고 했는데 줄바꿈을 하여 출력한다든지......일부 Online judge에는 있는 것 같지만, 일단 Codeforces에는 Presentation error verdict가 현재로서는 없습니다. 사실 옛날 초기 Codeforces에는 있었습니다만, 이 링크를 보면 폐지했습니다. 뭐 굳이 쓰자면 checker에서 검증할 수도 있겠습니다만......추천하지는 않습니다.

    • Memory limit exceeded: 문제에서 주어진 메모리보다 더 많은 메모리를 사용한 것을 의미합니다. 예시로는 배열의 크기가 너무 크거나(이 때는 컴파일이 거부되는 경우도 있습니다), std 컨테이너에 원소를 너무 많이 집어넣거나 하는 경우가 있습니다.

    • Failed: 프로그램 실행 도중 에러가 발생해 시스템이 프로그램을 중단하는 경우입니다. 달리 말하자면 Runtime error입니다. Runtime error가 나는 경우는 대단히 많지만, competitive programming을 하다가 runtime error가 나는 경우는 대부분은 이런 경우들입니다.

      • Out-of-bounds, 특히 배열을 잘못 참조할 때
      • 0으로 나눌 때(Division by 0)
      • 재귀함수를 너무 많이 호출해서 스택이 터졌을 때(stack buffer overflow)
이런 식으로 코드를 올리면 시험도 해봐야겠죠? 이를 Invocations 또는 Stresses에서 진행 가능하지만, 아직은 할 수 없습니다. 제출한 코드가 내놓는 답(participant's solution)이 실제 답(jury's solution)과 일치하는지 확인해야 하기 때문입니다. 이는 Checker라는 프로그램이 담당합니다.


'Polygon' 카테고리의 다른 글

12. Stress  (0) 2015.08.18
11. Checker  (0) 2015.08.17
9. Validator  (1) 2015.08.11
8. Tests (2 - Generator with Freemarker)  (0) 2015.08.09
7. Tests (1 - Generator with testlib.h)  (0) 2015.08.02
Posted by Evenharder
,

9. Validator

Polygon 2015. 8. 11. 20:38

Validator는 지금까지 고생하면서 만든 input 파일이 올바른 양식(이는 whitespace도 포함합니다)을 지니고 있는지, 또 문제 input 조건을 어기는 test가 invalid한지 등을 판별하는 프로그램입니다. 이런 프로그램이 따로 있는 것은 기본적으로는 test가 말 그대로 valid한지 판별하는 목적도 있겠지만, Codeforces의 Hack 등을 걸러내는 것에도 목적이 있습니다.


Validator 역시 testlib.h를 사용하여 만드는 것이 강력하게 권장됩니다. 우선 Polygon의 Validator 탭에 들어가 봅시다.



각 항목을 설명하자면 다음과 같습니다.

  • Select: Files 탭에서 'Source Files'에 업로드된 파일들을 선택할 수 있습니다. 기본적으로는 저렇게 'No validator'라고 나와 있습니다.

  • Or upload: 아니면 사용자의 컴퓨터에서 업로드할 수 있습니다. 확인해보지는 않았지만, 이 떄 올리는 파일의 이름 역시 4. Statement의 그림 파일 올릴 때처럼 다음 조건을 만족해야 할 겁니다.

    • 알파벳 소문자 및 대문자

    • 숫자

    • .(Period, 0x2E)

    • _(Underscore, 0x5F)

    • -(Hyphen, 0x2D)

  • Language: validator의 언어입니다. 일반적으로 Autodetect(자동 감지)를 사용해도 전혀 무리가 없으며, 아니면 testlib.h 자체의 특성상 대부분 gcc.c++로 할 테지만, 그 외에도 다양한 언어로 짤 수는 있습니다. 하지만 다른 언어로 옮기면서 예상치 못한 버그가 나타날 수도 있으니, 그냥 c++로 짜는 것을 추천드립니다.
아무튼 validator를 올리는 과정 자체는 간단합니다. 이제 validator를 만드는 과정이 남아 있을 뿐입니다. 그다지 어렵지는 않으므로, 걱정하진 마세요.
validator를 만드면서 꼭 필요할 함수들을 소개하겠습니다. registerValidation 함수만 제외하면, inf.xxx의 형태로 사용이 가능합니다. 이 inf는 testlib.h 에 선언되있는 class 중 하나인 InStream이 전역 변수의 형태로 선언되어 있는 것이며, generator가 생성한 값이 여기에 저장됩니다.
  • void registerValidation(int argc, char* argv[]):
    validator 선두에 무조건적으로 호출해야 하는 함수입니다. 이 함수의 역할은 argv로 받은 인자들이 올바른지 판별하는 역할을 합니다. 참고로 validator 실행파일에 주어지는 인자는 Polygon이 알아서 잘 집어넣어 줍니다.

  • void skipBlanks():
    whitespace가 아닌 문자를 만날 때까지, 아니면 EoF(End of File, 파일의 끝)를 만날 때까지 포인터를 이동합니다. 이 포인터는 그냥 input을 저장하는 배열값을 가리키는 포인터라고 생각하면 되겠습니다.

  • char readChar():
    문자를 하나 읽으면서 포인터를 다음 문자로 넘깁니다. return값은 읽은 문자값입니다.

  • char readChar(char c):
    문자를 하나 읽으면서, 포인터를 다음 문자로 넘깁니다. return값은 읽은 문자값입니다. readchar()과의 차이점은 읽은 문자가 c와 같지 않을 경우 'Unexpected character 'x', but 'y' expected'의 형식으로 stderr로 출력합니다.

  • char readSpace():
    readChar(' ')과 동일합니다. ' '(SPACE)를 읽으며 포인터를 다음 문자로 넘기되, SPACE가 아니면 stderr로 해당 사실을 출력합니다.

  • void unreadChar(char c):
    포인터를 한 칸 앞으로 옮기면서, input 배열에(실제로는 std::string입니다만)그 자리에 c를 집어넣습니다. 당연한 소리지만, 포인터가 맨 앞에 있는데 이 함수를 호출하면 에러가 납니다.

  • std::string readToken(), std::string readWord():
    한 단어, 즉 whitespace 또는 EoF를 만나기 전까지의 모든 글자들을 std::string 형식으로 읽으며, 이를 return합니다. 이 경우 포인터는 그 whitespace 또는 EoF를 가리키게 됩니다.

  • std::string readToken(const std::string& ptrn, const std::string& variableName = ""): 구조적으로는 위의 함수와 똑같지만, 2가지 차이점이 있습니다. 첫째는 읽은 문자열이 ptrn로 주어진 Regex 형태와 일치해야 하며, 둘째로는 이 문자열의 '이름'을 variableName을 통해 명명할 수 있다는 것입니다. '이름'을 붙이는 이유는, Regex 형태와 일치하지 않을 때 다음과 같이 stderr로 출력되기 때문입니다. 예를 들면 'Token parameter [name=str] equals to "abc", doesn't correspond to pattern "[ab]+"'의 형식으로 말이죠. 이 경우 입력받은 문자열은 abc, ptrn에는 [ab]+, variableName에는 str이 들어가 있는 것입니다. 이렇게 하면 어떤 변수가 조건을 부합하지 않는지 알 수 있습니다. readWord도 똑같이 오버로딩되어 있습니다.

  • long long readLong():
    long long 타입의 정수를 하나 읽습니다. 작동 원리는 readWord()를 부른 다음에 읽은 string이 long long 타입의 정수인지 판별하고(판별 과정은 생략하겠습니다), 그 값을 long long 으로 return하는 형식입니다. 이하 다른 readxxx함수도 마찬가지 방식으로 작동합니다.

  • int readInteger(), int readInt():
    int 타입의 정수를 하나 읽습니다.

  • double readReal(), double readDouble():
    double 타입의 실수를 하나 읽습니다.

  • long long readLong(long long minv, long long maxv, const std::string& variableName = ""): 구조적으로는 readLong()과 동일하지만, 이 경우 읽은 값이 minv 이상 maxv 이하여야 합니다. 그렇지 않을 경우 variableName에 들어가는 변수 명을 이용하여 'Integer parameter [name=n] equals to 132039, violates the range [1,100000]' 등으로 에러 메시지를 냅니다. 사실 이쪽을 사용하는 것이 권장됩니다. 

  • int readInt(int minv, int maxv, const std::string& variableName = ""):
    구조적으로는 readInt()와 동일하지만, 이 경우 읽은 값이 minv 이상 maxv 이하여야 합니다. variableName은 에러 메시지에 출력할 변수명입니다. readInteger 함수도 해당 버전이 있습니다.

  • double readDouble(double minv, double maxv, const std::string& variableName = ""):
    구조적으로는 readDouble()와 동일하지만, 이 경우 읽은 값이 minv 이상 maxv 이하여야 합니다. variableName은 에러 메시지에 출력할 변수명입니다. readReal 함수도 해당 버전이 있습니다.

  • double readStrictDouble(double minv, double maxv, int minAfterPointDigitCount, int maxAfterPointDigitCount, const std::string& variableName = ""):
    구조적으로는 readDouble(minv, max, variableName)과 동일하지만, 소수점의 자릿수가 minAfterPointDigitCount 이상 maxAfterPointDigitCount 이하이어야 합니다. readStrictReal 함수도 해당 버전이 있습니다.

  • std::string readString(), std::string readLine(): EOF나 EOLN(End of Line, 즉 줄바꿈을 의미하는 글자입니다)을 만날 때까지 입력된 값을 읽어나가, 그 읽은 값은 std::string의 형태로 반환합니다.

  • std::string readString(const std::string& ptrn, const std::string& variableName = ""):
    readString()과 동일하나, 읽은 값이 ptrn로 주어진 Regex 패턴을 만족해야 하며, 아닐 경우 variableName에 주어진 변수명을 토대로 에러를 띄웁니다.

  • void readEoln():
    줄바꿈 문자('\n')를 읽습니다. 줄바꿈 문자가 아닐 경우, 'Expected EOLN'이라면서 에러를 띄웁니다. 이 함수는 Windows에서는 0x0D와 0x0A를 읽으며(CR LF), OS X(버전 10 이상)와 *nix에서는 0x0A를 읽습니다(LF).

  • void readEof():
    파일의 끝을 읽습니다. 파일의 끝이 아닐 경우, 'Expected EOF'라며 에러를 띄웁니다.

  • inline void ensuref(bool cond, const char* format, ...):
    cond에 입력된 조건이 만족되지 않을 경우, format을 stderr로 출력합니다. printf처럼 가변형 인자를 가진 함수입니다. 이 함수는 주로 변수를 입력받은 다음에, 변수의 범위로만은 따질 수 없는 성질을 확인하고자 할 때 사용합니다. 

7. Tests (1 - Generator with testlib.h)에서 선보였던 generator가 기억나십니까?


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include "testlib.h"
#include <iostream>
 
int main(int argc, char* argv[])
{
    registerGen(argc, argv, 1);
    
    int query=atoi(argv[1]);
    int max_int=atoi(argv[2]);
    
    cout << query << endl;
    
    for(int i=0;i<query;i++)
    {
        int n=rnd.next(0, max_int);
        int r=rnd.next(0, n);
        std::cout << n << " " << r << endl;    
    }
    return 0;
}
 
cs


query와 max_int의 최댓값이 80000이라고 문제에 명시가 되어 있다면, 이 generator에 해당하는 validator의 한 예시는 다음과 같습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "testlib.h"
 
int main()
{
    registerValidation();
 
    int q = inf.readInt(180000"q");
    inf.readEoln();
 
    for (int i = 0; i < q; i++)
    {
        int n = inf.readInt(080000"n");
        inf.readSpace();
        int r = inf.readInt(080000"r");
        ensuref(r <= n, "'r' must not  exceed 'r'");
        inf.readEoln();
        
    }
    inf.readEof();
    return 0;
}
 
cs


q를 읽은 다음에 줄바꿈 문자을 읽고, 'n을 읽는다 ->  공백을 읽는다 -> r을 읽는다 -> r <= n인지 확인한다 -> 줄바꿈 문자를 읽는다'를 q번 반복합니다. 그 다음에는 EOF을 읽으며 끝납니다. Polygon의 Well-formed policy는 이런 whitespace을 각 문제별로 규격화하기 우해서 있는 것이지요. space가 난잡하게 어떤 곳은 1개, 어떤 곳은 3개 이렇게 있으면 validator가 작동하기 힘들기 때문입니다.


하나 더 예시를 들어보겠습니다. 이 코드는 다음 문제의 validator로 작동합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include "testlib.h"
char status[1000001];
int main()
{
    registerValidation();
 
    int n=inf.readInt(1100"n");
    inf.readEoln();
 
    for(int i=0;i<n;i++)
    {
        char ch=inf.readChar();
        ensuref(ch=='+'||ch=='-'"Invalid operation %c, + or - expected", ch);
        inf.readSpace();
        int x=inf.readInt(11000000"x");
        if(status[x]==ch)
        {
            ensuref(ch!='+'"Invalid operation %c %d, %d is already in the library", ch, x, x);
            ensuref(ch!='-'"Invalid operation %c %d, %d is not in the library", ch, x, x);
        }
        status[x]=ch;
        inf.readEoln();
    }
    inf.readEof();
    return 0;
}
 
cs


입력 데이터가 복잡해질수록 validator도 복잡해지지만, validator는 모든 invalid input을 잡아야 하기에, 신중히 코딩할 필요가 있습니다. 그래서 Polygon은 validator를 시험해볼 기회를 줍니다. Set validator 밑을 보면 다음과 같습니다.



Test를 하나 만들고 설명하겠습니다. Add test를 누르면 다음과 같은 화면이 나타납니다.



각 항목을 설명하자면 다음과 같습니다.Validator test #: test의 번호입니다. 여기서도 마찬가지로, test의 개수는 1000개를 넘을 수 없습니다(1~1000).

  • Multiple tests: 저 체크박스가 활성화되어 있으면 ===을 경계로 여러 개의 test를 한꺼번에 만들 수 있습니다. 특히 Validator test는 Archive로 한꺼번에 올릴 수도 없고, Create를 누르면 Tests의 경우처럼 다시 이 창으로 이동하는게 아니라 Validator 탭으로 다시 이동하기 때문에, 여러 개를 한꺼번에 만드는 것을 추천합니다.

  • Input(s): test data를 여기에 적으면 됩니다. 공백이나 줄바꿈에 유의하면서 입력하시기 바랍니다. 참고로 Multiple Test를 만들 때 구분을 ===로 한다고 했는데, 사용 예시는 다음과 같습니다.

    1

    2 1

    ===

    0


      ===를 사용할 때는, ===를 치고 바로 줄바꿈을 해야 합니다. 즉 === 직전까지(2 1 이후의 줄바꿈까지)가 1번째 test이고, === 다음 줄부터 2번째 test로 인식되는 것입니다.

    • Verdict(s): test가 올바른지 아닌지를 적는 칸입니다. 올바르면 1 또는 VALID를, 올바르지 않으면 0 또는 INVALID를 입력하면 됩니다. 영단어로 표기할 경우 대소문자 구별은 하지 않으며, test가 여러 개일 때는 각 줄마다 올바른지 아닌지를 해당 양식으로 적으시면 됩니다(즉, 공백으로 구분지을 수 없습니다).
    이런 식으로 만든 다음에 Create를 누르면 Validator 탭에 해당 test가 추가된 것을 볼 수 있습니다. 비록 지금은 Main Solution이 없어서 이를 지금 당장 확인할 수는 없지만, 다 만든 문제(위에 있었던 generator가 쓰이는 문제)에서는 다음과 같이 나옵니다.


    31번과 32번 test를 보면, INVALID한 이유가 상세히 나옵니다. 다만 예상했던 결과와 다르게 나오면 그 열의 배경색깔이 빨간색이 됩니다. 다음과 같이 말입니다.


    43번부터 45번까지는 VALID라 설정했지만 validator가 INVALID라 판별하였기에 빨간색이 되었습니다. 반대로 INVALID라 설정한 것이 VALID일 경우도 저렇게 됩니다. 그런 경우가 있다면, validator를 고쳐야겠지요!

    validator를 만들면서 주의해야 할 점은 특히 input의 범위나 양식은 올바른데 실제로는 올바르지 않은 경우(중복되었다든지, 추가적인 제약조건이 있다든지)도 고려해야 한다는 점입니다. 참고로 testlib.h 폴더 있는 validator 중에서도 bipartite graph validator 등이 있으니 참고하셔도 좋을 듯 합니다.

    그 외에 testlib.h zip 파일에 있는 'validate-using-testset-and-group.cpp' 파일을 보면 testset과 group에 따라 validator가 다르게 작동하는 것의 예시도 나와 있습니다. 이를 사용하면 group 또는 testset에 따른 sub-task와 그것의 제약조건을 고려한 validator를 만들 수 있습니다. sub-task에 주어진 제약조건을 어기는 test가 있으면 곤란하기 때문입니다(ex. N<=15, K<=100이라고 했는데 N=1, K=1000인 경우가 있을 때). 

    PS. 43번 test가 INVALID한 이유가 '0이 [1,80000] 범위에 있지 않아서'가 아니라 '정수가 아니어서'인 이유는, 복붙 과정에서 BOM이라는 문자가 끼어들어갔기 때문입니다. 하지만 직접 타이핑하면서 생길 문자는 아니므로, 특이한 케이스라고 보시면 되겠습니다.


    'Polygon' 카테고리의 다른 글

    11. Checker  (0) 2015.08.17
    10. Solution Files  (0) 2015.08.12
    8. Tests (2 - Generator with Freemarker)  (0) 2015.08.09
    7. Tests (1 - Generator with testlib.h)  (0) 2015.08.02
    6. testlib.h  (0) 2015.07.29
    Posted by Evenharder
    ,

    일러두기 : 제가 정작 generator를 만드는 것 자체를 간단히 넘어간 면이 없지 않아 있지만 우선 이는 문제에 따라서 그 양상이 너무나도 다르고(input이 자연수 한 개뿐인 문제도 있는 반면, 그래프 상태를 입력을 받고 추가적으로 쿼리까지 받는 복잡한 문제들도 존재하기 때문입니다), 거기에 여러 커팅등을 방지하는 corner case를 만드는 것까지 고려하면 이건 문제를 만드는 사람이 해결해나가야 하는 일입니다. Codeforces Round에서도 '이거 정해는 O(n^2*m)인데 왜 O(n^3)이 통과되나요' 등의 일이 자주 발생하기 때문입니다. 그래서 problem setter가 여러 분들의 도움을 받는다는 것을 알 수 있습니다. 이와 별개로, 가끔씩은 test case를 만드는 것 자체가 하나의 문제가 되는 경우도 많습니다(ex. 점 n개가 주어질 때 세 점을 지나는 직선이 존재하는지의 여부). 사실 이쪽이 문제를 만드는 데 많은 시간을 투자하게 되는 부분이기도 합니다.


    아무튼 testlib.h로 test case를 만드는 Generator를 작성하셨다면(참고로 testlib.h에는 bipartite graph generator라든지, tree generator라든지 만들기 힘든 generator도 있습니다), Polygon에 test를 zip 파일로 올리는 수도 가능하겠지만, 가장 좋은 방법은 만든 generator를 Polygon에서도 작동하게 만드는 것 아닐까요?


    5. Files에서 이미 나왔던 내용이지만 이런 종류의 file은 Files - Source Files에 업로드를 할 수 있습니다. 업로드를 합시다.


    업로드를 한 후에 Tests로 이동하여 Script로 이동해 봅시다. Script의 모습은 다음과 같습니다.


    이 창은 특수한 구문을 이용하여 자동으로 test를 추가해 줍니다. Generator의 이름이 randomGen(확장자는 무시하고 씁니다)이라고 하고, 기본적으로 인자를 2개 받는다고 합시다. 그러면 generator를 부를 때는 'randomGen 인자1 인자2' 형태로 쓰시되, '인자1'과 '인자2'에는 실제 프로그램에 전달할 인수의 값을 집어넣으시면 됩니다. randomGen 10 10 처럼 말입니다.


    하지만 이것만 적으면 안 됩니다. 이렇게 만들 test가 몇 번째 test인지 알려주어야 합니다. 알리는 방식은 크게 3가지가 있습니다.

    • randomGen 10 10 > 1 : 말 그대로 1번째 test를 randomGen 10 10을 실행했을 때 만들어지는 값으로 설정한다는 뜻이며, 이 경우 표준 입출력을 사용합니다. 뒤에 붙이는 숫자는 이전에 언급했듯이 1에서 1000까지만 있을 수 있으며(test 최대 개수가 1000개입니다)다만 Manual하게 만든 해당 번호의 test가 이미 있을 경우에는 사용할 수 없습니다. 또한 Script에 같은 test 번호를 가리키는 구문이 있을 수 없습니다.

    • randomGen 10 10 > {1} : 이 경우, 1번째 test를 randomGen 10 10을 실행했을 때 나오는 test로 설정한다는 뜻이나, 파일 입출력의 형식으로 지정됩니다일반적인 숫자 사용법과는 다르게, 범위를 지정할 수 있습니다. {1-3,7}의 경우 1,2,3,7에 randomGen 10 10이 들어가게 됩니다.
      다만 저 경우 각 test가 모두 같게 되는지, 아니면 Polygon에서 자체적으로 이 뒤에 parameter를 더 추가해 seed를 바꾸어 다른 test가 되는지는 잘 
      모르겠습니다.

    • randomGen 10 10 > $ : 이 경우, 해당하는 test는 Script에서 저렇게 test 번호가 명시적으로 나타난 경우를 모두 처리한 다음, 가능한 제일 작은 번호 값을 가지게 됩니다. $는 파일 입출력을 의미하는 {} 안에 넣어 사용할 수 없습니다.
    실제로 파일 입출력과 표준 입출력을 섞어서 쓰는 경우는 거의 없고, 또 testlib.h에서도 표준 입출력을 사용하도록 장려하고 있기 때문에 {}는 무시하면 됩니다만......{}처럼 범위 지정을 못한다는 것이 문제입니다.

    일단 그 문제는 잠시 제쳐두고, 그렇게 생성된 test를 한 번 봅시다. 다음과 같은 script를 시험삼아 한 번 돌려보았습니다.

    randomGen 10 10 1 > 1

    randomGen 10 10 2 > 3

    randomGen 10 10 3 > {4}

    randomGen 10 10 4 > $

    randomGen 10 10 5 > $


    parmeter는 2개만 전달하는 것 아니었나요라고 질문할 수 있습니다. 추가적으로 3번째 인자를 전달하는 것의 의미는 다음과 같습니다.

    • 저런 식으로 표시하지 않으면 test가 중복(coincide)된다고 에러를 띄웁니다.

    • 또, 저렇게 추가적인 인자를 보내면 generator 내의 함수 registerGen에서 seed값을 다르게 가지게 되어, 실제 test data도 다르게 됩니다.
    아무튼 저렇게 script를 만들고, Save Script를 누르면 script에 따른 test case가 생깁니다. 한번 볼까요?


    Manual하게 만든 test와는 달리, Content에 test data가 아닌 script가 들어가 있습니다. 단, 중괄호는 사라져 있습니다. 또, $를 사용한 test들의 위치가 번호에 맞게 들어간 것을 알 수 있습니다(참고로 이 때 밑에 적었던 script 자체의 순서도 이에 따라 변경됩니다). 이 때 Preview Tests를 누르면 실제 test data를 볼 수 있습니다. 물론, 아직은 validator, checker, main solution 등이 없어서 무용지물입니다.


    이 때 edit을 누르면, 7. Tests (1 - Generator with testlib.h)에서 생략하고 넘어간 Script Type의 test를 볼 수 있게 됩니다.



    주목할 점은 Script Line과 옆에 있는 체크박스입니다. Script Line에는 Script 창에 써넣은 구문이 각 test에 대해서 들어가 있습니다. 이를 수정하면 전체적인 script 역시 수정되며, 옆에 있는 체크박스 (Check it if generator produces test as file (doesn't use stdout)) 역시 수정시 그대로 script가 수정됩니다. 해당 체크박스는 파일 입출력을 사용 유무를 나타냅니다.


    그럼 다시 그 문제로 돌아와서......표준 입출력을 사용할 때 저렇게 대량의 test를 어떻게 양산해낼까요? 물론 모든 script를 출력하는 프로그램을 만들어서 (이 정도 코딩은 정말 간단하니까요) Ctrl CV하는 수도 있습니다. 하지만 그것보다 훨씬 더 효율적인 방법이 존재합니다. 바로 Freemarker Template을 이용하는 것입니다.


    저도 Freemarker Template은 잘 모르지만, Polygon Tests에서 Script를 만들 때 필요한 지식은 얼마 되지 않습니다. 다음은 그 내용입니다.

    • 변수 선언 및 간단한 연산은 <#assign i = 2/>, <#assign i = i + j /> 등의 식으로 #assign을 이용하여 할 수 있습니다.

    • for문의 경우, <#list 1..5 as i> ... </#list> 등의 식으로 할 수 있는데, i라는 변수를 1에서 5까지 1씩 증가시키면서 <#list 1..5 as i> 와 </#list> 사이에 있는 구문을 반복해서 실행한다는 의미입니다. #list는 중첩이 가능합니다.

    • 변수를 사용할 때는 ${변수명}으로 사용합니다. i를 사용하고 싶으면 ${i}, num을 사용하고 싶으면 ${num}......

    • Freemarker Template을 사용할 경우 generator 구문 맨 끝에 번호를 나타내는 인자에는 무조건 $가 와야 합니다. 숫자나 중괄호는 올 수 없습니다.

    • Freemarker Template으로는 random을 지원하지 않습니다. 대부분의 경우 Freemarker Template으로 random을 돌릴 이유가 없기도 하지만 말이죠.

    • Freemarker Template은 SPACE나 TAB으로 들여쓰는 것이 의무가 아닙니다.
    그러면 다음과 같은 간단한 구문으로 test를 만들 수 있습니다.

    <#assign i = 1/>
    <#list 1..100 as i>
        randomGen 50000 50000 ${i} > $
    </#list>


    여러 개의 generator를 이용해서 이렇게 만드는 수도 있습니다.


    <#assign num = 1/>

    <#assign i = 1/>

    <#list 1..100 as i>

        <#assign j = 1/>

        <#list 1..7 as j>

            randomGen ${i*i*8} ${i*i*8} ${num} > $

            <#assign num = num + 1/>

        </#list>

        CenterGen ${i*i*8} ${i*i*8} > $

        <#assign num = num + 1/>

        xStackGen ${i*i*8} ${i*i*8} > $

        <#assign num = num + 1/>

        yStackGen ${i*i*8} ${i*i*8} > $

        <#assign num = num + 1/>

    </#list>


    이런 방식으로, test를 만들 수 있습니다. 하지만 test를 만드는 것이 문제를 만드는 것에서 가장 중요한 부분 중 하나라는 것을 명심하시길 바랍니다. 일례로 바로 위의 코드도 CenterGen 등의 다른 generator를 사용한 이유 역시 커팅 등을 사용한 풀이를 TLE 내기 위해서이니까요 (참고로 CenterGen 등의 generator는 random generator가 아님을 밝힙니다). 물론 실제 test set에 test를 저렇게 1000개를 넣고 돌리지는 않을 겁니다. 저건 어디까지나 시험용일 뿐입니다. 실제 test set은 많아야 100개 남짓 되는 test가 들어가고, 이를 어떻게 구성할 지는 여러분의 몫이기 때문입니다.

    'Polygon' 카테고리의 다른 글

    10. Solution Files  (0) 2015.08.12
    9. Validator  (1) 2015.08.11
    7. Tests (1 - Generator with testlib.h)  (0) 2015.08.02
    6. testlib.h  (0) 2015.07.29
    5. Files  (0) 2015.07.28
    Posted by Evenharder
    ,

    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: 새로운 Test set를 만드는 링크이며, 누르면 새로운 이름을 입력하라고 나옵니다. 이 때 이름의 조건은 다음과 같습니다.
      • 이미 존재하는 Test set과 이름이 중복되면 안 되며
      • 알파벳 소문자/대문자, 숫자 그리고 underscore(_ : 0x5F)만 사용할 수 있습니다. 
    탭 밑에 존재하는 3개의 항목은 다음과 같습니다.
    • Testset: 이 test set의 이름을 의미합니다. test set은 한 번 만들어지면 이름을 자체적으로는 바꿀 수 없지만, 후술할 복사 기능을 이용해서 사실상의 이름 변경을 할 수 있습니다.
    • Test count: 이 test set에 있는 test의 개수를 의미합니다. 한 test set에 test는 최대 1000개 들어갈 수 있습니다.
    • Enable groups: test들의 그룹을 활성화하는 버튼입니다. 그룹을 지으면 한 test set에서도 이들을 묶을 수 있습니다. 이러면 나중에 Invocation에서나, Validator에서나 그룹별로 따로 작업을 수행할 수 있습니다. 이는 그룹이 활성화되어 있을 때만 적용됩니다. 다만 그룹을 만든 다음에 비활성화해도 그룹이 사라지지는 않습니다.
    밑에 Tests라고 적혀 있는 곳 오른쪽을 보면 두 개의 하이퍼링크가 존재하는데, 이들의 역할은 다음과 같습니다.
    • Preview Tests: Test set을 한 번 실제로 프로그램으로 돌려보아, 그 결과를 미리 봅니다. 이는 Validator, Solution, Checker 등의 모든 것들이 기본적으로 필요하기에, 지금 당장은 큰 의미가 없는 링크입니다.
    • Add Tests: test를 추가할 수 있는 링크입니다. 한 번 눌러봅시다.


    다음과 같은 창이 뜹니다. 역시 각 항목을 분석하면 다음과 같습니다.
    • Testset: 이 test set의 이름을 의미합니다.
    • Test #: 이 test가 해당 test set에서 몇 번째 test인지를 의미합니다. 같은 번호를 가지는 test가 2개 이상 존재할 수 없기 때문에, 일반적으로는 가능한 test 번호 중 최저의 숫자를 적어놓지만, 번호를 임의로 바꿀 수는 있습니다. 예를 들면 Test #1 대신 Test #23이라든지 말이죠. 그러나 일반적으로는 순차적으로 Test를 만들게 됩니다. 상식적으로 Test가 1부터 시작하지 23부터 시작할까요. 이렇게 숫자들의 순서 및 배열이 이상한 경우 어떻게 되는지는 후술하겠습니다.
    • Type: test를 어떤 방식으로 추가할 것인지를 의미하는 탭이며, 두 가지 선택지가 있습니다. 'Manual'과 'Script'입니다. Manual은 직접 더한다는 뜻이고, Script는 별도의 스크립드를 이용하여 test를 더한다는 뜻인데, 우선 이 글에서는 Manual만 다루고, Script는 다음 포스팅에서 Freemarker를 다룰 때 같이 설명하겠습니다.
    • Data: test 그 자체입니다. 입력해야 할 대상을 입력하시기 바랍니다. 다만 여기에 test를 입력할 때 General Info에서 'Are tests well-formed?'를 활성화시켰다면 3. General Info의 'Well-formed'에서 설명한 규칙이 적용되어야 합니다. 적용되지 않을 경우 강제로 규칙들을 적용하며, ‘Added test has been reformatted because of the problem well-formed policy’ 라는 구문이 create를 누르고 다음 창에 나타납니다. test의 규모가 클 때 어떻게 해야 하는지는 조금 있다 다루겠습니다.
    참고로 이미 존재하는 test는 만들 수 없습니다. 즉, 중복한 test는 만들 수 없습니다. 하지만 후술할 버그가 존재합니다.
    • Use in statements: Statement에서 만들던 pdf 파일을 기억하십니까? Statement에서는 예제를 더하는 기능이 없었습니다. 이를 여기서 시행할 수 있습니다. 누르면 다음과 같이 나타납니다.


    옆에 또 하이퍼링크가 있는 것을 알 수 있습니다. 누르면 다음과 같은 입력창이 추가적으로 나타납니다.



    추가적으로 나타나는 항목들은 다음과 같습니다.

    • Input in statements: 입력하는 값이 너무 많아서 pdf로 옮기기에는 좀 그런 상황일 때는 statement에 사용하지 않는 것이 정상입니다. 하지만 꼭 사용해야 할 경우 저렇게 statement에 어떻게 이 test를 나타낼지를 입력하는 창이 주어집니다. 예를 들면 처음 6줄만 쓰고 말줄임표로 생략한다든지......만일 모든 input data를 사용하고 싶다면 빈칸으로 내버려두시면 됩니다.

    • Output in statements: 생략당한 입력이 있으면 그 입력에 대한 출력도 생략당하겠죠. 마찬가지입니다. 기본적으로 Input in statements가 비어있지 않으면 이 입력창 역시 비어있으면 안 됩니다(역시, 비어있으면 모든 output data를 출력하겠다는 뜻입니다). 다만 input 쪽을 다 출력했는데 output은 일부 생략한다의 방식은 가능합니다.

    • Verify output for statements: 이 기능은 실제 statement에 output이 제대로 문제 형식에 맞추어서 작동하는지를 판별해야 하는데, 뭐 input을 막 조작하든 output을 조작하든 잡아내질 못합니다......결론은 무쓸모.
    참고로 Use in statements를 할 때 test는 다음과 같은 조건을 만족해야 합니다.
    • valid한 test여야 합니다. 즉, Validator와 Checker를 거쳐 나올 수 있는 test여야 합니다.

    • input이 5000바이트를 넘어갈 수 없습니다. output 쪽은 잘 모르겠습니다.

    • 아주 중요한 불문율로, Statement에 나오는 test들은 test set에서 가장 앞에 있어야 합니다.
    Use in statements 밑에는 단 하나의 텍스트 필드만 있습니다.
    • Description: test에 대해 기타 사항을 적는 곳입니다.
    다 완료되었다 생각하시면 밑의 create를 누르시면 됩니다. 그러면 자동으로 다음 test를 만드는 창으로 이동하게 됩니다.

    여기까지는 Manual하게 만드는 방법이며, 다음은 zip 파일을 통해서 제출하는 방법입니다. 창 우측 상단에 'Would you like to add several tests from the archive?'라는 탭이 존재하고, 여기에 input data가 적혀 있는 txt 파일로만 이루어진 zip 파일을 제출할 수 있습니다. 그러나 Polygon이 zip 파일에서 txt 이외의 파일은 읽지 않는다 이런 식은 아닙니다. 확장자에 관계 없이 plain하게 읽어버리는 것입니다. 이와 관계없이, Polygon 서버는 놀랍게도 zip 파일 이름에는 ASCII 코드를 비롯한 유니코드 등을 쓸 수 있습니다. 그리고 이 방식으로 중복된 test를 추가할 수 있습니다만, 무슨 의미가 있습니까. 일종의 버그 내지는 취약점인 것 같습니다. 

    문제들의 input이 클 경우, 즉 byte가 많을 경우 Ctrl+CV 신공이 시간이 상당히 많이 걸리며, 이 경우 저렇게 zip 파일째로 보내는 것을 추천드립니다. 그러나 txt는 한계가 있습니다. 물론 이러한 데이터들도 나름의 프로그램을 짜서 만든 것이겠지만, 그러한 프로그램들이 Polygon에서도 무리 없이 작동하게 하려면 어떻게 해야 할까요?

    기본적으로 test를 만드는 코드는 Generator라고 불립니다. Generator는 문제마다 천지 차이가 납니다. 정수 하나만 input으로 가지는 수학 문제는 매우 간단하며, 복잡한 그래프 문제라면 input의 형식이 상당히 복잡해집니다. 어쨌든 Polygon에서 이를 사용하려면 testlib.h를 통한 Generator를 사용해야 합니다.

    Generator를 만들어 봅시다. 그 전에, 이전에 다운받은 testlib.h zip파일에는 예제들도 들어가 있는데, 우선 몇몇 함수들의 사용법을 알아보고, 그 다음에 이가 적용된 예시를 탐구하겠습니다. 
    • void registerGen(int argc, char* argv[], int randomGeneratorVersion):
      이 프로그램이 generator라고 선언하는 코드로, main 함수 첫 줄에 쓰는 것이 권장됩니다. 이 함수는 next 함수(randomizer 함수)의 seed값을 정해, next 함수가 정상적으로 사용될 수 있게 작용합니다. 다시 한 번 쓰지만, rand()나 srand()는 쓸 수 없습니다. 내부적으로 사용하면 바로 stderr로 해당사항을 출력시킵니다. 이런 방법을 쓰는 이유는 아무래도 rand() 등의 함수들이 컴파일러나 IDE에 따라 그 값이 다르기 때문이라고 생각됩니다.

      • int argc : 네. main 함수의 그 argc 맞습니다. 실제로 main 함수의 그 argc를 넘겨야 합니다.
      • char* argv[] : 네. 역시 그 argv[] 맞습니다. 마찬가지로 main 함수의 그것을 넘겨야 합니다.
      • int randomGeneratorVersion : 1로 고정입니다. 초창기 testlib.h는 0을 사용했지만 이제는 버전이 높아져서 새로운 값인 1로 사용합니다. 0과 1 이외의 값을 넘길 경우 stderr로 해당사항을 알립니다.

      argc와 argv는 내부적으로 바로 seed값을 결정하는데 사용됩니다. argc와 argv가 가지는 자체적인 의미와, argc와 argv의 사용법은 후술하겠습니다.
    random과 관련된 몇몇 함수들의 역할은, type에 따라 달라질 수는 있겠지만, 기본적으로 다음과 같습니다. type은 그냥 T라고 쓰겠습니다. 참고로 밑에 서술할 모든 함수들은 testlib.h의 class random_t에 선언되어 있고 random_t rnd;라는 구문이 testlib.h에 전역으로 존재하기 때문에 rnd.next(); 등의 방식으로 호출하시면 됩니다.

    • double next()
      parameter가 없는 유일한 next입니다. 0 이상 1 미만의 double형 실수를 return합니다.

    • T next(T n)
      0 이상 n 미만의 T형 수를 return합니다. n이 음수거나 값이 너무 크거나 하면 stderr로 해당 사항을 알립니다.

    • T next(T from, T to):
      from 이상 to 이하의 T형 수를 return합니다. to가 from보다 작거나, to나 from의 값이 너무 클 경우 stderr로 해당사항을 알립니다.

    • std::string next(std::string ptm):
      ptm은 Regex에 따른 std::string(내지는 char*)입니다. Regex는 string에서 해당하는 패턴을 찾고자 할 때 사용하는 입력법인데요, ptm을 그런 식으로 입력해야 합니다. 물론 testlib.h가 모든 Regex 스펙을 따르고 있지는 않습니다. 간단한 것만 구현해서 사용하고 있는데요, 어차피 랜덤한 것을 만드는데는 별 상관 없습니다. Regex에서 사용할 수 있는 구문들은 다음과 같습니다.

      • 문자들의 집합은 대괄호 안에 넣어서 사용합니다. 예를 들어 [ac]는 a와 c를, [a-z]는 a부터 z까지, [^a-z]는 a-z를 제외한 모든 문자를, [a-z][A-Z]는 알파벳 대소문자 모두를, [0-9]는 숫자 0부터 9까지를 의미합니다.

      • 문자들의 개수는 대괄호 뒤에 중괄호를 붙여서 사용합니다. 예를 들어 [a-c]{5}는 a부터 c까지의 문자, 즉 a,b,c 셋 중 하나를 무작위로 골라 길이 5의 문자열을 만들고, [a-z]{1,100}의 경우 알파벳 소문자로만 이루어진 1자리부터 100자리의 문자열을 만들어냅니다. 
        이 중괄호는 바로 앞의 집합에만 적용됩니다. [a-z][A-Z]{10}의 경우 알파벳 소문자를 무작위하게 1개, 알파벳 대문자를 무작위하게 10개를 뽑습니다.
        또, %d 등을 통해서 범위를 변수로 조정할 수도 있습니다.


      • black|white 문자열의 경우 black 또는 white입니다.

      • 문자를 선택적으로 넣고 싶을 때는 ?를 사용합니다. 그 예시로 -?[1-9]가 있습니다. 이 경우 앞의 -가 선택적으로 들어갑니다. 그 결과 -9부터 9까지의 0이 아닌 자연수를 랜덤하게 만들게 됩니다.

      • 문자를 반복적으로 선택하고 싶을 경우 * 또는 +를 사용할 수 있습니다. [0-9]*의 경우, 0부터 9까지의 수를 0개 이상으로 연속적으로 선택하며, [0-9]+의 경우 0부터 9까지의 수를 1개 이상으로 연속적으로 선택합니다.

      • 추가적으로 실험을 해보고 싶으시면 이 링크에서 한 번 해보시길 바랍니다. 다만 testlib.h에서 지원하지 않는 기능들도 지원하니 유의하세요.

    • T wnext(T n, int type)
      w는 weight을 의미합니다. 가중치가 어떻게 구현되는지는 다음과 같습니다.

      • type이 양수일 경우 |type+1|개 만큼의 0 이상 n 미만의 T형 수를 뽑은 다음, 그 중 최댓값을 return합니다. 과정은 for문으로 이루어집니다.

      • type이 음수일 경우 |-type+1|개 만큼의 0 이상 n 미만의 T형 수를 뽑은 다음, 그 중 최솟값을 return합니다. 과정은 for문으로 이루어집니다.

      • type이 0일 경우 T형에 해당하는 next 함수와 동일한 역할을 합니다.

    • void shuffle(_RandomAccessIter __first, _RandomAccessIter __last)
      random access가 가능한 iterator를 돌려가면서 first와 last 사이의 원소들을 무작위하게 섞습니다. 주의할 점은 algorithm 헤더의 std::random_shuffle을 사용하면 안 된다는 점입니다.

    • typename Container::value_type any(const Container& c)
      container c에 있는 원소 중 하나를 랜덤하게 선택하여 리턴합니다.
    이 외에도 wany, from/to/type으로 이루어진 wnext도 있으나 설명은 생략하겠습니다.

    testlib.h의 예제를 일부 살펴보겠습니다. 매우 간단한 igen.cpp와 sgen.cpp를 살펴보면 다음과 같습니다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #include "testlib.h"
    #include <iostream>
     
    using namespace std;
     
    int main(int argc, char* argv[])
    {
        registerGen(argc, argv, 1);
     
        cout << rnd.next(11000000<< endl;
     
        return 0;
    }
    cs


    1부터 100000 중 하나의 값을 무작위하게 출력하는 Generator입니다.


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #include "testlib.h"
    #include <iostream>
     
    using namespace std;
     
    int main(int argc, char* argv[])cc
    {
        registerGen(argc, argv, 1);
     
        cout << rnd.next("[a-zA-Z0-9]{1,1000}"<< endl;
     
        return 0;
    }
    cs

    알파벳 소문자, 대문자, 숫자를 포함하는 길이 1에서 1000까지의 문자열을 출력하는 프로그램입니다.


    하지만 이러면 또 의문이 생깁니다. '저 프로그램들의 길이 범위는 정해져 있는 것이 아닌가? 우리가 조절할 수 있게 할 수는 없는건가?' 결론은 '조절할 수 있다'입니다. 이를 하기 위해서는 main 함수의 인자인 argc와 argv의 의미를 파악해야 합니다.


    흔히 int main()으로 생략되기도 하는 main 함수. main 함수의 형태는 비표준 확장을 제외하면 다음 2가지 중 하나를 지녀야 한다고 명시되어 있습니다.

    • int main()

    • int main(int argc, char* argv[])

    이 중 argc와 argv의 의미는 다음과 같습니다.

    • int argc: argv에 전달되는 인자의 개수입니다. argc는 0 이상의 값입니다.

    • char* argv[]: 실행 환경 자체에서 주어진 인자들입니다. argc가 1 이상의 값일 경우 argv[0]은 프로그램 이름을 나타내는 char*이며, argv[1] 부터 argv[argc-1]까지는 프로그램에 전달되는 인자(parameter)입니다. argv[argc]는 null pointer를 가리킵니다.

    즉, argv는 실행 환경을 매개하는 인자들을 모아놓은 것입니다. 그 인자들은 프로그램을 실행하면서 우리가 설정할 수 있는 것입니다. 간단한 예시를 들자면 다음과 같습니다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #include "testlib.h"
    #include <iostream>
     
    int main(int argc, char* argv[])
    {
        registerGen(argc, argv, 1);
     
        int query=atoi(argv[1]);
        int max_int=atoi(argv[2]);
     
        cout << query << endl;
        
        for(int i=0;i<query;i++)
        {
            int n=rnd.next(0, max_int);
            int r=rnd.next(0, n);
            std::cout << n << " " << r << endl;    
        }
        return 0;
    }
    cs

    query와 max_int를 프로그램 자체의 인자로 받아, query를 첫째 줄에 출력한 다음, max_int 개 만큼의 0 <= r <= n을 만족하는 n, r을 각 줄에 공백으로 구분지어 출력하는 generator입니다.


    이런 식으로, 우리는 프로그램이 원하는 범위만큼, 원하는 개수만큼 test를 출력하게 만들 수 있습니다. 프로그램의 인자 자체를 집어넣으려면 Windows의 경우, cmd 창 등의 shell을 이용해서 프로그램 이름 옆에 공백으로 인자를 입력하면 됩니다.


    주제가 약간 옆으로 샜지만, 밑에 보면 Script라고 칸이 있으며 그 옆에 약간의 설명이 나와 있습니다. 이에 관해서는 다음 글에서 포스팅하겠습니다.


    -UPD 2015.08.08 원래는 testlib.h의 자세한 함수 기능 등을 서술하려 했는데, 굳이 그럴 필요가 없어 보이고, 또 testlib.h 내에 자체적으로 주석 등으로 설명이 잘 되어 있기 때문에 서술을 생략하겠습니다.


    -UPD2 argc와 argv 설명을 추가했습니다. 원래 다음 포스팅에 실으려 했슨데 생각해보니 여기에 넣지 않으면 Generator를 만들 수가 없게 되어서......


    -UPD3 Group 관련 설명을 추가했습니다.

    'Polygon' 카테고리의 다른 글

    9. Validator  (1) 2015.08.11
    8. Tests (2 - Generator with Freemarker)  (0) 2015.08.09
    6. testlib.h  (0) 2015.07.29
    5. Files  (0) 2015.07.28
    4. Statement  (0) 2015.07.28
    Posted by Evenharder
    ,

    6. testlib.h

    Polygon 2015. 7. 29. 10:30

    testlib.h는 5. Files에서도 잠깐 설명했지만, Codeforces와 Polygon의 설립자 Mike Mirzayanov가 만든, 문제를 검증하는 프로그램을 짤 때 사용하는 C++ 헤더 파일입니다. testlib.h는 test를 만들거나(Generator), test가 유효한지 판별하거나(Validator), 출제자의 답과 문제를 부는 사람의 답이 일치하는지 판별하는 등(Checker)에 사용됩니다. 실제로 testlib.h를 이용되는 경우가 많다고 이 링크에 적혀 있습니다.


    testlib.h의 장점은 기본적으로 안정적으로 정수가 사용되는 문제이든, 문자열 문제이든, 실수 문제이든 Generator, Validator, Checker 등을 만들 수 있으며, 실시간으로 verdict를 알 수 있다는 데 있으며, 엔드 유저인 일반 사용자들이 더 쉽게 이러한 것들을 체크할 수 있다는 것에 의미가 있습니다.


    testlib.h를 다운로드하시려면 이 GitHub 저장소에서 옆에 보이는 Download Zip을 누르시면 됩니다. 이 경우 몇 개의 코드 샘플과 같이 다운로드되게 됩니다. testlib.h는 Polygon 시스템에서만 사용할 수 있는 게 아닌, 일반적인 헤더 파일입니다. 


    testlib.h를 사용하면서 필요한 함수들은 각 경우에 따라서 설명하는 형식으로 진행하겠습니다. 단 한 가지 팁을 드리자면, testlib.h는 자체적인 랜덤 함수를 쓰기 때문에 srand()나 rand() 함수의 사용이 금지되어 있으며, 이가 포함된 코드를 업로드할 수 없습니다. 그리고 또 한가지 주의점이 있습니다. testlib.h는 일부 함수들을 오버로딩하기 때문에, 항상 가장 먼저 include해야 합니다.


    이후 만들어야 하는 것들이 코드만 따지면 Generator, Validator, Solution, Checker 등이 있는데 실제로 작동하려면 이 4개가 기본적으로 다 있어야 합니다. 일단은 Generator부터 강의하도록 하겠습니다. tests쪽이 testlib.h 외에도 알아야 하는게 하나 더 있어서 말입니다.


    'Polygon' 카테고리의 다른 글

    8. Tests (2 - Generator with Freemarker)  (0) 2015.08.09
    7. Tests (1 - Generator with testlib.h)  (0) 2015.08.02
    5. Files  (0) 2015.07.28
    4. Statement  (0) 2015.07.28
    3. General Info  (0) 2015.07.22
    Posted by Evenharder
    ,

    5. Files

    Polygon 2015. 7. 28. 10:32

    이번에는 기능적인 역할을 수행하는 곳은 Files입니다. 말 그대로 파일들을 저장하는 곳입니다. 그러나 Polygon의 Files는 파일들의 용도에 따라 분류가 되어 있기 때문에, 그리고 여기에 올리는 게 아니라 다른 데 올리는 파일들도 있기 때문에(ex. Statement에 첨부되는 사진 파일들), 그런 것들을 설명하겠습니다.


    Files의 모습은 다음과 같습니다.


    크게 3개의 탭으로 나누어져 있는 것이 보입니다. 각각을 설명하자면 다음과 같습니다.





    • Resource Files: Polygon 시스템에서 자동으로 추가해주는 기본적인 파일들이 있으며, 전체적인 토대를 이루는 파일들을 저장하는 곳입니다. 아무것도 하지 않아도 생기는 4개의 파일들의 역할은 다음과 같습니다.

      • olymp.sty: TeX가 만드는 pdf 파일의 형식을 지정합니다. 엄밀히 말하자면 LaTeX 파일의 형식을 지정하는 것이죠.

      • problem.tex: Freemarker Template으로 만들어졌으며, 문제의 statement를 담는 파일이 되어 pdf나 html 변환에 이용됩니다.

      • statements.ftl: 역시 Freemarker Template으로 만들어졌으며, LaTeX이 pdf으로 변환될 때 관여하는 것 같습니다.

      • testlib.h: Codeforces와 Polygon의 설립자 Mike Mirzayanov가 만든, 문제를 검증하는 프로그램을 짤 때 사용하는 헤더 파일이며, Polygon의 가장 큰 장점으로 볼 수 있을 정도로 대단히 중요합니다. 얼마나 중요한 지는 다음 포스팅에 나올 것 같습니다. 참고로 Auto-update를 켜 놓으면 자동으로 testlib.h가 업데이트 될 때마다 이 쪽도 업데이트가 됩니다.

    • Source Files: 나중에 만들 Checker, Validator 등의 코드 파일을 올리는 곳입니다. 다만 Solution 파일은 여기에 올려봤자 아무런 영향을 끼치지 않고, 별도의 저장공간이 따로 있습니다. Check sources for compilability는 실제로 컴파일이 정상적으로 되는지 체크하는 버튼입니다.

    • Attachment Files: 그 이외의 파일들, 즉 나중에 Package로 문제를 만드는데 추가적으로 넣고 싶은 파일들을 여기에 첨부하면 됩니다. 전형적인 첨부 파일의 예시랄까요.


    이용약관에도 명시되어 있는 사실이지만, 이런 장소를 문제와 관련 없는 파일들의 개인 저장소로 사용하면 안 됩니다.



    'Polygon' 카테고리의 다른 글

    7. Tests (1 - Generator with testlib.h)  (0) 2015.08.02
    6. testlib.h  (0) 2015.07.29
    4. Statement  (0) 2015.07.28
    3. General Info  (0) 2015.07.22
    2. Make a problem & Commit Changes  (0) 2015.07.22
    Posted by Evenharder
    ,

    4. Statement

    Polygon 2015. 7. 28. 09:47

    Statement는 문제의 내용를 기술해놓는 곳입니다. 문제의 기술은 이미 General Info에서 하지 않았느냐고 말할 수 있겠지만, Statement에서는 TeX을 통해서 기술해야 한다는 점이 가장 큰 차이점입니다.


    일단 TeX에 관한 설명은 뒤로 미루고 본문으로 들어가겠습니다. Statement 탭에 들어가면, 아직 하나도 만든 것이 없기에 다음과 같은 화면이 나타납니다.



    언어를 하나 선택해야 하는데요, 기본적으로는 English와 Russian이 권장됩니다(언어 선택 탭을 누를 시 그 둘이 맨 위에 있는데는 이유가 있습니다. 기본적으로 Codeforces Round에서 그 두 언어만 공식적으로 지원하기 때문입니다). 개인적으로는 유니코드 충돌 문제 같은 것을 방지하기 위해 English를 우선시하며, 개발자분께서 아시아 언어는 자동으로 TeX으로 바꾸는 것이 어렵다는 을 올리신 바 있기 때문에 Korean은 접어두시길 바랍니다.


    그럼 English를 선택하고 들어가겠습니다. 그러면 다음과 같은 화면이 나타납니다.




    우선 위의 파란 탭부터 설명하겠습니다.


    • English: English statement로 이동하겠다는 하이퍼링크입니다. 다른 언어의 statement를 추가하면 그것도 역시 추가됩니다.

    • Review: 문제를 Codeforces 형식에 맞추어 html로 표시함과 동시에, 나중에 만들 Validator 코드 본문을 표시합니다.

    • Delete Current: 현재 statement를 삭제합니다.

    • Create New: 새로운 statement를 만듭니다. 참고로 statement는 언어별로 중복이 불가합니다.


    그 밑의 3개의 하이퍼링크는 다음과 같습니다.


    • In LaTeX: 정해진 양식에 따라서 적어놓은 Statement와 General Info에서 적어놓은 입출력 방식, Time/Memory Limit이 포함된 LaTeX 파일 그 자체을 평문으로 보여줍니다.

    • In HTML: 역시 정해진 양식에 따라서 변환하나, 차이점은 html로 보여준다는 것입니다. 때문에 LaTeX에서 보이던 것과는 달리 보일 수 있습니다(특히 줄바꿈).

    • In PDF: 사실상 이 기능이 제일 중요합니다. 위에 있는 LaTeX 파일을 기본으로 하여 pdf 파일을 만들어냅니다. Statement는 결국 이 pdf 파일을 만드는 것이 목표입니다.


    본문으로 들어가서 각 항목을 설명하자면 다음과 같습니다.


    • Encoding: 문제의 인코딩 설정입니다. 기본으로 설정되어 있는 UTF-8을 사용하시길 권장합니다.

    • Name: 문제의 제목입니다. Polygon에 저장되어 있는 문제 이름과는 달리 풀 네임으로 적으시면 되겠습니다.

    • Legend: 보통 전설이라는 뜻을 가지고 있지만, 여기서는 전문이라는 뜻을 가지고 있습니다. 문제의 기본적인 이야기를 적는 칸입니다. 다만 중요한 점은 이해가 잘 되게 써야 한다는 것이겠죠. 안 그러면 욕을 먹으니......

    • Input format: 입력 양식을 입력하는 곳입니다(ex. 첫째 줄에 정수 n이 입력됩니다. 그 이후 n개의 줄에 걸쳐 어쩌구 저쩌구)

    • Output format: 출력 양식을 입력하는 곳입니다.

    • Note: 추가 사항, 예를 들면 입출력 예제(이는 나중에 Tests에서 자동으로 추가됩니다)의 작동 방식을 설명한다든지를 적어놓으면 됩니다. 얼마나 구체적으로 적을지는 본인의 재량입니다.

    • Tutorial: Codeforces의 Editorial입니다. 문제의 풀이를 적으시면 되겠습니다. 풀이의 양 역시 본인의 재량입니다. 풀이를 자세히 설명할 것인지, 아이디어만 설명하며 끝낼 것인지......본인의 선택입니다. 고로 Tutorial 칸에 무엇이든, 입력하고 저장하면 3개의 하이퍼링크가 있던 곳 옆에 추가적으로 2개의 하이퍼링크(Tutorial in HTML, Tutorial in PDF)가 생깁니다. 역할은 말 그대로입니다.


    여기까지 입력한 것들은 창 맨 밑에 있는 Save 버튼을 통해서 저장이 가능합니다. 


    밑에 있는 Statement Resource Files는 옆의 Add File을 통해, 혹시 Statement에 그림 등이 들어가야 할 때 추가적인 파일을 올리는 장소입니다. 다만 여기에 올리는 파일은 다음과 같은 문자만 허용됩니다.

    • 알파벳 소문자 및 대문자

    • 숫자

    • .(Period, 0x2E)

    • _(Underscore, 0x5F)

    • -(Hyphen, 0x2D)


    이 이외의 문자는 Illegal filename specified 라고 표기되며, 업로드가 거부됩니다. 이는 다른 파일을 업로드할 때도 마찬가지로 적용됩니다.


    이제 TeX로 약간의 편집을 할 차례입니다. TeX은 일종의 조판 프로그램으로, 여려 명령어들을 이용해서 구조적인 글을 써 나가는 프로그램입니다. 주로 논문 등의 형식을 요구하는 것에 쓰입니다. TeX과 관련된 기초적인 지식은 구글링을 하시기 바랍니다. 사실 TeX은 그 명령어가 너무 많아, 궁금한 게 있으면 일단 구글링해야 합니다. 아무튼 본 블로그는 TeX에 관한 포스팅을 하는 곳이 아니므로, 간략한 팁 및 사용방법만 몇 가지 이야기하겠습니다.

    • 우선 TeX에서는 줄바꿈이 Enter를 친다 해서 바로 적용되지 않습니다. 줄바꿈 문자는 \\입니다. 그 이외에도 빈 줄 하나를 놓으면 줄바꿈이 이루어지지만, 빈 줄을 여러개 놓아도 줄바꿈은 한 번밖에 이루어지지 않습니다.

    • TeX에서는 일반적인 편집 모드(textmode)와 수식 편집 모드(mathmode)가 따로 있습니다. 일반적인 모드는 plain text를 입력할 때 사용하며, 수식 편집 모드는 흔히 이탤릭체로 표시되는 수식을 표현할 때 사용합니다.

    • 일부 특수 기호는 \를 앞에 붙여야 사용가능한 경우가 있습니다. 다만 일부 특수 기호는 수식 편집 모드에서만 사용 가능한 경우가 있습니다.
      (ex. _를 출력하려면 \_를 입력해야 합니다)

    • 그러한 특수 기호들은 이 사이트에서 직접 그려보면서 확인할 수 있습니다.

    • 수식 편집 모드에 접근하는 방법은 간단히 2가지가 있습니다. 첫번째는 $ 수식 내용 $의 형태입니다. 이 경우 $ 안에 있는 내용이 수식 편집 모드가 적용됩니다. 또다른 방법으로는 $$ 수식 내용 $$의 형태가 있습니다. 이 경우 $$ 안에 있는 내용이 가운데 정렬이 되며, 자동으로 줄바꿈을 해줍니다.

    • 수식 편집 모드에서 사용할 수 있는 주요 구문 중의 하나가 첨자입니다. 윗 첨자는 ^, 아랫첨자는 _로 연결합니다.

    • 그림 첨부는 다음과 같은 구문을 넣으면 해결할 수 있습니다. 그림이 'picture.jpg'라는 이름을 가지고 있을 때(jpg, bmp, png 등의 확장자들이 적용됩니다)


    • \begin{figure}[h]

      \begin{center}

      \includegraphics[scale=0.5,bb=0 0 501 75]{statement_create.jpg}

      \end{center}

      \end{figure}

      이를 설명하자면 다음과 같습니다.

      • \begin{figure}: 이것이 float한 figure라는 것을 의미합니다. float을 간단히 설명하자면 '페이지에 걸쳐서 나타나지 않는 것'입니다.

      • \begin{center}: \end{center}가 있는 곳까지 가운데 정렬을 하라는 의미입니다. \includegraphics: 여러 옵션을 사용하여 그림 등을 나타내는 함수입니다. [] 안에는 많은 것들이 들어갈 수 있지만, 여기서는 2개만 사용하도록 하겠습니다.

        • scale: 그림의 배율입니다. 0.5라는 것은 가로와 세로를 0.5배로 하라는 것입니다.

        • bb: BoundingBox라는 개념인데, 이 옵션은 Polygon 특유의 문제로 반드시 포함해야 합니다. 안 그러면 에러가 납니다. 일반적으로는 bb=0 0 'scale이 적용된 그림의 가로 크기' 'scale이 적용된 그림의 세로 크기'를 적습니다.

      • {}: 안에는 당연히 그림의 이름을 그대로 적어넣으면 됩니다. 기본적으로 ASCII 코드 인식 가능하지만 일단 Polygon에 파일을 올리려면 그렇게 해야 하기에 별 문제는 되지 않습니다.

    • TeX을 알고 계시는 분이라면, 각 항목을 편집할 때 \usepackage 같은 정의 헤더는 사용할 필요가 없으며, 사용해서도 안 된다는 것을 알려드립니다. 그리고 은근 많은 구문들이 사용 불가능하다는 것 역시 숙지하시길 바랍니다(ex. \begin{enumerate}, \textbf}.

    그 외에 다양한 것들은 직접 구글링하시길 바랍니다. TeX도 은근 복잡하기 때문에......예시를 들자면 다음과 같습니다.

    The first line contains a single integer $q\ (1 \leq q \leq 80,000)$, the number of the binomial coefficients Kevin wants to calculate with the mentioned function, C(int n, int r).\\
    The following $q$ lines contain two integers $n\ (0 \leq n \leq 80,000)$ and $r\ (0 \leq r \leq n)$, separated with a single blank. The values $n$ and $r$ are the input values of the function, C(int n, int r).


    이를 Statement의 Input format에 넣으면 다음과 같이 나타납니다.



    \leq 등이 부등호로 대체된 것을 알 수 있습니다. 아무튼 이런 식으로 Statement를 기술하면 됩니다.





    'Polygon' 카테고리의 다른 글

    6. testlib.h  (0) 2015.07.29
    5. Files  (0) 2015.07.28
    3. General Info  (0) 2015.07.22
    2. Make a problem & Commit Changes  (0) 2015.07.22
    1. Register  (0) 2015.07.22
    Posted by Evenharder
    ,