Hello! I shall proceed to act schizophrenic for the entirety of this blog post, because I doubt anyone will be reading any of this. I suppose this is a great place to explain some USACO (silver) problems or CSF problems to an imaginary audience; apparently this helps cement ideas or something? Though, I first need to complete a USACO/CFS problem. So ... let me do that rq.

Problem Link: https://mirror.codeforces.com/problemset/problem/2181/B

Log:

• 75s to read problem statement \n
• 23:33, first sub; TLE on test 13. \n
• 37:06, second sub; Happy new year! \n

Code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define str string
#define vec vector
#define prq priority_queue
#define mprq(x) priority_queue<x, vec<x>, greater<x>>
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define print(x) for(auto i : x) {cout << i << " ";} cout << endl;
#define cinVec(x) for(auto& i : x) cin >> i;

const ll MXN = 5e18 + 3, INF = 1e18 + 7;

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

int main() {
    fast_io();
    int t, x; cin >> t;
    while (t--) {
        ll n, m; cin >> n >> m;
        prq<ll> a, b;
        FOR(i, 0, n){
            cin >> x;
            a.push(x);
        }
        FOR(i, 0, m){
            cin >> x;
            b.push(x);
        }
        while (!a.empty() && !b.empty()) {
            ll topA = a.top(), topB = b.top();
            if (topA < topB) {
                b.pop();
                b.push(topB - topA);
            } else {
                b.pop();
            }
            if(a.empty() || b.empty()) break;
            topA = a.top(), topB = b.top();
            if(topA < topB){
                a.pop();
            } else {
                a.pop();
                a.push(topA - topB);
            }
        }
        if (b.empty()) cout << "Alice\n";
        else cout << "Bob\n";
    }
    return 0;
}

Cleaned code (more readable):

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define prq priority_queue
#define FOR(i, a, b) for(ll i = a; i < b; ++i)

void fast_io() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

int main() {
    fast_io();
    int t, x; cin >> t;
    while (t--) {
        ll n, m, tA, tB; cin >> n >> m;
        priority_queue<ll> a, b;
        FOR(i, 0, n){
            cin >> x;
            a.push(x);
        }
        FOR(i, 0, m){
            cin >> x;
            b.push(x);
        }
        while (!a.empty() && !b.empty()) {
            tA = a.top(), tB = b.top();
            b.pop();
            if (tA < tB) b.push(tB - tA);
            if(a.empty() || b.empty()) break;
            tA = a.top(), tB = b.top();
            a.pop();
            if(tA > tB) a.push(tA - tB);
        }
        if (b.empty()) cout << "Alice\n";
        else cout << "Bob\n";
    }
    return 0;
}

Alright, this is basically just a greedy priority queue question. I first did this with vectors, and then I realised that I should probably use priority queues instead, to not hit the TLE. Main concept: Basically, my solution was to be as greedy as possible. That is, the person who is currently having their move should try to reduce the other person's maximum number in their array. So, if it's Alice's turn she will compare her greatest number with Bob's greatest number. If it's larger, Bob will remove his number; otherwise, Bob will reduce his number. Priority queues were used to keep track of each of their largest numbers, as changes were made.

Example:

Alice: 30 30
Bob: 20 20 40

Alice: 30 30
Bob: 10 20 20

Alice: 10 30
Bob: 10 20 20

Alice: 10 30
Bob: 10 20

Alice: 10 10
Bob : 10 20

Alice: 10 10
Bob: 10 10

Alice: 10
Bob: 10 10

Alice: 10
Bob: 10

Alice:
BREAK.

Edit: got off my lazy bum and added an actual explanation instead of ridiculing the problem ;_; Also, what in the world, people are actually reading this (-///-). Sorry, didn't mean to be offensive,, I just got lazy

Alrighty, this has been your daily problem. I will (maybe) post here again if I feel like it. Also this was slightly a troll post because I didn't think people would actually see this, but here I am LMAO.