2021 in Review

I really thought COVID would be over by this December. Making a mockery of last year's review, where I wrote that daily cases were hitting record highs, year-end cases are now approaching ten thousand a day. Still, thanks to the living-with-COVID trial version and the World Finals I went to in the middle of all this, I got around a lot more than last year.

A Life Goal, Gone Just Like That

Luckily, I got invited to the ICPC World Finals. To compete, all three team members had to be fully vaccinated, and Korea's good vaccine supply made that possible. I got to look around Moscow, and also just looked at the problems before coming home.

Back in 2019, I guess I wanted to go to the World Finals that badly — making it to the World Finals was something of a life goal for me. And it always felt incredibly far away. Yet here I am, having achieved it in such an anticlimactic way. It leaves a vague, unsettled feeling in a corner of my heart. Maybe what I really wanted wasn't making it to the World Finals itself, but being good enough to advance to the World Finals from the Korea Regional.

It was a great experience, but personally, finishing 87th was really, really disappointing. And while it's true that I got the chance because we were one of the top teams at the 2019 Seoul Regional, I keep thinking I didn't truly achieve my goal, since we wouldn't have advanced if it weren't for COVID. So even though it's a goal I've already reached, I'm going to give it another shot after I go back to school. I want to settle this.

I'm writing up a post about competing at the World Finals and traveling around Moscow. Stay tuned!

Software Development

solved.ac

Continuing from last year, I poured a lot of effort into developing solved.ac this year too. Let's go over this year's big features.

• Source-based problem search. (January) You can search problems by their source. Things like from:sogang and from:ioi2021 work now.

• AC Rating. (March) We dropped experience-based tier calculation and introduced a new rating.

• A backend rewritten from scratch in Express. (June)

• solved.ac Discord and Discord integration. (June) You can link your solved.ac account to your Discord account so that when your tier changes on solved.ac, your role on Discord updates right away. Since you have to use your solved.ac handle as your chat nickname, moderating the server chat is less of a burden too.

• Twitter integration. (June) It tweets in real time whenever you solve a problem.

• Streaks. (July) It counts the number of consecutive days you've solved problems. Haven't you felt more motivated to solve problems since streaks came out?

• Stardust. (October) Solve problems and contribute, and you get some kind of currency.

• Problem-solving events. (November) There were lots of ups and downs, but we ran a Pepero Day event. We sent out real Pepero.

• Coins and the coin shop. (November) You can buy profile backgrounds and streak freezes.

That's a lot!

After the AC Rating update in March, I ported the entire backend, which used to be written in PHP, to Express.js. Would you believe me if I told you the old backend server sat on EC2, I edited it over FTP, and there was no version control whatsoever? It's unthinkable now.

solved.ac's API set was already huge, so porting it to Express took a whole three months. But looking at the update history after the port finished in June, I think the DP really paid off. If I have time, I'd like to write a post about the port too. Honestly, whenever I say this, I end up never writing it. I'd have to make time for it, and that's hard.

Summing up the big technologies and methodologies I've picked up since porting the backend, from March through December, there's

• Github Actions: CI/CD

• Zero-downtime deployment to ECS via AWS ECR

  • All the way to automated deployment with Github Actions

• Sequelize: ORM

• Setting up a monorepo with yarn workspaces and lerna

  • Building an efficient workflow with easy code sharing between client and server

• Building a rate-limiting middleware in Express

• Query optimization with SQL optimizer hints — this made advanced problem search massively faster

and so on. I always claim that I develop in a very hacky way, and I really do, but I finally feel like I'm building something somewhat properly. Still, I feel like I have a long way to go, and I want to keep growing. Now I'd like to try TDD….

Next year, rather than building new features, I want to focus on laying the groundwork for writing the guides. The guides have been delayed way way way way too long, I'm sorry, please bear with me next year too

It kind of feels like I alternate every year between a (relatively) challenging frontend task and a challenging backend task. Will I be able to finish the groundwork for the guides next year?

Korea Olympiad in Informatics Contest Frontend

This year, I designed and developed the frontend of the contest system for the Korea Olympiad in Informatics, which was held online. I did all the design too.

I tackled a ton of challenging frontend tasks. For example…

• Fetching judging status in real time over WebSockets

• Autocomplete that isn't perfect since there's no language server, but offers a bit of convenience

• A resizable split view of the problem statement and code editor, code blocks that get truncated when too long and can be expanded and collapsed with a button, snackbars that can render LaTeX, the Bebras Challenge (dynamically embedding interactive JavaScript code that renders to a canvas) …

• Screen recording and various other solutions to prevent cheating

and more. I can't go into more detail, but it was a really tough project. Maybe because I only started algorithmic problem solving after entering university, I always regretted never getting to compete in the Olympiad in Informatics, so I was proud to take part in it this way, at least. Same goes for NYPC!

It came striding up to me before I was ready

I don't know how, but after working at the company for a while, I ended up with a title…. Wow….

Despite my limited skills, I got to be an interviewer and got involved in various things at the company, and then in December I was appointed part lead. It's a small part, but it's my first time managing, so I'm nervous about whether I can pull it off.

Am I doing okay? Even if I'm not, I'll do my best so I don't let down the people who believe in me

It's hitting me all over again how good those days were. Though honestly, if you swap that for ‘team lead,’ it still holds for now

Competitive Programming

NYPC

After developing the NYPC system, this year I set problems for it.

I set Qualifier #1, Stairs and Qualifier #7, A Tree with Many Roots. The stairs problem came from my losing weight by climbing 100 floors of stairs a day, and A Tree with Many Roots was a problem I came up with while spinning around in my chair at the office and going, oh, this is pretty good. It was such an honor to present my problems at the best contest out there!

Contest Organizing

Not as many as last year, but I helped run lots of contests this year too.

• NYPC 2021 (Nexon) — problem setting, testing

  • Stairs

  • A Tree with Many Roots

• SPC 2021 (Sogang University) — problem setting, testing, typesetting

  • Ресторан (Read as ‘restoran.’)

  • Wards

  • Connected Components and Queries

• SUAPC 2021 Winter/Summer (Sinchon-area university alliance) — problem setting, testing, typesetting

  • Twinkle Twinkle

  • 성싶당

  • Chessboard Pieces

  • 다꾸 (Diary Decorating)

• Good Bye, BOJ 2021! — problem setting, testing, typesetting

  • Set 1 problem that can't be revealed yet

• PPC 2021 (POSTECH) — testing

On the other hand, I set way more problems than last year. I've now built up a problem bank and pull one out whenever a contest needs it.

NYPC and SPC in particular were held onsite, which was a lot of fun. I was hoping living-with-COVID would carry on so we could hold Hello 2022 onsite, but sadly a new variant showed up…. When will the next onsite contest be possible?

Codeforces

I think I got cocky after framing the orange I happened to hit by luck. I did one contest on January 28th, didn't do any until November, and when I came back I blew past purple and took a trip to blue.

I lost a whole year. Time to pull myself together again.

Contests I Competed In

This year, I competed in UCPC as a contestant. Surprisingly, it was my first time in the finals as a contestant, and we got a remarkable result: 5th prize (12th place).

Making Code Jam Round 3 and winning a prize at SCPC were my small goals for this year, but…

I'm not sure what happened at SCPC, and at Code Jam I made a ridiculous mistake and failed to advance to Round 3.

That's three years in a row of Code Jam Round 2 and SCPC finalist. I really, really hope I can achieve this year's goals next year. I'll have to work for it.

Besides that, I competed in the ICPC World Finals.

Graphic Design

This year, I tried 3D for the first time. I made some simple solved.ac profile backgrounds.

Also, as I mentioned above, I did the UI/UX design for the Olympiad in Informatics frontend. It was fun.

I made posters this year too.

Everything Else

Unlike last year, which was pretty boring, this year was full of life events.

Somehow I came to like someone, and we started dating.

We go out for pasta, tonkatsu, gomtang, kimchi jjigae, chicken and beer, cafés, cocktail bars — we're spending every moment together. These have been the happiest days of my life.

And I got the best birthday celebration ever. I don't think I'll ever forget it.

I used to live with my parents, but the office was too far, so I started living on my own in Nakseongdae. My round-trip commute got about 1.5 hours shorter, and I can get delivery from Sharosu-gil.

The problem is…. From December to June I lost a whole 15kg by climbing 100 floors of stairs every day, but after I moved out, between ordering delivery a lot and going all over the place with my partner, I gained back exactly as much as I lost. Determined to lose it again, I'm hiking up the mountain behind my place every day.

Living on my own, I've been making mapo tofu and carbonara a lot. My cooking has gotten better. The carbonara isn't the cream kind but the kind flavored only with egg yolks and cheese, and after a lot of practice I can now make a warm carbonara without scrambling the yolks. My place only has a single-burner induction stove, so it's still a bit tricky.

My laptop broke, so I bought a new one. I already use a Mac as my main work computer, but apart from briefly using one during my internship at Hyperconnect, this is the first MacBook of my life. I figured that past a certain level of performance, battery life matters most, so I got the 14-inch Pro. I think it was a good buy.

Finally, Hanbyeol, who hadn't been around much for a while, came back this year. Isn't she super cute? I'd long had a little wish to see her in Live2D someday, and this year it finally came true.

Lots of cute illustrations were added too. Many of them are also available as solved.ac profile backgrounds.

My New Year's goal this year was ‘have a reasonably good year.’ Would you say I had a reasonably good year? There were lots of happy things I never saw coming, and also some things that made me reflect on my cockiness.

Next year, my service as an industrial technical personnel ends. Whether to keep working at the company or go back to school and finish my studies early — and if I go back, whether to do a double major or prepare for grad school — I can't stop thinking it over.

Happy New Year! I hope next year we get to enjoy the full release of living-with-COVID. 🔔

This year the problems felt easier than in previous years. I solved all five.

Here are my solutions.

Round 1 Problem 1 – Friends

There are $N \leq 100\,000$ people.

Person number $i$ holds a number $D_i$, and if $i + D_i \leq N$, then person $i$ and person $i + D_i$ are friends. Also, a friend of a friend is a friend.

We need to find the number of 'maximal groups'.

Let's think of the friendships as a graph. If you think carefully about 'a friend of a friend is a friend', everyone inside a connected component ends up being friends with each other.

So counting the number of connected components with repeated DFS/BFS gives the answer. You can also use a DSU^{disjoint set union}. With DFS/BFS it can be solved in $\mathcal{O}\left(N\right)$.

I solved it with a DSU.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

int dsu[100001];

int find(int u) {
    return dsu[u] == u ? u : (dsu[u] = find(dsu[u]));
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u != v) dsu[v] = u;
}

void solve() {
    int n;
    cin >> n;

    iota(dsu + 1, dsu + 1 + n, 1);

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (i + x > n) continue;
        merge(i, i + x);
    }

    set<int> s;
    for (int i = 1; i <= n; i++) s.emplace(find(i));
    cout << s.size() << endl;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

When building a DSU, you can initialize it quickly and easily using a nice function called std::iota. Is it a bit surprising that the STL has a function like this?

Round 1 Problem 2 – Binary

There's a bit string $a$ of length $n \leq 50\,000$, and a bit string $b$ of the same length is defined as follows. $\vee$ is the OR operation.

Given $b$, we need to find the lexicographically smallest $a$.

I think this was a problem where you could get a little lost. Let's start from two facts.

• If $b_i$ is on, then $a_{i-t}$ or $a_{i+t}$ must be on.

• If $a_i$ is off, then $b_{i-t}$ and $b_{i+t}$ must both be off.

Now we scan $b_i$ from the left, and for each $b_i$ that is on while $a_{i-t}$ and $a_{i+t}$ are both still off, we greedily turn on bits of $a$.

• If we can turn on the right bit ($a_{i+t}$), we turn it on. For the right bit to be allowed, $b_{i+2t}$ must either not exist or be on. This is to construct the lexicographically smallest $a$.

• If we can't turn on the right bit, we turn on the left bit ($a_{i-t}$).

If you think about it, you can see that the input only contains cases where at least one of the two can be turned on for every $b_i$. Just implement this as is. It can be solved in $\mathcal{O}\left(n\right)$.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

void solve() {
    int n, t;
    cin >> n >> t;

    string b;
    cin >> b;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        if (b[i] == '0') continue;
        int l = i - t, r = i + t;
        if ((l >= 0 && a[l]) || (r < n && a[r])) continue;

        int ll = l - t, rr = r + t;
        if (r < n) {
            if (rr >= n || b[rr] == '1') {
                a[r] = 1;
                continue;
            }
        }
        if (l >= 0) {
            if (ll < 0 || b[ll] == '1') {
                a[l] = 1;
                continue;
            }
        }
    }
    for (int i = 0; i < n; i++) cout << a[i];
    cout << endl;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

Round 1 Problem 3 – No Cycle

There's a graph with $N \leq 500$ vertices and $M+K$ edges. Of the $M+K$ edges, $M \leq 2\,000$ are directed and $K \leq 2\,000$ have no direction assigned yet.

We want to choose the directions of the $K$ edges carefully so that the resulting graph has no cycle. With only the $M$ directed edges, the graph has no cycle.

The answer is a bit string of $K$ characters. When the $i$-th undirected edge is given as $\textcolor{#ff3b57}{u}$ $\textcolor{#ffb717}{v}$, the bit is $0$ if you direct it as $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$, and $1$ if you direct it as $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$. We need to print the lexicographically smallest bit string.

In a directed acyclic graph, suppose we pick arbitrary vertices $\textcolor{#ff3b57}{u}$ and $\textcolor{#ffb717}{v}$ and add an edge connecting them. We can make it $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$ or $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$. Can there be a case where both create a cycle?

Adding the edge $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$ creates a cycle if and only if a path $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$ already exists.

So if both $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$ and $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$ create cycles, both the path $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$ and the path $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$ must already exist.

But if those two paths already exist, we can form a cycle with just those two paths. This contradicts our initial assumption — a directed acyclic graph. Therefore, at least one of $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$ and $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$ doesn't create a new cycle.

So if the graph is already a directed acyclic graph, we can keep adding edges indefinitely. Since the numbers of vertices and edges are small, we can add edges one at a time, checking each time whether a cycle forms.

Since we need the lexicographically smallest bit string, we first add $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$ and keep it if no cycle forms. If a cycle forms, the proof above guarantees we can add $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$ instead, so we do that.

There are several ways to check whether a cycle exists. I implemented it with DFS. Note that the graph isn't guaranteed to be connected, so you need to start a DFS from every unvisited vertex.

We add $K$ edges and run a DFS each time, so it takes $\mathcal{O}\left(K\left(N+K+M\right)\right)$ time.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

bitset<501> root;
int vis[501], ans[2000];

bool dfs(int u, const vector<vector<int>> &graph) {
    // check for cycles
    if (vis[u]) return vis[u] == -1;
    vis[u] = -1;
    for (int v : graph[u]) {
        if (dfs(v, graph)) return true;
    }
    vis[u] = 1;
    return false;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    root.reset(), root.flip();

    vector<vector<int>> graph(n + 1);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].emplace_back(v);
    }
    
    for (int i = 0; i < k; i++) {
        int u, v;
        cin >> u >> v;

        // 0?
        graph[u].emplace_back(v);
        memset(vis, 0, sizeof vis);
        bool flag = true;
        for (int x = 1; x <= n; x++) {
            if (vis[x]) continue;
            if (dfs(x, graph)) {
                flag = false;
                break;
            }
        }
        ans[i] = !flag;
        if (flag) continue;
        
        // 1?
        graph[u].pop_back();
        graph[v].emplace_back(u);
    }

    for (int i = 0; i < k; i++) cout << ans[i];
    cout << endl;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

Round 1 Problem 4 – Reservation System

There's a hotel with $2 \times m$ rooms. $m \leq 50\,000$.

$n\leq 20\,000$ groups of guests want to stay at the hotel. Each group has size at least $5$, and each person stays in one room.

Every guest has a stress value $w_i$, and if a guest from a different group is in an adjacent room with stress value $w_j$, that pair produces a conflict of $w_i + w_j$. We want to minimize the sum of conflicts over all pairs.

(The problem is done once you explain it like this — do the SCPC staff have a talent for writing descriptions in a hard way?)

SCPC subtasks usually tend to ask for brute-force solutions unrelated to the full solution, but I think with this problem, thinking through the subtasks in order could lead you all the way to the intended solution.

On first read, I had no idea how to even arrange the guests, but taking a hint from the fact that the subtasks were split by whether group sizes are odd or even, I could start with the approach below.

Subtask 1: All groups are even

First, let's think about the optimal arrangement when all group sizes $l_i$ are even. It seems good to minimize the parts that 'touch' other groups. Such an arrangement is made by gluing together $2 \times \frac{l_i}{2}$ rectangles, as in the figure below.

Conflicts happen in the parts colored pink.

To minimize the total conflict when the order of groups is fixed, pick the $2$ smallest elements from the first and last groups, and the $4$ smallest elements from each of the other groups.

Put differently, pick the $4$ smallest elements from every group, then for just two groups, subtract the $3$-th smallest and $4$-th smallest elements, one each.

Let $m_{i,j}$ be the $j$-th smallest element of group $i$. Then sort all groups by $m_{i,3}+m_{i,4}$, and subtract the two groups with the largest $m_{i,3}+m_{i,4}$ from $\sum_i \left(m_{i,1}+m_{i,2}+m_{i,3}+m_{i+4}\right)$ — that's the answer.

Subtask 2: All groups are odd

We can arrange them similarly to the even case.

There are a bit more conflicts in this case, but we can approach it similarly to the even case.

First, each group has one element that's involved in two conflicts, so let's make it the smallest element of the group. Then it's the same as before — pick the $4$ smallest elements from every group, then for just two groups, subtract the $3$-th smallest and $4$-th smallest elements, one each — except that the smallest element has to be added once more.

In other words, sort all groups by $m_{i,3}+m_{i,4}$, and subtract the two groups with the largest $m_{i,3}+m_{i,4}$ from $\sum_i \left(\textcolor{#ff3b57}{2m_{i,1}}+m_{i,2}+m_{i,3}+m_{i+4}\right)$ — that's the answer.

Subtask 3: Even and odd groups are mixed

Based on the approaches above, we can broadly split this into $3$ cases.

• If there's at least one even group and one odd group, the case where the leftmost and rightmost groups are one even group and one odd group

• If there are at least $2$ even groups, the case where the leftmost and rightmost groups are both even

• If there are at least $2$ odd groups, the case where the leftmost and rightmost groups are both odd

3a: The leftmost and rightmost groups are one even group and one odd group

First, place all the odd groups on the left and all the remaining even groups on the right.

Pick the even group with the largest $m_{i,3}+m_{i,4}$ and the odd group with the largest $m_{i,3}+m_{i,4}$, and subtract them.

3b: The leftmost and rightmost groups are both even

Similar to the case above. Just take one of the even groups on the right and stick it on the far left.

Pick the two even groups with the largest $m_{i,3}+m_{i,4}$ and subtract them.

3c: The leftmost and rightmost groups are both odd

This case is a bit tricky.

Taking a hint from the fact that two odd groups can be combined nicely into a rectangle, we can come up with the arrangement below.

In this case, pick the two odd groups with the largest $m_{i,3}+m_{i,4}$ and subtract them.

But this arrangement is only possible when there are at least $4$ odd groups. If there are $2$ odd groups, we're forced to build it like below.

In this case, we need to do $\sum_i \left(\textcolor{#ff3b57}{2m_{i,1}}+\textcolor{#ff3b57}{2m_{i,2}}+m_{i,3}+m_{i+4}\right)$ on the even groups. Let's handle the case with $2$ odd groups specially.

The code covering all cases is below. Since it needs sorting, it takes $\mathcal{O}\left(n \log n\right)$ time. Actually, since we only need the two largest groups, $\mathcal{O}\left(n\right)$ is possible too if you write it well.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

int a[100000];
pii p[20000];

void solve() {
    int n, m;
    cin >> n >> m;

    ll s = 0, sa = 0;
    ll oc = 0, ec = 0;

    for (int i = 0; i < n; i++) {
        int l;
        cin >> l;
        for (int j = 0; j < l; j++) cin >> a[j];
        sort(a, a + l);
        ((l & 1) ? oc : ec)++;
        p[i].first = a[2] + a[3];
        p[i].second = (l & 1);
        s += (1 + (l & 1)) * a[0] + a[1] + a[2] + a[3];
        sa += 2 * a[0] + (2 - (l & 1)) * a[1] + a[2] + a[3];
    }

    sort(p, p + n, greater<>());

    if (oc && ec) {
        ll coe = 0, coo = 0, cee = 0;

        // coe: o o .. o e .. e e
        int o = 0, e = 0;
        for (int i = 0; i < n; i++) {
            if (!o && p[i].second) {
                coe += p[i].first;
                o++;
            }
            if (!e && !p[i].second) {
                coe += p[i].first;
                e++;
            }
            if (o && e) break;
        }

        // coo: o o .. o e .. e o .. o o
        if (oc >= 2) {
            o = 0;
            for (int i = 0; i < n; i++) {
                if (o < 2 && p[i].second) {
                    coo += p[i].first;
                    o++;
                }
                if (o >= 2) break;
            }
        }

        // cee: e e .. e o .. o e .. e e
        if (ec >= 2) {
            e = 0;
            for (int i = 0; i < n; i++) {
                if (e < 2 && !p[i].second) {
                    cee += p[i].first;
                    e++;
                }
                if (e >= 2) break;
            }
        }

        vector<ll> cd;
        cd.emplace_back(s - coe);
        cd.emplace_back(sa - coo);
        cd.emplace_back(s - cee);
        if (oc >= 4) cd.emplace_back(s - coo);

        s = *min_element(cd.begin(), cd.end());
    } else {
        s -= p[0].first + p[1].first;
    }

    cout << s << endl;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

$s$ is the sum of the following.

$sa$ is a value for specially handling the case with $2$ odd groups, and is the sum of the following.

In the array $p$, I stored the odd/even info and the $m_{i,3}+m_{i,4}$ info for every group and sorted it.

Side note

This problem was revised once at 7:33 PM.

A condition was missing from the Reservation System problem. We have stated it as below, and will increase the number of submissions to 20.

– All guests belonging to one set must be assigned a single contiguous block of rooms. A contiguous block of rooms means that for any two rooms in the block, it is possible to move between them through adjacent rooms that belong to the block.

It wasn't written anywhere, but luckily? I just assumed it'd obviously have to be a connected component to be minimal, and I got the problem right. If it hadn't needed to be a connected component, here's a counterexample.

1
5 14
6 1 1 1 1 1 1
6 2 2 2 2 2 2
6 2 2 2 2 2 2
5 10 10 10 10 10
5 10 10 10 10 10

In this case, the following arrangement is possible.

The answer here is $84$.

Round 1 Problem 5 – Difference

For at most $100\,000$ unknowns $X_i$, we need to process the following queries. There are at most $200\,000$ queries.

• 1 i j d: Add the condition $X_i + d = X_j$.

• 2 i j: Print $X_i-X_j$. Print CF if the conditions contradict, or NC if it can't be determined from the given conditions alone.

Without $d$, it's a simple DSU problem. This easily solves subtasks 1 and 3.

If we think of the edges of the DSU tree as having weights, we can solve subtasks 2 and 4.

The reason we can do DSU queries in $\mathcal{O}\left(\alpha\left(N\right)\right)$ is a nice technique called path compression. If $p_u$ is the parent of node $u$, path compression in the function $\mathrm{find}$, which finds the root of $u$, was done recursively as follows.

This way, every vertex on the path from $u$ to $u$'s root $r$ has its parent changed directly to $r$.

Let $d_u$ be the cost of going from the current node $u$ to its parent $p_u$. Then we can compress $d_u$ in a similar way.

When running the $\mathrm{find}$ function, the parent of $u$ was $p_u$, and the parent of $p_u$ was $r$. So getting from $u$ to $r$ costs $d_u + d_{p_u}$. While doing path compression in the $\mathrm{find}$ function, just update $d_u$ to $d_u + d_{p_u}$. Now we can do path compression on a weighted DSU tree too.

Both type 1 and type 2 queries take $\mathcal{O}\left(\alpha\left(N\right)\right)$ time. The total time complexity is $\mathcal{O}\left(K\alpha\left(N\right)\right)$.

$\alpha$ is the inverse Ackermann function^{inverse Ackermann function}, and it's so small — around $\alpha\left(2^{2^{2^{65536}}}-3\right)=4$ — that you can safely treat it as a constant.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

/* [t] [c] [s] */

int dsu[100001], conf[100001];
ll val[100001]; // [u] + val[u] = [dsu[u]]

int find(int u) {
    if (dsu[u] == u) return u;
    int pp = find(dsu[u]);
    val[u] += val[dsu[u]], dsu[u] = pp;
    return pp;
}

bool merge(int u, int v, ll x) {
    // [u] + x = [v]
    if (find(u) == find(v)) {
        if (val[u] + x != val[v]) {
            conf[find(u)] = true;
            return false;
        }
        return true;
    }

    int pu = find(u);
    x += val[u];
    int pv = find(v);
    x -= val[v];
    u = pu, v = pv;
    val[u] = val[v] - x, dsu[u] = v;
    conf[v] |= conf[u];
    return true;
}

void solve() {
    int n, q;
    cin >> n >> q;

    iota(dsu + 1, dsu + n + 1, 1);
    memset(conf, 0, sizeof conf);
    memset(val, 0, sizeof val);

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int i, j, d;
            cin >> i >> j >> d;
            merge(i, j, -d);
        } else {
            int i, j;
            cin >> i >> j;
            int pi = find(i), pj = find(j);
            if (pi != pj) {
                cout << "NC\n";
            } else if (conf[pi]) {
                cout << "CF\n";
            } else {
                cout << val[i] - val[j] << '\n';
            }
        }
    }

    cout.flush();
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        solve();
    }

    return 0;
}

conf is an array storing whether a contradiction has occurred. Since the find function always finds the root, it's enough to put the conf flag only at the top.

Great work, everyone, on solving problems for so long. See you in Round 2!

What on earth is this nonsense?

This post is my personal opinion^私見 on training for algorithmic problem solving.

Let's start with one assumption.

• If you do nothing but eat and study algorithms, you'll hit a Codeforces rating of 3,000 someday, however long it takes.

Well, there are plenty of monsters out there rated above 3,000, but for now let's just say that, in theory, if you do nothing but eat and solve problems, you can reach 3,000 someday. How long it takes will differ from person to person, of course. Based on this, let's model skill $f$ as a function of study time $t$ like this.

But skill doesn't only go up. Some days you're in great shape, your brain is firing on all cylinders and problems just fall apart, while other days you're tired or down, or, physically speaking, your fingers hurt or something. So to model skill a bit more accurately, we'd need to throw in some noise. How about a model roughly like this?

Great. I don't know what the scale of $t$ would be, but let's say this roughly models our current and future skill. Just trust me.

But my rating just stays put

Let's look at just one part of the graph above: someone's journey from a rating of 1,400 to 1,600.

Probably the first thing you're thinking is: 'Forget skill, my graph doesn't even look anything like this…' Right. It's hard to relate to, isn't it? But let me put a few dots on it.

… How about now, doesn't it look like a plausible graph? And if you're really unlucky, something like this could happen too.

Is the owner of this graph doomed to never get a blue nickname? We know they'll reach 1,600 in the end, but if you erased the dotted line and thought this was your own graph, it might be really sad…

Contests are merely samples of your skill

Here's one important observation.

There's a big difference between the skill graph we modeled and the Codeforces rating graph. Ours is continuous, but the Codeforces one isn't. This comes from the very nature of a system called a 'contest.'

A contest only tells you what your skill was at that particular moment; it doesn't tell you your skill in real time.

The reason this is a big deal is that it means your Codeforces rating graph doesn't accurately tell you your skill.

In short, a contest is merely a sample of your skill. And the sampling interval isn't even short. So, honestly, predicting where you're heading in the big picture just from the dots on the graph is close to impossible. Above, I lumped the fluctuations in skill into $b \sin ct$, but that's probably not really the case either.

On top of that, a contest usually has only 6 problems, so not every topic can be covered evenly, and if you're unlucky, a topic you're not confident in shows up and you solve fewer than usual. In other words, the sampling itself isn't all that perfect either.

Speaking of the number of problems, how about we think in terms of problems solved in a contest instead of rating? On Codeforces, how many problems you solve is a major factor in determining your rating. But the number of problems solved is usually a single-digit integer. It's extremely discrete, and if we assume each contest's problems have consistent difficulty, the skill model graph we made above turns into roughly this.

Even with the same 3 solves, a 3-solve where you barely got C is different from a 3-solve where you had D all figured out but ran slightly short on time. If you comfortably got 3 and just missed the 4th, you've definitely grown at least compared to barely getting 3, but in the end, what shows up on the scoreboard is the same three green cells.

Finally, even the Codeforces rating formula can't perfectly represent your skill. The Codeforces formula is designed so that your most recent contest result has a pretty big impact. Only about your last 5 contests meaningfully reflect your skill, and since it's a system where a streak of good or bad luck can outright change your color, it doesn't properly reflect your usual skill. On this topic, I recommend reading djm03178's post on Codeforces ratings.

So it's okay if you solve fewer problems than usual, and it's okay if your rating drops. That probably wasn't your real skill to begin with.

So, the destination isn't your rating

is what I'd like to say. Put differently, I think rating isn't your real skill, and improving at PS and raising your rating look similar but are different things.

Of course, studying algorithmic problem solving to change your color is a genuinely awesome thing. But if the process is truly exhausting and draining, rating might not be a good goal.

But if you build up your skill, your rating will rise naturally. With this mindset, and the hope that if you do enough contests you'll reach your target rating someday, let's believe in our own potential.

Some slightly more practical advice

• Upsolving / aiming for a number of problems — The number of problems you solve is more intuitive than rating and doesn't swing around as much, so I think it's a meaningful goal.
  This goes hand in hand with aiming for a problem rating: try solving the problem right after the hardest one you solved in the contest. If you can't figure it out, read the editorial and take away some insights. If you got it wrong because of an unfortunate mistake, don't beat yourself up too much; encourage yourself instead. The more painful the mistake, the less likely you are to repeat it. Ultimately, aim to increase the number of problems you can solve in a contest.

• Aiming for a problem rating — This goes hand in hand with aiming for a number of problems.
  After a Codeforces contest ends, problem ratings are published in the Problemset. Set a target problem rating $r$, and train by solving problems rated $r$ or below after the contest. Ultimately, aim to be able to reliably solve problems rated $r$ or below within contest time.

• Doing virtual contests — Codeforces has a feature that lets you virtually participate in past contests. There's also a service that calculates your virtual rating from virtual participation. If you use it and do virtual contests often, you can train your skill and also somewhat solve the sampling-interval problem I mentioned earlier.

• AtCoder — A Japan-based competitive programming site. Unlike the Codeforces formula, AtCoder calculates your rating as a weighted average of your performance across all the contests you've taken part in so far, so I think it better reflects a participant's usual skill. Plus, the problems are much cleaner than on Codeforces, there are no system tests, and above all, it's in the same time zone, so you can join casually at 9 PM on weekends. Highly recommended.

• Doing team practice — A great way to think about harder problems for a longer stretch of time. You can gain new insights.

• Taking a break for a while — If you're too worn out, it's fine to rest until you feel better. Forget about algorithms, go out, and eat something delicious. You'll bounce back in no time.

I hope algorithmic problem solving doesn't cause you heartache. I'm always rooting for your problem solving.

solved.ac is built on two key features:

• It assigns difficulty levels and tags to Baekjoon Online Judge problems, giving you a much easier way to pick which problems to solve out of BOJ's huge problem set.

• It provides a skill metric based not on the number of problems you've solved but on the difficulty makeup of those problems, along with rankings built on top of it, motivating algorithmic problem solving learners to take on more interesting problems.

As for the skill metric, until now you earned experience points every time you solved a problem, and your tier was determined by the total experience from all the problems you'd solved. This system has been in place for almost two years, ever since solved.ac was first created on June 6, 2019, but starting on the 1st, tiers will be determined by a new skill metric called AC RATING. AC RATING is the sum of the following, and is theoretically an integer no greater than 3,450.

• The sum of the difficulty values of the top 100 problems when your solved problems are sorted by difficulty in descending order (up to 3,000)

• A bonus based on your CLASS (up to 250)

• A bonus based on the number of problems solved (up to 175)

• A bonus based on the number of contributions (up to 25)

In case you're thinking, "Wait, the experience system was working fine, so why switch to some rating with weird conditions now?", here's how the rating system came to be.

Problems with the experience system

Here's a quick summary of the old experience system.

• Solving a Bronze 5 problem gives 320 points. A problem one tier higher than another gives about 1.5 times the experience.

• To reach Bronze 4, you need to solve 20 more Bronze 4 problems after reaching Bronze 5. To reach tier $x$, you need to solve $n_x$ more problems of difficulty $x$ after reaching tier $x-1$.

• Each contribution gives 10,000 experience.

This was designed with the expectation that you'd solve problems of roughly the same difficulty as your tier. But it had a number of side effects.

To give an extreme example, if someone who hasn't solved anything solves a single Ruby 1 problem, that one problem instantly makes them Diamond 5. Setting aside whether they want to improve their algorithm skills or not, if all they want is a higher tier, there's no need to climb step by step, grinding through Bronze and Silver — they just need to solve one hard problem.

Those 'hard problems' are usually quite difficult to solve on your own, so people often solve them by looking things up online, and the moment they do, that problem ends up making up most of their experience. From then on, solving problems at their actual skill level doesn't even raise their experience by 1%.

The hardest problem this user has solved is Ruby V, followed by one Gold II problem, two Gold III problems, and eleven Gold V problems.

Under the old experience system, this user's tier is Platinum V, and a Platinum V user gains 0.411% of their experience by solving one Gold V problem.

What if they hadn't solved that one Ruby V problem? This user's tier would have been Silver I, and in that case one Gold V problem would give a whopping 6.02% of their experience. So, having already solved that Ruby V problem, is solving Gold V problems really appealing? And would they spend a lot of time solving Platinum problems instead?

In most cases, they either lose motivation or go off looking for another hard problem. Code-copying abuse targeting exactly this happened quite frequently after solved.ac launched. solved.ac is a site meant to boost the motivation of algorithmic problem solving learners, and I felt the old experience system was steering learners in a not-so-great direction.

There were also minor issues: it was hard to tell how much experience a problem gives, how much total experience you need for the next tier, or which problems and how many you'd need to solve. On top of that, the current #1 user's total experience is a whopping 11 digits long, which is pretty unintuitive.

Goals of the rating system

The old system had these problems, and after a lot of thought, I created a new rating system to address them to some extent. The goals of the new rating system were as follows.

• Strike a reasonable balance somewhere between measuring skill accurately and motivating people. Even better if it can do both perfectly.

• Encourage lower-tier users to explore new and diverse areas of algorithms.

• Mitigate as much as possible cases where solving a huge number of problems makes your rating hugely higher, or where a single hard problem makes up most of your rating.

• Display it as an intuitive value.

• Make it fast for the server to compute.

Measuring skill vs. motivation

Many people wanted both the old experience system and the new rating system to reflect users' exact skill. To cut to the chase, gauging exact skill was impossible, so I didn't aim to increase the correlation between rating and skill, and was content with keeping a weak correlation like before.

The reason gauging exact skill is impossible is that BOJ is an OJ. Problems on an OJ have already appeared somewhere else, and in many cases you can easily find editorials for them. Contest platforms, on the other hand, give new problems every time and compute skill based on the number of wrong attempts and solve times.

So compared to contest platforms, OJs have far less information to work with for computing a user's skill, and that information is far less reliable. Even contest platform ratings can't be said to reflect exact skill, since a contest is nothing more than a sample of your skill. Just as there's no guarantee that a student who gets a top grade on a mock CSAT will get the same grade on the real CSAT…

For these reasons, I decided to keep the rough correlation between rating and skill at the existing level, while designing in a direction that emphasizes the motivational aspect the new rating system aims for.

The backbone of the rating

The reason people blindly go for high-difficulty problems is that, even though they take a long time to solve, they look really attractive in terms of climbing tiers.

Under the old experience system, solving one Ruby I problem gave about as much experience as solving roughly 300,000 Bronze V problems, which is an incredible return on the time spent solving. No wonder it looks attractive at every tier. So to nerf that appeal, first of all, the experience you get from solving problems shouldn't grow exponentially with difficulty.

But then, people who've solved lots of problems regardless of difficulty would always come out ahead. Other OJs with ratings and games with similar structures prevent this in mainly two ways.

• Limit the number of problems counted. If $n$ problems are counted, the theoretical maximum a user who can solve problems up to difficulty $x$ can get is $nx$.

• Count all problems, but pick a suitable constant $0<r<1$ and multiply the first problem by $1$, the second by $r$, the third by $r^2$, and so on. The theoretical maximum a user who can solve problems up to difficulty $x$ can get is $\frac{x}{1-r}$.

The two methods are practically the same, but the first is easy for the server to compute, with the downside that unless you solve problems above a certain difficulty, your rating won't go up at all no matter how many you solve. The second gives you the belief that your rating will keep going up as you solve problems (in reality, gaining even 1 point is pretty hard), with the downside that computing ratings costs the server a bit more.

So I decided to give people that belief that solving problems raises their rating in a different way, and went with the first method. I considered the rating to have converged after 100 problems, and made the simple sum of the difficulty values of the top 100 problems, sorted by difficulty, the biggest part of the rating. Conveniently, solved.ac problem difficulties range from 0 to 30, so this gives a total of 3,000 points, which is similar to the 4-digit ratings on other contest platforms and therefore intuitive.

On top of this, I added a bonus rating of $\left\lfloor 175\left( 1-0.995^n \right) \right\rceil$ based on the number of problems solved, to give the belief that solving any problem raises your rating until you've solved about 1,200 problems. I'm not sure whether you'll actually believe it, though. Please believe it.

The original plan was to count 50 of these 100 problems from (OI/ICPC problems set within the last 5 years) and 50 from the rest, but there wasn't enough justification for that, so I switched to just summing 100 problems.

Encouraging new and diverse algorithmic problem solving

Besides tiers, solved.ac has another skill metric called CLASS. You earn it by solving at least 20 out of 48 predetermined problems for each skill level.

CLASS problems are chosen with educational goals in mind for each level. For example,

• CLASS 1 consists of problems that are good for beginners to programming or algorithmic problem solving.

• CLASS 2 consists of topics that come up often in coding tests and programming contests and are easy for beginners to understand and implement. (Brute forcing, basic math, sorting, queues, stacks, deques)

• CLASS 3 consists of topics worth trying after fully understanding the topics from CLASS 2. (Graphs, graph traversal, heaps, priority queues, dynamic programming, etc.)

• CLASS 4 contains topics similar to CLASS 3 but that feel harder. (Backtracking, shortest path problems, tricky implementation, hard dynamic programming, hard graph problems, etc.)

The lower CLASSes aim to recommend a good path for beginners, structured similarly to 'Step-by-step problems'. To encourage this even more, I added a CLASS bonus to the rating. However, considering that it could create a gap between the new rating and actual skill, I set it up so that the CLASS bonus looks attractive at lower tiers but doesn't make a big difference in rankings at higher tiers, as follows.

• CLASS 1, 2: +25 points

• CLASS 3, 4, 5: +50 points

• CLASS 6 and up: +10 points

From CLASS 6 on, the topics are hard ones that mostly appear only in programming contests. Also, I figured that anyone skilled enough to get CLASS 6 or higher could easily get CLASS 5, and would know plenty of ways to improve without necessarily solving CLASS problems, so I decided that the rating reward for CLASS 6 and above shouldn't significantly affect rankings.

Rating cutoffs

Tiers by rating were determined by considering two main factors.

• Is the experience of going from tier $x$ to tier $x+1$ reasonable from the user's perspective?

• How will the proportion of users in each tier change?

In particular, the new rating system counts the top 100 problems, and for someone who's just started studying algorithms, even solving 100 problems could be a lot. So along with 'what CLASS do we expect them to have?', for lower tiers I also considered 'how many problems do we expect them to have solved?'. For example,

• In the Bronze range of the old experience system, users were expected to solve about 30 problems suited to their level. In the new rating system, I set the rating cutoffs with the journey of completing CLASS 1–2 in mind.

• From the Gold range on, users are expected to have solved 100+ problems, and I considered the expected average difficulty of their top 100 problems. For example, I figured a Gold III user would on average be at CLASS 2–3 and be able to easily solve problems around Silver II to Gold V. If they get CLASS 5 to pick up 100–150 rating, and while working on CLASS 5 get comfortable with upper Gold to lower Platinum problems so that their top 100 is made up of those, they'll find themselves in Platinum before they know it.

• The theoretical maximum rating is 3450, but given that there aren't many problems in the Ruby range, and that solving even harder Ruby problems when your top 100 is already packed with Diamond and Ruby is quite a difficult process in itself, I divided the Ruby range finely.

While doing so, I also made the rating cutoffs intuitive numbers — Bronze 30, Silver 200, Gold 800, Platinum 1600, Diamond 2200, Ruby 2700. After a lot of deliberation for each tier, the rating cutoffs were set this way.

I think it would be ideal for Platinum, Gold, Silver, and Bronze to be the top 10%, 33%, 67%, and 100% respectively, but since the rating formula hadn't been made public at the time, I set it slightly harder than before. That's because making the rating formula public could affect the user distribution.

Rating vs. the old skill metric

Comparing Codeforces ratings with new tiers for the top 569 users who have a Codeforces handle, the correlation under the new rating system was weaker than with the old tiers, but it still maintained some degree of correlation as before. The inversion count also increased from 148,135 to 161,462. I sacrificed some correlation with skill to fix the problems of the old experience system, but my interpretation is that it still has a reasonably meaningful correlation.

Challenges to overcome

The new rating system isn't perfect either. Most notably, for users who have solved 1,200 problems and received the full 175-point problem count bonus, solving problems below the difficulty of their top 100 becomes meaningless under the new rating system. Though there may well be interesting enough problems. There was also discussion on whether including the CLASS bonus rating was a good choice.

For these issues, I decided to think about how to improve them while running the rating system. There may also be things that can be improved outside of the rating formula, like making good guide content.

Deciding how to determine tiers is the hardest design decision in all of solved.ac. It's a design that came out of countless deliberations, and I hope it settles in as positively as the amount of thought that went into it.

Future plans

Now that I've started working full-time and have gotten busy with various things, I have relatively less time to build new content for solved.ac. Here's what I'm currently planning.

• Backend refactoring (through June). After the frontend, it's the backend's turn. The current backend is PHP, and since it's become way too hard to maintain, I'm rewriting it in Express. When I first made solved.ac, I had no idea it would get this big, so I guess it couldn't be helped. Lay a solid foundation from the start of your projects, folks.

• Guides (through September).

• Voting overhaul (through September).

Thank you for your continued interest and support!

Why Prop `className` did not match happens with Next.js + styled-components, and how to fix it

Last fall, while refactoring the solved.ac frontend into Typescript, I ran into something baffling. Whenever I clicked any link on the site to go to another page, the stylesheets all broke.

Opening the console, I saw the following error.

Warning: Prop `className` did not match. Server: "sc-xxxxxx xxxxx" Client: "sc-yyyyyy yyyyy"

As the error says, it happens because the classNames don't match between the server and the client. Next.js is a framework that helps with SSR^{Server-side Render}. For things like SEO^{search engine optimization}, it renders the page on the server on the initial load, but when you click a link on the page to move to another page, it renders the page with CSR. It's a framework that takes care of both SEO and speed.

So the server and the client should basically share the same logic, right? Then why does this happen?

Because babel-plugin-styled-components is missing

The first reason is that babel-plugin-styled-components is missing. This Babel plugin provides consistently hashed component classNames between environments. Wait, so does that mean that without this plugin, styled-components' className generation depends on the 'environment' by default? Yep, it does.

styled-components generates a unique identifier for every component made with the styled function using the generateId function, and as you can see in the function, it keeps a single global counter and increments it each time it processes a component.

So what can happen when identifiers are generated this way? The same component can end up with different identifiers depending on the order in which components are created! This doesn't matter with CSR alone, but when you use SSR and CSR together, the identifiers can differ depending on the order in which the server and the client create components. babel-plugin-styled-components normalizes this identifier generation process.

Here's how to fix it.

1. Install the plugin:

npm i --save-dev babel-plugin-styled-components

2. Edit .babelrc in the project root (create it if it doesn't exist):

{
  "plugins": ["babel-plugin-styled-components"]
}

3. If you're using Next.js, copy-paste the _document.js from here.

It still doesn't work

This is the core of this post.

In solved.ac's case, it still didn't work even after doing all of that, so I spent months banging my head trying to fix it. It wasn't a problem before the Typescript refactor; the error appeared when I brought in Typescript. While digging into what was wrong, I found out it was because of the custom theme type definition.

The solved.ac frontend code has a type called SolvedTheme, which holds the theme definition.

interface SolvedTheme {
  defaultFonts: string
  codeFonts: string
  background: string
  textColor: string
  textColorInverted: string
  textSecondaryColor: string
  border: string
  borderColor: string
  tableHeaderBackground: string
  tableBackground: string
  footerBackground: string
  primaryColor: string
}

Previously, components made with styled-components used it like this.

const TopBarContainer = styled.div`
  position: fixed;
  width: 100%;
  height: 48px;
  line-height: 48px;
  background: ${({ theme }) => theme.background};
  border-bottom: ${({ theme }) => theme.border};
  top: 0;
  left: 0;
  z-index: 10000;
`

This code is fine in Javascript, but in Typescript it throws a compile error. That's because the type of theme is styled-components' built-in DefaultTheme, not the SolvedTheme defined above.

To solve this, I googled hard, wrapped styled-components with my type definition like below, and imported the resulting new styled everywhere. Something like import styled from '../styles/Themes'.

import * as styledComponents from 'styled-components'
import { ThemedStyledComponentsModule } from 'styled-components'

const {
  default: styled,
  css,
  createGlobalStyle,
  ThemeProvider,
  ThemeConsumer,
  keyframes,
} = styledComponents as ThemedStyledComponentsModule<SolvedTheme>

export { css, createGlobalStyle, keyframes, ThemeProvider, ThemeConsumer }
export default styled

But if you define it this way, babel-plugin-styled-components becomes useless. That's because babel-plugin-styled-components only works when the import path is 'styled-components'.

It looks like you can change this in the options, but that doesn't seem like a clean solution. Instead, you can create a new styled.d.ts and set DefaultTheme to SolvedTheme there. That solves the problem above while still letting you use the custom theme's type definition.

import 'styled-components'
import { SolvedTheme } from './Themes'

declare module 'styled-components' {
  export interface DefaultTheme extends SolvedTheme {}
}

(Edited 21/12/23: Changed the code to use declaration merging. With type DefaultTheme = SolvedTheme, features like autocompletion in the VS Code editor didn't work properly.)

This might not be a common cause, but I shared my case in the hope that others won't have to go through what I struggled with for months without knowing why.

References

• Investigate better ways to create component-specific classes https://github.com/styled-components/styled-components/issues/2069

• Serverside rendering with Typescript for img tags has mismatching classNames with client https://github.com/styled-components/styled-components/issues/2064#issuecomment-427571787

• What is the point of the styledComponentId? https://spectrum.chat/styled-components/general/what-is-the-point-of-the-styledcomponentid~edd37201-7e63-43a8-981a-545ca344aed7