So the 2020 South African Programming Olympiad was yesterday, and someone thought it would be a good idea to put an output-only problem in the exam.

I thought the problem was quite interesting, although I could only get 52 points during the contest. The problem statement can be found here and the input files can be found at https://saco-evaluator.org.za/cms/sapo2020z

I think it's similar to Nowruz from IOI 2017, although BFS only achieves ~5 points instead of ~80... I heard that there's a relatively simple greedy algorithm that scores 60 points though (but no contestants found it during the contest).

Do any of you have any ideas about how to solve this problem? I'd love to hear them in the comments below.

With IOI just around the corner, some of you may be wondering: "what should I do after I AK after 3 hours?"

In this post, I'll share some activities that you can do to pass the time!

(Note that some of these may not be applicable for an online IOI)

Level 1 — Built-in software on your computer

The most obvious thing you can do is use the built-in stuff. I'm talking about playing Minesweeper, reading the C++ documentation, or anything similar.

While Minesweeper is quite fun and the C++ documentation is... interesting, Minesweeper quickly becomes boring and you'll look like a huge nerd if you read the documentation (and you don't want that, do you?)

That's why I'll only recommend this if you're a noob and only AK in 4 hours.

Level 2 — Creating software

So you've beaten Minesweeper 10 times already and read through the C++ documentation twice. What next? Well, you've got some mad programming skills — why not put them to good use for once?

You've got (almost) everything you need on your IOI computer to create the next Facebook or Google. Try making some cool software to kill the time! For example, I made this beautiful Japanese flag during the practice contest of IOI 2019. Of course, you can also make something more abstract if you're into that kind of thing.

This is my favourite option, but if you're looking for something spicier...

Level 3 — Entertaining yourself using other contestants

I'm not saying that you have to get up and talk to the other contestants (not that you can anyway), but you can look around and gather some pretty interesting statistics. Who has the loudest keyboard? Who types the fastest? What is the modal shirt colour?

Alternatively, you can imagine what's going on in the other contestants' heads. Did that sleeping Canadian guy also AK or has he just given up? Which problem is that Slovakian guy next to you hammering away at his keyboard working on now? What about that crying Portuguese guy with the group of scientific committee members gathered around his computer, shaking their heads in disbelief? How is his day going?

Level 4 — Implementing your solutions again in other languages

Ok, I get it — you're no fun and only want to do something related to the IOI. That's perfectly fine and I've got just the activity for you!

Try implementing your solutions in another language! Implementing your solutions again but in Java (or C++ if you're one of those people) is a fun (albeit not very rewarding) challenge. But you know what is a rewarding challenge? Implementing your solutions in Scratch, of course!

("But I don't have access to the online Scratch editor!" You have access to a normal text editor, no?)

Conclusion

These are all the potential activities I could think of. Of course, I've never been able to try them out (but maybe some of you will be able to).

I'd love to hear about other potential activities suggested by you in the comments below!

One of the many reasons why SAPO is the best informatics Olympiad is that we're allowed to submit solutions in Scratch (TianCilliers wrote a CMS plugin to support Scratch a while ago)

The second round of SAPO 2020 was held earlier this week, so obviously I had to try to solve the problems using Scratch.

The problems were:

• Given X, Y, and N, output N / X + N / Y - N / lcm(X, Y).
• Add two given numbers in base B for a given B.
• This problem but modulo 1e8.
• Given a tree and some paths, find the number of edges in the union of those paths.

I was able to solve the first and third problems this way:

but I couldn't implement the second and fourth problems.

As you can see in the code for problem 3, working with multiple arrays is a bit of a nightmare.

I feel like problem 2 is solvable using Scratch (albeit very painfully), but since Scratch doesn't have 2D arrays, I don't see how one could solve problem 4 using Scratch.

Do any of you have ideas about how one can work with graphs using Scratch?

(P.S. my other Scratch implementations are available at https://github.com/dolphingarlic/ScrAtChO)

EDIT: Thanks to -is-this-fft-, I was able to implement a solution for problem 4. https://scratch.mit.edu/projects/419364160

Introduction

I've come across several problems that require you to be able to efficiently find the sum of some values on a path from $$$A$$$ to $$$B$$$ in a tree. One can solve these problems using tree decomposition techniques like heavy-light decomposition or centroid decomposition, but that's a bit of an overkill and not very elegant in my opinion.

In this blog post, I will describe a way to solve these types of problems using just a DFS, a Fenwick tree, and LCA (as well as a way to solve JOIOC 2013 Synchronization this way).

Note: Whenever I talk about edge $$$(u, v)$$$ in this post, I assume that $$$u$$$ is the parent of $$$v$$$.

Prerequisites

• DFS
• Preorder traversal (DFS order)
• Fenwick tree
• Binary lifting and LCA

The idea

Say you have the following problem:

Given a tree with $$$N$$$ nodes, each node $$$i$$$ has a value $$$a_i$$$ that is initially 0. Support the following 2 types of operations in $$$O(\log N)$$$ time:

1. Increase the value of $$$a_i$$$ by $$$X$$$
2. Find the sum of $$$a_i$$$ on the path from $$$u$$$ to $$$v$$$ for 2 nodes $$$u$$$ and $$$v$$$

First, we flatten the tree using a preorder traversal. Let the time we enter node $$$i$$$ be $$$tin_i$$$ and the time we exit it be $$$tout_i$$$. Additionally, let $$$b$$$ be an array/Fenwick tree of size $$$2N$$$.

If you're familiar with LCA, you'll know that node $$$u$$$ is an ancestor of node $$$v$$$ if and only if $$$tin_u \leq tin_v$$$ and $$$tout_u \geq tout_v$$$.

If you're familiar with range updates and point queries with Fenwick trees, you'll know that if we want to increase the range $$$[A, B]$$$ by $$$X$$$ in an array/Fenwick tree $$$BIT$$$, then we increase $$$BIT[A]$$$ by $$$X$$$ and decrease $$$BIT[B + 1]$$$ by $$$X$$$. Then when we want to find the value of the element at $$$C$$$, we simply query the sum of $$$BIT[i]$$$ for each $$$i$$$ from 0 to $$$C$$$. This works because if $$$C$$$ isn't inside the range of an update, the 2 values we update "cancel out" in the query.

We can combine the 2 ideas above to work on trees — if we want to increase the value of node $$$u$$$ by $$$X$$$, we increase $$$b[tin_u]$$$ by $$$X$$$ and decrease $$$b[tout_u + 1]$$$ by $$$X$$$. Then when we want to find the sum of nodes on the path between node $$$v$$$ and the root, we simply query the sum of $$$b[i]$$$ for each $$$i$$$ from 0 to $$$tin_v$$$. This works because node $$$w$$$ only contributes to the sum if $$$w$$$ is an ancestor of $$$v$$$.

We can then use LCA and the principle of inclusion-exclusion to find the sum of nodes/edges on the path between nodes $$$u$$$ and $$$v$$$.

This idea also works if we want to sum edges instead of nodes — when we update edge $$$(u, v)$$$, update $$$b[tin_v]$$$ and $$$b[tout_v + 1]$$$ and make queries similarly.

Problem 1 — Infoarena Disconnect

Here's the gist of the problem:

You're given a tree with $$$N$$$ nodes. Process $$$M$$$ of the following queries online:

1. Delete the edge $$$(u, v)$$$ from the path.
2. Determine whether there is a path from $$$u$$$ to $$$v$$$.

$$$N \leq 10^5$$$ and $$$M \leq 5 \cdot 10^5$$$

Solution

Let the value of each edge in the tree initially be 0. When we "delete" an edge, we just update its value to be 1.

Notice how there is a path from $$$u$$$ to $$$v$$$ if and only if the sum of edges on the path between $$$u$$$ and $$$v$$$ is 0.

We can then apply the above idea and solve this problem in $$$O(M \log N)$$$ time.

Alternatively,

• Find the lowest ancestor $$$l_u$$$ of $$$u$$$ such that the sum of the edges between $$$u$$$ and $$$l_u$$$ is 0
• We can do this using binary lifting and our trick
• Find $$$l_v$$$ similarly for $$$v$$$.
• Check whether $$$l_u$$$ is an ancestor of $$$v$$$ and whether $$$l_v$$$ is an ancestor of $$$u$$$.

This solution runs in $$$O(M \log^2 N)$$$ time.

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, m;

vector<int> graph[100001];
int timer = 1, tin[100001], tout[100001];
int anc[100001][18];

void dfs(int node = 1, int parent = 0) {
    anc[node][0] = parent;
    for (int i = 1; i < 18 && anc[node][i - 1]; i++)
        anc[node][i] = anc[anc[node][i - 1]][i - 1];

    tin[node] = timer++;
    for (int i : graph[node]) if (i != parent) dfs(i, node);
    tout[node] = timer;
}

int bit[100001];

void update(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }

int query(int pos) {
    int ans = 0;
    for (; pos; pos -= (pos & (-pos))) ans += bit[pos];
    return ans;
}

int find_ancestor(int node) {
    int lca = node;
    for (int i = 17; ~i; i--) {
        if (anc[lca][i] && query(tin[anc[lca][i]]) == query(tin[node])) lca = anc[lca][i];
    }
    return lca;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("disconnect.in", "r", stdin);
    freopen("disconnect.out", "w", stdout);
    cin >> n >> m;
    FOR(i, 1, n) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    dfs();

    int v = 0;
    while (m--) {
        int t, x, y;
        cin >> t >> x >> y;
        int a = x ^ v, b = y ^ v;

        if (t == 1) {
            if (anc[b][0] == a) swap(a, b);
            update(tin[a], 1);
            update(tout[a], -1);
        } else {
            if (find_ancestor(a) == find_ancestor(b)) {
                cout << "YES\n";
                v = a;
            } else {
                cout << "NO\n";
                v = b;
            }
        }
    }
    return 0;
}

Problem 2 — JOIOC 2013 Synchronization

Here's the gist of the problem:

You're given a tree with $$$N$$$ nodes. Each edge is initially deactivated and each node stores a unique piece of information.

There are $$$M$$$ events. During event $$$i$$$, the state of exactly 1 edge is toggled.

When the edge $$$(u, v)$$$ becomes activated, $$$u$$$'s component and $$$v$$$'s component merge and "sync up". All nodes in the merged component will contain all the information stored on the other nodes in the component.

After all these events, you want to know how many unique pieces of information are stored in each node.

$$$N \leq 10^5$$$ and $$$M \leq 2 \cdot 10^5$$$

Solution

Firstly, root the tree arbitrarily. Let $$$a_i$$$ be the amount of unique information stored on node $$$i$$$. Let $$$c_i$$$ be the amount of unique information stored on node $$$i$$$ right before the edge from node $$$i$$$ to its parent was deactivated.

Notice how if we make the edge $$$(u, v)$$$ activated, then the new amount of information on all nodes in the merged component is $$$a_u + a_v - c_v$$$.

This gives us a way to find the amount of information on the merged component, but we still need a way to set each node in the component to have that amount of information.

Fortunately, we don't have to do that!

Since each node in a component has the same amount of information, we can just store that amount in the "root" (i.e. the lowest node) of the component. Let the root of $$$i$$$'s component be $$$root[i]$$$. The amount of information stored on $$$i$$$ is thus $$$a_{root[i]}$$$.

When we deactivate the edge $$$(u, v)$$$, $$$v$$$ becomes the root of its new component and $$$root[u]$$$ doesn't change. This means we can simply set $$$a_v$$$ and $$$c_v$$$ to equal $$$a_{root[u]}$$$ when that happens (we don't care what $$$a_v$$$ and $$$c_v$$$ were before this).

But how do we find the root of a component?

$$$root_u$$$ is the lowest ancestor of $$$u$$$ such that the path from $$$u$$$ to $$$root_u$$$ contains no deactivated edges. We can thus use the same idea we used for the previous problem, but this time, all edges initially have their weight equal to 1 instead of 0.

Using binary lifting, we can find the root of any component in $$$O(\log^2 N)$$$ time.

This solution runs in $$$O(M \log^2 N)$$$ time.

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, m, q;
bool active[100001];
vector<int> graph[100001];
pair<int, int> edges[200001];

int info[100001], last_sync[100001];

int timer = 1, tin[100001], tout[100001];
int anc[100001][20];

void dfs(int node = 1, int parent = 0) {
    anc[node][0] = parent;
    for (int i = 1; i < 20 && anc[node][i - 1]; i++) {
        anc[node][i] = anc[anc[node][i - 1]][i - 1];
    }

    info[node] = 1;

    tin[node] = timer++;
    for (int i : graph[node]) if (i != parent) dfs(i, node);
    tout[node] = timer;
}

int bit[100001];

void update(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; }

int query(int pos) {
    int ans = 0;
    for (; pos; pos -= (pos & (-pos))) ans += bit[pos];
    return ans;
}

int find_ancestor(int node) {
    int lca = node;
    for (int i = 19; ~i; i--) {
        if (anc[lca][i] && query(tin[anc[lca][i]]) == query(tin[node])) lca = anc[lca][i];
    }
    return lca;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    FOR(i, 1, n) {
        cin >> edges[i].first >> edges[i].second;
        graph[edges[i].first].push_back(edges[i].second);
        graph[edges[i].second].push_back(edges[i].first);
    }
    dfs();

    FOR(i, 1, n + 1) {
        update(tin[i], -1);
        update(tout[i], 1);
    }

    while (m--) {
        int x;
        cin >> x;
        int u = edges[x].first, v = edges[x].second;
        if (anc[u][0] == v) swap(u, v);

        if (active[x]) {
            info[v] = last_sync[v] = info[find_ancestor(u)];
            update(tin[v], -1);
            update(tout[v], 1);
        } else {
            info[find_ancestor(u)] += info[v] - last_sync[v];
            update(tin[v], 1);
            update(tout[v], -1);
        }
        active[x] = !active[x];
    }

    while (q--) {
        int x;
        cin >> x;
        cout << info[find_ancestor(x)] << '\n';
    }
    return 0;
}

Conclusion

I hope you've learned something from this tutorial. If anything is unclear, please let me know in the comments below.

Additional problems

• COCI 2020 Putovanje
• JOI 2015 Railroad but on a general tree instead of a line
• USACO 2015 Max Flow
• SACO 2015 Towers (Doesn't use a Fenwick tree but has a similar idea)

I think IOI 2010 Languages is a very interesting (but also slightly annoying) problem — not only is it one of the few IOI problems that use machine learning, but the maximum score is 110 points instead of the usual 100.

Because of how unusual the problem is, there are relatively few people who try to solve it and far fewer with more than 100 points.

I've recently been trying to push the limits on how many points I can score. So far, I've managed to score 102 points on Yandex — the highest score I'm aware of.

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;

#include "grader.h"

const int SZ = 100, LANGS = 56, MOD = 539653;

ll si[SZ], bi[SZ], tr[SZ], qu[SZ];
double cnt[LANGS];
int freq[LANGS][MOD];

inline double hyperb(int x) { return x / (x + 1.1); }

void excerpt(int *E) {
    FOR(i, 0, SZ - 3) {
        si[i] = E[i];
        bi[i] = ((si[i] << 16) + E[i + 1]) % MOD;
        tr[i] = ((bi[i] << 16) + E[i + 2]) % MOD;
        qu[i] = ((tr[i] << 16) + E[i + 3]) % MOD;
    }

    int best = 0;
    double best_sim = 0;
    FOR(i, 0, LANGS) {
        double sim = 0;
        FOR(j, 0, SZ - 3) {
            sim += hyperb(freq[i][qu[j]]) * 6;
            sim += hyperb(freq[i][tr[j]]);
            sim += hyperb(freq[i][bi[j]]) * 4;
            sim += hyperb(freq[i][si[j]]);
        }
        sim /= log(cnt[i] + 2);

        if (sim > best_sim) best = i, best_sim = sim;
    }

    int ans = language(best);
    cnt[ans]++;
    FOR(i, 0, SZ - 3) {
        freq[ans][qu[i]]++;
        freq[ans][tr[i]]++;
        freq[ans][bi[i]]++;
        freq[ans][si[i]]++;
    }
}

I found the correct weights by trial and error, so there's obviously a lot of room for improvement.

Here's my question: how high can we (realistically) go? A score of 103 points requires at least 93.6% accuracy, but my code only has an accuracy of 92.8%

All these blog posts about how people went from rank X to rank Y in Z days/months/years has been very inspiring and absolutely not at all overdone. However, (almost) every person whose post I've read has completely missed the point: their rating went up instead of down.

Think about it — would you rather be in 3000th place in a competition or 1000th place? That's right — lower is better. End of story. Codeforces even rewards you for having a low rating! What is the colour of AC? Green. What's the colour of the "pupil" rank? Green. Coincidence? I think not.

Now, time for my story. I went from 1500 to 1357 in just 10 days! No need to be jealous — I will now describe precisely how I did it.

My first contest was the 2018 Lyft Level 5 Challenge. As a newcomer to competitive programming, I had no idea what to expect.

Miraculously, I solved 1 problem. Was it pure skill? Was it beginner's luck? I guess we'll never know. But what we do know is that a single problem was enough to bring my rating from 1500 to 1403.

Not quite enough to become green, but I didn't lose hope.

My next contest was the 2018 Mail.Ru Cup. Again, I solved 1 problem. This time, it was enough to bring my rating to 1357 — comfortably in the green range.

This story proves that no matter who you are and what experience you had, you too can become green.

(Unfortunately, my skill has deteriorated significantly in the past 2 years and I am now orange — the colour of RTE)

Want to upsolve OI problems but feel overwhelmed by the sheer number of them? Spending too much time choosing between OI problems to upsolve? Just want to discover and solve new OI problems you've never heard of?

If you answered "yes" to any of these, you're in luck! I've made a Discord bot that sends random daily OI problems. Why spend time choosing problems to upsolve when a computer can do it for you?

This bot gets problems from APIOIPA — an API for OI problems I made. (Feel free to use it for your projects as well!)

Simply join this Discord server and let the magic happen!

Update 23/05: I recently updated the bot, so now it will send a daily problem to any server it's in with a channel named #problem-of-the-day or #potd. Add the bot to your server to receive problems there if you don't feel like joining a random server.

Not satisfied by 1 problem per day? You can also use the command $gimme for more random problems.

(Note: The problems are chosen at random and there are only about 700 problems in my database, so there will occasionally be repeated problems. Also, please don't spam.)

You can also host the bot yourself if you want to use it in other servers.

Firstly, huge thanks to Noam527 for guiding me to this solution by providing his output for N = 255. This probably wouldn't have been possible without his help.

As some of you may know, getting 100 points for IOI 2003 Reverse is pretty difficult. The editorial only explains an 88-point solution and there seemed to be no publicly-available code online that scored 100 points when I solved it.

This blog post serves as a tutorial for those who are stuck with 88 points (or less) but who would like 100 points (to fill in that last yellow cell on OIChecklist or just to flex).

88-point solution

I'll just quote the editorial for this.

Consider the case of trying to solve each input with only one S-operation. Clearly, register 1 might as well as be initialized to N. The register 2 can be N - 2. After printing out N, one S-operation turns register 1 to N - 1. Register 3 can be N - 5. After printing N - 2, S 3 1 makes register 1 N - 4. After printing out N - 2, S 1 2 turns register 2 into N - 3, the next value to output. Continuing this through all the registers, 44 is the largest value of N which can be solved in only one S-operation. This algorithm scores 90% of the points if extended to dealing with multiple operations.

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, k, reg[9];
int lim[8]{8, 44, 80, 116, 152, 188, 224, 260};

void INIT(int V, int P) {
    printf("%d", V);
    if (P == 8) printf("\n");
    else printf(" ");
    reg[P] = V;
}

void ADD(int A, int B) {
    reg[B] = reg[A] + 1;
    printf("S %d %d\n", A + 1, B + 1);
}

int FIND(int V) { return find(reg, reg + 9, V) - reg; }

void PRINT(int P) { printf("P %d\n", P + 1); }

int main() {
    scanf("%d %d", &k, &n);
    printf("FILE reverse %d\n", k);

    int mx = lower_bound(lim, lim + 8, n) - lim;

    int c = n;
    FOR(i, 0, 9) {
        INIT(max(0, c), i);
        c -= mx * i + mx + 1;
    }

    int nxt = 1, curr = -1, rising = 1;
    n++;
    while (n--) {
        int pos = FIND(n);
        if (pos == 9) {
            FOR(i, 1, mx + 1) {
                pos = FIND(n - i);
                if (pos != 9) {
                    ADD(pos, curr);
                    FOR(j, 1, i) ADD(curr, curr);
                    PRINT(curr);
                    break;
                }
            }
        } else {
            if (pos == rising && nxt != 8) rising = ++nxt;
            if (~curr && mx && reg[rising] + mx < n) {
                ADD(rising, curr);
                FOR(i, 1, mx) ADD(curr, curr);
                rising = curr;
            }
            PRINT(pos);
            curr = pos;
        }
    }
    return 0;
}

The code for 88 points is pretty clean and elegant. Most people would stop here. However, if you hate yourself want a challenge, then you'd probably try to get 100 points.

100-point solution

The 100-point solution is a relatively simple extension of the 88-point solution.

With the 88-point solution, the only test cases where we won't get AC are the cases with N = 97 (MAX_S = 2) or N > 188 (MAX_S = 4).

Consider the output of the 88-point code for N = 97 (the optimal MAX_S is 2; the MAX_S here is 3):

97 93 86 76 63 47 28 6 0
P 1
S 2 1
S 1 1
S 1 1
P 1
S 2 1
S 1 1
P 1
S 2 1
P 1
S 3 1
S 1 1
S 1 1
P 2
S 1 2
S 2 2
S 2 2
P 2
S 1 2
S 2 2
P 2
S 1 2
P 2
etc.

Notice anything inefficient?

That's right — we can use up to 3 consecutive S-operations but there are many places where we only use 1 or 2 consecutive S-operations. We are effectively wasting S-operations.

Moreover, we can increment any of the 9 values but for each block of consecutive S-operations, we only increase 1.

Here are the first few lines of output for the same case but with the 100-points code:

97 94 89 81 70 56 39 19 0
P 1
S 2 1
S 1 1
P 1
S 2 1
P 1
S 3 1
S 1 1
P 2
S 1 2
S 2 2
P 2
S 1 2
P 2

This is quite similar to the previous output (albeit with only 2 consecutive S-operations instead of 3), but it's the next few lines we should be interested in:

S 4 2
S 2 2
P 1
S 3 1
S 2 2
P 1

Notice how in the 4th and 5th lines, instead of only increasing the value from 1 register, we increase the value from 2 separate registers.

This means that we can waste fewer S-operations! Whereas the 88-point solution would alternate between 1 S-operation and 2 S-operations, the 100-point solution would have sections with only 2 consecutive S-operations, like

S 2 1
S 3 3
P 1
S 4 1
S 1 1
P 2
S 3 2
S 2 2
P 1
S 4 1
S 2 2
P 1
S 2 1
S 1 1
P 4

If we continue this pattern, we notice 2 things:

• The consecutive differences between the starting values of the registers (excluding the first) for an arithmetic sequence of the form $$$3N + 2$$$
• There are 2 types of "cycles" — type 1 is when we "fill in" wasted S-operations (like above) and type 2 is when we simply follow the strategy of the 88-point solution. We start on a type 2 cycle and whenever we need to print a value that is already present in some register, we switch to the other cycle.

Using this new strategy, we can use only 2 consecutive S-operations for up to N = 101!

It turns out that if we use the arithmetic sequence $$$9N$$$ instead of $$$3N + 2$$$, this strategy also works for 4 consecutive S-operations for up to N = 257.

I found the implementation for this to be quite tricky and I had to use the 88-point code for MAX_S != 2 and MAX_S != 4.

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

int n, k, reg[9];
int lim[5]{8, 44, 97, 116, 257};

void INIT(int V, int P) {
    printf("%d", V);
    if (P == 8) printf("\n");
    else printf(" ");
    reg[P] = V;
}

void ADD(int A, int B) {
    printf("S %d %d\n", A + 1, B + 1);
    reg[B] = reg[A] + 1;
}

int FIND(int V) { return find(reg, reg + 9, V) - reg; }

void PRINT(int P) { printf("P %d\n", P + 1); }

int main() {
    scanf("%d %d", &k, &n);
    printf("FILE reverse %d\n", k);

    int mx = lower_bound(lim, lim + 8, n) - lim;

    if (mx == 4 || mx == 2) {
        int c = n, diff1 = (mx == 2 ? 3 : 9), diff2 = (mx == 2 ? 2 : 0);
        INIT(c, 0);
        INIT(c - mx - 1, 1);
        c -= mx + 1;
        FOR(i, 1, 8) {
            c -= i * diff1 + diff2;
            INIT(max(c, 0), i + 1);
        }

        int nxt = 2, curr, rising = -1;
        queue<int> to_rise;
        bool twice = true;

        n++;
        while (n--) {
            curr = FIND(n);
            PRINT(curr);
            if (!n) break;

            int pos = FIND(n - 1);
            if (pos == 9) {
                FOR(i, 1, mx + 1) {
                    pos = FIND(n - 1 - i);
                    if (pos != 9) {
                        ADD(pos, curr);
                        for (int j = 1; j < i && reg[curr] < n - 1; j++) ADD(curr, curr);

                        if ((i != mx - 1 || mx == 2) && twice && rising > -1 && rising < 9 && rising != pos)
                            for (int j = i; j < mx && reg[rising] < n - 1; j++) ADD(rising, rising);

                        break;
                    }
                }
            } else {
                twice = !twice;
                if (twice && nxt != 9) {
                    if (!to_rise.size()) {
                        nxt++;
                        FOR(i, 0, nxt - 2) to_rise.push(reg[nxt] + i * diff1);
                    }
                    rising = FIND(to_rise.front());
                    to_rise.pop();
                } else {
                    FOR(j, 2, 2 * mx + 3) {
                        rising = FIND(n - j);
                        if (rising != 9) break;
                    }
                }

                if (rising != 9) {
                    ADD(rising, curr);
                    for (int i = 1; i < mx && reg[curr] < n - 2; i++) ADD(curr, curr);
                    rising = curr;
                }
            }
        }
    } else {
        int c = n;
        FOR(i, 0, 9) {
            INIT(max(0, c), i);
            c -= mx * i + mx + 1;
        }

        int nxt = 1, curr = -1, rising = 1;
        n++;
        while (n--) {
            int pos = FIND(n);
            if (pos == 9) {
                FOR(i, 1, mx + 1) {
                    pos = FIND(n - i);
                    if (pos != 9) {
                        ADD(pos, curr);
                        FOR(j, 1, i) ADD(curr, curr);
                        PRINT(curr);
                        break;
                    }
                }
            } else {
                if (pos == rising && nxt != 8) rising = ++nxt;
                if (~curr && mx && reg[rising] + mx < n) {
                    ADD(rising, curr);
                    FOR(i, 1, mx) ADD(curr, curr);
                    rising = curr;
                }
                PRINT(pos);
                curr = pos;
            }
        }
    }
    return 0;
}

Unfortunately, when I used $$$6N + 1$$$ for the MAX_S = 3 case, it got RTE on some cases. This didn't matter though since the test data was weak enough for a sub-optimal MAX_S = 3 solution to pass. However, I believe it should work for up to N = 179.

If anyone can improve my code or make it more general, please let me know in the comments. Additionally, if anything isn't clear, please let me know so I can try to fix it.

Hi everyone! An awesome teammate (thanks TianCilliers) decided to scrape the IOI scoreboard to get the country rankings (by points). Here it is:

1	USA			1815	3G	1S	0B
2	Russia			1780	4G	0S	0B
3	China			1779	3G	1S	0B
4	Iran			1604	1G	3S	0B
5	Korea			1586	2G	1S	1B
6	Japan			1581	1G	3S	0B
7	France			1554	1G	3S	0B
8	Việt Nam		1527	2G	1S	1B
9	Taiwan			1494	2G	0S	2B
10	Bulgaria		1492	1G	2S	1B
11	Ukraine			1466	1G	2S	1B
12	Slovakia		1408	0G	3S	1B
13	Indonesia		1397	1G	2S	1B
14	Canada			1380	1G	1S	1B
15	Israel			1362	0G	2S	2B
16	Australia		1361	1G	1S	2B
17	Hong Kong		1351	0G	2S	2B
18	Romania			1343	0G	2S	2B
19	Kazakhstan		1338	1G	1S	2B
20	Croatia			1327	0G	2S	2B
21	Singapore		1306	1G	1S	1B
22	Lithuania		1300	0G	2S	1B
23	Belarus			1268	0G	2S	2B
24	Serbia			1228	0G	1S	3B
25	Georgia			1195	1G	0S	2B
26	Italy			1186	0G	0S	3B
27	Czechia			1161	0G	2S	1B
28	Sweden			1159	0G	1S	3B
29	Poland			1158	0G	2S	1B
30	Hungary			1154	1G	0S	1B
31	Thailand		1145	0G	1S	2B
32	Estonia			1108	0G	1S	2B
33	India			1048	0G	1S	1B
34	Germany			1046	0G	0S	3B
35	Latvia			1043	0G	0S	2B
36	Turkey			1041	0G	1S	1B
37	North Macedonia		1037	0G	0S	2B
38	Bangladesh		1029	0G	0S	3B
39	Kyrgyzstan		1022	0G	0S	3B
40	Moldova			983	0G	1S	1B
41	Syrian Arab Republic	973	0G	0S	2B
42	Mexico			966	0G	0S	2B
43	Finland			962	0G	0S	2B
44	Philippines		946	0G	0S	1B
45	South Africa		910	0G	0S	0B
46	Egypt			908	0G	0S	1B
47	Brazil			904	0G	0S	1B
48	United Kingdom 		879	0G	0S	2B
49	Switzerland		876	0G	0S	2B
50	Greece			846	0G	0S	1B
51	Argentina		842	0G	1S	0B
52	Portugal		831	0G	1S	0B
53	Belgium			827	0G	0S	0B
54	Slovenia		824	0G	0S	2B
55	Malaysia		817	0G	0S	1B
56	Macao			805	0G	0S	0B
57	Mongolia		795	0G	1S	0B
58	New Zealand		787	0G	0S	1B
59	Netherlands		768	0G	0S	1B
60	Norway			767	0G	0S	1B
61	Azerbaijan		752	0G	0S	0B
62	Ireland			699	0G	0S	1B
63	Tunisia			645	0G	0S	0B
64	Chile			634	0G	0S	0B
65	Jordan			626	0G	1S	1B
66	Cyprus			620	0G	0S	0B
67	Denmark			598	0G	0S	0B
68	Saudi Arabia		573	0G	0S	1B
69	Morocco			518	0G	0S	0B
70	Austria			514	0G	0S	0B
71	Spain			508	0G	0S	0B
72	Bosnia and Herzegovina	484	0G	0S	0B
73	Uzbekistan		477	0G	0S	0B
74	Colombia		463	0G	0S	0B
75	Tajikistan		451	0G	0S	0B
76	Sri Lanka		382	0G	0S	0B
77	Montenegro		278	0G	0S	0B
78	Turkmenistan		241	0G	0S	0B
79	Luxembourg		241	0G	0S	0B
80	El Salvador		219	0G	0S	0B
81	Cuba			205	0G	0S	0B
82	Iceland			157	0G	0S	0B
83	Nigeria			146	0G	0S	0B
84	Bolivia			145	0G	0S	0B
85	Palestine		102	0G	0S	0B
86	Dominican Republic	64	0G	0S	0B
87	Venezuela		25	0G	0S	0B

Fun fact: South Africa was the best country not to have gotten a single medal this year (bruh)

(3 of our team members were within 1 point of each other)

Hi everyone! I thought it would be a good idea to create a shared Google Photos album for the participants of IOI 2019 to add their photos. Here is the link to the album:

https://photos.app.goo.gl/Mu8YQc5VjYoKUyG29

Mirror, Mirror on the Wall, Who’s the Fairest of Them All?

What do all of you think is the prettiest online judge out there?

My vote goes to oj.uz, with Atcoder coming a close second

(Sorry, codeforces. You're just not aesthetically pleasing enough)

Do you have nothing to do on Sunday the 10th of February and want to speedrun a South African training camp contest? Are you feeling down and need to flex on the South African IOI team to get your spirits back up? Are you just looking for a live contest to participate in because of your insatiable need for competition?

Well, you're in luck! On Sunday the 10th of February, South Africa will be holding a training camp contest that will be open to the public!

As some of you may remember, South Africa will now be hosting all future contests on our own CMS page. For those of you who don't, that page in question is https://www.saco-evaluator.tk. All future contests held on there will most likely be open to the public.

Simply head to https://www.saco-evaluator.tk, register for an account, and wait until 9:00 AM SAST to participate in the contest. Live rankings can be found at https://www.saco-evaluator.tk/rws. (Sorry for the inconvenient times)

Note: If you want your name to show up on the rank list, you must register on the website the day before the contest or earlier.

Good luck and have fun!

Has it always been your lifelong dream to flex on the South African IOI team? Or maybe you've run out of problems to solve and want to solve more? Or maybe you just want a self-confidence boost from solving some somewhat easy problems?

Well, you're in luck!

South Africa will (hopefully) be using a CMS page open to the public for all future olympiads and camps.

Simply go to https://saco-evaluator.tk/ and register for an account to solve our problems and/or flex on the South African IOI team by getting perfect scores in under an hour.

Currently, there is only 1 "contest" with 6 problems running, but more will be made in due time. Solutions can only be submitted in C++ or Java right now, but Python3 support will probably be added later in the year.

The scoreboard can be found at https://saco-evaluator.tk/rws/. (The scoreboard takes a while to update rankings, so don't be alarmed when your name doesn't show up on the scoreboard at first)