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:

{a,b} {a+b,ab} {2a,2b}

The first query returns ab. 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 i3. Since we already know one variable and we get the output of the query, then ai=xk, where x is the current value in position 1, and k is the output of the query (since the output is xai). We then need to set x to x+ai.

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.


Comments

There are no comments at the moment.