새로운 기능

서브태스크 문제는 2018 KAIST RUN Spring Contest 덕분에 생긴 기능입니다. 이 대회와 함께 생긴 기능은 유의 사항을 보여주는 기능과 대회 후원을 보여주는 기능이 있습니다. 또, 문제에서 제한 탭을 보여주는 기능도 생겼습니다.

서브태스크

서브태스크(Subtask)는 기존의 채점 기준과는 조금 다른 기준을 사용합니다.

ACM-ICPC 스타일의 문제는 입력과 출력 데이터를 모두 준비한 다음, 모든 데이터에 대해서 올바른 답을 출력해야 그 문제를 맞았다고 합니다.

서브태스크 문제는 ACM-ICPC 스타일의 채점 방식과 매우 유사하지만, 데이터를 특정 기준을 가지고 그룹을 지어 놓고 채점합니다. 여기서 그룹을 서브태스크라고 합니다.

보통 서브태스크의 구분은 문제의 N제한을 기준으로 하는 경우가 많습니다. 각각의 서브태스크는 배점을 가지고 있고, 유저는 한 서브태스크에 포함된 데이터를 모두 맞아야 그 서브태스크에 포함된 배점을 획득하게 됩니다.

예를 들어, 어떤 서브태스크 문제의 배점이 다음과 같은 경우를 살펴봅시다.

• 서브태스크 1: 20점
• 서브태스크 2: 30점
• 서브태스크 3: 50점

위와 같은 경우에 어떤 사람이 서브태스크 1에 포함된 데이터에 대해서 모두 올바른 답을 출력하면 20점 획득하게 됩니다. 서브태스크 2에 포함된 데이터도 모두 올바른 답을 출력한다면 30점을 획득하게 됩니다. 하지만, 서브태스크 3에 포함된 데이터에서 하나라도 올바른 답을 출력하지 못한다면, 50점은 획득할 수 없는 점수가 됩니다. 이와 같은 경우에 유저는 서브태스크 1과 2를 맞았기 때문에, 50점을 가져가게 됩니다.

서브태스크 문제는 각각의 서브태스크가 하나의 독립된 ACM-ICPC 스타일 문제와 같은 역할을 하게 됩니다.

BOJ는 주로 ACM-ICPC 스타일의 문제를 채점하는 사이트입니다. 따라서, 서브태스크 문제를 구현하기 위해서 최대한 기존 시스템을 이용하기로 결정했습니다.

두 가지 서브태스크 방식

서브태스크 방식의 문제를 BOJ에 추가할 때 가장 중점으로 생각했던 것은 기존 BOJ 채점 프로그램의 소스를 최대한 활용하자는 것 이었습니다. 따라서, 다음의 두 가지 방식을 생각하게 되었습니다.

1. 각각의 서브태스크를 BOJ의 문제로 등록
2. BOJ의 새로운 문제 유형으로 서브태스크 문제를 추가

1번 방식을 자세하게 설명하면 다음과 같습니다.

어떤 문제의 서브태스크를 모두 BOJ의 독립된 문제로 등록합니다. 그리고, 이 각각의 독립된 문제에는 제출을 할 수 없게 설정합니다. 제출을 할 수 있는 새로운 문제를 만들고, 여기에만 제출을 할 수 있게 합니다.

이렇게 되면, 총 3개의 서브태스크를 가지는 문제는 BOJ에는 총 4개가 등록되게 됩니다. (제출용, 서브태스크 1, 2, 3)

각각의 서브태스크는 일반적인 ACM-ICPC 스타일 문제와 채점하는 방식이 같기 때문에, 채점 프로그램의 채점 방식은 그대로 이용하면 됩니다. 결과를 합치는 부분은 새로 작성해야 하지만, 채점을 건드리지 않으니 수정이 그렇게 많지 않을 것 같습니다.

유저의 입장에서는 이 방식이 좋을 수도 있고, 나쁠 수도 있습니다. 서브태스크 문제 1개를 제출하면, 실제로는 서브태스크 개수만큼 제출을 한 것으로 처리가 됩니다. 서브태스크 문제 1개의 모든 서브태스크를 통과했다면, 문제 1개를 푼 것이 아니고 서브태스크 개수만큼 문제를 푼 것으로 통계가 올라가게 됩니다.

이 방식은 제출수와 맞은 문제의 개수를 부풀리기는 매우 좋지만, 공정한 방식은 아니라 생각되어 결국 2번 방식을 사용하게 되었습니다.

새로운 문제 유형: 서브태스크

웹은 섹션만 추가하면 되는 것이기 때문에, 큰 문제가 되지 않습니다.

중요한 것은 채점 방식입니다.

위에서부터 반복해서 언급했지만, 서브태스크 문제의 각 서브태스크 문제는 ACM-ICPC 스타일 문제입니다. 이미 ACM-ICPC 스타일의 문제는 채점할 수 있기 때문에, 이를 어떻게 잘 이용하면 될 것 같았습니다.

BOJ의 채점 방식은 데이터 디렉토리에 있는 모든 .in을 순회하면서 채점하는 방식입니다. 이를 이용하기 위해 서브태스크 방식은 데이터 디렉토리에 서브태스크 별로 디렉토리를 만들고, 각 디렉토리를 데이터 디렉토리로 설정하고 채점하는 방식을 사용하기로 결정했습니다.

예를 들어, BOJ의 1000번 데이터가 ~/boj/data/1000에 들어있다고 하면, 기존의 방식은 ~/boj/data/1000/*.in을 모두 찾아서 입력해보는 방식입니다. 데이터의 디렉토리만 변경하면, 서브태스크의 채점이 될 것 같습니다. 서브태스크 1은 ~/boj/data/1000/subtask1, 서브태스크 2는 ~/boj/data/1000/subtask2에 데이터를 넣고, 데이터 디렉토리를 변경해서 채점하게 했습니다.

채점 큐에는 채점번호와 서브태스크 번호를 같이 넣는다면, 기존 문제의 채점과 다를바 없이 동작하게 됩니다.

이제 다음 문제는 채점 결과를 모으는 것 입니다. 각각을 내부적으로는 독립적인 문제로 간주하고 채점하기 때문에, 어떤 서브태스크의 채점이 먼저 끝날지 알 수가 없습니다.

BOJ의 채점 프로그램은 크게 보면 채점 준비 -> 채점 -> 채점 마무리와 같이 나누어져 있습니다.

채점 준비는 채점을 하기 전에 필요한 값을 DB에서 모두 가져오는 과정에 속합니다.

채점은 컴파일과 데이터를 입력해보는 과정을 의미합니다.

채점 마무리는 모든 채점이 완료된 이후에 웹에 보여주기 위한 여러가지 값들을 계산하는 과정입니다. 어떤 문제를 맞추었는지, 총 몇 개의 문제를 맞추었는지, 제출한 소스 중 가장 좋은 결과를 갖는 채점 번호는 무엇인지, 가장 짧은 채점 번호는 무엇인지 등이 여기에 포함됩니다.

서브태스크는 모든 서브태스크 문제가 채점되기 전에는 채점 마무리가 불필요하기 때문에, DB에 새로운 테이블을 만들고, 각각의 서브태스크가 얼마나 채점되었는지 기록하기로 했습니다. 이 테이블은 실시간 채점 현황을 보여주기 위해서도 필요한 테이블입니다. 서브태스크가 어떤 순서로 어떻게 채점이 될지 알 수가 없기 때문에, 채점 진행을 보여주기 위해선 한 곳에 정보를 취합하는 과정이 필요합니다.

문제를 기다리는 중 -> 채점중으로 변경하는 것도 1번만 필요한 작업입니다. 아직 채점을 시작한 서브태스크가 없는 경우에만 채점중으로 변경하기로 했습니다.

채점 프로그램에 서브태스크의 데이터 디렉토리를 변경하는 곳과, 각 서브태스크의 결과를 기록하는 곳, 채점 진행 상황을 계산 하는 곳, 서브태스크 결과를 모두 모으는 곳 정도만 코딩해서 서브태스크를 구현해냈습니다.

ACM-ICPC 스타일 문제의 채점 부분은 전혀 손을 대지 않고 구현할 수 있어 매우 큰 의미가 있었습니다.

서브태스크 그 이후

이제 남은 문제 유형은 인터렉티브입니다.

과연 언제쯤 이 유형을 구현할 수 있을까요?