Editorial for DMOPC '21 Contest 3 P1 - Sums & Differences

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: Riolku

Subtask 1

We only get two queries. How can we determine both of the numbers? We have two queries, but let's just use (1, 2). Let's query it twice. We will show a simulation of the array based on hidden variables a and b:

\displaystyle \{a, b\} \displaystyle \{a + b, a - b\} \displaystyle \{2a, 2b\}

The first query returns a - b. The second returns 2b. We can use the output of the second query to determine b, and the output of the first to determine a from that.

Subtask 2

There exists a solution here that makes 3 queries and solves a system of equations (after all, it's just 3 equations with 3 variables). However, we omit it, since it is long. We instead proceed to the last subtask, which contains an easier solution.

Full Solution

The full solution simply applies the subtask 1 solution to the first two indices, and then after that queries (1, i) for i \ge 3. Since we already know one variable and we get the output of the query, then a_i = x - k, where x is the current value in position 1, and k is the output of the query (since the output is x - a_i). We then need to set x to x + a_i.

We end with some advice: if a problem is challenging, look at the subtasks. The first subtask should be a good hint. Even on problems without subtasks, making your own subtasks is very often helpful for approaching the final solution.


There are no comments at the moment.