So here’s the story... I was doing Codeforces Round 1099 (Div. 2) recently and things were going pretty well. I had managed to solve A, B, C, and D, and there were still about 45 minutes left on the clock. I looked at problem E, read it for about a minute, and my brain just went "hell nahh". I didn't feel like even trying to untangle that one. Out of pure curiosity, I opened 2231F - Quadratic Jumps... Obviously, I wasn't expecting to actually solve a Div2 F by myself, but the problem looked kinda graphy and weirdly approachable. I figured, whatever, I have 45 minutes to kill. I'll just throw a custom BFS at it. I knew it probably wouldn't pass, but hey, it's F. It's supposed to be hard, so getting a TLE won't hurt me in anyway lol.

Step 1: The "Let's just throw BFS and watch"

My first thought was super trivial. Just check if the distance is 0 (same node) or 1 (the difference is exactly a perfect square). If it's neither... let the BFS it ignoring the time complexity. But it wasn't just a general bfs. I did make some changes like instead of visited array, I used timestamps. Instead of storing true/false in my visited array, I store an integer tk. Every time a new query starts, I just do tk++. Inside the BFS, a node is only considered visited if visited[node] == tk. This effectively clears the visited array in O(1) time! Looked neat tbh. 375547172

// ... inside query loop ...
if (a== b) {
    cout<<0<<endl;
    continue;
}
if (ii[abs(a-b)]) {
    cout<<1<<endl;
    continue;
}

// Just BFS it with the tk trick and watch
cout << bfs(a, b, n, tk, vv, dd, ss) <<endl;

Result? TLE on test case 5. Honestly, totally expected.

Step 2: Wait... I can check dist=2 without BFS?

I realized I could check for a distance of 2 much faster. If node a and node b share a common neighbor, the distance is 2. I generated all valid 1-step jumps from a (stored in aa) and from b (stored in cc), and just checked if they intersected using a quick frequency array bb. 375549547

// ... generated neighbors aa and cc ...
for(auto x: cc) bb[x] = 1;

bool d2 = 0;
for(auto x: aa) {
    if(bb[x]) {
        d2 = 1; break;
    }
}

// clean up target array
for(auto x: cc) bb[x] = 0;

if(d2) { cout << 2 << "\n"; continue; }

// Fallback to BFS
cout << bfs(a, b, n, tk, vv, dd, ss) <<endl;

Result? TLE on test 5 again. It was faster, but calculating distances greater than 2 was still using the BFS.

Step 3: The Last-Minute Panic & The Tragic Bug T_T

Time was draining fast, and I lil bit panicked. I decided I'm NOT writing a distance 4 check. I just wanted to hardcode the check for distance 3 to avoid the bfs as much as possible.

The logic was right: if I can jump from any neighbor of a to any neighbor of b, the dist is 3. But in my panic with the time passing, look at where I put the array cleanup line for bb: 375562626

// ... distance 2 check ...
    if(bb[x]) { d2 = 1; break; }
}

// THE PANIC BUG: I cleared the array here!!
for(auto x: cc) bb[x] = 0; 

if(d2) { cout << 2 <<endl; continue; }

bool d3 = 0;
for(auto x: aa) {
    for(auto s: ss) {
        // bb is literally all zeros now so this never hits true
        if(x + s <= n && bb[x + s]) { d3 = 1; break; }
        // ...

Because I cleared bb before the d3 loop, my code never actually found a distance of 3 and just passed everything straight to the slow bfs anyway.

I hit submit... contest ends... and I immediately see the bug. nvm... After the contest, I moved that single cleanup line to the correct spot, submitted it, and it got Accepted. 375563883 But this is not where it ended.

Step 4: The Number Theory course which got me >_<

This is the part that actually blew my mind.

I was staring at the accepted code, and suddenly a blurred memory from a Number Theory course I just studied for my college end-sems hit me. There’s a thing called Lagrange's Four-Square Theorem(I didn't know the name, I just knew the theory, googled the name before writing blog). It mathematically proves that any natural number can be represented as the sum of at most 4 perfect squares. Wait... if any difference between a and b can be made using at most 4 perfect squares, then the maximum distance in this entire graph is literally just 4!!

I didn't need the bfs at all! If my code checks 0, 1, 2, and 3, and they all fail... the answer is just 4 by mathematical law. I deleted the entire BFS function entirely and just wrote this:

// ... after d3 check fails ...
if(d3) {
    cout << 3 <<endl;
    continue;
}

// the theorem says if its not 0/1/2/3, its 4.
cout << 4 <<endl;

Submitted it. Accepted. 375610826 I was so hyped! Even though I couldn't get it in time during the contest because of my panic bug, actually solving a Div2 F and having a random college math theorem perfectly replace a graph algorithm was the best feeling ever. Even though I didn't perform better in the college exam in that course (due to last minute preparation), it made me hyped up.

Let me know your thoughts on this!?