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

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

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

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

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

      → Ответить
»
6 лет назад, скрыть # |
← 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.

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

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

Thank you for a lot of hacking attempts!!!

→ Ответить