안녕하세요, 출제자입니다.

• 말씀해 주신 대로 Grader가 adaptive라면, 모든 입력에 대해 문제를 풀 수 있는 (deterministic이든 randomized든) 풀이는 존재하지 않습니다. 계속해서 100점 가치의 선물을 주다가, 한 번 받아들이는 순간 600점 가치의 선물을 주기만 하면 알고리즘의 competitive ratio를 쉽게 6 이상으로 끌어올릴 수 있습니다.
• Grader가 nonadaptive하다는 정보는 디스크립션을 쓸 때 직접 포함하지는 않고 유추하는 것으로 의도하고 쓴 것은 맞습니다. (백준 슬랙의 spoiler 채널에서 나온 init() 함수의 호출 조건 때문에 nonadaptive하다는 것을 유추할 수 있다는 의견과 같습니다. "프로그램이 실행되고 나서 로봇 다오가 있었을 때 선물의 가치를 계산한 직후"라고 되어 있는데, 선물의 가치를 미리 계산하려면 (Sample Grader처럼) 모든 입력을 다 받고 나서 (DP 등을 통해) 최적 선물의 가치를 계산한 후 선물의 가치를 순서대로 pick()에 넘겨주는 수밖에 없다는 것입니다.) 이 때문에 대회 중에도 nonadaptive 조건을 직접 물어보신 분들께는 대답해 드렸지만, 전체 공지를 하지는 않았습니다. (대회 이후 디스크립션 수정을 딱히 하지 않은 이유이기도 합니다.)
  • 그러나, Grader의 adaptive 여부에 대한 명시는 시간 제한 및 메모리 제한과 같은 성격의 것으로, 반드시 명시해야 한다는 의견도 받았습니다. 디스크립션에 적혀 있는 Grader에 대한 조건을 보고 실제 Grader가 어떻게 작동하는지를 유추해야 하는 것이 인터랙티브 문제의 한계입니다. 이는 Sample Grader와 실제 Grader가 다르게 작동할 수도 있기 때문입니다. 이에 대해서 특히 adaptive 조건을 중심으로, 인터랙티브 문제를 볼 때 어디까지 믿으시는지에 대해 많은 분들의 의견을 들어보고 싶습니다.
    
• 2번 서브태스크에 한해, 정해의 풀이는 grader에서 주는 a_i들의 확률 분포와 관계없이 a_i = -100인 것의 개수가 40%(50% 미만의 일정 수준)를 넘지 않기만 하면 아주 높은 확률로 정답을 받을 수 있는 풀이입니다. 개수가 적으면 기댓값은 같지만 표준편차가 커 확률이 높지는 않고, 표준편차를 줄여 확률을 높이기 위해 최소 N을 상당히 크게 잡을 수밖에 없었습니다. 따라서 nonadaptive라는 정보를 알고 있다면, a_i들의 확률분포는 문제를 푸는 데 필요하지는 않습니다. (다르게 말하면, a_i = -100인 것의 개수가 40%를 넘지 않는다는 조건으로 이미 분포를 충분히 제약하고 있다고 생각합니다.)
  • 그러나 이 풀이만으로 1번 서브태스크를 높은 확률로 맞을 수는 없습니다. 위 조건이 1번 서브태스크로 연장되어야 정해의 풀이로 서브태스크 1과 서브태스크 2를 동시에 맞을 수 있습니다. 이 조건을 서브태스크 1에 적용되도록 수정하겠습니다.
• 별개로, 디스크립션의 많은 부분이 수정되어야 하는 것은 맞습니다. 빠르게 확인한 것만 아래와 같은 정도이고, 이 부분에 대해서는 백준님께 별도로 연락하여 빠른 시일 내에 일차적인 디스크립션 수정을 가하도록 하겠습니다.
  • 제공 파일의 파일 링크 옆에 "테스트의 편의를 위해, N ≥ 318인지는 검사하지 않습니다."라는 조건을 달 필요가 있습니다.
  • 예제 입력 1의 첫 줄을 500에서 30 500으로 고쳐야 합니다.

이 문제 등 제2회 키파컵에서 디스크립션 문제로 많은 시간을 허비한 참가자 분들께 다시 한 번 죄송하다는 말씀을 드립니다.

차후 대회에서는 이런 일이 최대한 발생하지 않도록 최선을 다해 출제 및 검수하겠습니다. 감사합니다.