2020 in Review

Starting this year, I've decided to write a yearly review on my blog of what I've done. It'd be sad if I forgot all of it later, right?

I had neither a partner nor friends to begin with, so it was a great year in that I could blame COVID for my empty calendar. So to speak, I was put under an honorable self-quarantine. I bow three times a day in the direction of the bat cave closest to my house.

I still thought COVID would be over by December, but nope. The daily case count keeps hitting new records, and I'm working from home. Oh, but at least I have a job now. Thank goodness

Software Development

solved.ac

This year I focused quite a lot on developing solved.ac. Here are the big features added to solved.ac this year.

• Problem sorting. (February) You can easily sort problems in the problem list.

• Advanced search. (February) Besides problem titles, you can now filter by the number of solvers, problem level, problems you've solved, and so on, and search using operators like AND and OR. I designed the search query syntax myself and built a parser to interpret it, too.

• Profile backgrounds. (February) You can now decorate your profile with a background.

• Rivals. (April) You can register other users as rivals and see your ranking among your rivals.

• Profile pictures. (May) You can now upload a profile picture.

• End of the whitelist system and end of beta. (June 5) It's hard to imagine now, but before June, you had to email me and get whitelisted to use solved.ac. From June on, we switched from crawling and parsing to receiving user information directly from BOJ, so anyone can use the site.

• Code redemption. (August) You can now enter redeem codes to get backgrounds, profile badges and more.

• Auto-refresh. (November) This is also hard to imagine now, but before November, you had to manually press the ‘Refresh’ button on your profile after solving a problem. Now your EXP is updated the moment you solve a problem, so there's no need to press the refresh button.

The integration work with BOJ is also almost done, so you can now check solved.ac problem difficulties and tags on BOJ without having to visit solved.ac. Also, new features like the Guide are about to be released. Looking forward to another year with you all!

Into the World of JavaScript Frameworks

Most of solved.ac's source code was originally written in PHP. As the frontend code got more complex, maintenance became a struggle, and because of various characteristic quirks of PHP, I figured it would be hard to develop anything more as long as the codebase stayed in PHP.

So I just dove in and started porting the frontend to React, which I'd heard was great for building and reusing components. I also needed search engine optimization, so I used Next.js as well, which supports SSR.

Back then I knew nothing about React, but now I use it every day at work, so I feel it's a framework that's easy to get used to. So much so that I wonder why I didn't do this sooner. For reference, before using React, all the sites I'd made ran on pure vanilla JS without any framework.

After that I also adopted TypeScript and refactored the project. I could really feel how much type inference boosts development efficiency. For example, previously there were no type definitions for API responses (lazily, I hadn't even written a spec), so I'd mix up fields or types, causing errors or slowing development down. Now I've diligently written type definitions and drastically reduced the chance of errors caused by my own human error. It's really basic stuff, but it was a rewarding experience for me, so I'm sharing some source code.

type SolvedPageContext = NextPageContext & GlobalProps

export type SolvedPage<
  P = { siteTitle?: string[] },
  IP = P
> = NextComponentType<
  SolvedPageContext,
  IP & { siteTitle?: string[] },
  P & { siteTitle?: string[] }
>

export default SolvedPageContext

Defined this way, the type that getInitialProps must return is determined by the type definition of the page's Props. In the page below, the type of props.result is set to Problem[], which makes writing the render logic in ProblemList much easier. Not to mention the editor integration.

type Props = SolvedApiResponse<SearchProblems>

const LevelProblems: SolvedPage<Props> = (props) => {
  // ...
  return (
    <PageLayout>
      <h1>
        <TierMark value={level} locked={false} showName={true} />
        {caption ? ` — ${caption}` : null}
      </h1>
      <ProblemSortController
        currentSort={newQuery.sort}
        currentDirection={newQuery.direction}
      />
      <div>
        <ProblemList
          result={props.result}
          page={page}
          keys={['id', 'title', 'solved_count', 'average_try']}
        />
      </div>
    </PageLayout>
  )
}

LevelProblems.getInitialProps = async (ctx) => {
  // ...
  try {
    const response = await SolvedApi<SearchProblems>(token).get(
      '/search/problems.json',
      {
        params: {
          query: queryString,
          page: +(page ?? 1),
          sort: sort ?? ctx.currentSettings?.problem_sort_by,
          sort_direction:
            direction ?? ctx.currentSettings?.problem_sort_direction,
        },
      }
    )
    return {
      siteTitle: ['문제', '레벨', levelName(+(level ?? 0))],
      ...response.data,
    }
  } catch (e) {
    // ...
  }
}

Anyway, this is how I rewrote the entire frontend, previously written in PHP, in React + TypeScript + Next.js over several months.

Unfortunately, the backend is still in PHP. I'm currently planning to reimplement the backend in Node + Express while building the Guide. Once that's done, you'll be hard-pressed to find any PHP code in solved.ac.

Getting a Job

Thanks to the development experience above, I started working at Engine Studios, a subsidiary of Nexon Company, in mid-June. As of writing this review, it's already been over half a year since I joined.

It's a game company, but my main role is web frontend engineer. I'm in charge of developing various internal and external services. I can't really say which ones, but quite a few of you reading this have probably already used a service I worked on. 😉

As an aside, the company gives us a certain amount of Nexon Cash every month, and since I had nothing in particular to spend it on, I started playing MapleStory. Morass is right around the corner now. I got to Morass on December 30. Somehow I've ended up spending more than I receive, but I figure it's fine since they give (?) back what I spend in the form of my salary..

Competitive Programming

Codeforces

This year I finally reached orange, which I'd longed for so much.

But my rating is exactly 2100.

And yet I pull off this difficult feat once more.

What on earth is this person doing? How on earth did he do it?

The graph sits right on 2100.

Now that I'm orange, my rating doesn't change outside of Div 1. But Div 1 rounds aren't held often, and whenever one is, I'm somehow busy and miss it every time. In a word, I got lazy. Whatever happened to the shift who swore he'd return to school in red robes (적의환향)? I need to get back to competing hard.

Hosting Contests

I hosted UCPC 2020 and tested and set problems for many contests.

• The Real Final Gudeki Cup 2 – Problem setting, testing

  • Hyper Sequence and Hyper Query

• UCPC 2020 (Union of Collegiate Programming Contest Clubs Summer Contest) – General management, problem setting, testing, typesetting

  • Math Is a Remote Lecture

• SUAPC 2020 (Shinchon Union Summer Contest) – Problem setting, testing, typesetting

  • Honeybee

  • Legend

  • Reckless Development

• Shinchon Union Camp 2020 – Testing

• SNUPC 2020 (Seoul National University) – Testing

• Uni-CODE 2020 (UNIST) – Testing, typesetting

• SPC 2020 (Sogang University) – Testing, typesetting

It was a year in which I learned an almost excessive amount about creating and testing algorithm problems and the process of running programming contests. In particular, I learned how to write well. If I get the chance, I'd like to write up my SUAPC/SPC problem-setting/testing retrospectives too.

Competing

I took part in several contests, but this year was somewhat disappointing.

• ICPC Asia-Seoul 2020 National First Round – Competed as team Redshift, 5/12 solved, #36

  • I had the right idea for three more problems.. I blamed the lecture room keyboard.

• SCPC 2020 – Finalist, 172/1000

  • Problem 4 looked really solvable, so I spent three hours on just problem 4, couldn't solve it in the end, and bombed. Scrape those partial points, everyone.

In team practice we were cruising through NxxRC sets with 8–10 solves, so I thought we'd do well, but then we got that result in the actual Korean regional preliminary, which was baffling. I guess I lacked individual practice.

…Will I ever return in red robes?

Running Study Sessions

At the start of the year, I ran a study group at Sogang ICPC Team covering the topics below.

• Updating segment trees lazily ^{lazy propagation}

• Divide and conquer on trees using weights ^{heavy-light decomposition}

• Persistent segment trees ^{persistent segment tree}

• Winning strategies for games and the Sprague-Grundy theorem

• Number-theoretic algorithms

Graphic Design

As I helped run many programming contests, I naturally ended up making posters for them.

I also made lots of graphics for programming contest problems.

When solved.ac got official social media accounts, I also made square graphics.

I do solved.ac's web design directly in CSS rather than firing up Photoshop or Illustrator, so there aren't really any mockup designs.

Unfortunately, I didn't have the time to make personal pieces like I used to.

Other Stuff

I thought I hadn't done anything while on leave from school and working at the company, but now that I've organized it all, I actually did quite a bit. My health checkup told me to rest a lot, so my goal for next year should be to spend the year not being busy.

I switched my phone to a Galaxy Note 20. The white one was so pretty that I bought it in white, and I think it was a good choice. It's a 5G phone, but I heard a lot that 5G barely gets any signal, so I bought it unlocked to avoid using 5G. But the S Pen, arguably the most important feature of the Note, I don't end up using much. Maybe because it's on the left side..

For the first time in a looooong while, I watched a lot of anime. I watched a lot of Netflix too. After watching Beth Harmon, I bought a chess set. But I don't think I'm very good at it.

Discovering that trains depart from Sindorim Station improved my quality of life.

SEGA's rhythm game ‘CHUNITHM’ was officially released in Korea, so I took a week off and went every day.

I think this was also a year I rode my bike unusually often. Especially after hanging out or solving problems at school, or playing at the arcade near Sangsu Station, I'd often cross Sogang Bridge and ride a Ttareungyi bike home. But now that the COVID situation has gotten worse, even riding a bike around outside feels awkward. I really miss the days before COVID..

I wanted to finish porting the solved.ac backend to Node.js, I wished I could learn to draw, I wanted to reach red on Codeforces; there were so many things I really wanted to do. Since I didn't achieve all of them, I thought I hadn't done much this year.. but after organizing it all, I did a whole lot this year, even in times like these 😅 I guess I just wanted to do too many things. I think I can afford to live a bit more leisurely. My health checkup told me to rest a lot too.

All things considered, I spent this year pretty well. I'll make my New Year's goal to spend the year reasonably well, too. Happy New Year~ 🔔

Looking back on hosting UCPC 2020

This year I got the chance to serve as president of the National Union of University Programming Contest Clubs^전대프연 and host UCPC 2020. It's the second contest I've run, after the 2019 Sogang University Programming Contest.

The Union is a coalition of 26 clubs from 25 universities that love algorithmic problem solving, and UCPC is the programming contest it hosts every year. It started out as a sort of practice contest for the ICPC Korea Regional, which is usually held in the fall, and today it's the largest community-run programming contest in Korea.

Why did you volunteer?

Coordinating a contest is hard. So people rarely step up to take charge, and in fact, three years ago the contest didn't happen at all. It was April and still nobody had offered to run the contest, so I said I'd give it a go this year. At the time I was on a leave of absence from school, unemployed, happily lazing around all day eating potato chips and having staring contests with my computer. If I hadn't been on leave, I'd probably have been pretty busy and wouldn't have volunteered.

As soon as I took over, I started planning the contest and recruiting problemsetters. But this year there was a big problem. A huge one that could change the very foundation of the plan depending on how things went. Namely..

The COVID era, which strode right up to us before we were ready

Everyone living through 2020 probably has a priority queue in their heart. It's the priority queue called things to do when the COVID era is over. Mine is already about to pass 120 elements. When COVID's over I'll travel, when COVID's over I'll go on a food tour, when COVID's over I'll grab a meal with the friends I haven't seen, … Back around April, I definitely didn't think the queue would get this big. I thought things would get better.

UCPC was no different. We had a vague hope that things would be better by July, when the contest would be held. So we planned to hold it offline. Here are the reasons holding it offline is better:

• UCPC aims to be a venue for interaction and competition among members of programming contest clubs.

• Cheating is hard to check. It's easy to tell whether a participant copied another team's code. But it's hard to prevent, and nearly impossible to detect, cheating like, say, four or more people writing code in UCPC, a three-person team contest, or (as a really, really extreme example) asking tourist for the solution during the contest and using it.

• A contest the size of UCPC needs a lot of money to run. So sponsors' help is crucial. But if it's held online, compared to offline, it's relatively hard to figure out what benefits we can give sponsors in return and to pitch them.

On the other hand, holding it online has its own advantages.

• We no longer have to budget for venue rental.

• Nobody has to come to the venue. I've heard that people coming up to Seoul from other regions often have to set aside an entire day just to participate. All of those costs go away.

There are definitely advantages to running it online, but the advantages of an offline contest were far more critical, so I wanted to do it offline if at all possible.

But as everyone knows…

…daily confirmed cases, which had been in the 10s, suddenly went back up to 30, 40, 80, and I felt that if we held it offline the staff couldn't take responsibility for disease control, so we gave up on an offline contest.

As I write this, over 100 new cases are being confirmed every day.

Doing what we can because it's online

So we decided to make whatever we could do as fun as possible. First, I thought about how we could keep the advantages of an offline contest mentioned above in an online format.

• A venue for interaction and competition – We decided to run the solution broadcast and scoreboard broadcast, which used to happen at the venue, as an online stream on Twitch. It won't be as good as a physical space, but people can interact through live chat.

• Appeal to sponsors – During the stream, we use part of the screen to continuously show sponsor logos. If we can get a studio, we hold the sponsor session right after the contest ends and before the problem explanations, when the most participants will be watching.

Cheating was what I worried about the most. My stream of consciousness went roughly like this.

• Could we prevent cheating with webcams?

  • Even with a webcam, couldn't someone easily cheat by putting KakaoTalk or something on their screen? Then do we need screen recording too?

  • Even with screen recording, couldn't someone easily cheat with another device?

  • Does a video chat service that can handle 50 teams connected at once even exist?

  • Whether or not it exists, do we have the capacity to monitor all those screens?

• Webcams seem tough, so let's do copy checks

  • We could catch copy-pasting between teams, but how do we stop four or more people competing as one team?

  • Even if there aren't four or more people on a team, what if someone asks a random Codeforces red to solve a problem during the contest? How would we stop that?

  • And when would we read all that code?

• So isn't it impossible to prevent cheating no matter what we do?

• But anyway, if someone we've never seen before cheats their way to a high score and ends up at the top of the scoreboard, wouldn't it be obvious?

In the end, we decided to trust the PS community and not do any cheating checks beyond code copy checks. That decision was only possible because it was a community contest. If it had been a corporate contest with big prize money, this situation would have been pretty troublesome.

Live streaming

Once that was decided, the stream became the most important part of planning the contest, other than problemsetting and testing. I asked the world-class star with worldwide popularity Jaeheon Jeong^Gravekper, who has competed in lots of programming contests (the ICPC World Finals, no less!) and often streams related content, whether he could join, and he gladly agreed, so we planned the online stream together.

Right up until the contest, we discussed hard what to cover on the stream, when to start streaming, how to lay out the screen, and so on. The stream had to include the solutions, the scoreboard, and the sponsor session, and beyond that we thought about what to do before the contest ended, keeping in mind that both people participating in the contest and people who weren't could watch. So we looked at other contests that have online streams.

• ICPC and IOI show a live scoreboard and problem analysis during the contest. ICPC broadcasts are more fun than you'd think. That's actually close to the ideal stream I wanted to do, but since this was an online contest and we'd given up on webcams, there was nothing to show on screen, and since contestants could also watch the UCPC stream, we couldn't show problem analysis either.

• Google Hash Code's stream, on the other hand, can be watched by participants during the contest. So they only stream before and after the contest and show nothing during it.

But showing nothing during the contest would be boring, so we decided to just put the scoreboard up.

The solutions and sponsor session were also a worry. Until now, UCPC solutions were presented by the problemsetters showing slides at the podium, and the sponsor session was the same. So what do we do this year?

Fortunately and gratefully, the Korea University SW-Centered University Program provided a space again following last year, so we could use one of the large lecture halls at Korea University's College of Informatics as a studio. Just like before, the problemsetters could present slides at the podium and we could film and stream it.

Problemsetting and testing

What doesn't change about programming contests even in the COVID era is problemsetting and testing. This year I started preparing early, worried that I'd be starting a job in the summer. We recruited problemsetters from BOJ Slack, the largest algorithmic problem solving community in Korea, and later took additional submissions through a call for tasks. We received a lot of problems this year, so the problemsetters' pool was pretty big.

All communication, including planning, happened on Slack. The biggest drawback of (the free version of) Slack is that once more than 10,000 messages pile up, older messages become inaccessible one by one, but conveniently, Slack was offering the Standard Plan free for 3 months because of COVID, so we used it without a second thought.

We made one channel per problem so we could talk without losing context as much as possible. We also made topic-based channels as needed: #general for overall contest announcements, #broadcasting for planning the stream, #contest-finals / #contest-preliminaries for handling live issues during the contest, and so on.

In particular, with help from Suchan Park^tncks0121, we set up a Slack–Zapier integration so that emails received through the call for tasks were automatically forwarded to a Slack channel. However, I'm not sure whether it was a Zapier issue or the UCPC mail server issue I'll get to later, but a few emails went missing. In those cases I had to deliver the submitted problems from the UCPC inbox to the problemsetting channel myself.

We used Google Drive for tracking problemsetting/testing progress and managing problem materials. We made heavy use of shared drives, a G Suite feature.

Problemsetting

Setting the tone of the contest

Early in problemsetting, it's important to decide on an appropriate difficulty curve for both the preliminaries and the finals. If the problems are too easy, teams that solve everything have nothing to do until the contest ends and get bored; if they're too hard, teams overwhelmed by the problems get frustrated. So you decide the difficulty curve first, and based on that you can decide what problems to set, and which problems from the pool to use and which not to. This is also something I mentioned in last year's Sogang contest problemsetting retrospective.

On this front, the biggest difference between last year's UCPC and this year's was the existence of solved.ac, a way to gauge problem difficulty. Referring to the difficulty distribution of the Seoul Regional, each of us estimated the difficulties of the problems in the pool, and we worked out a good flow for which problems to use in the preliminaries and which in the finals. We also added algorithm tags to the sheet so we could arrange problems such that the contest wasn't too skewed toward one area. However, seeing difficulty and tag information during testing could negatively affect testing, so only problemsetters edited that sheet, and we made a separate testing status sheet.

For the problems submitted through the call for tasks, the problemsetters gauged their difficulty the same way and adopted the ones we thought the contest needed. Because there were so many submitted and internally set problems, unfortunately a lot of problems couldn't be used.

Writing descriptions and data

To ensure data integrity as much as possible, all work except writing descriptions was done on Polygon using testlib. The Polygon server was somewhat unstable, which led to a few nerve-wracking moments, and we backed up entire packages often.

Problem statements were written on the secret secret princess self-hosted Overleaf running on the solved.ac server.

For descriptions and data, so that participants wouldn't waste time understanding problem descriptions or dealing with issues we didn't consider important to the problem, we created the UCPC problemsetting conventions based on the following principles and tried our best to follow them.

• Unless it's a problem whose concept is to make the description deliberately hard to understand, the description should be easy enough to understand on a single read, and it shouldn't get in the way of solving the problem.

  • In the same vein, avoid difficult mathematical notation and concepts wherever possible. It should be understandable to someone who just graduated from high school. For instance, we don't bother writing ‘$\sum_{a\in A} a^2$’ for something that can be written as ‘the sum of the squares of all elements of $A$’.

  • Text and variables should be easy to tell apart, and variables shouldn't interfere with reading. So all variables are written in italics, formulas are spaced properly, and the correct symbols are used.

• It's best to state the ranges of input/output variables all together in the input/output section.

• Data must be correct. There must be no data that differs from the stated format, and no output data that isn't the correct answer for its input data.

• Participants shouldn't have to struggle with unfamiliar I/O methods and such. This especially goes for input data that marks its end with EOF.

Also, if there's a reason we didn't bother writing descriptions in Polygon, it's BOJ Stack, BOJ's problemsetting platform. Since the contest is hosted on BOJ, all the problems need to be moved to BOJ before the contest, and descriptions get edited a lot right before the contest. But if descriptions are managed in Polygon, then you have to edit the description in the problem statement PDF, which you have to make anyway, and also in BOJ Stack. On top of that, BOJ Stack asks you to avoid LaTeX as much as possible, so all the problems written in TeX have to be reformatted into HTML — for instance, a formula like $1 \leq N, M \leq 200\ 000$ $1 \leq N, M \leq 200\ 000$ into 1 ≤ N, M ≤ 200 1 &le; <em>N</em>, <em>M</em> &le; 200 000 — and that is far more painful than you'd think. To cut down on this work, we managed descriptions only in Overleaf.

Of course, to cut even the work of formatting into HTML, we just used TeX for every problem. That way, copy+pasting the problem body from Overleaf into Stack finishes the setup. Easy, right?

For figures used in problems and editorials, we made a separate channel for requests, took requests from the problemsetters, and I worked hard drawing them.

Finally, following ICPC trends, model solutions were written in both C++ and Kotlin (or Java), guaranteeing the problems were solvable in those languages.

Testing

Once a problem draft is done, it gets verified. Mainly, the following need to be checked.

• Whether the data and description are correctly formatted^well-formed and valid (whether they follow the UCPC conventions)

• Whether the setter's solution is flawless

• Whether the problem can be solved by a solution the setter didn't intend, and if so, whether that solution should also be accepted

Testers are the ones who carefully check exactly the items above. Besides crosschecking^{crosschecking} among the problemsetters, we also brought in external testers.

We anticipate incorrect approaches participants are likely to try (also called ‘사풀이’, i.e. fake solutions) and block them appropriately. There are many ways. For example,

• In a problem where you need to determine whether some natural number $N$ is prime, you can prepare data with $N=1$ to fail code that doesn't correctly handle $N=1$ as input. (edge case data)

• In case there are cases we didn't think of, you can add more general data generated randomly.

• If code that solves the problem with a completely wrong method luckily passes all the prepared data, you can prepare data on which the wrong method gets a wrong answer or time limit exceeded. (counterexample data)

• If the problem can be solved with a much easier solution than the intended one, you can adjust the time limit or the constraints on constants in the problem. You tune the limits so that the intended approach passes but unintended approaches get time limit exceeded.

Through processes like these, we made the problems perfect.

Gather around

I liked the eligibility rules from the past two years and kept them as is. I only clarified the eligibility for integrated MS–PhD students.

• Must participate as a team of 3

• Undergraduates can participate whether enrolled or on leave

• Graduate students can participate if in a master's program or up to the 2nd year of an integrated MS–PhD program

• Members of different schools can team up

I also thought about adding restrictions based on past awards, but UCPC kind of has the concept of being a showdown of Korea's strongest, so I didn't. A total of 299 teams registered for the preliminaries.

As in every year, we took registrations with Google Forms and sent announcements through GMail, but as the contest grew, I thought it was getting a bit unreasonable to keep using this method.

• Several participants made typos in their email addresses. As real examples, I found addresses with typos in the domain like nvaer.com^naver.com, gamil.com^gmail.com, and kaist.co.kr^kaist.ac.kr, and I fixed them by hand. Domain typos can be fixed somehow, but were there really no typos before the @? I felt we should use a service based on email verification, or implement one ourselves.

• I wrote and sent 299 preliminary account information emails one by one. Also, it was while running this contest that I first learned GMail has a daily sending limit. I should have built an automated bulk mailing system at that point, and not doing so led to the preliminary disaster I'll describe later.

Securing a budget

We set the budget so we could fairly compensate problemsetters and testers for their efforts and give prizes to participants. Since it was an online contest, I thought we wouldn't need to consider venues, supplies, meals, and so on.. which was a miscalculation. We needed a place and equipment for the stream, and if there were prizes, we needed money to ship them. Adding up rental, equipment, shipping, and so on, the budget came out pretty heavy — not as much as previous years held on-site, but still.

Gratefully, as soon as I announced we'd hold the contest, Kennysoft, Algospot, Startlink, and the Korea University SW-Centered University Program offered to sponsor. After that I recklessly sent emails to a bunch of dev companies (…) and MINDsLab and NAVER D2 covered the problemsetting and testing costs. Thank you so much! (solved.ac is essentially my personal sponsorship, so it doesn't count)

Since it was an online contest and we couldn't run the sponsor session the usual way, I thought hard about how to pitch it, but we decided to pitch that precisely because it's an online contest with a public stream, anyone can watch the broadcast even if they're not participating, so companies can promote themselves to viewers with a real interest in algorithmic problem solving.

Honestly, problemsetting and testing were somewhat familiar since I'd run the Sogang contest before. But the Sogang contest was a department project, so there was no need to find sponsors, whereas UCPC had a lot of ups and downs, and I made mistakes.

The biggest mistake was that I didn't clearly define the sponsorship terms, and didn't properly share them with the sponsors. UCPC holds presentation sessions for promoting companies, and since I was worried that in an online stream participants would drop off midway and halve the effect, I set the sponsorship threshold high. But I'm sorry to say that, due to my own carelessness while distracted by other busy things, there was a sponsor who wasn't informed of this. From the next contest on, we should learn from this, and if possible, like PyCon does, set fair and clear sponsorship terms, post them on the website, and communicate closely with sponsors.

Once again, my endless thanks to our sponsors.

Preliminary stream rehearsal (July 23): The calm before the storm

Before the contest, we fleshed out the stream plan through a rehearsal. The organizers ate curry at Go Go Indian Cuisine, a famous Anam spot, then gathered in the Korea University College of Informatics lecture hall that would be our studio (raiding it in the middle of a noble joint contest) to check the room layout and equipment, see whether the internet was fast enough to stream, and discuss how to handle the solutions and/or sponsor session given the room's structure. For more on this, check out Jaeheon's UCPC 2020 broadcast retrospective; he's the one who thought about it the most.

Taking advantage of the fact that OBS can overlay browser windows, I built simple stream scenes in React as planned, right before the contest (until 3 AM on the day!). The code is up here.

Preliminaries (July 25): This place is filled with a dark aura; something seems about to happen

I pulled an all-nighter making the stream scenes, arrived at Korea University at 10, and started setting up. The organizers placed bets on how many teams would get an all-solve and when the first one would come in.

Then, as contest time approached, BOJ, the contest platform, started spitting out 500 Internal Server Error and 502 Bad Gateway errors. Uh…? I figured we couldn't run the contest properly like this, so I pushed the start back 10 minutes to 14:10.

It seemed to calm down a bit, but around 14:07 the same thing happened again. Just as I was wondering whether to delay another 10 minutes, BOJ Stack went down too. Contest settings have to be edited from an admin page called BOJ Stack. If BOJ Stack is inaccessible, even the organizers can't change the contest time.

I thought, ‘It'll be fine by 14:20, right? Then I'll extend the end time by 10 minutes or so.’ The server kept refusing connections as if to mock me. Meanwhile, teams started calling the phone number I'd put at the bottom of UCPC emails. I told them that even the organizers couldn't access the contest server.

Now we had to decide quickly and fairly what to do with the contest. In particular, I knew many teams had rented study rooms to gather from different areas and compete, so I thought about how to minimize the damage to them. In the middle of all this, we got a report that some team had read the problem titles on the contest site. A team having read the problem titles meant some teams might have read the problems, so we had to decide carefully.

Very fortunately, this UCPC was an online contest, so we weren't limited by space and could accommodate however many teams advanced to the finals. So we decided to go with the format of a corporate contest's qualification round, stating an explicit cutoff for the finals and greatly extending the time. Then I sent out a mass email.

But then, how kind of it, Google detected me trying to send a large number of emails from my iPad (a ‘new device’ from the Google account's perspective) and locked the Union's account. The password I'd changed when I became president didn't work, and I had to verify with the previous password — which was set by the president three terms before me. I contacted him immediately, but I couldn't just sit around waiting for a reply, so I sent the mass announcement and the problem set from my personal email. That was at 3 PM.

The server situation improved around 4 PM, and code could be submitted. We'd planned to do the editorial and scoreboard reveal for the preliminaries too, and the problemsetters had gathered for it, but unfortunately we couldn't do the stream after that. It was disappointing in many ways. You can read about why the server incident happened on the day of the preliminaries here.

As a result, 170 teams advanced to the finals, unintentionally making it the largest finals ever. Many said it would have been better to set the cutoff at 5 problems, but unfortunately at the time of the decision it was hard to gauge the teams' skill.

The finals ended up as big as the preliminaries, and the same thing couldn't happen again in the finals, so we prepared thoroughly. First, together with Startlink, we analyzed why it happened and took technical measures to prevent a recurrence. We decided to hold the finals on BOJ too, but just in case, the UCPC organizers also set up our own DOMjudge server as a backup.

Finals (August 1):

Very fortunately, the finals went smoothly without any problems.

Apart from server preparations, there were a few more things we prepared for the finals. The most notable one, which we also announced during the contest, was that this UCPC used a somewhat unusual freeze rule to make the scoreboard reveal more fun.

The freeze was 60 minutes before the end of the contest, but regardless of the freeze time, once a team solved 9 problems, all of that team's subsequent submissions were hidden. To do this, we didn't use BOJ's scoreboard and instead put the scoreboard on a separate site, scoreboard.ucpc.me. This was possible thanks to Suchan Park^tncks0121, who wrote a Python script that fetched all submissions from the admin scoreboard every $n$ seconds, hid what needed hiding, and showed the rest on the public scoreboard.

We originally planned to stream the solutions live, but since the solution slides were finished during the contest, and to give ourselves some breathing room, we switched to a pre-recorded broadcast. The solution slides used on the stream differ from the published ones: the stream slides have problems sorted by the difficulty order the setters had in mind, while the published slides are in A, B, C.. order. If there was a particular reason, it was so people could find the problem they need the solution for faster in the published slides.

After successfully wrapping up the finals, the organizers, minus me, apparently went off and had a delicious meat dinner. Unfortunately I was so exhausted that day that I just went home and passed out. A tragic ending.

How was it

Would it be cliché to say it was a tough but meaningful experience?

The hard parts

I'd heard plenty that being president of the Union is hard, but I didn't really know what specifically was hard. Now I roughly know.

• Finding sponsors was pretty hard. Being online made it even harder. Considering that ICPC's sponsorship situation isn't great this year either, it seems similar everywhere. So personally, I was pretty jealous of the sponsorship situation at the regional in the neighboring country.

• Handling prize money and shipping participation prizes by courier was another hard part.

• At the end of June, I joined Nexon Korea Engine Studio as an alternative-service industrial technical personnel. Until June I was unemployed so I didn't realize, but coordinating a contest alongside a 3-hour round-trip commute was physically pretty exhausting. There was even a time I stepped out of a company dinner to prepare for the contest.

• Other than that, participant registration was a hassle. Especially checking enrollment certificates and leave-of-absence certificates one by one was really tedious and tiring.

Still, since I wasn't preparing an on-site contest, I suspect I had a relatively easier time than in other years.

What I missed

I regret not handling the various unexpected situations during the contest properly and/or quickly. Just to revisit the ones I mentioned earlier, for example…

• GMail had a daily sending limit, and the mail server I was personally paying a monthly fee for to send from the shiftpsh.com and ucpc.me domains also had a daily sending limit.

• On a smaller note, the Zapier script connecting the call for tasks mail account to Slack intermittently didn't work, so we almost missed some submitted problems.

• Because we didn't verify email addresses through email confirmation or similar, some emails went missing during sending. It would have been nice to build our own registration site instead of using Google Forms. Combined with the reason above, it would have been even better to have a system that sent emails automatically.

• When the contest server went down, we had to decide the contest format without enough time to discuss. If we'd planned in advance what to do in such a situation, we could have reduced the participants' trouble and stress.

• I regret that we didn't prepare the stream plan and script in advance, so it felt a bit less smooth.

• (This wasn't an unexpected situation, it was just me being frazzled) Due to my carelessness, communication with a sponsor didn't go properly, and unfortunately this led to a somewhat unpleasant incident.

UCPC has grown to the point where it's now looking at 1,000 participants in the preliminaries. Thanks to the coding test craze, more and more people are getting into algorithmic problem solving and competitive programming, and as long as this trend doesn't fade, I expect the contest to keep growing. For a contest of this size, I belatedly feel it's right to identify, think through, and prepare for all the situations that can happen at that scale ahead of time.

The good parts, despite everything

There were many ups and downs, but I'm proud we successfully wrapped up the Union's first-ever online contest. Even COVID couldn't beat programming contests. 😎

It was fun and rewarding to create the best community contest with amazing, awesome people. Though since it was online, sadly I didn't get to meet the participants.

So, another year as president?

Actually, right after UCPC 2020 I also ran and set problems for SUAPC, and participated in testing and typesetting for the Sinchon camp contest and SNUPC. The experience and resources I got from UCPC helped a lot.

But I'm not sure I'll be president next year. For one, I'm working now, and above all, decisively, I got a really miserable result in the ICPC 2020 online preliminary, where I competed on a team of students on leave.

I figured it was because I was so busy running, setting, and testing various contests, and on top of that developing solved.ac, that I didn't have enough time to practice problem solving, so now I'm doing team practice again, joining Codeforces rounds often, and grinding BOJ problems. I'd like to take part as a contestant next year. When I go back to school, I have to make a triumphant return in red robes^赤衣還鄕 and live up to the Redshift name.

In conclusion, we're looking for someone to lead the Union next year. Well, if nobody turns up, I guess it can't be helped…

Wrapping up

My deep thanks to the Korea University SW-Centered University Program, MINDsLab and NAVER D2, Jongman Koo of Algospot, and Hyunmin Park^525hm of Kennysoft, for their special interest in and support of the Union and UCPC. Special thanks especially to Baekjoon Choi^baekjoon, the Union's first president and now of Startlink, who worked to the very end to resolve the preliminary server issue, even coding into the early morning.

My sincere thanks to Suchan Park^tncks0121, who helped a lot technically not only with testing but with running the contest overall; to Donghyun Kim^kdh9949, Changdong Kim^sait2000, Jeonghwi Na^jhnah917, Younghoon Noh^Diuven, Hyun Mo^ahgus89, Changhyun Moon^ckdgus2482, Bandeutbul^79brue, Geunwoo Bae^functionx, Yugeun Sim^cozyyg, Donggwan Lee^windflower, Sangheon Lee^evenharder, Jongyoung Lee^moonrabbit2, Giwoong Jung^QuqqU, and Changmin Cho^Ronaldo, who set great problems; and to Hoseok Ryu^rhs0266 and Eunki Hong^pichulia, who tested passionately.

Many thanks also to Inho Kong^inh212 and Younghyun Kim^kipa00, who were a huge help with operations toward the end, and to Jaeheon Jeong^Gravekper, who gladly agreed to host despite it being an experimental kind of contest.

Finally, thank you to all the participants of UCPC 2020 who love algorithmic problem solving.

Contest resources

I've published the materials used in UCPC 2020 online so they can help anyone hosting other programming contests.

Open source

• ucpcc/ucpc2020-site UCPC 2020 contest site
  A static site built with Jekyll. Made for posting contest announcements and such.

• ucpcc/problemsetting-guidelines UCPC description writing and formatting conventions
  Conventions established for creating UCPC problems. They can help with writing consistent data and descriptions.

• ucpcc/ucpc2020-description-layout UCPC 2020 problem statement layout
  A heavily modded olymp.sty. Based on the 2019 Sogang University Programming Contest problem statement layout.

• ucpcc/ucpc2020-solutions-theme UCPC 2020 solutions Beamer theme
  A theme you can use with Beamer.

• ucpcc/ucpc2020-broadcast-scene UCPC 2020 broadcast scenes
  16:9 broadcast scenes built with React, inspired by the fact that OBS can use a web browser in a scene.

Shared documents

• UCPC 2020 problemsetting status sheet
  The layout of the problemsetting status sheet we used to run the contest. It's not the sheet exactly as it was during the contest: the checkbox states are staged to help understanding, and information about unused problems has been removed since they may be used elsewhere. If you'd like to use it, click File > Make a copy to make an editable copy.

Other posts

• UCPC 2020 broadcast retrospective – by Jaeheon Jeong^Gravekper

• UCPC 2020 problemsetting retrospective – by Sangheon Lee^evenharder

• UCPC 2020 problemsetting retrospective – by Jeonghwi Na^jhnah917

• The July 25, 2020 server incident – by Baekjoon Choi^baekjoon

• UCPC 2019 retrospective: To run an algorithm contest – by Subin Ahn^subinium

• Round 1 solutions

In Round 2, I solved problems 1, 2, 3 and 5, getting 750 out of 1,000 points.

Problem 5 looked easier to implement than problem 4, so I solved 5 first. Then, looking at the partial scores, problems 1 + 2 + 3 + 4 + 47 points on problem 5 = 747 points, which is less than 1 + 2 + 3 + 5 = 750 points. So I was confident I was in the top 27, poked at problem 4 leisurely for a while, and gave up.

Here are my solutions to Round 2 problems 1, 2, 3 and 5. I didn't implement problem 4, so I only have a rough idea for it.

Round 2 Problem 1 – Matching Skills

There are two teams, A and B, each with $N \leq 300\ 000$ members. Each member has a skill value. We want to replace at most one member of A so that, when we match each member of team A with one member of team B, the total sum of skill differences over all matches is minimized.

We can make two observations.

• If no member of team A is replaced, it's obvious that the optimal strategy is to sort the skill values of team A and team B and match them one by one in descending order.

• If one member is replaced, no matter how we replace them, it's always better to replace them so their skill equals that of some team B member. In that case, the skill difference of the newly matched pair is $0$.

So instead of thinking of it as replacing a member of team A, we can think of it as excluding one member each from team A and team B and matching the rest optimally. To solve this, we sort both team A and team B and consider the following dynamic programming.

• $dp\left(i,0\right)$: the minimum sum of skill differences when matching members $\left[0, i\right]$ of team A and team B respectively.
  So $dp\left(i,0\right) = dp\left(i-1,0\right) + \left|A_i-B_i\right|$.

• $dp\left(i,1\right)$: the minimum sum of skill differences when excluding one member of team A and matching members $\left[0, i\right]$ of team A with members $\left[0, i - 1\right]$ of team B.
  So $dp\left(i,1\right) = \min\left\{ dp\left(i-1,0\right), dp\left(i-1,1\right) + \left|A_i-B_{i-1}\right| \right\}$.

• $dp\left(i,2\right)$: the minimum sum of skill differences when excluding one member of team B and matching members $\left[0, i - 1\right]$ of team A with members $\left[0, i\right]$ of team B.
  So $dp\left(i,2\right) = \min\left\{ dp\left(i-1,0\right), dp\left(i-1,2\right) + \left|A_{i-1}-B_i\right| \right\}$.

• $dp\left(i,3\right)$: the minimum sum of skill differences when excluding one member each from team A and team B and matching members $\left[0, i\right]$ of team A and team B respectively.
  So $dp\left(i,3\right) = \min\left\{ dp\left(i-1,3\right), dp\left(i-1,1\right), dp\left(i-1,2\right) \right\}$.

Once all of these are computed, the answer is the smaller of $dp\left(n,0\right)$ and $dp\left(n,3\right)$. I implemented it with 1-based indices.

#include <bits/stdc++.h>

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

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

int a[200001], b[200001];
ll dp[200001][4];

const ll inf = 1e18;

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

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

        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        sort(a + 1, a + 1 + n);
        sort(b + 1, b + 1 + n);

        dp[1][0] = abs(a[1] - b[1]);
        dp[1][1] = 0; // ignore a[i - 1]
        dp[1][2] = 0; // ignore b[i - 1]
        dp[1][3] = 0;

        for (int i = 2; i <= n; i++) {
            dp[i][0] = dp[i - 1][0] + abs(a[i] - b[i]);
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][1] + abs(a[i] - b[i - 1])); // ignore a[i - 1]
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][2] + abs(a[i - 1] - b[i])); // ignore b[i - 1]
            dp[i][3] = min({dp[i][1], dp[i][2], dp[i - 1][3] + abs(a[i] - b[i])});
        }

        cout << min(dp[n][0], dp[n][3]) << endl;
    }

    return 0;
}

Round 2 Problem 2 – Sweet Potatoes

$N\leq 300\ 000$ sweet potatoes are connected in a long line. Each sweet potato has a price of $-10^{12} \leq A_i \leq 10^{12}$. A negative value is a disposal cost, incurred because the potato has no commercial value.

With a budget of $M$, we want to cut the connected chunk of sweet potatoes appropriately and buy a middle chunk. The size of the chunk doesn't matter, but we can only buy one chunk. We want to cut the sweet potatoes so that we buy as expensive a chunk as possible without exceeding the budget $M$.

In short, it's the maximum subarray sum problem, but we need to find the largest sum that is less than or equal to $M$.

Because of this constraint, we can't use Kadane's algorithm, which solves the maximum subarray sum problem in linear time. But since we need to find a maximum subarray, we can approach it with a prefix sum array.

After building the prefix sum array $P$, if the current index is $i$, we just need to find the maximum of $P_i-P_j$ over $P_i-P_j \leq M$ with $j < i$. This can be easily done by inserting all prefix sums up to the previous index into a std::set and using std::set::lower_bound, which takes $\mathcal{O}\left(\log n\right)$. For some reason, during the contest I implemented it with std::set::upper_bound.

#include <bits/stdc++.h>

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

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

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

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

        int n;
        ll m;
        cin >> n >> m;

        set<ll> s;
        s.emplace(0);
        ll mx = 0, prf = 0;
        for (int i = 0; i < n; i++) {
            ll x;
            cin >> x;
            prf += x;
            s.emplace(prf);
            ll v = *s.upper_bound(prf - m - 1);
            mx = max(mx, prf - v);
        }

        cout << mx << endl;
    }

    return 0;
}

Round 2 Problem 3 – Part-time Job

Unfortunately I don't remember the description exactly, but you're given an array $A$ of size $N \leq 200\ 000$, and you perform $Q\leq 2\ 000$ operations that change the value at a specific index. After each operation, you need to find the median of the sums of all subarrays of $A$ of length $K \leq \min\left\{200,N\right\}$. If the number of possible subarrays is even, you need to find the larger of the two middle values.

BOJ 1572 is a problem where you have to find a constantly changing median. For that one, I made two std::multisets of equal size and kept every element of one set smaller than every element of the other. You can see my source code for 1572 here.

Let's set the original array aside and think of an array storing the subarray sums. When one element of the original array changes, at most $K$ elements of the subarray sum array change. Because of the condition $K \leq \min\left\{200,N\right\}$, even handling everything naively means at most $KQ \leq 400\ 000$ changes, so I figured that coding the above approach diligently would get AC, and got TLE.

Insertion/deletion in std::multiset has $\mathcal{O}\left(\log n\right)$ complexity, but the constant factor is large, so you have to be careful using it. To cut down the constant, I came up with a somewhat unusual segment tree and solved it.

Similar to the solution for BOJ 1572, I built two segment trees, $mxt$ and $mnt$. $mxt$ is a max segment tree and $mnt$ is a min segment tree, maintained so that $\max mxt \leq \min mnt$ always holds. To maintain this, if $\max mxt > \min mnt$, we need to swap the maximum of $mxt$ with the minimum of $mnt$, and we also need to support value updates at a specific index $i$.

For this, each tree node stores the max/min value along with the index in the array where that max/min value is located. Also, to make random access easy, I fixed the size of both segment trees to $N-K+1$, and a node value of $-1$ means that no value exists at this index in this tree.

I'm not sure if this is the intended solution. It seems like you could make it a bit faster by cleverly mixing in lazy propagation, but the code below got full marks too, so I decided to stop thinking about it.

I hear it can also be solved with a Fenwick tree of size $NK$. Well, Fenwick trees are fast, after all.

#include <bits/stdc++.h>

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

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

struct node {
    int i, v;

    node() : i(0), v(0) {}

    node(int i, int v) : i(i), v(v) {}

    bool operator<(const node &rhs) const {
        return v < rhs.v;
    }
};

node mnt[524288], mxt[524288];
int a[200001], val[200001], vals[200001];
ll prf[200001];
int tn, mxs, mns;

node minimum() { return mnt[1]; }

node maximum() { return mxt[1]; }

node argmin(const node &lhs, const node &rhs) {
    if (lhs.v == -1) return rhs;
    if (rhs.v == -1) return lhs;
    return min(lhs, rhs);
}

node argmax(const node &lhs, const node &rhs) {
    if (lhs.v == -1) return rhs;
    if (rhs.v == -1) return lhs;
    return max(lhs, rhs);
}

void setn(int i, int v, int x = 1, int s = 0, int e = tn - 1) {
    if (s == e && s == i) {
        mnt[x].v = v;
        return;
    }
    if (i <= (s + e) / 2) {
        setn(i, v, x * 2, s, (s + e) / 2);
    } else {
        setn(i, v, x * 2 + 1, (s + e) / 2 + 1, e);
    }
    mnt[x] = argmin(mnt[x * 2], mnt[x * 2 + 1]);
}

void setx(int i, int v, int x = 1, int s = 0, int e = tn - 1) {
    if (s == e && s == i) {
        mxt[x].v = v;
        return;
    }
    if (i <= (s + e) / 2) {
        setx(i, v, x * 2, s, (s + e) / 2);
    } else {
        setx(i, v, x * 2 + 1, (s + e) / 2 + 1, e);
    }
    mxt[x] = argmax(mxt[x * 2], mxt[x * 2 + 1]);
}

void update(int i, int dx, int x = 1, int s = 0, int e = tn - 1) {
    if (s == e) {
        if (mxt[x].v != -1) mxt[x].v += dx;
        if (mnt[x].v != -1) mnt[x].v += dx;
        return;
    }
    if (i <= (s + e) / 2) {
        update(i, dx, x * 2, s, (s + e) / 2);
    } else {
        update(i, dx, x * 2 + 1, (s + e) / 2 + 1, e);
    }
    mxt[x] = argmax(mxt[x * 2], mxt[x * 2 + 1]);
    mnt[x] = argmin(mnt[x * 2], mnt[x * 2 + 1]);
}

void init(int x = 1, int s = 0, int e = tn - 1) {
    if (s == e) {
        mnt[x].i = mxt[x].i = s;
        if (s >= tn / 2) {
            mxt[x].v = -1, mnt[x].v = vals[s];
            mns++;
        } else {
            mnt[x].v = -1, mxt[x].v = vals[s];
            mxs++;
        }
        return;
    }
    init(x * 2, s, (s + e) / 2);
    init(x * 2 + 1, (s + e) / 2 + 1, e);
    mxt[x] = argmax(mxt[x * 2], mxt[x * 2 + 1]);
    mnt[x] = argmin(mnt[x * 2], mnt[x * 2 + 1]);
}

bool exchange() {
    const auto mx = maximum(), mn = minimum();
    if (mx.v <= mn.v) return false;
    // set mntree
    setn(mn.i, -1);
    setn(mx.i, mx.v);
    // set mxtree
    setx(mx.i, -1);
    setx(mn.i, mn.v);
    return true;
}

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

    int t;
    cin >> t;

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

        int n, k, q;
        cin >> n >> k >> q;
        tn = n - k + 1;

        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            prf[i] = prf[i - 1] + a[i];
        }

        for (int i = k; i <= n; i++) {
            val[i - k + 1] = prf[i] - prf[i - k]; // [1, n - k + 1]
            vals[i - k] = val[i - k + 1];
        }

        init();
        while (exchange());

        cout << minimum().v << ' ';
        while (q--) {
            int i, v;
            cin >> i >> v;
            int d = v - a[i];
            for (int j = max(0, i - k); j < min(i, tn); j++) {
                update(j, d);
            }
            while (exchange());
            cout << minimum().v << ' ';
            a[i] = v;
        }
        cout << endl;
    }

Round 2 Problem 4 – Safe Driving

You're given the left and right boundaries of a road and a driving path. The road and the driving path consist of line segments, each parallel to the $x$-axis or the $y$-axis. We want to pick at most one horizontal segment of the driving path and reflect the rest of the path after it appropriately, so that the total length of the vertical segments of the driving path contained within the road is maximized. However, the path must not get longer after the reflection.

I thought it could be solved with coordinate compression followed by sweeping from top to bottom, or with a segment tree similar to problem 4 of Round 1. But by the time I'd solved 1, 2, 3 and 5, I was already guaranteed a top-26 finish in Round 2, so I gave up midway through implementing it.

Round 2 Problem 5 – Distance Between Triangles

There's a simple polygon with $N \leq 300$ vertices. It may be concave. We want to triangulate this polygon by connecting its vertices.

If we move from one triangle to another only through shared edges, we can define the distance between triangles. For example, the distance to a triangle adjacent to the current one is 1. We want to triangulate the given polygon so that the maximum distance between any two triangles is minimized.

For the Small set of this problem, the polygon is convex, so it's the same problem as ICPC 2019 Korea Regional Problem J. I got First Solve on that problem at the actual contest, so it was still fresh in my memory, which helped.

A triangulation of a polygon can be represented as a tree where every node has $\deg \leq 3$. Representing the triangulation as a tree, the problem becomes minimizing the diameter of this tree.

If we cut the given shape along some diagonal, the triangle formed on the right of that diagonal is always connected to the triangle formed on its left. Based on this, we can think of a 2D dynamic programming. Suppose we have a shape made using only points from the $i$-th point $P_i$ to the $j$-th point $P_j$, and $\overline{P_iP_j}$ is adjacent to some other triangle. Think of it as a polygon with one side open. That's the pink area in the figure below.

Now define $dp \left(i,j\right)$ as the shortest distance from $\overline{P_iP_j}$ to another triangle when the pink shape is triangulated well. Then for every $i<k<j$, if the triangle $P_iP_jP_k$ is contained in the original polygon, we can split along that triangle and solve the DP recursively.

So, letting $K_{ij}$ be the set of all $i<k<j$ for which $P_iP_jP_k$ forms a triangle, the shortest distance can come either from the $\overline{P_iP_k}$ side or the $\overline{P_kP_j}$ side, so $dp\left(i,j\right)$ can be computed as follows.

But this isn't enough to find the diameter of the tree. That's because this DP considers going from $\overline{P_iP_k}$ toward $\overline{P_iP_j}$ and from $\overline{P_kP_j}$ toward $\overline{P_iP_j}$, but it doesn't consider paths that go from $\overline{P_iP_k}$ through $P_iP_jP_k$ and back out toward $\overline{P_kP_j}$.

Let's redefine the recurrence. Given some value $d$, define $dp_d \left(i,j\right)$ as follows.

Now if we compute $dp_d\left(0,n-1\right)$ using this recurrence and the value isn't $\infty$, it means the polygon can be triangulated so that the tree's diameter is at most $d$. Now we can determine the minimum $d$ with binary search.

One run of the DP is $\mathcal{O}\left(n^3\right)$, and since $0 \leq d \leq n-3$, the problem is solved in $\mathcal{O}\left(n^3 \log n\right)$ total. There are various ways to determine whether a diagonal lies inside a concave polygon, but that doesn't seem to be the focus of the problem, so let's skip it.

I found out after the contest that there's apparently a paper that solves this problem.

#include <bits/stdc++.h>

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

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

struct point {
    int x, y;

    point() : x(0), y(0) {}

    point(int x, int y) : x(x), y(y) {}

    point operator*(const int &rhs) const {
        return {x * rhs, y * rhs};
    }

    point operator+(const point &rhs) const {
        return {x + rhs.x, y + rhs.y};
    }

    point operator-(const point &rhs) const {
        return *this + (rhs * -1);
    }
};


int ccw(const point &a, const point &b, const point &c) {
    point bb = b - a, cc = c - a;
    ll t = (ll) bb.x * cc.y - (ll) cc.x * bb.y;
    return t ? (t > 0 ? 1 : -1) : 0;
}

bool intersects(const point &la, const point &lb, const point &ma, const point &mb) {
    if (ccw(la, lb, ma) * ccw(la, lb, mb) != -1) return false;
    if (ccw(ma, mb, la) * ccw(ma, mb, lb) != -1) return false;
    return true;
}

point A[300];

const int inf = 1e8;

int dp[300][300], dg[300][300];

bool diag(int i, int j, int n) {
    if (i > j) swap(i, j);
    if (dg[i][j] != -1) return dg[i][j];
    if (i == j || i + 1 == j) return dg[i][j] = false;
    if (i == 0 && j == n - 1) return dg[i][j] = false;

    for (int v = 0, u = n - 1; v < n; u = v++) {
        if (intersects(A[i], A[j], A[u], A[v])) return dg[i][j] = dg[j][i] = false;
    }

    point V1 = A[(i + 1) % n] - A[i], V2 = A[(i + n - 1) % n] - A[i], V3 = A[j] - A[i];
    ll a = (ll) V1.x * V2.y - (ll) V1.y * V2.x;
    ll b = (ll) V1.x * V3.y - (ll) V1.y * V3.x;
    ll c = (ll) V3.x * V2.y - (ll) V3.y * V2.x;
    bool in = (a >= 0 && b >= 0 && c >= 0) || (a < 0 && !(b < 0 && c < 0));
    if (!in) return dg[i][j] = dg[j][i] = false;
    return dg[i][j] = dg[j][i] = true;
}

int f(int i, int j, int d, int n) {
    if (i + 1 == j) return dp[i][j] = 0;
    if (!(i == 0 && j == n - 1) && !diag(i, j, n)) return dp[i][j] = inf;
    if (dp[i][j] != -1) return dp[i][j];

    dp[i][j] = inf;

    for (int k = i + 1; k < j; k++) {
        if (!(i + 1 == k || diag(i, k, n))) continue;
        if (!(k + 1 == j || diag(k, j, n))) continue;
        if (f(i, k, d, n) + f(k, j, d, n) > d) continue;
        dp[i][j] = min(dp[i][j], max(f(i, k, d, n), f(k, j, d, n)) + 1);
    }

    return dp[i][j];
}

bool sat(int d, int n) {
    memset(dp, -1, sizeof dp);
    return f(0, n - 1, d, n) != inf;
}

int g(int x) {
    if (x == 3) return 0;
    if (x == 4) return 1;
    if (x == 5) return 2;
    return g((x + 1) / 2) + 2;
}

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

    int t;
    cin >> t;

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

        int n;
        cin >> n;

        memset(dg, -1, sizeof dg);

        for (int i = 0; i < n; i++) {
            cin >> A[i].x >> A[i].y;
        }

        if (n == 3) {
            cout << 0 << endl;
            continue;
        }

        int l = g(n), h = n - 3;
        while (l < h) {
            int m = (l + h) / 2;
            if (sat(m, n)) {
                h = m;
            } else {
                l = m + 1;
            }
        }
        cout << l << endl;
    }

    return 0;
}

Ever since I tried KaTeX on a project at work, I've been switching all the math on my blog to KaTeX. Rendering is much faster, and automatic line breaking of formulas works well on mobile. Personally, I think it's a better library than MathJax in many ways.

• Round 2 solutions

In Round 1, I solved problems 1, 2, 3, and 4, scoring 600 out of 800 points. I didn't couldn't get any partial points.

I had surgery the next day, and by the time I finished problem 4 it was already early morning, so I went to bed without solving problem 5. Overall, the problem descriptions felt pretty convoluted, which was a shame.

Here are my solutions to problems 1, 2, 3, and 4 from Round 1.

Round 1 Problem 1 – Diet

There are two restaurants, A and B, and each has $N \leq 50\ 000$ menu items. You're given the calorie values of these items. If you eat one meal at A and one meal at B every day for $K$ days, you want to minimize the maximum number of calories eaten in a single day.

Just greedily match them up one by one over the $K$ days: the highest-calorie dishes from restaurant A in order, with the lowest-calorie dishes from restaurant B in order.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

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

int a[200000], b[200000];

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

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        int n, k;
        cin >> n >> k;

        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a, a + n);
        for (int i = 0; i < n; i++) cin >> b[i];
        sort(b, b + n);
        int mx = 0;
        for (int i = 0; i < k; i++) mx = max(mx, a[i] + b[k - i - 1]);
        cout << mx << '\n';
    }


    return 0;
}

Round 1 Problem 2 – Card Game

There are two decks, X and Y, each with $N \leq 3\ 000$ cards stacked. Each card has a positive integer of at most $K \leq 3\ 000$ written on it. Two players take turns taking cards, where

• you must choose exactly one deck and take one or more cards from the top,

• the sum of the cards taken must be at most $K$,

• and the player who takes the last card loses.

If we call the state where, on my turn, there are $i$ cards left in deck X and $j$ cards left in deck Y $\left(i,j\right)$, then for a game with fixed $N$ and $K$, there are $\left(N+1\right)^2$ possible intermediate states in total. For each state, assuming both players play optimally, we want to count the number of states where I'm guaranteed to win and where I'm guaranteed to lose.

Grundy numbers might come to mind right away, but unfortunately this is a game where the player who takes the last card loses (misère), so we can't use Grundy. Before reaching for Grundy, it's worth asking yourself, “Is this really the kind of knowledge that would show up in Problem 2 of Qualification Round 1?”

Instead, we can approach it with dynamic programming.

• If from the current state $\left(i,j\right)$, no matter which deck I take from or how many cards I take, every resulting state is one where the next player wins, then the current state is a losing state for me.

• Otherwise, there's some move I can make that puts the next player in a losing state. In that case, the current state is a winning state for me.

So, after setting up a DP table, we just take cards one at a time from X and one at a time from Y, keeping the sum of the taken cards at most $K$, and check whether there's a state where the next player wins. Since we do this computation for $\left(N+1\right)^2$ states, it's $\mathcal{O}\left(N^3\right)$.

Since $N \leq 3\ 000$, this isn't enough to solve the Large set. We can optimize it to $\mathcal{O}\left(N^2\right)$ using prefix sums.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

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

int x[3010], y[3010], xp[3010], yp[3010], xi[3010], yj[3010];
bitset<3010> dp[3010];
int prs[3010][3010];

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

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        memset(dp, 0, sizeof dp);
        dp[0][0] = true;

        int n, k;
        cin >> n >> k;

        for (int i = 1; i <= n; i++) {
            cin >> x[i], xp[i] = x[i] + xp[i - 1];
            int v = xp[i] - k - 1;
            int ii = upper_bound(xp, xp + i, v) - xp;
            xi[i] = ii;
        }
        for (int j = 1; j <= n; j++) {
            cin >> y[j], yp[j] = y[j] + yp[j - 1];
            int v = yp[j] - k - 1;
            int jj = upper_bound(yp, yp + j, v) - yp;
            yj[j] = jj;
        }

        int a = 0, b = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                int xc = (prs[i][j + 1] - prs[xi[i]][j + 1] - prs[i][j] + prs[xi[i]][j]);
                int yc = (prs[i + 1][j] - prs[i + 1][yj[j]] - prs[i][j] + prs[i][yj[j]]);

                dp[i][j] = ((i - xi[i]) - xc) || ((j - yj[j]) - yc);
                dp[0][0] = true;
                (dp[i][j] ? a : b)++;
                prs[i + 1][j + 1] = dp[i][j] + prs[i][j + 1] + prs[i + 1][j] - prs[i][j];
            }
        }

        cout << prs[n + 1][n + 1] << ' ' << (n + 1) * (n + 1) - prs[n + 1][n + 1] << endl;
    }


    return 0;
}

Round 1 Problem 3 – Ladder Game

There's a ladder with $N \leq 1\ 500$ vertical lines and $K \leq 2\ 000$ horizontal lines.

$M \leq 100\ 000$ queries come in, each of the form $\left(i,j\right)$. We want to manipulate the ladder by removing some horizontal lines so that a path starting at position $i$ at the top ends at position $j$ at the bottom, and we need to find the minimum number of horizontal lines that must be removed.

It's quite similar to Problem E from Kotlin Heroes: Episode 4.

I approached it by thinking of the horizontal lines as edges of a graph, and solved it as a shortest path problem.

If there's a horizontal line connecting $u$ and $v$, we create $4$ edges: the cases that ignore the horizontal line ($u \rightarrow u$, $v \rightarrow v$) with weight $1$, and the cases that don't ignore it ($u \rightarrow v$, $v \rightarrow u$) with weight $0$.

We create $N$ vertices at the start, and each time we process a horizontal line, we add one more at each endpoint of the line, for $2$ more in total. Building the graph this way gives $N+2K \leq 5\ 500$ nodes in total.

Now, if we run Dijkstra or 0-1 BFS from each starting point to get the shortest distance to each endpoint, that gives the maximum number of horizontal lines that need to be removed on the way from the start to the end. Using this, we preprocess all the query answers, then just print the precomputed values as the queries come in.

The graph we built has $N+2K$ vertices and $4K$ edges, so a single run takes $\mathcal{O}\left(N+K\right)$ with 0-1 BFS, or $\mathcal{O}\left(K \log K\right)$ with Dijkstra. Running it once for every starting point solves the problem in $\mathcal{O}\left(N^2+NK\right)$ with 0-1 BFS, or $\mathcal{O}\left(NK \log K\right)$ with Dijkstra. I just went with Dijkstra.

Apparently it can be solved with DP too.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

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

pii seg[2000];
int last[1500], dist[1500][1500], dtemp[9000];
bitset<9000> vis;

void dijk(int s, const vector<vector<pii>> &graph) {
    memset(dtemp, -1, sizeof dtemp);
    vis.reset();
    priority_queue<pii> pq;
    dtemp[s] = 0;
    pq.emplace(0, s);
    while (pq.size()) {
        int u = pq.top().second, d = -pq.top().first;
        pq.pop();
        if (dtemp[u] < d) continue;
        if (vis[u]) continue;
        vis[u] = true;
        for (const auto &kv : graph[u]) {
            int v = kv.first, c = kv.second;
            if (dtemp[v] == -1 || dtemp[u] + c < dtemp[v]) {
                dtemp[v] = dtemp[u] + c;
                pq.emplace(-dtemp[v], v);
            }
        }
    }
}

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

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        memset(dist, -1, sizeof dist);

        int n, k, q;
        cin >> n >> k >> q;

        vector<vector<pii>> graph(n);
        for (int i = 0; i < n; i++) last[i] = i;

        for (int i = 0; i < k; i++) {
            cin >> seg[i].first >> seg[i].second;
            seg[i].first--, seg[i].second--;
        }

        for (int i = 0; i < k; i++) {
            const auto &l = seg[i];
            int gn = graph.size();
            graph[last[l.first]].emplace_back(gn, 1);
            graph[last[l.second]].emplace_back(gn + 1, 1);
            graph[last[l.first]].emplace_back(gn + 1, 0);
            graph[last[l.second]].emplace_back(gn, 0);
            last[l.first] = gn;
            last[l.second] = gn + 1;
            graph.emplace_back();
            graph.emplace_back();
        }

        for (int i = 0; i < n; i++) {
            graph[last[i]].emplace_back(graph.size(), 0);
            last[i] = graph.size();
            graph.emplace_back();
        }

        for (int i = 0; i < n; i++) {
            dijk(i, graph);
            for (int j = 0; j < n; j++) dist[i][j] = dtemp[last[j]];
        }

        int s = 0;
        while (q--) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            s += dist[u][v];
        }
        cout << s << endl;
    }

    return 0;
}

Round 1 Problem 4 – Numbers in Range

You're given a string $t$ made up of $n \leq 50\ 000$ digits from 0 to 9. Treat each substring of length $k \leq \min\left\{9,n\right\}$ as a number, and place them all on a number line.

Now, by changing at most one character to 1, we want to maximize the maximum number of numbers that fall within an interval $\left[a,a+m\right]$ of length $m \leq 10^9$ for some integer $a$. We need to find that maximum.

First off, $k$ is at most $9$, and $n$ isn't that big either, so if we ignore the fact that we can change one character to 1, this problem can be solved with a sweep. If we call the value of a substring $x_i$, we lay the segments $\left[x_i,x_i+m\right]$ on the number line and find the number of segments at the point where the most of them overlap.

Now let's consider being able to change one character to 1. I didn't feel there was any particularly special property to observe in the act of “changing one character to 1.” Instead, I focused on the fact that changing one character to 1 means only $9$ segments need to be rebuilt.

If there were a sweep that could dynamically remove and add segments, then even if we changed each position's digit to 1 one by one and reverted it, there would only be $\mathcal{O}\left(kn\right)$ additions/removals, so it seems like it'd fit in the time limit.

Fortunately, such a sweep exists: you can do it with a segment tree that supports a max query and range addition (lazy propagation, etc.).

However, the indices are pretty large, so you have to either implement a dynamic segment tree or coordinate-compress all possible values before processing. I went with the latter. The total time complexity is $\mathcal{O}\left(kn \log kn\right)$.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

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

ll tree[1048576 * 2], lazy[1048576 * 2];

int c;

void _propagate(int x, int s, int e) {
    if (!lazy[x]) return;
    tree[x] += lazy[x];
    if (s != e) {
        lazy[x * 2] += lazy[x];
        lazy[x * 2 + 1] += lazy[x];
    }
    lazy[x] = 0;
}

ll _maximum(int x, int s, int e, int l, int r) {
    _propagate(x, s, e);
    if (l > e || r < s) return 0;
    if (l <= s && e <= r) return tree[x];
    int m = (s + e) / 2;
    return max(_maximum(x * 2, s, m, l, r),
               _maximum(x * 2 + 1, m + 1, e, l, r));
}

void _update(int x, int s, int e, int l, int r, ll dv) {
    _propagate(x, s, e);
    if (l > e || r < s) return;
    if (l <= s && e <= r) {
        tree[x] += dv;
        if (s != e) {
            lazy[x * 2] += dv;
            lazy[x * 2 + 1] += dv;
        }
        return;
    }
    int m = (s + e) / 2;
    _update(x * 2, s, m, l, r, dv);
    _update(x * 2 + 1, m + 1, e, l, r, dv);
    tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
}

ll maximum(int l, int r) {
    return _maximum(1, 0, c - 1, l, r);
}

void update(int l, int r, ll dv) {
    _update(1, 0, c - 1, l, r, dv);
}

ll zip(ll x, const vector<ll> &a) {
    return lower_bound(a.begin(), a.end(), x) - a.begin();
}

ll v[50000], v1[50000][10];

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

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        ll n, k, m;
        cin >> n >> k >> m;
        string t;
        cin >> t;

        // init values
        vector<ll> ps;
        ll curr = 0, mod = 1;
        for (int i = 0; i < k; i++) mod *= 10;
        for (int i = 0; i < k; i++) curr *= 10, curr += t[i] & 15, curr %= mod;
        for (int i = k; i <= n; i++) {
            v[i - k] = curr;
            ps.emplace_back(curr);
            ll l = curr, r = 0, p = 1;
            for (int j = 0; j < k; j++) {
                v1[i - k][j] = (l / 10 * 10 + 1) * p + r;
                ps.emplace_back(v1[i - k][j]);
                l /= 10, r += (curr / p) % 10 * p, p *= 10;
            }
            if (i == n) break;
            curr *= 10, curr += t[i] & 15, curr %= mod;
        }
        int ts = ps.size();
        for (int i = 0; i < ts; i++) ps.emplace_back(ps[i] + m);

        sort(ps.begin(), ps.end());
        ps.erase(unique(ps.begin(), ps.end()), ps.end());

        memset(tree, 0, sizeof tree);
        memset(lazy, 0, sizeof lazy);
        c = ps.size();
        // query
        for (int i = 0; i <= n - k; i++) {
            update(zip(v[i], ps), zip(v[i] + m, ps), 1);
        }

        ll mx = maximum(0, ps.size() - 1);

        for (int i = 0; i < n; i++) { // replace i-th number to 1
            // remove
            for (int j = 0; j < k; j++) {
                if (i - k + j < 0 || i - k + j > n - k) continue;
                update(zip(v1[i - k + j][j], ps), zip(v1[i - k + j][j] + m, ps), -1);
            }
            if (i <= n - k) {
                update(zip(v[i], ps), zip(v[i] + m, ps), -1);
            }
            // add
            if (i - k >= 0) {
                update(zip(v[i - k], ps), zip(v[i - k] + m, ps), 1);
            }
            for (int j = 0; j < k; j++) {
                if (i - k + 1 + j < 0 || i - k + 1 + j > n - k) continue;
                update(zip(v1[i - k + 1 + j][j], ps), zip(v1[i - k + 1 + j][j] + m, ps), 1);
            }
            // query
            mx = max(mx, maximum(0, ps.size() - 1));
        }
        cout << mx << endl;
    }

    return 0;
}

Hi, this is Suhyun Park, the operator of solved.ac. This isn't the official blog but my personal one, but since solved.ac doesn't really have a good place to post something like this, I decided to write it here.

solved.ac started its closed beta last July, and as of now it's been running for 10 months. Here's why I've been running the site as a whitelist-based closed beta:

1. In the early days of the site, very few problems had difficulty ratings (~2,000 contributions from Sogang University), and there was no proper standard for difficulty, so I wanted to shape a direction for a difficulty standard that many people could consider reasonable

2. Since Startlink doesn't officially allow scraping BOJ, I needed to keep the number of scraped users down in order for the site to keep existing

That said, I really hoped a lot of people would get into problem solving through this site, so with that in mind I left difficulty lookups open to everyone, even those not on the whitelist.

Later, as the integration with BOJ was decided, the impact of (2) shrank, so I slowly expanded the whitelist. Currently, 15,342 users are on the whitelist. Compared to 3,517 in August, right when the beta started, that's about a fivefold increase.

However, individual whitelisting had its side effects, so I stopped accepting individual whitelist applications in March. Here's why:

• People frequently copied other people's source code and submitted it to meet the tier requirement for individual whitelisting. Neither solved.ac nor BOJ allows this, and solved.ac removed such users from the whitelist as soon as cases were found.

• The load of scraping individually whitelisted users grew. The current structure of solved.ac is designed so that scraping group whitelists works much more efficiently.

Reports of malicious users copying and pasting source code increased, so I ended up handling requests I wouldn't have had to deal with if I hadn't created the individual whitelist in the first place, which took time away from developing other features, not just for me but for Startlink as well. I decided to stop accepting individual whitelist applications, judging that spending that time on the integration work or on new features would be far more beneficial to the users waiting for the integration.

Since then, I've received a lot of criticism and reproach from some BOJ users (mostly saying it's unfair), and after much thought, I've decided to stop accepting the group whitelist, which I'd kept open, after May 16. However, once the integration with BOJ is completed soon, everyone will be able to use the site regardless of the whitelist, so I kindly ask you to wait just a little longer.

Thank you.

Additionally, below are some frequently asked questions about the site and my answers to them.

What's good about the integration? – Once the integration is done, the beta ends. The whitelist goes away and anyone can log in. Right now each user and group has a fixed update interval, but after the integration I plan to make experience points reflect immediately as soon as you solve a problem.

What's your salary? / How much are you paid for this? – solved.ac is entirely my personal project, and I'm not receiving anything other than donations. That said, the operating costs are supported by Startlink.

Are there plans to provide an API? – There are plans, but it's not a high priority. The main reason is that I don't have enough time to write documentation. If you want to build something using solved.ac's content, rather than crawling the solved.ac site itself, please figure out the undocumented API endpoints by reverse engineering the plugin source code and use those.

My whitelist application was rejected / I was removed from the whitelist for copying source code. Can I use the site normally after the integration? – You'll be able to log in, but according to solved.ac's rules, your experience points will remain fixed at 0 for 65,535 days even after the integration.