안녕하세요.

지난 2018년 5월 23일 서브태스크 문제가 생겼습니다.

2018년 6월 10일 올라온 글에 KOI 문제의 서브태스크 변환에 대한 글이 있는데, 저 당시 슬랙에서 기존 문제의 변환 계획은 없다고 답변했었습니다. 조금 생각해보니 최대한 문제의 원본을 따라가는게 좋다는 생각을해 시간이 나면 바꿀 계획이 있다고 답변도 했습니다.

2019년 6월 28일에 올라온 글에는 각 서브태스크 별 채점 결과를 보는 법을 모르는 사람이 많다는 의견이 있었는데, 현재는 링크임을 표시하기 위해 밑 줄을 추가해서 보여주고 있습니다.

2020년 9월 12일에는 일부 서브태스크의 경우 표로 조건을 볼 수 있는 업데이트가 있었습니다.

2021년 5월-6월에는 기존에 업로드되어 있는 문제 중 원본이 서브태스크인 문제를 서브태스크로 변환했습니다. (KOI, BOI, COCI, COI, JOISC, IOI, CEOI, JOI, 등등)

2021년 9월 24일에는 서브태스크 별로 시간/메모리 제한을 정할 수 있는 업데이트가 있었고, 2022년 1월 7일에는 서브태스크 변환도 재채점 기록을 남기기로 했고, 1월 8일에는 서브태스크 + 점수 문제와 관련된 업데이트가 있었습니다.

오늘 업데이트는

• 서브태스크 3,4 데이터가 부족합니다.
• 서브태스크 위계에 문제가 있습니다.

와 관련된 업데이트 입니다.

서브태스크의 채점은 각 제출을 서브태스크 별로 나눠서 채점한 다음 모든 서브태스크의 채점이 끝나면 각 서브태스크 별 결과를 종합해서 최종 결과를 만들고 있습니다. 서브태스크 문제의 경우에는 한 서브태스크가 다른 서브태스크를 포함하는 경우가 자주 발생합니다. 예를 들어, 15740번: A+B - 9의 경우 서브태스크 3은 1을, 서브태스크 4는 1, 2, 3을, 서브태스크 8은 1, 2, 3, 4, 5, 6, 7의 조건을 포함합니다.

채점 프로그램의 수정을 최소로 하면서 서브태스크 문제의 채점을 구현하기 위해서 각 subtask1에는 서브태스크 1의 데이터, subtask2에는 서브태스크 2의 데이터, ..., subtask8에는 서브태스크 8의 데이터를 담게 구현했습니다. 이 방법은 채점의 구현이 쉽다는 장점이 있지만, 채점 서버의 용량이 낭비되는 단점이 있습니다.

글을 별도로 남기지는 않았지만, 2021년 5월-6월에 기존 문제의 서브태스크를 변환하는 작업을 하면서 채점 서버가 사용하는 용량의 낭비를 없애는 업데이트를 했습니다. all/이라는 폴더에 모든 채점 데이터를 넣어두고, 각 서브태스크별 폴더에는 심볼릭 링크를 넣어 용량 낭비를 줄였습니다. 이 작업은 모든 서브태스크 문제에서 하지 않았고, 용량을 많이 차지하는 일부 서브태스크 문제에서 각 데이터 파일의 내용 또는 파일 이름을 비교한 다음에 같은 파일인 경우에만 심볼릭 링크를 만들었습니다.

용량의 낭비를 줄였으니 이제 채점 시간을 줄여볼 차례입니다.

채점 시간을 줄이기 위해서 각 데이터 파일을 최소 횟수로 채점하게 만들었습니다. 서브태스크 i가 서브태스크 j의 조건을 포함하면 j -> i로 표현하겠습니다. j -> i의 경우 서브태스크 i의 채점 데이터에는 서브태스크 j의 채점 데이터가 들어있을 필요가 없습니다.

예를 들어 서브태스크가 총 4개 있고, 서브태스크 1의 조건을 만족하는 데이터가 10개, 서브태스크 2는 20개, 서브태스크 3은 30개, 서브태스크 4는 40개라고 한다면, 기존에는 프로그램의 실행을 총 10+20+30+40 = 100번해야 합니다. 하지만, 서브태스크 2의 조건을 만족하는 데이터 20개 중에서 10개는 서브태스크 1의 조건을 만족하기 때문에, 업데이트 된 방식에서는 서브태스크 2의 채점을 위해 실행을 10번만 하고, 서브태스크 1의 결과를 참고하면 됩니다. 따라서, 바뀐 방식에서는 프로그램의 실행이 총 40번만 있게됩니다.

이 방식을 이용하면 서브태스크의 채점에 필요한 시간이 매우 줄어들게 됩니다.

앞으로 올리는 일부 서브태스크 문제, 그리고 채점이 오래 걸렸던 기존 일부 문제는 이 방식으로 변환해 채점하는데 필요한 시간을 조금 줄여보려고 합니다.

원래는 서브태스크의 포함 관계가 DAG라는 점을 이용해서 위상 정렬 하면서 채점을 해볼까하는 생각도 했는데, 최종 결과는 모든 서브태스크의 채점이 종료된 후에 결정되고, 채점 서버가 여러개라 구현하기가 조금 복잡해 일단 이 방식은 구현하지 않았습니다. 나중에 시간이 생기면 한 번 도전해보겠습니다.

이제 남은 서브태스크 문제 채점의 업데이트는 서브태스크 재채점입니다.

재채점 규칙을 보면 ICPC 스타일 문제에서 데이터 추가 재채점은 추가된 데이터만 채점하게 구현했습니다. https://help.acmicpc.net/judge...

이 규칙은 2020년 3월 6일에 생긴 규칙이고, 당시 서브태스크 문제가 많지 않아 서브태스크 문제는 전체 데이터 재채점을 하게 구현했습니다. 이 글을 작성하는 날을 기준으로 서브태스크 문제는 1200개가 있습니다. https://help.acmicpc.net/statu... 문제의 수도 꽤 많으니 이제 서브태스크 재채점도 ICPC 스타일 문제처럼 하게 변경해야 재채점 시간이 많이 절약될 것 같습니다. 이 업데이트는 항상 그랬듯이 나중에 시간이 나면 할 예정입니다.

이번에 추가된 업데이트를 눈으로 보거나, 어떤 문제가 이러한 방식을 사용하는지 직접 확인할 수 있는 방법은 없습니다.

감사합니다.