Today, I went for hacking less optimized solutions for 2094H - La Vaca Saturno Saturnita. Although I didn't try to hack many, there was one hack test that I enjoyed much to construct. The submission to hack is 315476741. You can see right there, they used unordered_map<int,vector<int>> g; to store the positions of each value.

Note that in this blog, I mentioned that it's hard to hack unordered_map when the range of elements is small. Because $$$a_i \le 10^5$$$, the maximum number of hash collisions it can make per indexing is only around $$$\sqrt{10^5}$$$, and its constant factor is relatively small.

At first thought, it didn't look very feasible to attack this unordered_map effectively, because constructing an unordered_map hack test usually means you give up other patterns that can cause slow down on the code. This submission already took $$$3843$$$ ms on the original tests (test #6 seems to be a very strong test against many solutions) without exploiting its vulnerability regarding unordered_map. I believe the test uses almost only the divisors of $$$83160$$$, which has the most number of divisors ($$$128$$$) within the constraint (along with $$$98280$$$), so it works quite slow against solutions that test all divisors of the original $$$k$$$ every time. This submission was also one of these cases, and constructing a hack for unordered_map would most likely ruin this pattern. Could it still be hacked?

Its running time is $$$\mathcal{O}(q \times (\log{n} + \text{(# of hash collisions)}) \times \text{(# of divisors of }k\text{)} \times \text{(# of positions where }k\text{ is divided at least once)})$$$, so fully going for unordered_map hack means we would lose most of the last two factors. So, I tried to save them as much as possible while attacking the hash to some extent. Here is how it goes.

First, the evil prime that works best for $$$a_i \le 10^5$$$ in G++17 is $$$337$$$, and we can only have $$$296$$$ multiples of them. Randomly spamming these values with $$$a_i$$$ will make in average $$$296 \over 2$$$ collisions whenever we index a multiple of $$$337$$$. Second, we want $$$k$$$ to have many divisors, but it also has to be a multiple of $$$337$$$ to make use of the hash collisions, and as large as possible because if(d>k) continue; can skip some divisors when $$$k$$$ becomes too small. Within the constraint, I found $$$337 \times 2^2 \times 3^2 \times 7 = 337 \times 252$$$ to be the best one. Third, we want the number of outer loop iteration is maximized, which means $$$k$$$ should actually be divided, not just once by a multiple of the evil prime, but several times by many of its factors. To achieve this, it's also necessary to insert some non-evil values to $$$a$$$, so that in each outer loop iteration it finds that these values can further divide $$$k$$$. Specifically, I rarely inserted $$$2$$$, $$$3$$$, and $$$7$$$ (and $$$5$$$ for my mistake, and it was too rare...), so now it in average ran more than $$$3$$$ outer loops in average. Conclusively, all these efforts made the solution run $$$\sim 4.5$$$ seconds in average, which was enough to hack almost surely.

However, there was something that I overlooked so I further strengthened the test: https://mirror.codeforces.com/contest/2094/hacks/1127536 . We can force the order of division on $$$k$$$ so that it always takes $$$5$$$ times of outer loop iterations. So, this time I fixed the positions of $$$2$$$, $$$3$$$, and $$$7$$$ in order (actually $$$2$$$, $$$7$$$, $$$3$$$ order would've technically been better because $$$3^2 \gt 7$$$...) and queried only these positions. Now the average time it takes is more than $$$5$$$ seconds.

I also hacked the same code in G++20 https://mirror.codeforces.com/contest/2094/hacks/1127539 with evil prime$$$= 257$$$ and $$$k=257 \times 360$$$, and it's even better! I don't even know why it takes so much time, but custom invocation shows that it failed to run even in $$$15$$$ seconds (runs in around $$$4$$$ seconds with $$$q=10000$$$).

I like how many different factors I had to consider to hack this one solution, and how it actually managed to make unordered_map something slow even within this tight constraint. I'm looking forward to seeing more of these solutions fail on system test (though I doubt if many actually used it) :)