This is the editorial for my **Small Imprecision Contest**↵
( https://codeforces.me/gym/106258 ).↵
It is more detailed than regular editorials and is meant to be a standalone↵
blogpost, so it should still be an interesting read even if you didn't↵
participate.↵
↵
This problem has been passed around as a funny concept in some Discord servers,↵
and it was first proposed by [user:pajenegod,2025-12-25] in 2023.↵
↵
This problem doesn'treally belong in normalregular competitions.↵
R, but regardless, I thought ↵
it was too cool to not exist, and at the same time,↵
solving it requires some ↵
advanced floating point knowledge and intuition;↵
this blogpost is more detailed ↵
than usual in an attempt to create a good↵
introduction to these concepts. introduction to these concepts.↵
↵
*With this blogpost I would like to participate in↵
https://codeforces.me/blog/entry/149422 , a cool initiative by [user:ntherner,2025-12-25]↵
that is rewarding interesting Codeforces blogposts.↵
If you have something interesting to share, please give it a read.*↵
↵
I hope you enjoy it. ^-^↵
↵
[cut]↵
↵
<hr>↵
↵
All problems were variations of the same interactive problem:↵
↵
There's a hidden permutation of size $n$↵
($2 \leq n \leq 100$), $a_1, a_2,...,a_n$, and our goal is to find this↵
permutation.↵
↵
To find it, we can perform this query multiple times:↵
↵
- Print $n$ numbers, $b_1, b_2, ..., b_n$.↵
- The numbers will be summed in the order $b_{a_1}, b_{a_2}, ..., b_{a_n}$.↵
- You read the result of this sum.↵
↵
Despite it seeming impossible, the numbers are treated as floating point↵
numbers, `float`, and we can use the imprecision of their sum to find↵
information about the order of operations.↵
↵
# A. The Easy One↵
↵
**$a_1 = 1$, at most $15n$ queries, interactor prints with maximum precision**↵
↵
First of all, and for all versions of the problem, we will print numbers with↵
maximum precision, since we want to have total control over the numbers the↵
interactor will read.↵
In C++, we can do this with:↵
↵
```↵
std::cout << std::setprecision(std::numeric_limits<float>::max_digits10);↵
```↵
↵
Floating point arithmetic breaks some properties of regular sum.↵
Ignoring `NaN` values, one that it doesn't break is commutativity.↵
This means that for all $x$ and $y$, $x + y = y + x$.↵
An implication of this to our problem is that $b_{a_1} + b_{a_2}$ is always↵
equal to $b_{a_2} + b_{a_1}$, so it's impossible to distinguish the two;↵
the hidden permutation must always have some restriction for us to be able to↵
disambiguate them.↵
↵
What floating point arithmetic does break is associativity.↵
This means that there exist values $x$, $y$, and $z$ such that↵
$(x + y) + z \neq x + (y + z)$.↵
The reason behind it is that in the case of `float`s, there are just $32$ bits↵
that we can use to represent numbers↵
↵
As a side note, there is $1$ bit for the sign, $8$ for the exponent and $23$ for↵
the mantissa.↵
Here is a scheme of how it is organized:↵
↵
↵
↵
The sign bit indicates whether the number is signed or not, the mantissa gives↵
$23$ bits (with an added implicit bit) to represent the number and the exponent↵
scales this $24$-bit number.↵
↵
The finite limitation of $32$ bits means there are values that are impossible to↵
be represented; any finite representation faces this problem, and integers deal↵
with it by putting a maximum limit on the values, having a uniform coverage of↵
their domain.↵
↵
On another hand, `float`'s coverage of the domain is not uniform.↵
If we look at just integer values, all integers up to $2^{24}$ are↵
representable (their binary representation fits in the mantissa), but after↵
$2^{24}$, their binary representation is too big and `float`s handle it by↵
removing lower bits and making a best effort to represent numbers accurately.↵
Since the lower bit will be removed, this makes all odd numbers impossible to be↵
represented, so the coverage now has gaps missing one integer;↵
reaching $2^{25}$, now one more bit must be removed and the values that are not↵
multiples of four cannot be represented, leading to gaps missing three integers;↵
reaching $2^{26}$, we start having gaps missing seven integers, and so on.↵
↵
A way to trigger an associativity inequality is by having one of the values be↵
big and by having two smaller values that by themselves cannot cover the gap to↵
the next number, but that together they can.↵
An example of such values is $2^{24}$, and two $1s$.↵
We have that $2^{24}+1$ is not representable, so when the operation is↵
performed, it rounds back down to $2^{24}$ (we will talk about rounding in more↵
detail soon).↵
However, $2^{24}+2$ is representable, so the sum behaves properly.↵
So we have that $(2^{24}+1)+1 \neq 2^{24}+(1+1)$.↵
↵
Restructuring these in a way that is more useful to us, we have that there are↵
values $x$, $y$ and $z$ such that $(x + y) + z \neq (x + z) + y$.↵
By starting with $x$, we can distinguish the order in which we summed the other↵
two, either we summed $y$ then $z$ or we summed $z$ then $y$.↵
Of course, we can use the values indicated previously to do it, $2^{24}$ and two↵
$1s$ (alternatively, we can test random `float` values, we can quickly find↵
numbers that trigger the inequality).↵
↵
So now we have a way of checking whether a position $p$ comes before another↵
position $q$:↵
↵
- Since we know $a_1 = 1$, the first value to be summed will always be $b_1$, so↵
we set it to $1$.↵
- We set $b_p$ to $1$ and $b_q$ to $2^{24}$.↵
- All other values are set to $0$.↵
↵
Based on the result of the sum, which is either $(1+2^{24})+1$ or↵
$(1+1)+2^{24}$, we know whether $p$ appears before $q$ in the hidden↵
permutation.↵
↵
Since we have a way to compare two positions, we can do a comparison-based↵
sorting of the numbers from $2$ to $n$, resulting in $O(n log(n))$ queries.↵
Since $n \leq 100$, this should fit comfortably in $15n$ queries.↵
↵
# B. The Vanilla One↵
↵
**$a_1 = 1$, at most $15n$ queries, interactor prints with default precision**↵
↵
Now the interactor prints with default precision.↵
This means that the computation is the same as in the previous case, but now↵
when the interactor prints the result to the user, some precision was lost.↵
Unfortunately, this loss of precision affects the behavior of our chosen values.↵
Consider a variable `VAL` with the value $2^{24}$.↵
While previously the printed results were:↵
↵
```↵
VAL :16777216↵
VAL+1:16777216↵
VAL+2:16777218↵
```↵
↵
Now they are:↵
↵
```↵
VAL :1.67772e+07↵
VAL+1:1.67772e+07↵
VAL+2:1.67772e+07↵
```↵
↵
Fortunately this is an issue that is easy to fix, we can easily find values that↵
are not affected by this by testing random `float` numbers.↵
In C++, to test what values are printed we can use a `stringstream`, by printing↵
to it and then reading the value.↵
↵
Despite this, a concrete example of values that have this property is↵
$x = 2^{24}$, $y = -2^{24}$ and $z = 1$.↵
We have that $(2^{24} + 1) - 2^{24} = 2^{24} - 2^{24} = 0$ and we have that↵
$(2^{24} - 2^{24}) + 1 = 0 + 1 = 1$, and these results don't suffer from↵
precision issues.↵
↵
So we solve this problem in the same way as the previous one, changing just the↵
summed values.↵
↵
↵
# C. The Unnecessary One↵
↵
**$a_1 < a_2$, at most $15n$ queries, interactor prints with default precision**↵
↵
The added challenge with this one is that we no longer know a position that↵
appears before every other.↵
↵
The most direct way to solve this version is to determine the first position and↵
then apply our old solution to it, whiche we can do by finding $a_1$ and $a_2$,↵
which are indistinguishable, and disambiguating them.↵
↵
Previously, the two possible results of our comparison were $(x+y)+z$ and↵
$(x+z)+y$.↵
Now, let's see what happens when we consider $(y+z)+x$ (note that all other↵
orders of operations result in one of these three values due to commutativity of↵
the first two elements).↵
We know that $(x+y)+z \neq (x+z)+y$, so the value $(y+z)+x$ is different from at↵
least one of them, no matter what it ends up being.↵
Let's assume, without loss of generality, that $(y+z)+x$ is different from the↵
first option, $(x+y)+z$.↵
This makes $(x+y)+z$ distinguishable from all other possibilities, and this↵
result always indicates that $z$ was summed last.↵
If this is the case, then we know that the position that held the value $z$↵
cannot be $a_1$ or $a_2$, since it has at least two positions appear before it.↵
↵
We can use this information to be able to discard one position by doing at most↵
two queries:↵
↵
- Let's consider positions $p$, $q$ and $r$.↵
- We set $b_r$ to $z$, and the other two to $x$ and $y$; all others positions↵
are set to $0$.↵
- If the value is $(x+y)+z$, then we know $r$ cannot be the first position.↵
- If not, we test again with a different order, this time setting $b_q$ to $z$.↵
- If the value is $(x+y)+z$, then we know $q$ cannot be the first position.↵
- If not, the only alternative is that both $r$ and $q$ appear before $p$, so↵
$p$ cannot be the first position.↵
↵
When there are only two positions remaining, we know they must be $a_1$ and↵
$a_2$, so we disambiguate them with the permutation restriction, $a_1 < a_2$.↵
↵
This adds at most $2(n-2)$ queries to our previous solution, which still fits↵
comfortably under $15n$ queries.↵
↵
# D. The Hard One↵
↵
**$a_1 < a_2$, at most $2n$ queries, interactor prints with maximum precision**↵
↵
The added challenge now is the limit of $2n$ queries, which means sorting is not↵
enough and we need to completely change the idea of our solution.↵
We also go back to printing with maximum precision.↵
↵
To find the new idea, in **A.** we saw that $2^{24}+1$ wasn't representable and↵
was rounded down, but $2^{24}+2$ was, so it was the value correctly obtained;↵
let's see what happens when we add other values.↵
Here we show the floating point value and in parenthesis the accurate value of↵
the sum, and as before, `VAL` holds $2^{24}$:↵
↵
```↵
VAL+ 0: 16777216 (16777216)↵
VAL+ 1: 16777216 (16777217)↵
VAL+ 2: 16777218 (16777218)↵
VAL+ 3: 16777220 (16777219)↵
VAL+ 4: 16777220 (16777220)↵
VAL+ 5: 16777220 (16777221)↵
VAL+ 6: 16777222 (16777222)↵
VAL+ 7: 16777224 (16777223)↵
VAL+ 8: 16777224 (16777224)↵
VAL+ 9: 16777224 (16777225)↵
VAL+10: 16777226 (16777226)↵
VAL+11: 16777228 (16777227)↵
VAL+12: 16777228 (16777228)↵
VAL+13: 16777228 (16777229)↵
VAL+14: 16777230 (16777230)↵
VAL+15: 16777232 (16777231)↵
VAL+16: 16777232 (16777232)↵
VAL+17: 16777232 (16777233)↵
VAL+18: 16777234 (16777234)↵
VAL+19: 16777236 (16777235)↵
```↵
↵
We can see the pattern: odd values are not representable, so they alternate↵
between rounding down and rounding up.↵
↵
The observed rounding strategy is called **round half to even** and it's the↵
default rounding strategy for `float` values.↵
Exemplifying with the decimal base, the half values, $0.5$, would round to the↵
nearest even value, meaning $9.5$ would round to $10$ and $10.5$ would↵
also round to $10$.↵
In `float` values, a number is considered "even" if the last bit of the mantissa↵
is $0$.↵
For our purpose around $2^{24}$, the "even" values are those who are multiples↵
of four.↵
↵
To use this to obtain information about the position $p$, we can set all values↵
to $1$ except $b_p$, which we set to $2^{24}$.↵
Going through the hidden permutation, before position $p$ appears, all positions↵
will add $1$ with perfect accuracy, but once $p$ appears, $2^{24}$ will be added↵
and the sum will behave according to the rounding we described above.↵
We can use this idea to group the positions in equivalence classes, and↵
afterwards we can sort the positions within each class.↵
↵
Lastly, we still have a detail to take care of, after $p$ appears in the hidden↵
permutation, the following positions still have $1s$, so we must see what↵
happens when $1s$ are added to the values:↵
↵
```↵
(VAL+ 0)+1: 16777216↵
(VAL+ 1)+1: 16777216↵
(VAL+ 2)+1: 16777220↵
(VAL+ 3)+1: 16777220↵
(VAL+ 4)+1: 16777220↵
(VAL+ 5)+1: 16777220↵
(VAL+ 6)+1: 16777224↵
(VAL+ 7)+1: 16777224↵
(VAL+ 8)+1: 16777224↵
(VAL+ 9)+1: 16777224↵
(VAL+10)+1: 16777228↵
(VAL+11)+1: 16777228↵
(VAL+12)+1: 16777228↵
(VAL+13)+1: 16777228↵
(VAL+14)+1: 16777232↵
(VAL+15)+1: 16777232↵
(VAL+16)+1: 16777232↵
(VAL+17)+1: 16777232↵
(VAL+18)+1: 16777236↵
(VAL+19)+1: 16777236↵
```↵
↵
Here we can observe that when we add $1$ to the values that are not multiples of↵
four (`VAL+2`, `VAL+6`, etc.), they round up to the next multiple of four.↵
Similarly, adding $1$ to the multiples of four will not change them (this is↵
also what happens when $2^{24}+1$ rounds back down to $2^{24}$).↵
Repeatedly adding more $1s$ will not change the values anymore, since now they↵
all will be a multiple of four.↵
↵
So now we can we perform this for every position $p$ between $1$ and $n$, and↵
not only we find the first position (it will be one of the two that return↵
exactly $2^{24}$), we will also split the positions in equivalence classes of↵
size at most $4$.↵
↵
To solve the problem, we just need to be able to sort these small sets in a↵
short amount of queries (at most one query per element of the set, since in the↵
previous operation, $n$ queries were performed, and now we just have $n$ queries↵
remaining), and since we already determined $a_1$, we can try to do it with the↵
comparison function we described for problem **A.**.↵
↵
First of all, the edge cases which are still possible: sets of size $1$ are↵
already sorted, sets of size $2$ can be sorted with one comparison, and sets of↵
size $3$ can also be sorted by hand (find the position that comes last with two↵
comparisons and sort the remaining two positions with one, for a total of three↵
queries).↵
↵
The hard part is to sort sets of size $4$ with at most four queries, which turns↵
out to be impossible in the worst case with this method.↵
There are $4! = 24$ permutations of the elements of a set of size $4$, and each↵
comparison gives us a binary value, either $p$ comes before $q$ or $q$ comes↵
before $p$.↵
In the best scenario a binary query splits the search space in two, and the↵
maximum amount of permutations we could distinguish using four comparisons is↵
$2^{4} = 16$, which is insufficient to distinguish all permutations.↵
↵
This makes us look for queries that are not binary.↵
Previously, when we were looking for the first position in **C.**, we mentioned↵
that for values $x$, $y$ and $z$, if $(x+y)+z \neq (x+z)+y$, $(y+z)+x$ would be↵
different from at least one of them, but would it be possible for that value to↵
be different from both?↵
There's nothing preventing it.↵
↵
It turns out that yes, such numbers are possible, and they are easy to find by↵
searching random `float` values.↵
The specific numbers and results I found were:↵
↵
```↵
x : 2.10142636↵
y : -3.76973276e-07↵
z : -0.993138254↵
(x + z) + y : 1.10828769↵
(y + z) + x : 1.10828781↵
(x + y) + z : 1.10828757↵
```↵
↵
Using this query, three results are now possible, and they identify which of the↵
positions came last: if the result was $(x+y)+z$, it indicates that the position↵
holding $z$ came after the other two.↵
↵
So now we can sort sets of size $4$ with four queries: first we find the last↵
position with two queries, next the last position of the three remaining can be↵
found with just one query, and now one more of the original comparisons can sort↵
the remaining two.↵
↵
Summarizing the final solution:↵
↵
- For all positions $p$ from $1$ to $n$, we set $b_p$ to $2^{24}$ and all other↵
positions to $1$.↵
- This will split the values into classes of size at most $4$, ordered by the↵
outputted result.↵
- For each of these classes, we order them using hand-written comparisons.↵
↵
This results in at most $2n$ queries.↵
↵
# Honorable Mention↵
↵
Credit to : [user:bronze_coder,2025-12-25] and [user:davi_bart,2025-12-25], who solved the problem↵
with this idea at around the same time.↵
↵
If we analyze the concrete values explained in the solution for **B.**, we can↵
find a stronger property.↵
Notice that $(...((2^{24}+1)+1)...+1) = 2^{24}$, and once we add $-2^{24}$, this↵
becomes $0$.↵
Adding more $1s$ would make them sum and behave properly.↵
↵
If we set $b_1$ to $2^{24}$, $b_p$ to $-2^{24}$ and all other positions to $1$,↵
we would know how many positions appear after $p$ in the hidden permutation,↵
determining the exact location of $p$.↵
Doing this for all positions from $2$ to $n$ leads to determining the full↵
permutation in $n-1$ queries.↵
↵
It's also possible to solve **C.** and **D.** extending this idea for a much↵
cleaner solution.↵
↵
<hr>↵
↵
For those who participated, I hope you enjoyed the contest.↵
If anyone found better solutions to any of the problems, I would be interested↵
in hearing about them; I now know that it's possible to solve **A.** and **B.**↵
under $n$ queries, but I don't know if there's a solution for **D.** that↵
performs significantly less than $2n$ queries, and it doesn't look impossible.↵
I would also be interested in different cool variations of the problems if you↵
have them.↵
( https://codeforces.me/gym/106258 ).↵
It is more detailed than regular editorials and is meant to be a standalone↵
blogpost, so it should still be an interesting read even if you didn't↵
participate.↵
↵
This problem has been passed around as a funny concept in some Discord servers,↵
and it was first proposed by [user:pajenegod,2025-12-25] in 2023.↵
↵
This problem doesn't
R
it was too cool to not exist, and at the same time,
advanced floating point knowledge and intuition;
than usual in an attempt to create a good
introduction to these concepts.
↵
*With this blogpost I would like to participate in↵
https://codeforces.me/blog/entry/149422 , a cool initiative by [user:ntherner,2025-12-25]↵
that is rewarding interesting Codeforces blogposts.↵
If you have something interesting to share, please give it a read.*↵
↵
I hope you enjoy it. ^-^↵
↵
[cut]↵
↵
<hr>↵
↵
All problems were variations of the same interactive problem:↵
↵
There's a hidden permutation of size $n$↵
($2 \leq n \leq 100$), $a_1, a_2,...,a_n$, and our goal is to find this↵
permutation.↵
↵
To find it, we can perform this query multiple times:↵
↵
- Print $n$ numbers, $b_1, b_2, ..., b_n$.↵
- The numbers will be summed in the order $b_{a_1}, b_{a_2}, ..., b_{a_n}$.↵
- You read the result of this sum.↵
↵
Despite it seeming impossible, the numbers are treated as floating point↵
numbers, `float`, and we can use the imprecision of their sum to find↵
information about the order of operations.↵
↵
# A. The Easy One↵
↵
**$a_1 = 1$, at most $15n$ queries, interactor prints with maximum precision**↵
↵
First of all, and for all versions of the problem, we will print numbers with↵
maximum precision, since we want to have total control over the numbers the↵
interactor will read.↵
In C++, we can do this with:↵
↵
```↵
std::cout << std::setprecision(std::numeric_limits<float>::max_digits10);↵
```↵
↵
Floating point arithmetic breaks some properties of regular sum.↵
Ignoring `NaN` values, one that it doesn't break is commutativity.↵
This means that for all $x$ and $y$, $x + y = y + x$.↵
An implication of this to our problem is that $b_{a_1} + b_{a_2}$ is always↵
equal to $b_{a_2} + b_{a_1}$, so it's impossible to distinguish the two;↵
the hidden permutation must always have some restriction for us to be able to↵
disambiguate them.↵
↵
What floating point arithmetic does break is associativity.↵
This means that there exist values $x$, $y$, and $z$ such that↵
$(x + y) + z \neq x + (y + z)$.↵
The reason behind it is that in the case of `float`s, there are just $32$ bits↵
that we can use to represent numbers↵
↵
As a side note, there is $1$ bit for the sign, $8$ for the exponent and $23$ for↵
the mantissa.↵
Here is a scheme of how it is organized:↵
↵
↵
↵
The sign bit indicates whether the number is signed or not, the mantissa gives↵
$23$ bits (with an added implicit bit) to represent the number and the exponent↵
scales this $24$-bit number.↵
↵
The finite limitation of $32$ bits means there are values that are impossible to↵
be represented; any finite representation faces this problem, and integers deal↵
with it by putting a maximum limit on the values, having a uniform coverage of↵
their domain.↵
↵
On another hand, `float`'s coverage of the domain is not uniform.↵
If we look at just integer values, all integers up to $2^{24}$ are↵
representable (their binary representation fits in the mantissa), but after↵
$2^{24}$, their binary representation is too big and `float`s handle it by↵
removing lower bits and making a best effort to represent numbers accurately.↵
Since the lower bit will be removed, this makes all odd numbers impossible to be↵
represented, so the coverage now has gaps missing one integer;↵
reaching $2^{25}$, now one more bit must be removed and the values that are not↵
multiples of four cannot be represented, leading to gaps missing three integers;↵
reaching $2^{26}$, we start having gaps missing seven integers, and so on.↵
↵
A way to trigger an associativity inequality is by having one of the values be↵
big and by having two smaller values that by themselves cannot cover the gap to↵
the next number, but that together they can.↵
An example of such values is $2^{24}$, and two $1s$.↵
We have that $2^{24}+1$ is not representable, so when the operation is↵
performed, it rounds back down to $2^{24}$ (we will talk about rounding in more↵
detail soon).↵
However, $2^{24}+2$ is representable, so the sum behaves properly.↵
So we have that $(2^{24}+1)+1 \neq 2^{24}+(1+1)$.↵
↵
Restructuring these in a way that is more useful to us, we have that there are↵
values $x$, $y$ and $z$ such that $(x + y) + z \neq (x + z) + y$.↵
By starting with $x$, we can distinguish the order in which we summed the other↵
two, either we summed $y$ then $z$ or we summed $z$ then $y$.↵
Of course, we can use the values indicated previously to do it, $2^{24}$ and two↵
$1s$ (alternatively, we can test random `float` values, we can quickly find↵
numbers that trigger the inequality).↵
↵
So now we have a way of checking whether a position $p$ comes before another↵
position $q$:↵
↵
- Since we know $a_1 = 1$, the first value to be summed will always be $b_1$, so↵
we set it to $1$.↵
- We set $b_p$ to $1$ and $b_q$ to $2^{24}$.↵
- All other values are set to $0$.↵
↵
Based on the result of the sum, which is either $(1+2^{24})+1$ or↵
$(1+1)+2^{24}$, we know whether $p$ appears before $q$ in the hidden↵
permutation.↵
↵
Since we have a way to compare two positions, we can do a comparison-based↵
sorting of the numbers from $2$ to $n$, resulting in $O(n log(n))$ queries.↵
Since $n \leq 100$, this should fit comfortably in $15n$ queries.↵
↵
# B. The Vanilla One↵
↵
**$a_1 = 1$, at most $15n$ queries, interactor prints with default precision**↵
↵
Now the interactor prints with default precision.↵
This means that the computation is the same as in the previous case, but now↵
when the interactor prints the result to the user, some precision was lost.↵
Unfortunately, this loss of precision affects the behavior of our chosen values.↵
Consider a variable `VAL` with the value $2^{24}$.↵
While previously the printed results were:↵
↵
```↵
VAL :16777216↵
VAL+1:16777216↵
VAL+2:16777218↵
```↵
↵
Now they are:↵
↵
```↵
VAL :1.67772e+07↵
VAL+1:1.67772e+07↵
VAL+2:1.67772e+07↵
```↵
↵
Fortunately this is an issue that is easy to fix, we can easily find values that↵
are not affected by this by testing random `float` numbers.↵
In C++, to test what values are printed we can use a `stringstream`, by printing↵
to it and then reading the value.↵
↵
Despite this, a concrete example of values that have this property is↵
$x = 2^{24}$, $y = -2^{24}$ and $z = 1$.↵
We have that $(2^{24} + 1) - 2^{24} = 2^{24} - 2^{24} = 0$ and we have that↵
$(2^{24} - 2^{24}) + 1 = 0 + 1 = 1$, and these results don't suffer from↵
precision issues.↵
↵
So we solve this problem in the same way as the previous one, changing just the↵
summed values.↵
↵
↵
# C. The Unnecessary One↵
↵
**$a_1 < a_2$, at most $15n$ queries, interactor prints with default precision**↵
↵
The added challenge with this one is that we no longer know a position that↵
appears before every other.↵
↵
The most direct way to solve this version is to determine the first position and↵
then apply our old solution to it, whiche we can do by finding $a_1$ and $a_2$,↵
which are indistinguishable, and disambiguating them.↵
↵
Previously, the two possible results of our comparison were $(x+y)+z$ and↵
$(x+z)+y$.↵
Now, let's see what happens when we consider $(y+z)+x$ (note that all other↵
orders of operations result in one of these three values due to commutativity of↵
the first two elements).↵
We know that $(x+y)+z \neq (x+z)+y$, so the value $(y+z)+x$ is different from at↵
least one of them, no matter what it ends up being.↵
Let's assume, without loss of generality, that $(y+z)+x$ is different from the↵
first option, $(x+y)+z$.↵
This makes $(x+y)+z$ distinguishable from all other possibilities, and this↵
result always indicates that $z$ was summed last.↵
If this is the case, then we know that the position that held the value $z$↵
cannot be $a_1$ or $a_2$, since it has at least two positions appear before it.↵
↵
We can use this information to be able to discard one position by doing at most↵
two queries:↵
↵
- Let's consider positions $p$, $q$ and $r$.↵
- We set $b_r$ to $z$, and the other two to $x$ and $y$; all others positions↵
are set to $0$.↵
- If the value is $(x+y)+z$, then we know $r$ cannot be the first position.↵
- If not, we test again with a different order, this time setting $b_q$ to $z$.↵
- If the value is $(x+y)+z$, then we know $q$ cannot be the first position.↵
- If not, the only alternative is that both $r$ and $q$ appear before $p$, so↵
$p$ cannot be the first position.↵
↵
When there are only two positions remaining, we know they must be $a_1$ and↵
$a_2$, so we disambiguate them with the permutation restriction, $a_1 < a_2$.↵
↵
This adds at most $2(n-2)$ queries to our previous solution, which still fits↵
comfortably under $15n$ queries.↵
↵
# D. The Hard One↵
↵
**$a_1 < a_2$, at most $2n$ queries, interactor prints with maximum precision**↵
↵
The added challenge now is the limit of $2n$ queries, which means sorting is not↵
enough and we need to completely change the idea of our solution.↵
We also go back to printing with maximum precision.↵
↵
To find the new idea, in **A.** we saw that $2^{24}+1$ wasn't representable and↵
was rounded down, but $2^{24}+2$ was, so it was the value correctly obtained;↵
let's see what happens when we add other values.↵
Here we show the floating point value and in parenthesis the accurate value of↵
the sum, and as before, `VAL` holds $2^{24}$:↵
↵
```↵
VAL+ 0: 16777216 (16777216)↵
VAL+ 1: 16777216 (16777217)↵
VAL+ 2: 16777218 (16777218)↵
VAL+ 3: 16777220 (16777219)↵
VAL+ 4: 16777220 (16777220)↵
VAL+ 5: 16777220 (16777221)↵
VAL+ 6: 16777222 (16777222)↵
VAL+ 7: 16777224 (16777223)↵
VAL+ 8: 16777224 (16777224)↵
VAL+ 9: 16777224 (16777225)↵
VAL+10: 16777226 (16777226)↵
VAL+11: 16777228 (16777227)↵
VAL+12: 16777228 (16777228)↵
VAL+13: 16777228 (16777229)↵
VAL+14: 16777230 (16777230)↵
VAL+15: 16777232 (16777231)↵
VAL+16: 16777232 (16777232)↵
VAL+17: 16777232 (16777233)↵
VAL+18: 16777234 (16777234)↵
VAL+19: 16777236 (16777235)↵
```↵
↵
We can see the pattern: odd values are not representable, so they alternate↵
between rounding down and rounding up.↵
↵
The observed rounding strategy is called **round half to even** and it's the↵
default rounding strategy for `float` values.↵
Exemplifying with the decimal base, the half values, $0.5$, would round to the↵
nearest even value, meaning $9.5$ would round to $10$ and $10.5$ would↵
also round to $10$.↵
In `float` values, a number is considered "even" if the last bit of the mantissa↵
is $0$.↵
For our purpose around $2^{24}$, the "even" values are those who are multiples↵
of four.↵
↵
To use this to obtain information about the position $p$, we can set all values↵
to $1$ except $b_p$, which we set to $2^{24}$.↵
Going through the hidden permutation, before position $p$ appears, all positions↵
will add $1$ with perfect accuracy, but once $p$ appears, $2^{24}$ will be added↵
and the sum will behave according to the rounding we described above.↵
We can use this idea to group the positions in equivalence classes, and↵
afterwards we can sort the positions within each class.↵
↵
Lastly, we still have a detail to take care of, after $p$ appears in the hidden↵
permutation, the following positions still have $1s$, so we must see what↵
happens when $1s$ are added to the values:↵
↵
```↵
(VAL+ 0)+1: 16777216↵
(VAL+ 1)+1: 16777216↵
(VAL+ 2)+1: 16777220↵
(VAL+ 3)+1: 16777220↵
(VAL+ 4)+1: 16777220↵
(VAL+ 5)+1: 16777220↵
(VAL+ 6)+1: 16777224↵
(VAL+ 7)+1: 16777224↵
(VAL+ 8)+1: 16777224↵
(VAL+ 9)+1: 16777224↵
(VAL+10)+1: 16777228↵
(VAL+11)+1: 16777228↵
(VAL+12)+1: 16777228↵
(VAL+13)+1: 16777228↵
(VAL+14)+1: 16777232↵
(VAL+15)+1: 16777232↵
(VAL+16)+1: 16777232↵
(VAL+17)+1: 16777232↵
(VAL+18)+1: 16777236↵
(VAL+19)+1: 16777236↵
```↵
↵
Here we can observe that when we add $1$ to the values that are not multiples of↵
four (`VAL+2`, `VAL+6`, etc.), they round up to the next multiple of four.↵
Similarly, adding $1$ to the multiples of four will not change them (this is↵
also what happens when $2^{24}+1$ rounds back down to $2^{24}$).↵
Repeatedly adding more $1s$ will not change the values anymore, since now they↵
all will be a multiple of four.↵
↵
So now we can we perform this for every position $p$ between $1$ and $n$, and↵
not only we find the first position (it will be one of the two that return↵
exactly $2^{24}$), we will also split the positions in equivalence classes of↵
size at most $4$.↵
↵
To solve the problem, we just need to be able to sort these small sets in a↵
short amount of queries (at most one query per element of the set, since in the↵
previous operation, $n$ queries were performed, and now we just have $n$ queries↵
remaining), and since we already determined $a_1$, we can try to do it with the↵
comparison function we described for problem **A.**.↵
↵
First of all, the edge cases which are still possible: sets of size $1$ are↵
already sorted, sets of size $2$ can be sorted with one comparison, and sets of↵
size $3$ can also be sorted by hand (find the position that comes last with two↵
comparisons and sort the remaining two positions with one, for a total of three↵
queries).↵
↵
The hard part is to sort sets of size $4$ with at most four queries, which turns↵
out to be impossible in the worst case with this method.↵
There are $4! = 24$ permutations of the elements of a set of size $4$, and each↵
comparison gives us a binary value, either $p$ comes before $q$ or $q$ comes↵
before $p$.↵
In the best scenario a binary query splits the search space in two, and the↵
maximum amount of permutations we could distinguish using four comparisons is↵
$2^{4} = 16$, which is insufficient to distinguish all permutations.↵
↵
This makes us look for queries that are not binary.↵
Previously, when we were looking for the first position in **C.**, we mentioned↵
that for values $x$, $y$ and $z$, if $(x+y)+z \neq (x+z)+y$, $(y+z)+x$ would be↵
different from at least one of them, but would it be possible for that value to↵
be different from both?↵
There's nothing preventing it.↵
↵
It turns out that yes, such numbers are possible, and they are easy to find by↵
searching random `float` values.↵
The specific numbers and results I found were:↵
↵
```↵
x : 2.10142636↵
y : -3.76973276e-07↵
z : -0.993138254↵
(x + z) + y : 1.10828769↵
(y + z) + x : 1.10828781↵
(x + y) + z : 1.10828757↵
```↵
↵
Using this query, three results are now possible, and they identify which of the↵
positions came last: if the result was $(x+y)+z$, it indicates that the position↵
holding $z$ came after the other two.↵
↵
So now we can sort sets of size $4$ with four queries: first we find the last↵
position with two queries, next the last position of the three remaining can be↵
found with just one query, and now one more of the original comparisons can sort↵
the remaining two.↵
↵
Summarizing the final solution:↵
↵
- For all positions $p$ from $1$ to $n$, we set $b_p$ to $2^{24}$ and all other↵
positions to $1$.↵
- This will split the values into classes of size at most $4$, ordered by the↵
outputted result.↵
- For each of these classes, we order them using hand-written comparisons.↵
↵
This results in at most $2n$ queries.↵
↵
# Honorable Mention↵
↵
Credit to : [user:bronze_coder,2025-12-25] and [user:davi_bart,2025-12-25], who solved the problem↵
with this idea at around the same time.↵
↵
If we analyze the concrete values explained in the solution for **B.**, we can↵
find a stronger property.↵
Notice that $(...((2^{24}+1)+1)...+1) = 2^{24}$, and once we add $-2^{24}$, this↵
becomes $0$.↵
Adding more $1s$ would make them sum and behave properly.↵
↵
If we set $b_1$ to $2^{24}$, $b_p$ to $-2^{24}$ and all other positions to $1$,↵
we would know how many positions appear after $p$ in the hidden permutation,↵
determining the exact location of $p$.↵
Doing this for all positions from $2$ to $n$ leads to determining the full↵
permutation in $n-1$ queries.↵
↵
It's also possible to solve **C.** and **D.** extending this idea for a much↵
cleaner solution.↵
↵
<hr>↵
↵
For those who participated, I hope you enjoyed the contest.↵
If anyone found better solutions to any of the problems, I would be interested↵
in hearing about them; I now know that it's possible to solve **A.** and **B.**↵
under $n$ queries, but I don't know if there's a solution for **D.** that↵
performs significantly less than $2n$ queries, and it doesn't look impossible.↵
I would also be interested in different cool variations of the problems if you↵
have them.↵
