algo/baby-game

345 solves / 272 points

Writeup by Aryan

The problem statement is quite simple.

We are given two players Caring Koala and Red Panda, who are on an n x n grid, and Koala moves first. In a turn, each player can move exactly one square in any of the orthogonal directions. The winner is the first player to move to the square occupied by the other player. Furthermore, we receive a guarantee that the players have knowledge about whether they are destined to win or lose. If a player can win, they will win as soon as possible; conversely, if a player can only lose, they will try to delay said loss as long as possible.

We are given n <= 3 * 10^5, as well as integers x1, y1, x2, y2, where (x1, y1) is Caring Koala's starting position and (x2, y2) is Red Panda's starting position. We are requested to output the winner name.

The challenge is easily cheesable, as test cases are not randomly generated, so one could hard-code the solution, but it is easier to just solve it. In order to solve it, we can just compute the Manhattan Distance between the points -- defined as abs(x1 - x2) + abs (y1 - y2) -- if it is odd, Caring Koala will win, and otherwise Red Panda will win.

This solution is hardly a few lines of code, so one does not need to prove it, but it can intuitively be proven.

For d=1, it is obvious Koala wins.

For d=2, Koala does not want to move closer to Panda, because after Koala moves d=1 and Panda will win. Thus, Koala will keep moving away from Panda until he gets cornered, at which point Panda will be able to win.

This pattern will repeat, where if d ≡ 1 (mod 2), then Koala wins, and otherwise Panda wins.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n;
    int x1, y1, x2, y2;
    
    cin >> n;
    cin >> x1 >> y1 >> x2 >> y2;
    
    int manhattan_distance = abs(x1 - x2) + abs(y1 - y2);
    
    if (manhattan_distance % 2 == 1) {
        cout << "Caring Koala" << endl;
    } else {
        cout << "Red Panda" << endl;
    }
    
    return 0;
}

Flag: vsctf{baby_game_pure_luck_uwu}