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 pajenegod in 2023.

This problem doesn't belong in regular competitions, 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.

With this blogpost I would like to participate in https://codeforces.me/blog/entry/149422 , a cool initiative by cadmiumky that is rewarding interesting Codeforces blogposts. If you have something interesting to share, please give it a read.

I hope you enjoy it. ^-^

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 floats, 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 floats 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 \lt 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 \lt 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 \lt 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 : bronze_coder and davi_bart, 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.

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.