algo/baby-game-revisited

13 solves / 495 points

Writeup by Aryan

I cheesed this problem, so if you want an actual writeup, look somewhere else.

The problem statement is quite similar to baby-game except now Red Panda can move one or two squares. Caring Koala is still constrained to a max move of one square.

I started taking a look at this problem when there was less than an hour left in the CTF, and I knew I would not be able to solve it, so I started thinking outside the box.

This time, n <= 25, which presents an interesting opportunity to reverse engineer the cases!

This is possible because of a few factors.

• The judge does not randomize test cases.

• The judge shows the result of all test cases.

• The judge shows the amount of test cases.

• The judge distinguishes between Wrong Answer and Runtime Error.

See the following submission:

#include <iostream>
using namespace std;

int main() {
    int n; cin >> n;
    int a, b, c, d; cin >> a >> b >> c >> d;
    if (n == 3) { // arbitrarily chosen for explanation purposes
        cout << 5/0 << endl;
    } else {
        cout << "skip" << endl;
    }
}

The code 5/0 will result in a Runtime Error, which we can distinguish from a Wrong Answer. We can now figure out which cases have input values of n = 3.

We can see test 26 has n = 3

After figuring out the input n's for all cases, we can try bruteforcing small x in the expressions "Red Panda {x}" and "Caring Koala {x}" to figure out the cases that map to the input n's. Here's an example:

#include <iostream>
using namespace std;

int main() {
    int n; cin >> n;
    int a, b, c, d; cin >> a >> b >> c >> d;
    int x = 1;
    cout << "Caring Koala " << x << endl;
}

We get this output from the above script:

Now, we know test 26 has n = 3 and answer "Caring Koala 1"

Since n <= 25, one can intuitively assume x will be pretty small too, and that turns out to be true, as the largest x ended up being 64 for a case when n=24. I came across an interesting insight here -- namely, that x is always even whenever Red Panda wins -- and there is probably some nice proof, but I was too lazy to think about it.

Once we have the input n and output answer for each case, we are almost ready to write our code. All we need to do is figure out some constraints on a, b, c, and/or d for the scenarios when multiple cases have the same n. We use an approach similar to prior scripts, executing runtime error if certain criteria are met. Finally, we put it all together.

#include <iostream>
using namespace std;

int main() {
    int n; cin >> n;
    int a, b, c, d; cin >> a >> b >> c >> d;
    if (n == 3) {
        cout << "Caring Koala 1";
    } else if (n == 5) {
        cout << "Red Panda 8";
    } else if (n == 25) {
        cout << "Red Panda 56";
    } else if (n == 24) {
        cout << "Red Panda 64";    
    } else if (n == 23) {
        cout << "Red Panda 50";    
    } else if (n == 21) {
        cout << "Red Panda 56";    
    } else if (n == 19) {
        cout << "Red Panda 40";    
    } else if (n == 16) {
        cout << "Red Panda 38";    
    } else if (n == 14) {
        cout << "Red Panda 30";    
    } else if (n == 13) {
        cout << "Red Panda 26";    
    } else if (n == 8) {
        if (a < 5) {
            cout << "Red Panda 16";
        } else {
            cout << "Red Panda 18";
        }
    } else if (n == 6) {
        cout << "Red Panda 14";
    } else if (n == 4) {
        if (a < 3) {
            cout << "Red Panda 8";
        } else {
            cout << "Red Panda 6";
        }
    } else if (n == 18) {
        cout << "Red Panda 38";
    } else if (n == 17) {
        if (a < 9) {
            cout << "Red Panda 48";
        } else {
            cout << "Red Panda 20";
        }
    } else if (n == 7) {
        if (a == 2) {
            cout << "Red Panda 18";
        } else if (b == 2) {
            cout << "Red Panda 16";
        } else {
            cout << "Red Panda 14";
        }
    } else if (n == 15) {
        if (b < 5 || a < 7) {
            cout << "Red Panda 36";
        } else {
            cout << "Red Panda 34";
        }
    } else if (n == 9) {
        if (b == 8 || a >= 7) {
            cout << "Red Panda 20";
        } else if (c != 9) {
            cout << "Red Panda 20";
        } else {
            cout << "Red Panda 16";
        }
    }
    return 0;
}

Flag: vsctf{totally_not_a_dynamic_flag_318de8aa7b123ee9}