Editorial for Girls Invitational '19 S5 - Dodgeball Club

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: mastery

For the first subtask, the intended solution was to pre-compute all possible answers, since if Kstar only asks about Team 1, there are possible answers.

The number of operations is equal to for the case with one team, for teams, for teams, and so on.

The total number of operations is   For the second subtask, the intended solution follows directly from the intended solution of the third subtask, which can be found below.

One interesting unintended solution is to use brute force but store every question that has been asked before into a hash map. In order to find how much time this takes, let's construct and then analyze the worst case.

In the worst case, all questions are unique, since any question that has been asked before takes one hash map access to answer. Also, answering a question using brute force takes operations, so maximizing the number of operations requires the minimization of across questions.

For any , , so we can ask questions unique questions if is fixed. In order to keep as small as possible, we first question with , then the questions with , then the questions, and so on. To find what number we go up to, we need to find the that satisfies the equation Since ,  (ignoring constant factors) Now, notice that to answer all questions for some fixed value of , there are unique questions, multiplied by operations per question, giving a total of operations. We previously calculated that in the worst case, the questions will ask about the first teams, so the total number of operations is .

The intended solution for the third (and second) subtask is to notice that for large values of , it is easy use brute force, while for smaller values of , it is feasible to pre-compute all values.

Suppose we choose some value such that if , we precompute all answers before answering questions and look it up when we do answer questions, and for , we use brute force.

In the first case, it takes operations to compute all answers to questions for a fixed , so the number of operations is .

In the second case, it takes operations to find the answer using brute force, giving a worst case when , which is operations.

Also, since for , the answers are precomputed, an update to the array would take operations since each value of would also need to be updated.

In total, that's operations for precomputation, plus operations for each update and time for each question. Since in the worst case, , we can substitute , and the number of operations is   Intuitively, is minimized by setting . Therefore, in total, the number of operations is   (the constant factor of 2 is ignored)

This process of problem solving can be generalized to a technique called Square Root Decomposition, since in most cases, the optimal is across all problems. Additional reading can be found here.