This is my second ICPC regional and my first Seoul regional. Ironically, my first regional was the 2019 Bangkok Regional.

In 2018 I was a freshman, my Codeforces rating was blue, and most importantly, I hadn't even been doing competitive programming for a full year, so I just went with my adorable fellow freshmen to get a feel for ‘oh, so this is how contests work~’. Over the winter I did some hard training of my own on Codeforces and pushed my rating up to 2000, and this year I prepared with the goal of winning an award. So this was the first year I seriously prepared for ICPC, and I'd like to write down how I prepared, from the preliminary all the way to the regional.

Team practice

I had never done team practice before, so I asked my teammates how they'd done it in the past, but their memories seemed hazy. So I just ran things somehow myself.

Picking dates and places

I think we started team practice a bit late. After the semester started (in September at the earliest), we set dates and times so all three of us could make it. The place was either the club or a PC bang, and the time was 7:30 PM, twice a week.

학회실 못 써서 팀연습하러 PC방에 49시간 충전하는 흑우가 있다 pic.twitter.com/GvQQXkBDSM

— shift* 시프트 (@shiftpsh) September 16, 2019

At Sogang University, the four computer science lab rooms are each managed by a study club (ICPC Team, Release, CSPC Lab, CNU), and when there are no classes in a lab, CS students can use it freely. Opening the lab outside the department's official hours is up to the club, so it was a pretty nice setup: we could start practice at 7:30 PM, solve problems until 12:30 AM, read the editorial, and then go home. On days when the lab had classes, though, we had to practice at a PC bang, and besides the cost, using your brain in a noisy environment was a real ordeal. Well, couldn't be helped.

Picking a platform

At first we practiced by joining virtual contests on Codeforces Gym, and at some point we switched to using the practice feature of BOJ groups.

Codeforces Gym has a feature called Ghost. It reflects the submission history of the actual contest on the scoreboard, and I think the upside is that you can gauge where you would've ranked if you'd actually taken part in that contest. But early in our team practice, I only picked sets that were way too easy or way too hard, so it wasn't very meaningful, and so we moved to BOJ to avoid getting stressed out by the scoreboard + to train ourselves to spot the easy problems quickly.

The BOJ practice feature is really simple, so there's not much to explain. You set the practice time and register the problems in advance. Of course, the scoreboard only shows group members who participated during that time. When we couldn't find the easy problems, we'd pull up the final scoreboard on the contest's official site 1–2 hours into the contest. I don't think it was a great method.

Picking sets

Again, I knew nothing about ICPC regionals, so at first I literally picked whatever. Our first two team practices weren't ICPC regional sets. If I remember correctly, the first was an unofficial contest and the second was the KAIST RUN contest.

Every set I picked seemed to be either super easy or super hard, so I figured this wasn't going to work and looked up a bunch of posts online. After that, I relied a lot on the ICPC-style section of koosaga's How I practice problem solving, and mostly picked European regionals, especially NWERC. Subregionals were too easy, and regionals seemed to be the most appropriate difficulty. We also did sets recommended to us on the BOJ Slack.

We ended up doing about 13 sets in total before the contest. Personally, I do kind of regret not starting practice in the spring.

Building a strategy

Since it's not a solo contest, the more we practiced, the more I realized how important it is to schedule who solves which problem and when. Things like ‘this was definitely a problem we could solve, so why didn't we?’ happened a lot until about midway through our practice. The typical cases were

• when the solution seemed right but kept getting WA

• when I'd come up with a perfect solution, but another teammate spent all the time debugging so I couldn't even get it into code

.

The first case is most likely a simple mistake, so at onsite contests it's common to request a printout of your code and have another teammate work on a different problem. But I didn't know that, and on top of that you can't print at a PC bang… so taking advantage of the big PC bang monitors, another teammate worked on a different problem on the left side while I put my code up on the right side and debugged it by eye. I wish I'd known sooner that printing is available onsite.

The second case was a scheduling problem. For example, it's the case where ‘I've got solutions for E, F, and H!’ but someone keeps debugging J, and J creates a bottleneck for E, F, and H. So we prioritized writing solutions we were sure about over debugging wrong ones. And since only one person can use the computer, we tried to never leave the computer seat empty. With this strategy, the number of ‘problems we could've solved but didn't’ dropped a lot.

Learning from failure

Lastly, after each contest, we always read the editorial. We analyzed whether it was a technique we knew, and if we knew it, what we did wrong; if we didn't, we learned something new: oh, so this technique exists. Techniques we didn't know or ones we made lots of mistakes with went into the team notebook. Though as it turned out, we didn't really need the team notebook at the actual contest…

Solving the contest problems you couldn't solve after practice is called upsolving^upsolving, but by the time we'd read the whole editorial and discussed where we went wrong, it was well past 1 AM, and we had to come back to school during the day, so sadly that was too much. If circumstances allow, I'd really like to do upsolving too in future practice.

Preliminary

The preliminary was held at our school, in a homey atmosphere. In the club lab, no less. It's a place I'm always at, so I thought I'd be able to compete comfortably, but the server was in shambles, so I couldn't. Anyway.

In the preliminary, we solved 6 problems quickly.

I. Registration (3 min, shiftpsh): A problem that's been showing up consistently since 2013. You just print your ID and password. Right after the contest started I think I heard people all over going ‘hey, where's the registration one’, but the submission server was broken so it didn't matter. I thought it was just because everyone was submitting the registration problem, but…

B. Balanced String (14 min, semteo04): An easy problem where you compute $2^{\left\lfloor\frac{n+1}{2}\right\rfloor}$. It was an easy problem, but the server was broken so we ended up submitting about 5 minutes later than when we actually solved it.

H. Four Squares (24 min, shiftpsh): I'd solved Lagrange's four-square theorem before, so I wrote it quickly.

C. Byte Coin (32 min, lvalue): It was an easy greedy, so it got written quickly. Again, the submission got delayed a few minutes because of the judging server.

L. Two Machines (73 min, semteo04): It was a knapsack DP. I knew it was knapsack, but the solution suddenly escaped me, so I declared that I couldn't write it.

D. Canal (117 min, shiftpsh): I was thinking about it, and semteo04 said it was binary search, so I trusted multiset and wrote it. Because of the contest server, we didn't get the judging result for this one until an hour or two after the contest ended, and after hearing another team say their multiset blew up, I was crushed and decided to calm my body and soul by watching the Yeouido fireworks.

pic.twitter.com/421LdWXW3r

— shift* 시프트 (@shiftpsh) October 5, 2019

Sogang University isn't that far from Seogang Bridge, so I walked from school to Seogang Bridge without thinking much and watched the fireworks alone. Right before I got to Seogang Bridge, the judging results were released, and I was relieved to find out D was accepted. Apparently we were 9th before the freeze.

It was such a shame that we couldn't solve J even though we knew it was the convex hull trick, and when I went to copy the code from the team notebook, the code in there was just the Commando solution. I brought an improved version to the regional afterwards, but there was no CHT at the regional. So mean

It was also a shame we didn't realize A was LR flow. But I think even if we'd written more code, the chance of getting more problems accepted was slim anyway with the server down.

Fast-forwarding…

The day before the regional

The regional is an onsite contest, and at onsite contests you get to meet lots of people you'd otherwise only see online, so the day before, I was busy chatting and sadly didn't get to practice.

Team Redshift @ Sogang U
+ Team Twitter Heavy Light Decomposition @ Hanyang U
+ Team JonMatTaeng @ POSTECH pic.twitter.com/mZgRwOXlHE

— shift* 시프트 (@shiftpsh) November 8, 2019

We had dinner the night before the contest with team Twitter HLD from Hanyang University and team JonMatTaeng from POSTECH. I don't remember the restaurant's name, but it was pretty good. Please open a branch near Sogang too.

Everything seems to be concentrated in the Yonsei/Ewha commercial area, so Sogang students have to go down toward Sinchon to eat or do anything, and here too almost everything is concentrated in the Konkuk University area, so I wondered if Sejong University students also have to go down toward Konkuk. If I'm right, Sogang and Sejong surprisingly have something in common. Though Sogang is a much smaller school…

??? pic.twitter.com/aM9qEjXeYQ

— shift* 시프트 (@shiftpsh) November 8, 2019

The contest was in the morning the next day, so we stayed at a nearby hotel. There was a concert I wanted to go to, but I couldn't sign up because of the contest schedule, and it turned out it was held in the building right next to our hotel. Why are you doing this to me

Regional

First thing after waking up, I did a lot of chocolate doping. It was Pepero Day season, so there was a 2+2 deal on Ferrero Rocher, and I should've stocked up…

One of my teammates didn't come to the hotel because of an exam they had to take on the day of the regional, studied at school instead, and overslept. Fortunately, the taxi driver transported(?) them at an admirable speed, so we avoided disqualification.

At the regional, we solved 7 problems. My personal goal was 7 problems and I was really happy we hit it. On top of that, we were the first to solve C and J.

J. Triangulation (11 min, shiftpsh, First to solve): A was a pretty easy problem, so lvalue came up with a solution right away and started implementing, but I was looking at J, drew a picture, and…

…it looked like it'd be way easier to implement than any other problem, so I cut in and submitted it. I came up with the idea quickly and luckily got the first solve. I was glad there were no server issues.

Right after solving J, we were 1st for a very brief moment. I took a screenshot, and after the contest I took a photo of the computer screen with my phone.

A. Fire on Field (13 min, lvalue): An easy problem where you just implement what it tells you to. When I cut in to write J, the code for A was almost done, so it got submitted right away and accepted.

L. What’s Mine is Mine (36 min, semteo04): A simple type of DP, so semteo04 solved it quickly.

I. Thread Knots (47 min, shiftpsh): Just looking at the picture, the problem smelled like binary search. I knocked it out right away.

B. Gene Tree (103 min, semteo04): We knew it was tree DP, but there were squares mixed in, so the formula came out monstrous. While I was busy expanding the formula, I said something like ‘what if we break it down and think of it like this?’, and semteo04 seemed to have an idea, implemented it hard, submitted, and got AC.

H. Strike Zone (164 min +2, semteo04): I figured mixing Kadane’s with a segment tree would work, so I wrote it first and submitted twice, but got WA. It turned out to be the exact same problem as Gold Mine from KOI 2014 middle school division. lvalue and I had no experience preparing for or competing in the Olympiad in Informatics so we didn't know, but semteo04, who did, threw out my code, rewrote it, and got it accepted in no time.

C. Islands (204 min +6, lvalue, First to solve): None of the remaining problems looked solvable, so lvalue took this one, and honestly nobody knows to this day why it got accepted. Whether the solution is actually correct or the data is just weak…

Problem K, Washer, seemed to deal with 3D, so I was writing code for 3D vector operations, and 15 minutes before the end of the contest I thought ‘what if we cut it with planes and brute-force in $\binom{100}{3}\times 2^3$?’ and implemented it that way, but kept getting WA. After the data was uploaded to BOJ, I implemented the same approach again and submitted it, and got AC, which was so frustrating. I probably implemented the cross product wrong or messed up the output format…

#8 pic.twitter.com/RginoGOZ1v

— shift* 시프트 (@shiftpsh) November 9, 2019

Our final placement was 15th in the team ranking and 8th in the school ranking. It's the first time in 4 years since 2015 (6th) that Sogang University placed in the single digits in the school ranking, so I was satisfied with the result. We also upheld the legend that teams named with a color plus a nickname win awards (BlueJoker in 2017, PurpleNoon in 2015).

Personally, I'm a bit disappointed since I didn't solve that many + never solved K in the end. Still, I made a lot of assists, so maybe it was okay ..?

It was a shame that the scoreboard was only revealed after the award ceremony. Did it really have to be this way… Still, the regional was run well overall (especially in that CLion was available!), and the snacks and dinner were delicious. Thank you.

I actually found out that overseas regionals have a registration fee because of the Bangkok contest, and it turns out Korea was the unusual one for not having one. Apparently there'll be a registration fee starting next year, and I'm fine with whatever the fee is, as long as problems like the preliminary server issues don't happen again.

I'm planning to take a leave of absence for a while, so I think the next one I'll take part in will be the 2022 or 2023 regional. Like our team name says, I'd love to actually make red and go to the World Finals at least once!

Great work, everyone. 🎈

The title says it all: I hosted this year's Sogang University programming contest. I was in charge of both problem setting and running the contest! Apart from Real Gudegi Cup 2018 (…), this was my first time setting problems, and apart from volunteering as balloon staff at UCPC 2018, my first time running a contest. I'd like to write down some thoughts from preparing and running it.

What do I do first

At Sogang University, every year since 2005, the team(s) ranked 1st–2nd within the school at the ICPC Korea Regional have run the contest and set the problems. The contest is usually at the end of November and the ICPC Regional is held in early November, so you usually get about 2–3 weeks to prepare. Wait, I don't even know what it takes to run a contest, how am I supposed to prepare one in two weeks??

But as with everything in life, surprisingly, once the contest date gets closer you just end up preparing. Three teams from our school competed at the ICPC Regional, and while running the happy-thoughts circuit of 'Our team will at least place 2nd among them, right?', I counted my chickens 10⁹ + 7 times over and started preparing for the contest in advance.

Here's roughly what you need to host a contest.

• Problems. It's a contest for solving problems, so you can't go without problems.

  • Problem setters. Without setters, there can't be any problems in the first place.

  • Testers. Of course, it's fine for the setters to do the testing too.

• Time and place. You need to decide when and where to hold it.

• Participants. Not much I can do about this one..

• Posters, balloons, snacks, stuff like that

Out of these, the only thing I could do at that point was make problems. If Redshift placed 1st or 2nd in the school at the Regional, all three of us would have to set problems, so we decided to start vaguely thinking within the team about what problems to set. Here are roughly the ideas we came up with.

• 7-segment display (shiftpsh's idea)

  • I personally thought it was a good problem, so I even made a generator for it.

• A graph isomorphism problem to prevent anyone from solving everything (shiftpsh's idea)

  • It got weakened and set as a tree isomorphism problem. Apparently this is well-known for people at orange and above. Why is everything I think isn't well-known actually well-known??

• A shortest path problem, but since the product of the lengths has to be minimized, you take the log of every edge weight (lvalue's idea)

  • This idea came up on the practice day of the Bangkok Regional, but it actually showed up the next day as problem F(?) in the main contest, so we couldn't use it in our contest for fear of plagiarism accusations.

  • Thanks to this idea, our team was the second fastest to solve F during that contest, but ironically, it became the reason we bombed the contest. More on this in another post.

Fortunately, we managed to place 1st in the school at the Seoul Regional, so we got to take part in running the contest, and now we had to consider all four of the 'things needed to run a contest' I mentioned earlier.

Problems

Everyone has problems they want to set, but I figured that if everyone actually set only the problems they wanted, it could end up being a brutal-implementation coding test instead of a programming contest, or a veteran's data structure party, or a computational math olympiad. So I set the overall framework of the contest problems with the following principles.

• The topics of the problems should be balanced.

  • Having 5 DP problems out of 12 is kind of.. (Are you listening, ICPC Seoul preliminary setters?)

• Nobody should solve every problem, and nobody should solve zero.

  • I heard this is the ICPC problem-setting philosophy.

Personally I really wanted to set the tree isomorphism problem, so we decided on 8 problems per division, 16 problems in total. Looking back, we shouldn't have, or we should have had some problems shared between divisions, but anyway, that's what we decided.

I remembered setting up a spreadsheet to organize problems for the Gudegi Cup, so I did the same.

After proposing 20 problems, we wrote down each one's expected difficulty on the solved.ac scale and the algorithms/data structures used, and assigned 8 problems each to Champion and Master. Along the way, it looked like the contest would get too hard, so we cut 4 problems from the topics that showed up a lot. Then we prepared the problems by filling in the circles one by one.

Setting expected difficulties had its pros and cons:

• The pro was that assigning problems was easy,

• and the con was that we misjudged problem difficulty and the Master division scoreboard was a disaster.

  • I realized that setters and participants think very differently, and felt that I should try harder to think about problem difficulty from the participants' point of view.

After assigning the problems, we made them in this order: statement and reference solution – data and testing – limits.

Statements

From a participant's point of view, the clearer the statement, the better. Contests held on a certain Russian site often had vague or weird statements, and since I'd been stressed out by that, I tried to write statements that wouldn't get in the way of participants solving the problems. Unless the intent is to deliberately slow people down with a long statement, cut the unnecessary stuff, eliminate grammatical errors and awkward sentences as much as possible, and keep sentences short. Honestly, that's just the basics of writing.

Below is a comparison of the draft and final versions of the statement for Placing Cards.

Which one is easier to understand, the top or the bottom? (Please say the bottom)

• It's hard to tell exactly how big 1000000 is at a glance, so it should be changed to 1,000,000 or 10⁶.

• <= isn't a proper notation, so change it to ≤. Variable names are written in italics to make them easy to distinguish from regular text. Italics also look more like the characters that appear in actual math formulas.

• Separate comma-listed items with spaces (1,2,3 → 1, 2, 3).

• When text with the same meaning is repeated several times, think about whether it can be shortened.

You might not notice just reading the statements, but we went through this kind of fairly careful editing so they'd be easy to read for participants who'd be tense the whole time.

Also, since text alone can make problems hard to understand, I drew illustrations and inserted them in appropriate places for some problems. Luckily I know how to do graphic design, so I drew all the illustrations myself.

Reference solutions

The setter's reference solution must not be wrong. In recent university contests, setters have often written incorrect solutions, and even at Sogang University the setter wrote a wrong reference solution in 2017. In particular, this happened at another university's contest held while we were preparing ours, so we were extra careful with testing.

The department told us not to bring in external testers, but we had to set 16 problems in 2 weeks with 6 people with little problem-setting experience — it would've been strange if we didn't make mistakes. And decisively, Startlink literally strongly recommended bringing in testers, so I decided on my own to invite testers. They had served as testers for many contests, so I could trust them with problem security, and personally I thought not making wrong problems was more important.

Sure enough, an external tester found that the setter's reference solution for Colored Tower of Hanoi was wrong, so we could fix it early. The testers also verified the data and time limits, which I'll get to below. Without the external testers, this contest would have nearly been another one with problem errors, so I'm really glad. I'd like to take this opportunity to thank them once again.

Data and testing

I made data using Polygon. Polygon is a platform made by Codeforces to help create programming problems. It can do things like:

• Generating and managing data

• Validating input/output formats

• Producing printable statement PDFs

In particular, input format integrity is quite important, which is why I use Polygon. For example, Parallel Universe must guarantee that the input satisfies these conditions:

• Each graph given as input must be connected and must be a tree. If there are s nodes, the node numbers must be given as 0, 1, 2, …, s − 1.

• The number of trees in the input must be at most 10⁶. Each tree must have at most 30 nodes. Also, the total number of nodes across all trees must be at most 10⁶.

• Obviously, no line of the input should have leading or trailing whitespace, and there shouldn't be double spaces or a missing newline at the end of the last line. It might somehow work out in C/C++, but it may not work properly in Java and Python.

testlib.h lets you write integrity checkers like this easily. On top of that, Polygon uses these checkers to automatically run integrity checks on every piece of data as it's generated, which lets you focus on other, more important things.

testlib.h can also be used for writing data generators. Unfortunately, the other setters had no experience with Polygon, and with only 2 weeks the schedule was pretty tight, so as a stopgap they made generators without testlib.h. In fact, at one point data that didn't meet the input constraints got uploaded, and it was hard to find because there was no integrity checker. Luckily we found and deleted it right before the contest.

But Polygon itself also depends on the code the setter writes, so even if it catches most mistakes, some are hard to catch. For example, with Parallel Universe, I was making problems frantically through sleepless nights and apparently mixed up 100,000 and 10⁶. The problem says the number of stars and constellations doesn't exceed 10⁶, but I only realized at the award ceremony that I'd prepared only weak data where each didn't exceed 10⁵.

The data itself was valid, so it wasn't an error in the problem or data, but unintended solutions could have passed. Maybe it was lucky that nobody solved it during the contest? I'm planning to add more data soon.

Limits

You have to set limits so that intended solutions pass and unintended ones don't. But this is surprisingly hard, because

• Execution time differs between languages.

  • An optimal solution in Python might run slower than a naive solution in C++.

• Even the same solution in the same language can have very different running times depending on how input is read.

  • If you set the time limit based on slow input methods, code that uses fast input but a slow algorithm might pass in time.

solved.ac is a problem where any sorting method is fine, but it was originally planned as a problem that required sorting in O(n) using index sort. So originally the limit was n ≤ 10⁷. But C++ code using fast input and std::sort ran in a bit over 500ms, while Java code using index sort took 800ms, so I just gave up and made it easier.

Unlike last year, we allowed Python this time, but we didn't guarantee every problem could be solved in Python. The contest rules said 'It is guaranteed that the setters have solved all problems in C++ and Java or Kotlin', and we did verify every problem in C++ and Java or Kotlin, but some problems couldn't be solved in Python. Python is significantly slower, so setting time limits based on Python could let naive C++ code pass. This is the same as the ICPC World Finals rules.

All memory limits were set to 1024MB. We ran lots of tests, and whenever wrong code passed or correct code failed, we adjusted limits or strengthened data, finishing the problems that way.

Once the whole sheet was filled with circles, I could finally catch my breath.

Operations

As the problems neared completion, I also had to think about running the contest. Fortunately, the department had been helping run the contest for years, so these things got sorted out without much trouble.

Before the contest

• Venue. The computer labs are managed by the university, so the department handled booking them.

• Balloons. Also provided by the department.

  • Helium balloons were pricier than I thought. They were 1,500 won each, and it was a bit sad to think we'd have to pop all the balloons we couldn't give out after the contest.

• Snacks. The department provided these too.

The department only prints the poster, so I had to make it. I grabbed the Dinic code from our team notebook and whipped it up in 3 hours.

We put up posters around campus and recruited participants by posting on the school community. A total of 91 people signed up. Unfortunately, many didn't/couldn't show up on the day, so about 70 people actually participated.

We also made the problem sets. They were typeset in L^AT_EX and printed the day before. We printed them at the department office and did all the binding and carrying by hand — I think that was the hardest part of running the contest.

Contest day

Things went smoothly on contest day. Installing PyCharm and IntelliJ in the lab took a long time, though — it would've been nice to install them the day before. Since it was a lab, there was leftover code written by students, so we hacked together a batch file (.bat) on the spot to delete it all and ran it on every computer.

To hand out balloons you really want a seating chart, and I overlooked that. We hacked one together on the spot too, in Korean alphabetical order. Because of all this, balloons went out late early in the contest.

Nothing much happened in the Champion division, but in the Master division scoreboard, lots of people were stuck at 1 solve for quite a while. I sensed I'd misjudged the difficulty of problem B. Even in the Open Contest the next day, B wasn't solved much. ainta even solved all of A–P and then solved B last.

It seemed many people overlooked that the 도깨비불 phenomenon (a consonant jumping to the next syllable) happens with double final consonants, so quite a while after the contest started we provided an additional test case as an announcement. Thanks to that test case a few people got B, but I regret not realizing it simply wasn't a problem fit for Master B in the first place. I guess string processing is a harder topic for beginners than I thought.

Contest staff can read all participants' source code, so I read a bunch of code from the submission status. This was to check whether correct code got judged wrong or wrong code got judged correct. While checking, I saw cases where people narrowly got a problem wrong because they didn't do cout << fixed. It was a shame, but nothing could be done.. Fortunately, there were no cases of wrong code passing or correct code failing.

In Master, 5 problems were solved: A, B, D, G, H; in Champion, 5 problems: A, B, C, D, F. Champion went as I expected, but it was disappointing that not many problems were solved in Master. Was it really a contest everyone could enjoy? I think Champion was. Unfortunately, I think I badly misjudged the difficulty for Master.

After that the open contest also went smoothly, and since there weren't any problem errors, we released the problems right away. I'm proud that Parallel Universe, which I set and planned as the hardest problem, has been getting some popularity (among veterans) since release. That said, I don't want to see tree isomorphism at next year's ICPC Seoul Regional.. well, anyway.

This made me realize that running a contest and setting problems are harder than I thought. And that hosting a good contest is really tough. There were so many things to think about. I hope the things I wrestled with help anyone planning to host a contest.

I'll probably be going to work at a company next year, so I think I won't set contest problems again for another 3 years. Next time, I want to pay more attention to balancing difficulty. Thank you to my fellow Sogang University students who set problems with me, to those who helped with testing, and to all the participants.

This post continues from Building solved.ac, Part 1: Making a Service for My Club.

The service I could use in my club was finally done. Unfortunately, though, there aren't that many people at Sogang University who are good at PS.

Theorem 1. It is hard to consistently assign difficulties to a large number of BOJ problems with Sogang University members alone.

Lemma 1. There aren't that many people at Sogang University who are good at PS.

Proof of lemma. To begin with, shift himself is bad at PS. ∎

Proof of theorem. By Lemma 1, it’s trivial. ∎

So does the attempt to rate difficulties through collective intelligence just collapse like this? Nope, it's fine as long as the collective gets big enough.

The update logic I'd written was built to make it easy to scrape and update from group ranking pages, and on top of that I figured scraping every single user might get the service blocked altogether, so I thought it'd be good to offer it to groups that have a ranking page first. We could just build it up together with lots of other schools.

That said, since I'd thought it'd only be used in my club, there were a lot of things I hadn't cared about. For one, as I mentioned in the last post, updating solved-problem info only ran at 150 problems per second.

As of today, the total number of problems solved by Sogang University students adds up to 80,989. At 150 problems per second, that can be processed in 9 minutes. With an hourly update cycle, that's a tolerable update time.

But what if Seoul National University, with 132,249 solved problems, gets added on top of that? And what if ten, twenty or more schools get added after that? An hour would probably be nowhere near enough for updates. Surely the update time could be cut down further, but where is there room to cut?

Update time

The update job can be split into several smaller tasks.

Scrape the problem list to get the problems → scrape the group ranking list to get the users → scrape user pages to get solved problem lists → calculate EXP from the solved problem info → send solved problem info to the solved.ac server

To see what could be trimmed, I measured how long each step took.

• Scraping, whether group rankings or user pages, never took more than 1 second per page (300ms–700ms). But for a group of, say, 400 people, scraping every user page in the group took about 3.6 minutes.

• Scraping the problem list in particular took around 1–2 minutes to scrape in full, since the full problem list is about 160 pages.

• Calculating EXP didn't take long either, because problem difficulty info was also fetched from solved.ac while scraping the full problem list. Since both the list of all m problems and the list of the n problems a user solved were sorted, EXP can be calculated in O(n + m), or in O(n log m) if n is small enough. For my user page, with about 2,000 solved problems, calculating EXP took a mere 13ms or so.

• Updating solved-problem info took longer than I expected. As mentioned above, it handles 150 problems per second, and for my page it took about 1350ms.

In the end, I could see that a single update spent most of its time on updating solved-problem info, then scraping user pages, then scraping the problem list, in that order. I didn't really see anything more to trim in the EXP calculation logic. So how could I cut these down?

Scraping the problem list

The first thing that came to mind as ‘I can definitely cut this!’ was scraping the problem list. BOJ does have a lot of problems, around 16,000, but even so, problems don't get added on an hourly basis.

So I made the somewhat slow problem scraping run only at 6 AM every day, when there would be the fewest users.

That alone saved about 2 minutes.

Scraping user pages

Do we need to update a user who hasn't solved anything in the past hour? If they haven't solved anything, maybe we don't need to update them at all?

To cut down user page scraping time, you have to avoid visiting the user page itself. Luckily, you can check whether the solved count changed without visiting the user page, because we're scraping the ranking page in the first place.

Luckily, the ranking page shows the number of solved problems and the number of submissions. I cache these on the server, and only go into the user page to scrape it when they've changed. Note that the solved count can go down due to things like rejudging, so you have to check both the solved count and the submission count.

Even between 12 PM and 1 PM, when BOJ is at its most active, under 8% of Sogang University users had a change in their solved count or submission count. Since not every user is glued(?) to BOJ all the time, applying this method cut scraping time dramatically—about 12x per school. On top of that, it also drastically cut the number of requests sent to the BOJ server.

Updating solved-problem info

I was also able to speed up the solved-problem update logic, which took the most time. Updating tons of records in the DB takes quite a while, so I changed it to fetch the solved-problem info stored on solved.ac and the scraped solved-problem info, and only insert the differences into the DB.

Fetching a user's info for the first time still took a long time, but since nobody is going to solve hundreds of problems in an hour (or are they?), after the first fetch the number of records updated became tiny compared to the number of solved problems, and update time dropped considerably.

After applying these three methods, I went from processing 390 people in 9 minutes to processing 8,000 people in 5 minutes on average. That's roughly a 37x speedup. After applying this, I registered schools one by one—Hongik University, Seoul National University, KAIST, and so on—and right now 37 groups are being updated without much trouble.

But the number of users currently being updated is only about 10,000, while BOJ has about 160,000 users in total, so this probably won't be enough if I update all users. I'm also considering pipelining the backend so that it sends requests to BOJ, computes solved-problem diffs, and updates the solved.ac server all at the same time, but since the server only has 2 vCPUs to begin with, I'm not sure it'd be effective..

As an aside, solved.ac's monthly ad revenue is only enough for me to eat exactly 5 bowls of 2,500-won cafeteria ramen. I wish I had something like Bitcoin I'd mined back in middle school ㅠ

What I didn't consider

After adding all those schools, I spent a while peacefully(?) adding various features. Everything was running fine without any problems. But when everything runs fine, you start getting uneasy. Or is that just me?

Anyway, I was spending peaceful days developing until dawn every day, sleeping in, and waking up late since I had no morning classes anyway. Until I got this message.

Wait, why on earth?

There's no particular reason login would suddenly stop working, but apparently it won't log in. Hmm, what?

It says No space left on device. I checked the remaining space with the df command, and there's still plenty of space left. Seriously, what??

After some googling, I found out. The ext4 file system has inodes that store file metadata, and there's a limit on how many there can be. You can analyze inode usage with df -hi.

Sure enough, inode usage was maxed out. Running out of inodes would mean I'd created a ridiculous number of files, but I didn't think I'd ever made that many files—so where did this come from?

It was the session data. Let's take a look at one tall image.

There were millions of session files. These session files were eating up all the inodes.

Fortunately, PHP lets you write your own session handler. I deleted all the existing session files and swapped in a session handler that uses MySQL, so all sessions got stored in the DB, and the inode explosion never happened again.

Next time I have some free time, I'd like to talk about the things I wrestled with while building the frontend. Recently, the number of difficulty opinions submitted to solved.ac passed 12,000. I only meant to use it in my club, but somehow it's come this far. Thank you so much for your interest in the site, and I'll spare no effort to make it a good community project that can guide people studying algorithmic problem solving.

Thank you!

The word is that the number of alternative military service slots is getting cut. There's a vague sense of crisis in the air. I was planning to stay on as president of Sogang ICPC Team until I graduated (assuming nobody else wanted the job), but if I don't sort out my military service now, who knows what'll happen after graduation, so I decided to go serve as an industrial technical personnel after this semester. That is, if someone actually hires me..,

Anyway, there were a lot of things I wanted to do as president, but since I'm disappearing right after this semester, I made up my mind to do the one thing I wanted to do most.

There's a lot of TMI ahead (is that redundant?). Read at your own risk!

Sogang ICPC Team is the algorithmic problem solving club of the Department of Computer Science and Engineering at Sogang University. An algorithmic problem solving club should, true to its purpose, be solving algorithm problems, right? Our club uses a platform called Baekjoon Online Judge (BOJ) as its problem bank.

The problem is, BOJ is great and all, but it has no metric called ‘problem difficulty’. BOJ has over 14,000 problems collected from all sorts of contests, and assigning difficulties to that many problems on a consistent scale is probably pretty hard.

But without any ‘problem difficulty’ information, it was hard for new club members to get started studying. Sure, there's jh05013's Step-by-Step Problems, but there aren't that many problems per step, so it wasn't really enough for practice. What we could do was make problem sets, so up until now, our club had been sorting tons of problems into rough difficulty groups and managing them with a whole bunch of problem sets, like this.

This worked fine at first, but as more problem sets got added, all kinds of issues came up.

• There were way too many problem sets. Our club group currently has 64 of them.

• A problem set can only hold up to 100 problems. BOJ has over 500 dynamic programming problems alone.

• Adding a single problem to a problem set right after solving it takes at least five clicks. (‘Groups’ – ‘ICPC Team’ – ‘Problem sets’ – ‘Edit’ – ‘OK’) It's a lot more tedious than you'd think.

Eventually I came to the conclusion: let's build a Chrome extension that lets us assign a difficulty to each individual problem. Going further, I figured that if we gave each person a level based on the difficulty of the problems they'd solved, it could give people motivation to solve problems, too. I got started right away.

The first version

Thanks to the exam-season buff, the first version was out in just two days. I threw together a simple backend in PHP. I'd made a Chrome plugin before, so building a new one wasn't hard.

Last year (2018), Soongsil University's finest club SCCC once picked a fight with us, and since I couldn't just let that slide, I quickly built a service that tracked the problems Sogang University hadn't solved yet. I took the problem database I'd built back then, added a ‘problem difficulty’ column, and implemented voting by just writing the value into it. Naturally, only one person could vote.

But a problem I find hard might be one that our finest officer, raararaara, finds easy. Letting only one person vote didn't seem right. So I planned to let multiple people vote, and make the final difficulty the average of everyone's votes. To implement this, I had to think about the following:

• How should the database for storing votes be structured? Existing votes also need to be editable…

• Say I cast a vote — how do we verify that the voter is actually shiftpsh? You should never trust the client, so just scraping the username off the page won't do… (In fact, you could break that approach really easily by opening the developer tools and tampering with the HTML)

The database structure wasn't that hard. I made a new table with one difficulty value per user and problem number. Verifying who voted needed some thought. At the time, I was only planning to let officers vote on difficulty, so it wasn't a big concern. More on that later.

Calculating tiers

After the officers and I worked hard rating difficulties, about 600 problems ended up with a difficulty. That's only 4% of all problems, but since we focused on the ones lots of people had solved, I figured it was enough to start calculating tiers.

Here are the things I had to consider to calculate tiers.

• The experience table: the level-up thresholds and the experience per problem. Problem difficulties and tiers each have 30 levels. I wanted harder problems to give more experience, but giving a huge reward for solving a problem just one tier higher felt off, and on the other hand I didn't want people reaching Platinum by grinding nothing but Bronze 5 problems.

• Fetching the problems a user has solved: in one word, crawling. BOJ doesn't allow crawling that puts load on the site. Baekjoon knows about this site now, but back then it was a secret project, so I had to crawl while sending as few requests to BOJ as possible.

• I also had to think about the structure of the database storing the problems each user had solved.

Initially, I set up the table so that each step up in difficulty gives 1.4 times the experience. The level-up condition was that your total experience reach (the previous tier's threshold) + (the experience for solving a problem of the same difficulty as your current tier) * (a constant). It's set up a bit differently now.

Unless a problem's difficulty goes down, your tier never drops either. Knowing your tier is unlikely to drop gives plenty of motivation to take on lots of hard problems.

I'd settled on the table, but crawling was the problem. For starters, there were about 390 Sogang University members registered on BOJ at the time.

The crawler I wrote in Kotlin parses the entire problem list (about 160 pages) and every Sogang University member. That comes to 550 requests per run. If I updated once a minute to keep things real-time, the math said I'd be firing 792,000 requests a day at BOJ's servers. That would definitely get me banned.

So I gave up on real-time for now and settled on updating once an hour. 13,200 requests a day is still a lot, but it's way fewer than 790,000, so with some vague thought like ‘Hmm.. someone who solves a lot of problems could probably send about 10,000 requests a day, right?' (they couldn't), I set up a cron task. It ran just fine once an hour.

But there was another problem I didn't see coming. Parsing worked fine, but inserting the solved problems into the database took way too long. Inserting the solved problems of just the top 15 users by problems solved took a whopping 12 minutes. That's 54 problems per second. I could tell something about my approach was wrong.

I used my Twitter lifeline.

What I need to do: say the DB has 3 fields A B C – if there's a record matching the new data on A and B, update C – if not, insert it.. and I have to do this nonsense for 100k records an hour (most of the time A B C all match)

— shift* (@shiftpsh) July 2, 2019

Even though I tweeted at a whopping 1:30 AM, a developer who has dedicated their life to Twitter replied right away.

just make (a,b) the pk (backseat coder here)

— 썩죠👀 (@suckzo_o) July 2, 2019

But A was a string. Thinking there was no way a string could be a primary key, I replied ‘A is a string though’. I also didn't know primary keys and indexes could span multiple columns. I got smacked down in the replies.

strings can be pks too yknow

— 썩죠👀 (@suckzo_o) July 2, 2019

Turns out I just didn't know SQL. I immediately put a primary key, unique constraint, and index on the username and problem number, and the query speed improved to about 150 problems per second.

With the PK in place, updating all of Sogang University took about 6 minutes. Still a bit slow, but back when only Sogang was using it, the performance was good enough, so I decided to worry about it later.

Since I was parsing solved problems anyway, I figured I could make a user page sorted by difficulty, so I built that too. I borrowed and modified the CSS from ask.shiftp.sh, so it didn't take long. I'm also thinking that if I develop it further, I could use it as a kind of personal framework.

I also built a new rankings page that day.

Identity verification

Earlier I mentioned the problem of not being able to verify who cast a difficulty vote. To solve this, I first built a separate sign-up system for solved.ac.

I solved it by having the server issue a token when you log in through the plugin, storing it locally, and sending it back to the server as credentials whenever you rate a problem's difficulty.

The catch was that it's tricky to verify whether someone signing up for solved.ac is really that person on BOJ, but I got some inspiration from a bot in CP Community, an international competitive programming community on Discord.

CP Community is based around Russia's Codeforces platform, and that Discord server verifies your identity by having you submit code that causes a compile error on a specific problem.

BOJ has a feature for sharing source code publicly. Source code shared this way can be viewed by anyone, even if they haven't solved the problem or aren't even logged in.

So you pick a problem where a wrong answer doesn't hurt, submit code containing a string randomly generated by the server, share that source, and send the source URL to the server, which then verifies it. That way we can confirm whether you're really you. This also took care of my worry about who was voting.

And so, a service for use within our club was complete.

Limitations

This service had clear limitations. Not technical ones, though. Sogang University is small, so there's no way a lot of people would be on the school list. But precisely because there were so few people, there just weren't many difficulty opinions. The only people actively rating difficulties were the officers, including me, and people who'd solved a lot of problems, and even they couldn't handle rating problems beyond a certain level.

The solution was to bring in lots of strong people from outside Sogang. But turning a service used by at most about 100 club members into one used by thousands took a lot of thinking.

This post didn't cover much technical content beyond ‘wow, I really didn't know SQL’ and ‘here's how I do identity verification, cool right?’, so it ended up being more like a daily life post, but in the next post I plan to cover the things I thought about while turning solved.ac into a service used by thousands of people.

I found the ACM-ICPC 2016 Pyongyang Regional problems on the internet. I was curious how hard North Korean problems are and how much their computer science terminology differs from ours, so I rewrote the low-quality photos as text to make them easier to read. I changed some line breaks and symbols at my own discretion.

There are 12 problems in total. Personally, they feel like problems from a Mathforces contest.

You can try all of the problems on ICPC Live Archive. The time limits are different there.

Problem 1. Array Inversion Number

• Time limit: 1 second

• Memory limit: 64MB

Description

You all will know about the inversion number of an array (배렬)1배열 (array).. The inversion number of an array $\left\{ a_1, a_2, \cdots, a_n \right\}$ is defined as the number of pairs $\left(i, j \right)$ such that $i < j$ and $a_i > a_j$.

Hanmin is clever, and he is now thinking of a new inversion number of an array.

If $i$ and $j$ have the same parity and $a_i > a_j$, he considers $\left(i, j \right)$ an inverted pair. Meanwhile, if the parities are different and $a_i < a_j$, he also considers such a pair $\left(i, j \right)$ an inverted pair. In other words, the index pair (첨수쌍)2벡터 (vector). $\left(i, j \right)$ is an inverted pair if $a_i > a_j$ when $i$ and $j$ have the same parity, or $a_i < a_j$ when they differ.

You are Hanmin's best buddy (딱친구)3단짝 친구 (best friend). and have been asked to compute the number of inverted pairs of the array. Can you solve it?

Input

The first line of the input file consists of the number of input data (입력자료)4Test cases. $T \left(1 \leq T \leq 5\right)$.

The first line of each input data contains one integer (옹근수)5정수 (integer). $N \left(1 \leq N \leq 5000\right)$, which is the length of the array.

In the next line, $N$ real numbers come in separated by spaces.

Output

For each input data, you print the inversion number on one line.

Standard input

1
5
1 4 3 2 5

Standard output

5

Problem 2. $B_N$

• Time limit: 1 second

• Memory limit: 128MB

Description

The clever student Ri Giung is very good at physics but not good at math. His comrade Sin Yeongjin, on the contrary, is good at math and not good at physics. So Comrade Ri helps Comrade Sin with his physics homework, and Comrade Sin helps Comrade Ri with his math homework.

Today Comrade Ri came back with a very difficult math problem and asked Comrade Sin. But Comrade Sin was very busy, so he asked you to solve it. You are Comrade Sin's best buddy and must solve it. The problem is as follows.

An array $\left\{ A_1, A_2, \cdots, A_n \right\}$ is given. A new array $\left\{ B_1, B_2, \cdots, B_n \right\}$ is defined by the following formula.

6% is the modulo operator

Of course, $1 \leq i_1, i_2, \cdots, i_k \leq n$. For $u \neq v$, $i_u = i_v$ is also possible. In fact, $B_3 = A_1 \times A_1 \times A_1 + A_1 \times A_2 + A_2 \times A_1 + A_3$. You must compute $B_N$ for the given $N$.

Can you help them?

Input

The first line of the input file consists of the number of input data $T$.

The first line of each data consists of two integers $n$ and $N$. $\left(1 \leq n \leq 100, 1 \leq N \leq 100\right)$

In the next line, $n$ integers come in separated by spaces.

Output

Print the result of the problem.

Standard input

1
2 5
3 2

Standard output

495

Problem 3. Matrix Check

• Time limit: 1 second

• Memory limit: 512MB

Description

Professor Jeong is a problem setter for the 41st International Collegiate Programming Asia Pyongyang Regional Contest. He finished multiplying 100 sets of a 2016 × 1946 matrix and a 1946 × 2016 matrix. Of course, the result is a 2016 × 2016 matrix. The computation took almost 10 days. The results are 100 sets, and they will become the input/output data for problem C.

After the computation was finished, Professor Jeong fell asleep and his son touched the results. He erased one digit of some number and wrote the digit (수자)7숫자 (digit). 1 in its place.

The next day Professor Jeong was very angry. But the kid is only 2 years old, so he doesn't remember everything.

Professor Jeong listens to his son and examines the details. So he found out that his son changed one digit of one number in each set, and that the digit was one of 2, 0, 1, 6. He also found out that the position his son changed has a row number and column number of at most 70. The top-left corner of the matrix is numbered (1, 1). The first index is the row number and the next is the column number.

He must send the input/output by the end of today. So he made up his mind to check the results. You are his excellent student. Help Teacher Jeong.

Input

The input file consists of exactly 100 sets of input/output data. Each set is defined as follows.

The first line consists of 5 integers $a_1, a_2, a_3, a_4, a_5$. You can obtain the matrix $A$ as follows.

The next line consists of 5 integers $b_1, b_2, b_3, b_4, b_5$. You can obtain the matrix $B$ as follows.

Next there is the top-left 70 × 70 integer matrix. You must check this matrix.8The exact input format of the 70 × 70 matrix isn't given, but I'd expect it to be separated by spaces and line breaks.

When you multiply the two matrices, you must take the matrix modulo 2016011010.

Output

You must print which input sets were changed by the son. The inputs are numbered from 1 to 100. Your output must be printed in increasing order, separated by spaces. If none of the input sets were changed, print 0.

Examples of input and output

The input and output are too big, so we cannot show you examples of input and output. You must guarantee the input/output format.

Problem 4. Sharing Apples

• Time limit: 8 seconds

• Memory limit: 512MB

Description

Hyeonil is a moral student. He always treats his classmates and friends like himself. One day he brings a delicious, big apple and wants to share it with his friends. What is interesting is that the apple is elliptical.

He always performs two operations.

The first is to calculate the remaining area of the apple between angle $L$ and angle $R$.

The second is to give away all the apple pieces between angle $L$ and angle $R$.

Hyeonil placed the apple on a Descartes coordinate system (데카르트자리표계)9데카르트 좌표계, i.e., the Cartesian coordinate system (=직교좌표계)., and as a result the apple sits on the ellipse $\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$.

You, Hyeonil's older brother, want to test your little brother's computing ability, and you must answer all the questions.

Can you do it? You can.

Ah, there is one more condition⋯ $prev$ is the last printed number, and the actual $L$ and $R$ are calculated by the following formula.

If $L_{real} > R_{real}$, you must swap the two values. You must perform the operation with the two values $L_{real}$ and $R_{real}$. Initially, $prev = 0$.

Input

The first line of the input file contains three integers. – $a$ $b$ $n$ $\left( 1 \leq a, b \leq 100, n \leq 300000 \right)$

$a$ and $b$ are the numbers described above, and $n$ is the number of operations.

The next $n$ lines contain three numbers “$type$ $L$ $R$”. ($1 \leq type \leq 2$, $L$ and $R$ are arbitrary real numbers.) It can be guaranteed that $0 \leq L + prev,0 \leq R + prev$.

Output

You must calculate the result for every operation 1. Print it rounded at the 5th decimal place.

Standard input

10 10 3
1 10.00000 30.00000
2 40.00000 70.00000
1 10.00000 300.00000

Standard output

17.45329
226.89280

Notes

To make the problem easier, $L$ and $R$ are also given to 5 decimal places. And $prev$ is the value of the last printed first-type question. For example, $prev = 17.45329$, but the actual answer is $17.453297519943295769236907684886\cdots$.10Put simply, when computing prev, use the printed (rounded) value.

Problem 5. Easy Geometry Problem

• Time limit: 1 second

• Memory limit: 32MB

Description

$ABCD$ is a tetrahedron given by $\overline{DA} = a$, $\overline{DB} = b$, $\overline{DC} = c$, $\angle BDC = \alpha$, $\angle ADC = \beta$, $\angle ADB = \gamma$. You must calculate the radius of the inscribed circle11An inscribed sphere. of $ABCD$.

Input

The first line consists of the number of input data $T (1 \leq T \leq 100000)$.

Each input data contains 6 numbers $a, b, c, \alpha, \beta, \gamma$ $(1 \leq a, b, c \leq 100, 0 < \alpha, \beta, \gamma < 360)$.

Output

Print the radius of the inscribed circle rounded at the 6th decimal place.

Standard input

1
10 10 10 90 90 90

Standard output

2.113249

Problem 6. Finding the Best Path

• Time limit: 4 seconds

• Memory limit: 256MB

Description

Bit City is the capital of Byteland. Bit City has a modern highway system, and the system is frequently updated, with highways being added to it. The system consists of highways connecting intersections.

You, the president of a transport company, want to transport computers from one intersection to another. But gasoline is too expensive in Byteland, so you want to carry them with only one truck. You want to carry as many computers as possible, but every highway has a restriction that it cannot carry more than $W$ computers.

You must calculate the maximum number of computers you can carry. On your initial highway system, you can travel between any two intersections. In other words, the original system was connected.12i.e., it is connected.

Input

The first line consists of the number of input data $T (1 \leq T \leq 3)$.

Each input data begins with two integers $N$ and $M$, meaning the number of intersections and roads. $(3 \leq N \leq 70000, N-1 \leq M \leq 150000)$

The next $M$ lines contain three integers $a$ $b$ $c$, meaning there is a road between $a$ and $b$ with limit $c$. $(1 \leq a, b \leq N, 1 \leq c \leq 10000)$

The next line contains one integer $Q (1 \leq Q \leq 105000)$, meaning the number of questions. Every question is one of the following two kinds.

1. $a$ $b$ $c$: Connect a road between $a$ and $b$ with limit $c$.

2. $a$ $b$: Calculate the maximum number of computers that can be carried from $a$ to $b$. $(1 \leq a, b \leq N, 1 \leq c \leq 10000)$

There can be two or more roads between two intersections.

Output

For each question of the second kind, print the maximum number of computers that can come out.

Standard input

1
5 6
1 2 2
1 3 3
2 4 7
2 5 1
3 4 6
3 5 5
4 
2 2 5
1 4 5 8
2 2 5
2 3 4

Standard output

5
7
6

Problem 7. Good Days

• Time limit: 1 second

• Memory limit: 64MB

Description

You receive two dates $\texttt{y/m/d}$ and $\texttt{yy/mm/dd}$ as input; one is the first good day and the other is the last good day. All the days between them are also good days, and the others are not. You must calculate the number of good days.

Input

The first line consists of the number of input data $T (1 \leq T \leq 10000)$.

Each input data consists of 6 integers $y$ $m$ $d$ $yy$ $mm$ $dd$. $(1 \leq y, yy \leq 5000)$

Output

Print the number of good days.

Standard input

1
2016 11 8 2016 11 11

Standard output

4

Problem 8. Hyoseong and Gwangseong

• Time limit: 1 second

• Memory limit: 256MB

Description

There is a long string $S$ consisting of lowercase English letters. Two boys, Hyoseong and Gwangseong, play a fun game. The rules of the game are as follows.

Initially, the referee Hakmyeong gives them a non-empty substring of $S$. (Let us denote it by $P$.) The two players take turns appending one character to the end so that the newly formed string is a substring of $S$. If they cannot append a character, the game ends.

Hyoseong wants the final string to be as short as possible, and Gwangseong wants the string to be as long as possible. Hyoseong is the first player. If they play optimally (최량)13최선 (optimal)., the number of characters appended for each string can be guessed. (Let us denote it by $f(P)$.)

A substring $A$ is defined to be smaller than a substring $B$ if $f(A) < f(B)$, or $f(A) = f(B)$ and $A$ comes before $B$ in lexicographic order.

For a given integer $K$, find the $K$-th smallest string of the string $S$. Can you find it?

Input

The first line consists of one string, whose length is at most 500000.

The second line consists of one integer $K (1 \leq K \leq 1000000000)$.

Output

For the resulting string, print the number of characters appended to it and the resulting string, separated by a space.

Standard input

aababb
8

Standard output

1 abab

Problem 9. International Network Service

• Time limit: 1 second

• Memory limit: 256MB

Description

There are numerous network servers (망봉사기)14서버 (server). on Earth. For every number $i$, the $i$-th network server has an index value $R_i$ called the “radius,” and the server can serve (봉사)15서비스 (service). all points at a distance of at most $R_i$ from itself.

Some points can be served by many servers. Your task is to find the point that can be served by the largest number of servers.

The Earth is regarded as a perfect sphere with radius 6370, and the distance between two points on the Earth's surface is not the Euclidean distance but the distance along the surface.

To make the problem easier, the radii of the network servers are between 2012 and 2016. (2012 and 2016 inclusive)

Input

The first line consists of the number of input data $T (1 \leq T \leq 6)$.

The first line of each input data contains the number of servers $N (1 \leq N \leq 1000)$.

The next $N$ lines contain three integers representing the server's longitude, latitude and radius. (0 ≤ longitude < 360, -90 < latitude < 90)

Output

Print the answer to the problem.16As you can tell from the data, you need to print the number of servers serving the area that's served by the most servers, not the location of that area.

Standard input

1
2
0 0 2012
0 1 2016

Standard output

2

Problem 10. Jewel Boxes

• Time limit: 3 seconds

• Memory limit: 256MB

Description

Seongyeong can solve any math problem very quickly. His older brother Choe Gwang has $N$ empty jewel boxes that can store expensive jewels.

One day Choe brought $N$ jewels from a jewelry store. Choe will put all the jewels one per box. In other words, he will store only one jewel in each box.

Every jewel has 4 numbers: a storage number $p$, a time it arrives at the box $t$, and 2 values $a$ and $b$. Let us explain $(p, t, a, b)$.

When jewel $(p, t, a, b)$ arrives, Choe must find the best-matching jewel among the jewels that have already arrived. The best-matching jewel $(p_1, t_1, a_1, b_1)$ must satisfy the following conditions.

1. It must arrive before the new jewel. In other words, $t_1 < t$.

2. Its box number must be smaller than $p$. In other words, $p_1 < p$.

3. The combination effect must be maximized. The combination effect is defined as follows. $a_1 \times a + b_1 \times b$.

Then Choe wants to write the combination effect of the jewels on the lid of that box. So Choe asked Seongyeong to calculate the numbers and write them on the lid of each box. Let us help Seongyeong.

Input

The first line contains an integer $N (1 \leq N \leq 100000)$, which is the number of jewel boxes.

Then there are the next $N$ lines.

The $p$-th line contains 3 variables $t$ $a$ $b$. – That means jewel $(p, t, a, b)$. $(1 \leq t \leq 1000000000, 1 \leq a, b \leq 1000000)$

No two jewels arrive at the same time.

Output

Print $N$ integers. The $p$-th number is the number to write on the $p$-th lid.

Standard input

3
1 1 1
2 2 2
3 3 3

Standard output

0
4
12

Problem 11. K-th Graph Cut

• Time limit: 3 seconds

• Memory limit: 512MB

Description

Jiseong likes learning graph theory (그라프리론)17그래프 이론 (graph theory).. First he learned about minimum generating trees (최소생성나무)18최소 스패닝 트리 (minimum spanning tree).. Next he learned about shortest paths. And now he is learning about the graph cut problem.

A weight-attached directed graph (무게붙은 방향그라프)19가중 방향 그래프 (weighted directed graph). (it need not be connected), a source and a destination are given. Needless to say, the source and destination are vertices of the graph.

Next, you must remove edges (마디)20간선 (edge). from the graph so that there is no path between the source and the destination. The sum of the weights of the removed edges is then called a “cut.”

Jiseong already knows that in a general graph the minimum cut is equal to the maximum flow between the source and the destination. And now he wants to know about the $K$-th minimum cut. He can find the $K$-th minimum spanning tree and the $K$-th shortest path, but he cannot find the $K$-th minimum cut. Let us help him.

Input

The first line contains 5 integers $N$ $M$ $K$ $S$ $T$.

$N (1 \leq N \leq 100)$ – means the number of vertices of the graph.

$M (1 \leq M \leq 1000)$ – means the number of edges of the graph.

$K (1 \leq K \leq 100)$

$S (0 \leq S < N)$ – the vertex number of the source.

$T (0 \leq T < N)$ – the vertex number of the destination. $(S \neq T)$

The next $M$ lines contain 3 integers $a$ $b$ $c$. – It is an edge between $a$ and $b$, and its weight is $c$. $(0 \leq a, b < N, a \neq b)$

To make the problem easier, for each $i (0 \leq i < N, i \neq S, i \neq T)$ there is at least one edge between $i$ and $T$.

Output

Print the answer to the problem.

If there is no $K$-th minimum cut, print -1.

Standard input

3 3 3 0 2
0 1 1
0 2 3
1 2 2

Standard output

6

Problem 12. Long Integer Factorization

• Time limit: 1 second

• Memory limit: 256MB

Description

I like algebra very much, especially factorization. Long integer factorization gives me joy, but it is a hard problem.

My teacher gave me a new factorization problem. “Given an integer $N$, you must factorize the big integer $N^4 + 64$.”

As a first step, I want to express $N^4 + 64$ as the product (적)21곱 (product). of 2 integers $a$ $b$. Of course, $1 < a, b < N^4 + 64$.

I can do this, but I am busy. Can you help me?

Input

The first line contains the number of input data $T (1 \leq T \leq 10000)$.

Each input data contains one integer $N (1 \leq N \leq 10000)$.

Output

Print $a$ and $b$ satisfying $N^4 + 64 = a \times b$. If there are multiple cases, print any one of them.

Standard input

1
1

Standard output

5 13