13. Invocation

Polygon 2015.09.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' 카테고리의 다른 글

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

12. Stress

Polygon 2015.08.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
12. Stress  (0) 2015.08.18
11. Checker  (0) 2015.08.17
10. Solution Files  (0) 2015.08.12
9. Validator  (0) 2015.08.11
8. Tests (2 - Generator with Freemarker)  (0) 2015.08.09
Posted by Evenharder
TAG polygon

11. Checker

Polygon 2015.08.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
11. Checker  (0) 2015.08.17
10. Solution Files  (0) 2015.08.12
9. Validator  (0) 2015.08.11
8. Tests (2 - Generator with Freemarker)  (0) 2015.08.09
Posted by Evenharder
TAG polygon