wery0's blog

Hacker Cup T-shirt giveaway
By wery0, history, 4 weeks ago, In English

Hello codeforces community!

Since I already have top-2000 and top-200 t-shirts from previous participations and because I don't wanna spent another ~40$ to get it delivered to Russia (especially with current ruble situation :/) I decided to give it to the first person who will hack my solution to the Shortest Routes I problem from CSES.

The solution is based on SPFA algorithm which in theory could run in $$$O(nm)$$$ as Ford-Bellman does, but in practice it is quite fast, sometimes even faster then Dijkstra.

Give it a try!

UPD: Faisal-Saqib was the the first to hack, congratulations! Sent you the code in DMs.

  • Vote: I like it
  • -16
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

is it still valid or did someone win ?

→ Reply
»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

I have hacked your solution. https://cses.fi/problemset/hack/1671/result/33262/

The explanation is that your code does kinda bfs, but you can add a vertex again, and that is the catch.

I would have been alot easier if you didn't randomly shuffle the adjacent list(also the MAGIC thing).We kind of use a little bit probability. We make the graph like this from every vertex i put edge to next k=5 (from i+2 , .. n), vertexes with weight 2*(n-i). At the end add egdes i to i+1 with weight 1. First it visits all vertex with wrong distance with some probability,then it visits them with correct once.

I tried some value for k but the worst I found was for k=5.

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Pls give me sensei ,it will motivate me to code more and be gm one day

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

different hack: https://cses.fi/problemset/hack/1671/result/33264/

vector<std::array<int, 3>> gen(int N=66665) {
    vector<Edge> edges;
    for (int i = 0; i < N / 2; ++i) edges.push_back({i, N / 2, N - 2*i});
    for (int i = 0; i < N / 2; ++i) edges.push_back({i, N+i, 1});
    for (int i = 0; i < N / 2; ++i) edges.push_back({N+i, N+N/2, 3*N-2*i});
    for (int i = N / 2 + 1; i < N; ++i) edges.push_back({N / 2, i, 1});
    for (int i = 0; i < N / 2 - 1; ++i) edges.push_back({i, i + 1, 1});
    return edges;
}

The testcase is basically the first result on google: https://stackoverflow.com/a/76249282 which is already robust against shuffling edges. The only thing that needs to be changed is to handle MAGIC. This can be done by adding new edges to dummy vertices that just avoid swapping vertices to the front:

  • For $$$i\in[0,N/2)$$$, add edge $$$i\to N+i$$$ with weight $$$0$$$
  • For $$$i\in[N,N+N/2)$$$, add edge $$$i\to N+N/2$$$ with weight $$$4N-i$$$

This is a working testcase. However, you will realize that this problem does not allow $$$0$$$ edges, the code above already handles this. (just increase zero edges and decrease non zero edges properly).

→ Reply