### peltorator's blog

By peltorator, 3 years ago,

There's a really weird situation with the last Educational Codeforces Round 107. risujiroh is top 1 but his solution for problem G is $\mathcal{O}(n^2)$. A bunch of people tried to hack him but all these tests work like 4.6 seconds and TL is 5 seconds.

So here goes my challenge. I'm really interested in how to hack it so the first person who will hack risujiroh's solution in the next 24 hours (until April 14th 2021 19:15 UTC) will get $50 from me if you'll share your test generator with me. Good luck if you're interested! UPD. I'm sad to announce that nobody accomplished it. I wasn't expecting this scenario so I decided to donate$50 to charity. I chose this. It's a Russian organization that helps people to overcome domestic violence problems.

• +700

| Write comment?
 » 3 years ago, # |   +201 It's unhackable AVX magic. The tight loop is just this on my machine. That easily fits in TL.  1520: c5 fa 6f 18 vmovdqu (%rax),%xmm3 1524: c4 e3 65 38 40 10 01 vinserti128 $0x1,0x10(%rax),%ymm3,%ymm0 152b: 48 83 c0 20 add$0x20,%rax 152f: c5 fd fa c2 vpsubd %ymm2,%ymm0,%ymm0 1533: c5 f5 ef c8 vpxor %ymm0,%ymm1,%ymm1 1537: 48 39 d0 cmp %rdx,%rax 153a: 75 e4 jne 1520 
•  » » 3 years ago, # ^ |   0 I'm not sure that it EASILY fits in TL. There are some hacks on which this solution runs 4.8 secs. It seems super close to 5. But maybe you're right.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Excuse me, will the following code autovectorized? I know nothing about sssembly language. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") #include #define watch(x) std::cout << (#x) << " is " << (x) << std::endl using LL = long long; int main() { //freopen("in", "r", stdin); std::cin.tie(nullptr)->sync_with_stdio(false); int n; std::cin >> n; std::vector lx(n), ly(n), rx(n), ry(n); for (int i = 0; i < n; ++i) std::cin >> lx[i] >> ly[i] >> rx[i] >> ry[i]; int l = 1, r = n, m = (l + r) / 2; LL ans = 0; for (int i = l; i < m; ++i) { for (int j = m; j < r; ++j) { ans = std::max(ans, LL(j - i + 1) * std::min(lx[i], rx[j]) * std::min(ly[i], ry[j])); } } return 0; } 
•  » » » 3 years ago, # ^ |   +6 I also know nothing about assembly, but this comment helped me a lot. If you compile with the flags mentioned in the comment, you can see everything being vectorized and everything being missed. It's also helpful to experiment in custom invoc, it's pretty easy to tell if stuff is getting vectorized or not based on the speed.
 » 3 years ago, # | ← Rev. 3 →   +79 FYI, if you want to easily see the result of compiling of programs, you can use the Godbolt compiler explorer. Here's this submission (with the appropriate flags): https://godbolt.org/z/Pjdc7bxbE. You can see the tight loop is getting autovectorized (it's also a totally sequential access pattern), so it's probably unhackable.
•  » » 3 years ago, # ^ |   0 Thanks for this website!
 » 3 years ago, # |   +132 I'm sad to announce that nobody accomplished it. I wasn't expecting this scenario so I decided to donate \$50 to charity. I chose this. It's a Russian organization that helps people to overcome domestic violence problems.
•  » » 3 years ago, # ^ |   +51 Wholesome!! . Almost makes me happy that risujiroh's hacky solution got through :)
•  » » » 3 years ago, # ^ |   +43 It wasn't hacked but another interesting thing happened. sansen hacked risujiroh's solution for problem F!
•  » » » » 3 years ago, # ^ |   +13 lmao. This is interesting. Almost seems like fate. His solution to G passes, you donate to charity, now his F goes down. Damn :)
•  » » » » 3 years ago, # ^ |   0 For me it says that its Accepted. Usually if the submission was hacked, it would say "Hacked" in red, but instead it says "Accepted". Maybe I'm missing something.
•  » » » » » 3 years ago, # ^ |   +11 It was hacked after the 12-hour hacking phase, so it still counts as Accepted.
 » 3 years ago, # |   +413 Thank you for a lot of hacking attempts!!!