IOI 2003 Reverse - 100-point solution
Разница между en1 и en2, 6,160 символ(ов) изменены
Firstly, huge thanks to [user:Noam527,2020-04-07] 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](https://contest.yandex.ru/ioi/contest/558/problems/C/) is [pretty](https://mirror.codeforces.com/blog/entry/66014?#comment-499829) [difficult](https://contest.yandex.ru/ioi/contest/558/standings/). The [editorial](https://github.com/mostafa-saad/MyCompetitiveProgramming/blob/master/Olympiad/IOI/official/2003/reverse.pdf) 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
 solution.↵

> 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.

<spoiler summary="My code for 88 points">```cpp↵
#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;↵
}↵
```↵
</spoiler>↵

The code for 88 points is pretty clean and elegant. Most people would stop here. However, if you <s>hate yourself</s> 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 
youwe won't get AC are probably 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 &mdash; 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" &mdash; 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.↵

![Example of type 1/type 2](/predownloaded/b0/55/b055e6965c031478dca7ad72793e13867160ece2.png)↵

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`.↵

<spoiler summary="My (somewhat messy) code for 100 points">```cpp↵
#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;↵
}↵
```↵
</spoiler>↵

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский dolphingarlic 2020-04-08 10:41:12 11
en2 Английский dolphingarlic 2020-04-08 10:40:02 6160 Tiny change: '00 points>\n```cpp\n#i' -> '00 points>```cpp\n#i' (published)
en1 Английский dolphingarlic 2020-04-08 09:23:37 4156 Initial revision (saved to drafts)