Блог пользователя peltorator

Hack risujiroh for $50
Автор peltorator, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +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 <main+0x340>
→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить
  • »
    »
    4 года назад, # ^ |
    ← 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 <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;
}
    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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.

      → Ответить
»
4 года назад, # |
← 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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +51 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +43 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

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

        → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 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.

        → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +11 Проголосовать: не нравится

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

          → Ответить
»
4 года назад, # |
  Проголосовать: нравится +413 Проголосовать: не нравится

Thank you for a lot of hacking attempts!!!

→ Ответить