승리 경계 공격자가 항상 이기는 데 필요한 비교 횟수의 최솟값은 다음과 같다.
따라서 이면 공격자, 그렇지 않으면 수비자를 선택한다.
공격 전략: 상한 서로 다른 두 값의 대표 를 찾는다. 그 전의 같은 값들은 하나의 그룹으로 모은다. 세 값의 대소 관계가 한 번 확인되면 가운데 값은 반드시 이다. 이후에는 나머지 각 위치를 그 대표와 한 번씩 비교하면 값을 알 수 있다.
아직 세 값을 찾지 못했다면, 처리한 위치들은 두 그룹 에 속한다. 새 위치 두 개 를 묶어서 처리한다. 먼저 둘을 비교한다.
각 쌍은 세 번 이하의 비교로 처리된다. 마지막에 한 위치가 남으면 두 번 이하가 필요하다. 세 값이 모두 등장하므로 끝까지 세 번째 값이 나오지 않는 경우는 없다.
처음 서로 다른 대표를 얻기 전에 같은 값임을 확인한 위치의 수를 라 하자. 처음 개 위치에는 번의 비교를 쓴다. 라 하면 총 비교 횟수는 이다. 가운데 값을 일찍 찾은 경우에는 남은 위치당 한 번만 비교하므로 더 늘어나지 않는다.
수비 전략: 하한 DSU로 같다고 답한 위치들을 묶고, 각 그룹에 미분류, 낮음, 높음 중 하나의 상태를 둔다. 엄격한 비교는 항상 낮음에서 높음으로 향하도록 유지한다.
미분류 그룹이 없고 그룹 수가 둘이 되려면, 먼저 개 위치를 분류하는 데 최소 번의 비교가 필요하고, 별도로 번의 병합이 필요하다. 따라서 최소 번이 필요하다.
그보다 적은 비교 후에는 항상 서로 다른 유효한 수열 두 개를 만들 수 있다. 미분류가 남아 있고 낮음·높음 그룹이 있다면, 각각의 값을 또는 으로 지정한다. 여기서 순서는 낮음, 높음, 미분류이다. 아무 비교도 없으면 서로 다른 두 유효한 수열을 임의로 고른다. 미분류가 없다면 낮음 또는 높음 중 적어도 한쪽에 그룹이 둘 이상 있다. 다른 쪽을 끝값으로 고정하고, 그쪽의 서로 다른 두 그룹 중 어느 그룹을 로 둘지 바꾸면 두 증거 수열을 얻는다. 모든 엄격한 비교와 등호가 보존된다.
따라서 이면 이 수비 전략으로 모든 질의를 처리하고 두 증거 수열을 제출할 수 있다.
채점과 복잡도 공격자 상대용 수비자는 위 전략을 쓰다가, 그룹 세 개에서 같은 상태의 두 그룹을 더 합칠 수 없게 되면 둘 사이에 엄격한 순서를 정한다. 이 시점에는 세 그룹의 값이 유일하게 정해진다. 그 전에는 위 구성으로 항상 두 수열이 존재하므로, 인터랙터는 단순 추측을 정확히 거부할 수 있다. 수비자 제출은 최종 두 증거 수열을 모든 질의 기록과 대조한다. 유효한 두 증거가 있으면 모든 중간 답변의 일관성도 보장된다.
공격 전략은 시간과 공간을 사용한다. 수비 전략은 시간, 공간을 사용한다. 인터랙터의 기록 저장은 공간이다. 모든 수치 계산은 64비트 정수 범위 안에 있다.
서브태스크 1은 가능한 모든 개 수열 중 유효한 것들을 열거하고, 가능한 수열 집합을 상태로 비교 결정 트리를 메모이제이션하는 완전 탐색으로 해결한다. 상태 수는 지수적이지만 에서는 작다. 서브태스크 2는 위 선형 크기의 전략을 사용한다.
Solution written by GPT6