peltorator's blog

Hack risujiroh for $50
By peltorator, 4 years ago, In English

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.

  • Vote: I like it
  • +700
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
4 years ago, # |
  Vote: I like it +201 Vote: I do not like it

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 <main+0x340>
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 <bits/stdc++.h>
#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<int> 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;
}
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +79 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +132 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    Wholesome!! . Almost makes me happy that risujiroh's hacky solution got through :)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +43 Vote: I do not like it

      It wasn't hacked but another interesting thing happened. sansen hacked risujiroh's solution for problem F!

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        lmao. This is interesting. Almost seems like fate. His solution to G passes, you donate to charity, now his F goes down. Damn :)

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          It was hacked after the 12-hour hacking phase, so it still counts as Accepted.

          → Reply
»
4 years ago, # |
  Vote: I like it +413 Vote: I do not like it

Thank you for a lot of hacking attempts!!!

→ Reply