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

The number of operations is equal to ~\frac{N}{1}~ for the case with one team, ~\frac{N}{2}~ for ~2~ teams, ~\frac{N}{3}~ for ~3~ teams, and so on.

The total number of operations is ~\frac{N}{1} + \frac{N}{2} + \frac{N}{3} + \dots + \frac{N}{N}~

~= N \left( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{N} \right)~

~\approx N \log(N)~

Additional reading about the math can be found here.

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 ~\frac{N}{t}~ operations, so maximizing the number of operations requires the minimization of ~t~ across questions.

For any ~t~, ~1 \leq x \leq t~, so we can ask ~t~ questions unique questions if ~t~ is fixed. In order to keep ~t~ as small as possible, we first ~1~ question with ~t = 1~, then the ~2~ questions with ~t = 2~, then the ~3~ questions, and so on. To find what number we go up to, we need to find the ~k~ that satisfies the equation

~1 + 2 + 3 + \dots + k = N~

Since ~1 + 2 + 3 \dots k = \frac{k(k + 1)}{2} = N~,

~k^2 + k= 2N~

~k^2 \approx N~ (ignoring constant factors)

~k \approx \sqrt{N}~

Now, notice that to answer all questions for some fixed value of ~t~, there are ~t~ unique questions, multiplied by ~\frac{N}{t}~ operations per question, giving a total of ~N~ operations. We previously calculated that in the worst case, the questions will ask about the first ~\sqrt{N}~ teams, so the total number of operations is ~N \sqrt{N}~.

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

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

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

In the second case, it takes ~\frac{N}{t}~ operations to find the answer using brute force, giving a worst case when ~t = K~, which is ~\frac{N}{K}~ operations.

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

In total, that's ~NK~ operations for precomputation, plus ~K~ operations for each update and ~\frac{N}{K}~ time for each question. Since in the worst case, ~Q = N = 100\ 000~, we can substitute ~Q = N~, and the number of operations is

~NK + Q\left(\frac{N}{K}\right)~

~= NK + N\left(\frac{N}{K}\right)~

~= N\left(K + \frac{N}{K}\right)~

Intuitively, ~K + \frac{N}{K}~ is minimized by setting ~K = \sqrt{N}~. Therefore, in total, the number of operations is

~N\left(\sqrt{N} + \frac{N}{\sqrt{N}}\right)~

~= N\left(\sqrt{N} + \sqrt{N}\right)~

~= N \sqrt {N}~ (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 ~K~ is ~\sqrt{N}~ across all problems. Additional reading can be found here.