Problem: 2044F - Easy Demon Problem

I initially wrote this here, but it has gotten too long and it's hard to find within so many comments, and I see many people are wondering what exactly happened there. So, I'm re-writing all things in a single blog again.

If you got time limit exceeded on test 25 or later, then you're caught by one of these hacks.

What did the hack aim for?

The editorial says a map (or a set, as they're basically the same) solution was intended to pass and no further optimization is needed. Unfortunately, it turns out that the tests weren't strong enough to actually evaluate its performance on the worst case.

Let $$$SumA$$$ be the sum of elements of array $$$a$$$, and $$$SumB$$$ be the sum of elements of array $$$b$$$ (as stated in the editorial). Let's also say $$$SA$$$ is the set of $$$SumA-a_i$$$s and $$$SB$$$ is the set of $$$SumB-b_i$$$s. The most basic way to implement this solution is for each $$$i \cdot j = x$$$ ($$$1 \le i \le \sqrt{|x|}$$$), to check if any of the following conditions is true:

• $$$i$$$ is in $$$SA$$$ and $$$j$$$ is in $$$SB$$$
• $$$j$$$ is in $$$SA$$$ and $$$i$$$ is in $$$SB$$$
• $$$-i$$$ is in $$$SA$$$ and $$$-j$$$ is in $$$SB$$$
• $$$-j$$$ is in $$$SA$$$ and $$$-i$$$ is in $$$SB$$$

Now it's easy to come up with a sub-worst case for this solution. We need to find a number $$$x$$$ that has most number of divisors, and construct proper arrays $$$a$$$ and $$$b$$$ so that every condition above becomes false. By spamming $$$x$$$ as the queries, this solution will go through every divisors of $$$x$$$ and try to check all four conditions. By making every element of $$$SA$$$ distinct, we can make the $$$\log{n}$$$ part of the set's time complexity as slow as possible.

However, there is one more thing that can fatally slow this solution down. Note that each condition actually contains two checks, concatenated by an "and". This means that such codes, in most languages, will be short-circuit-evaluated. So, if none of them is in $$$SA$$$, it will perform only the first check of each condition and move on, without checking the $$$SB$$$ part, resulting only in 4 checks each time.

Therefore, my idea was to query the number with most number of divisors, while letting $$$i$$$, $$$j$$$, $$$-i$$$, $$$-j$$$ are always in $$$SA$$$, while none of them are in $$$SB$$$. In this case, the best $$$x$$$ I found is $$$196560$$$, which has $$$160$$$ positive divisors as well as being the largest number between the ones with the same number of divisors. This way, I was able to force these solutions to perform 8 checks each time, and as expected, many of the solutions that took a little more than 2 seconds in the original tests, well-exceeded 4 seconds on this hack test.

How is the hack case generated?

You can refer to this hack generator.

Basically, we want to aim for $$$SumA = SumB = 0$$$. That'll make it easy for us to work with the elements, because then each element itself would just be the element of $$$SA$$$ and $$$SB$$$ (to be precise, it's the negative value of it but it doesn't really matter since positive and negative are symmetric in this problem).

An easy way to keep the sum $$$0$$$ is for distinct $$$k$$$s, to put $$$k$$$ and then $$$-k$$$. However, I prefer using the following random method because for some reason sets and maps are fast on most of data that have patterns, and is easy to modify the seed to generate another similar test. A simple shuffle wouldn't have been any worse than this, but idk.

We can first put $$$n-1$$$ elements to an array, and then insert the negative of the sum of these $$$n-1$$$ elements. Since we can only use elements within range $$$[-n, n]$$$, the sum of the $$$n-1$$$ elements has to be within that range too. The strategy for this is simple. While we're making these $$$n-1$$$ elements, we pick either a posivie random value or a negative random value based on the current sum. If the sum is negative then we put a positive value, and vice versa. We just need to hold an additional set to check if the value is duplicated. If the $$$n$$$-th element is to be duplciated, we can remove the $$$n-1$$$-th element and try choosing it again.

The only difference between $$$SA$$$ and $$$SB$$$ is that, for $$$SA$$$ we start by inserting every divisors of $$$x$$$ first, while for $$$SB$$$ we avoid such values while picking random values.

Why didn't you hack unordered_sets?

Hacking unordered_sets is quite tricky in this case, and I thought it would be impossible actually, so I didn't bother trying it on the open hacking phase. You can read "When the constraints are tough" section on https://codeforces.net/blog/entry/132929 to see why it's hard to generate such cases. However, it turned out it's actually possible, at least for C++20 and C++23 now, although I didn't manage to hack every one of them. I still haven't figured out a way to make this work on C++17. Anyways it's my bad not to carefully think about this back then, but at least now we have this test after the round.

How does the hack for unordered_set work?

Before starting reading this section, I recommend you to read https://codeforces.net/blog/entry/132929 first.

The strategy for hacking unordered_set is basically not too different from hacking normal sets, but we can't naively use the $$$x$$$ with the most number of divisors, since it won't properly blow up the hash. Instead, we need to work with an evil prime, which is best with $$$541$$$ in this case. So what we want now is to make as many checks to involve a multiple of $$$541$$$ as possible. Searching for a value that involves most number of multiples of $$$541$$$, I found $$$194760$$$ makes this number $$$48$$$, and if we can make both $$$SA$$$ and $$$SB$$$ check all $$$48$$$ of them, it would be as slow as $$$2 \times 541 \times 48 \times 50000 \simeq 2.6 \cdot 10^9$$$, although its constant is relatively small.

Anyways, to do this, I put only $$$540$$$ distinct elements for both $$$a$$$ and $$$b$$$, only consisting of multiples of $$$541$$$, where $$$a$$$ has all the $$$48$$$ elements involved with checking on $$$x$$$, while $$$b$$$ has none of them. However, there was a problem with this: for each $$$i < \sqrt{x}$$$, we know that $$$\cfrac{x}{i}$$$ is likely to be divided by $$$541$$$, but $$$i$$$ is not. As a result, it skipped some check on $$$SB$$$ because $$$i$$$ wasn't found in $$$SA$$$, even though checking $$$\cfrac{x}{i}$$$ in $$$SB$$$ is a costly operation. Therefore, I adjusted the generator a little so that it also contains all $$$i$$$s in $$$a$$$ as well if $$$\cfrac{x}{i}$$$ is divisible by $$$541$$$. This sacrifices the cost for hash collision a little (but not much), while it greatly increased the number of checks (it skipped all the "slow" checks on $$$SB$$$ before).

A challenge with this hack is, that the speed of finding an element in a hash is dependent on the order of insertion, but as stated in the other blog, I don't know the exact rule for this. Just by reversing $$$a$$$ in the generator, it runs very fast on the hacked submissions. So if anyone finds a specific way to make this slower, we can perhaps make even stronger tests, or make C++17 solutions hackable too.