On November 23, the 2018 Sogang University Programming Contest was held for 3 hours. It's an individual ACM-ICPC style algorithm contest held every year for Sogang University undergrads. This is its 14th year. (2016 was the 12th, so this year is probably the 14th..? Not totally sure, but it should be)

There's the Master division, open only to freshmen and sophomores, and the Champion division, open to all years. I'm a freshman without much offline contest experience, so I entered the Master division. Since I'll be the president of the algorithm club starting next year, this might be my first and last time taking part in the school contest as a contestant 😄

There were 6 problems per division, 12 in total. You can try the open contest on Baekjoon Online Judge. The Master division got problems A, C, D, E, G, and I from the open contest, and the Champion division got B, F, H, J, K, and L.

Over the summer I worked as balloon staff at the 2018 Union of Collegiate Programming Clubs Contest (UCPC 2018), tying balloons to contestants' desks, and this time I was on the receiving(?) end of the balloons. When I was tying them, I was a bit worried it might distract the contestants, but once I was the one solving problems, it turned out to be less distracting than I thought!

When lots of balloons go up, the contest hall looks pretty. I love this culture!

It was a bit of a shame that I couldn't use Kotlin at the contest. Kotlin is my main language, and over 90% of the problems I've solved on BOJ were in Kotlin. But I'd gotten fairly used to C++ from studying with the club, so it wasn't really a problem. As for Kotlin, I'd like to settle for using it at the ICPC World Finals if I ever get there and hogging all of JetBrains' attention. Though, well, I'd have to actually make it to the World Finals first..

Anyway, enough rambling from a freshman at his first contest like this, let's talk about the problems!

The problems

Warning: solutions below.

The solutions are in the order I solved the problems.

C. 어려운 소인수분해 (Hard Prime Factorization) / BOJ #16563

Surprisingly, the solution for A didn't come to me right away, so I started with C. I was confident with the Sieve of Eratosthenes.

Since the input is a natural number between 2 and 5 million, I first precompute the primes up to $\sqrt{5000000} \approx 2236$ with the Sieve of Eratosthenes. During the contest, instead of taking the exact square root of 5 million, I just went with roughly 3000. Since $\pi (2236)=331$, you get a bit under 350 primes.

Read some number n. Now for each prime p, divide n by p until it's no longer divisible by p, printing p each time. Increase p starting from 2, and once n becomes smaller than $p^2$, conclude it can't be divided by p anymore and break out of the loop. If n still isn't 1 after trying every prime up to 2236, the remaining n is itself prime, so print n as well. This way, even with a million numbers to factorize, the number of primes p you try dividing by is small, so there's nothing to worry about. First solve 9 minutes into the contest.

A. 3의 배수 (Multiples of 3) / BOJ #16561

Surprisingly, I spent a lot of time on this one because I misunderstood the problem at first. You're supposed to split into 3 natural numbers, but I missed that and read it as just the number of ways to partition a natural number. Anyway.

If you read the problem, you'll notice n being a multiple of 3 doesn't really mean much, right? It's really the same as splitting $\frac{n}{3}$ into 3 natural numbers. But it says the order matters. How should we split it?

First, there's only one way to split 3 into 3 parts: 1 + 1 + 1. Splitting 4 into 3 parts gives 3 ways by rearranging 2 + 1 + 1, splitting 5 into 3 parts gives 6 ways by rearranging 3 + 1 + 1 and 2 + 2 + 1… So we could think of this as finding the number of ways to distribute $\frac{n}{3}$ balls into 3 distinct boxes with at least 1 in each! This equals the combination with repetition

. Working it out, it's simply

, and solving it this way gets you AC!

Of course, I forgot my high school probability and statistics ages ago, so I split 3, 4, 5, and 6, saw I got 1, 3, 6, and 10, thought 'this must be some nCr!', coded it right away, and it was accepted. Accepted 14 minutes into the contest.

B. 친구비 (Friend Fee) / BOJ #16562

It was a simple graph problem. Find the connected components and add up just the minimum value of each. It doesn't really matter whether you find the components with BFS or DFS, and since you visit every node only once, it's solved in $O(N)$ in no time. Just print “Oh no” only when this sum exceeds K. Accepted 21 minutes into the contest.

D. 히오스 프로그래머 (HotS Programmer) / BOJ #16564

I solved it by binary searching the team's target level T between 0 and $2 \times {10}^{9}$. Actually, during the contest I didn't bother with the theoretical maximum of T and searched between 0 and ${10}^{12}$. For some reason I just couldn't get a feel for how far the range should go..

At each step of the search, I compared K with the total levels $\sum \mathrm{max} (0, T-X_i)$ you'd need to raise for a target level of T. N is at most a million and K is at most a billion, so using int would overflow, right? Of course I used long long.

Computing the total levels to raise is $O(N)$, and searching for the target level T is $O\left(\log\left(2\times{10}^{9}\right)\right)$. So this problem is also solved in linear time. Got one WA from setting the binary search range wrong, then first solve 32 minutes into the contest.

E. N포커 (N-Poker) / BOJ #16565

A probability and statistics problem. I think I ended up scribbling a lot of numbers on the problem sheet.

Let's take picking 7 cards as an example. In the figure from the problem, pick one of the 13 vertical columns, then pick 3 of the remaining 48 cards. In this case, the number of ways is

in total.

But what if you pick 11? If you pick one column from the figure and then pick 7 of the remaining 48 cards, those 7 cards might form another column. In that case, subtract the cases where you pick two columns and then 3 of the remaining 44 cards. The number of ways comes out to

!

What about picking 15? If you think like above, subtracting the duplicates also removes the cases with 3 columns. So if you add back the cases with 3 columns, you get

ways.

You get the idea by now, right? Looks like we can generalize. Looking at the pattern above, for any n the number of ways we want seems to be

, and it actually is!

Computing the binomial coefficients is another issue: you can't get them by computing factorials and dividing. long long only goes up to $2^{63}-1$, and $21! \approx 2^{65.46}$ already blows way past that range, so computing the $\binom{48}{7}$ from above is out of the question. long double has a bigger range than long long, but once it gets really big its precision is worse than long long's. Instead, using the recurrence

, you can precompute binomial coefficients for n ≤ 52, k ≤ 52, k ≤ n with dynamic programming. The numbers might get too big, but since we only need to print the result modulo 10,007 anyway, by the properties of modular arithmetic you can just store every binomial coefficient modulo 10,007 when precomputing.

With these precomputed binomial coefficients, whatever n comes in, you only add up at most 13 terms, so it's solved in $O(\lfloor n/4 \rfloor)$. Got 3 WAs from writing the formula wrong before getting it right, then first solve 1 hour 1 minute into the contest.

F. 카드 게임 (Card Game) / BOJ #16566

I found out later that this problem was originally planned as problem F of the Champion division. But apparently they thought this one was easier, so they swapped Champion's F and Master's F. (No wonder there were two card problems in a row)

Anyway, at first I thought 'oh, is this a binary search tree..?' and spent about 10 minutes trying to implement one, but I'd practiced trees way too little (plus, as I mentioned above, I rarely had to write structs in C++ because I was doing Kotlin), so I gave up, thought 'well, my original goal was just to place in the top 5 anyway,' and kind of threw a solution at it. And it was accepted!! I think the test data was a bit weak.

First, sort the cards Minsu took. Then make a flag array that stores whether each of the M cards has been used. Now, letting x be the value of the card Cheolsu plays, find x + 1 among Minsu's cards with lower_bound. If it hasn't been used yet, print it right away. If it has, keep incrementing the index by one until you hit an unused card, and print it when found.

Actually, this approach is $O\left(K^2\log M\right)$ in the worst case, a complexity where getting TLE wouldn't be surprising. I think I just got lucky! It's hard to say I properly solved the problem, but anyway, first solve 1 hour 47 minutes into the contest.

Apparently the intended solution uses index sort. It seems possible because M ≤ N ≤ 4,000,000; I should solve it again the intended way.

I solved all 6 problems and won the Master division. Since it's probably my first and last school contest as a contestant, winning it means a lot to me personally. Great job to all the contestants and problem setters. Thanks to the organizers for putting together a great contest!

I had a hard time when backspace stopped working in the middle of coding (turns out some international students had changed the keyboard language settings to their own languages), but my first offline contest in a while was so much fun. I'll probably be a problem setter starting next year, and I'll work hard to make a contest everyone can enjoy 😊

Great job, everyone! 🎈

This post is a reworked version of a short internal talk I gave during my internship at Hyperconnect, where I implemented Camera2 API support in a camera app. You can find the slides on SlideShare. (Slides that couldn't be made public have been removed.)

Ever since smartphones came along, phone cameras have become more and more important. Manufacturers keep improving smartphone camera performance day by day to meet users' demands. These days, people often don't even bring a separate digital camera when they travel.

Android, however, used the API created in Android 1.0 (API 1; September 23, 2008) for quite a long time, with only a few features added, until it was replaced in Lollipop 5.0 (API 21, November 12, 2014). Honestly, the only thing added to the Camera API that you could really call a feature was face detection.

Since the old API was made in the early days of Android, nobody expected cameras to evolve this far, and it only offered simple features like a compact camera would. The Camera2 API improves on this in a lot of ways.

To avoid confusion, from here on I'll call the old camera API the Camera1 API.

The new API

The Camera2 API was introduced in Lollipop 5.0 (API 21). After Lollipop, the Camera1 API is deprecated, but you can still use it.

Camera2 supports many features that Camera1 didn't. To name just a few:

• You can now use three or more cameras. On Pie 9.0 (API 28) and above, you can even use multiple cameras at the same time.

• It supports manual controls commonly found on DSLRs. The Camera1 API only let you set where to focus, but with Camera2 you can directly set the focus distance, exposure time, ISO, and more through the API.

• Burst shooting, RAW support, and more are added.

Fragmentation

But there's one thing you always have to think about before implementing a new API: will this actually work? To cut to the chase, Camera2 works well in most cases, but there are cases where it behaves strangely.

So, is it worth using?

• Camera1 is no longer supported,

• the features Camera2 offers are just too powerful,

• it's faster than Camera1 thanks to the new way it works (described below) and its use of the HAL (Hardware Abstraction Layer),

• and Lollipop 5.0 (API 21) and above now has over 87% market share (as of July 23, 2018), so lots of users can make use of Camera2's professional features.

So despite those issues, Camera2 is well worth implementing. That said, for now it seems you'll still need to implement two sets of logic: one for devices below API 21 that don't support Camera2, and for devices whose Camera2 is so buggy that they need to use Camera1.

What changed?

Unlike Camera1, the Camera2 API is built on a pipeline model.

Camera1 handles everything asynchronously, so when you changed a setting or issued a command, apart from a few methods, there was no way to know when the value would be applied, or whether it was applied correctly at all. Camera2's new structure improves on this a lot. Everything is handled synchronously inside the API, and you can get feedback through callbacks.

Looking at the flowchart, you'll see some unfamiliar things you never saw in Camera1. The most unfamiliar ones are probably CaptureRequest and CameraCaptureSession. Here's what each component does.

The API works by sending CaptureRequests to a Session like this. Not just taking photos, but the preview too works by sending CaptureRequests continuously. The capture settings are sent along with the Request.

As you can see in the figure above, buffers are sent to multiple Surfaces: you can send the preview straight to a SurfaceView, or post-process it using SurfaceTexture or RenderScript. Something unusual is that it sends to ImageReader or MediaCodec — unlike Camera1, which gives you a ByteArray right away when you take a photo, Camera2 gives you an Image through an ImageReader.

Since it can send to multiple Surfaces, you don't need to set buffer Preview size or Picture size separately like in Camera1; it sends according to each Surface's size. (However, so far a bug has been observed on many devices where images get weirdly stretched unless all Surfaces have the same aspect ratio.)

Why did it change like this?

Camera operations usually take quite a while, and this approach solves the problems caused by things not being synchronized while also giving speed benefits. For an image to go through the camera and be decoded into something the device can use, it has to go through a series of steps called image processing. Let's look at the figure below.

Here you can see images being processed nicely with setting A. Image processing has multiple stages, so multiple images can be processed at once like this.

Camera1 applies settings globally. But if settings are applied globally and you switch from A to B while an image is being processed, the resulting image ends up with A and B mixed like this.

So Camera1 handles it like this: process one image completely, then apply the new setting, process a new image, apply a new setting again, …. and so on.

Camera2, on the other hand, attaches the settings to the request itself, so there's no need to handle things one at a time like Camera1. Each stage just checks the settings attached to the request. Settings never get mixed up either.

Of course, using the new version of the HAL plays a part too, but with this approach Camera2 can process images much faster than Camera1, and even burst shooting at 30 photos per second at full quality became possible. Considering you could only take about 1–3 photos per second before, that's a huge improvement.

By the way, many Camera2 operations take a Handler as an argument and do the synchronous work on that Handler. (I suspect this might be because many people didn't realize Camera1 operations block the UI thread and did things like Camera.open() on the UI thread.)

Implementing Camera2 in an existing app

First, break down how the app works step by step regardless of the API, then abstract the class that previously handled the Camera accordingly, and implement the Camera1 and Camera2 logic.

You can see the code differences between Camera1 and Camera2 on pages 32 through 47 of this slideshow!

But even if you abstract things well and check the API level to use Camera2 on 21 and above, not every device supports Camera2 properly. If the manufacturer implemented the HAL well, it'll work; if not, it won't.

Still, it'd be a shame if devices that do support Camera2 properly couldn't use its great features because of a small number of devices like that. So how should we offer Camera2's great features?

First, if you have a ton of devices, you can test them one by one. Just make a whitelist and add the devices that work.

But if you don't have that many devices or an environment where you can test like that, you can also ask users whether it works. Like KakaoTalk's 'Labs' feature.

For devices on API 21 or above that the developers haven't tested, it's a good idea to put an option like 'Use advanced camera features' in Labs so users can try the Camera2 features themselves. If a lot of errors occur on a device, try fixing them or drop support if they can't be fixed; if hardly any errors occur, add it to the whitelist.

Useful references

• Google I/O 2014 – Building great multi-media experiences on Android (30:00~): Not a video that helps with the implementation itself, but I referred to it quite a lot for this post!

• googlesamples/android-Camera2Basic: If you move from Camera1 to Camera2, there may be a lot of things you don't get even after reading the documentation. Referring to the sample project helped me much more than reading the documentation.

• Camera 2 APIはじめの一歩 (translated version)

• The least you can do with Camera2 API

This post describes what I've been doing at home for the past year. I did do quite a lot. It's a pretty long post.

The Beginning

Sure, people joke that high school is a four-year program these days, but who actually wants to do senior year all over again? With the same scores, I would definitely have been admitted in the first round to that department last year, but this year I watched my chances on the mock application service drop day by day until it finally said I had no chance at all. I can't even describe that despair. That's how it was for me.

Of all the KICE exams I took that year, the CSAT was the one I did best on, and yet these were my actual CSAT scores.

I was aiming for the top universities in Seoul, but for various reasons I did poorly on my exams in senior year compared to my lofty goals (more on that later). And school GPA, where almost everything came down to memorization, just didn't suit me at all, so I consistently stayed in the low grade 3 range at a regular high school. Of course, that low grade 3 average was made up of things like a grade 5 in a major subject like Calculus I, mixed with grade 1s in minor subjects I was confident in, like Japanese and Computer Science.

Anyway, I had zero confidence that I could handle a full gap year of retaking, so I decided on a 반수 (studying for a retake while enrolled) and applied to a national university that allowed taking a leave of absence in the second semester. With these scores, it obviously wasn't a top Seoul school, or even a school in Seoul at all. And I got in on the first round. But…

After getting this text, all sorts of worries started creeping in, starting with "what if I get comfortable with the drinking-and-partying college life and just settle down there?" and going all the way to whether I could actually pull off studying for a retake while enrolled. And the decisive factor: I was really jealous of my friends going to prestigious universities.

So I got my enrollment fee refunded and impulsively crossed the river of no return that is the gap-year retake (not to be confused with retaking a course).

Winter

There are many prestigious universities along Seoul Subway Line 2. Among them, the one you can graduate from the fastest is Gangdae.

Of course, my scores probably weren't even good enough to get into Gangnam Daesung Academy. But students retaking the exam usually enroll in some kind of cram school, whether a full-course retake program or a self-study retake program, and attend it for a year like high school. That's the standard route, so I figured I had to go somewhere.

So in February, I went around various retake academies in Mokdong listening to their pitches. But since my family wasn't exactly well off, we decided I'd self-study at home first and enroll in an academy later.

As I started self-studying at home for who knows how long, I naturally started studying with online lectures and past CSAT problem books. And at this point, I had no idea I'd end up studying at home until November, apart from some single-subject cram classes.

Spring

Late February these days is definitely not spring weather, but let's just call this section spring so the seasons line up with the plot

Before starting my retake year, I analyzed in some detail why I'd failed on the 2017 CSAT. The idea was to get a sense of how I should study this year to actually raise my scores.

Korean had always been around grade 4 for me, so I figured that as long as I did what I did in November, I could hold on to grade 2, and the same went for chemistry. English had switched to absolute grading, so 90 and 100 got the same grade, and even scores in the 80s barely got 'dinged' by universities, so there wasn't much pressure there.

The problems were math and biology. The 2016 math mock exams had been easy overall, but I'd made a lot of mistakes on the easy problems, so from September to November that year I practiced solving every problem twice while working through private mock exam packs. That was the root of the problem. The 2017 CSAT math was anything but easy, and solving it that way without even looking at the later problems, I found myself with only 40 minutes left by the time I got to problem 18. Biology went wrong because I hadn't mastered the more obscure concepts. So for math, I first needed to train the skill of solving easy problems quickly and accurately in one go, and for biology, I felt I needed to restudy all of the concepts from scratch.

After analyzing what went wrong and actually starting my retake year, I found I had a huge amount of time to use. I tend to give in easily to the temptation of my laptop and smartphone, and I couldn't be bothered to get rid of them, so I decided to plan out a study schedule for each day.

From the day I was born until I was nineteen, I had never once made a 'daily schedule.' Starting self-study at home was the first time I ever tried making one.

Every morning, I'd plan out the day in 30-minute blocks starting from the time I woke up, and then actually follow it. If I didn't get something done, I marked it with an X and did the missed studying the next day. I also arranged the subjects in the same order as they appear on the actual CSAT.

After making these plans for a while, I realized that studying with a plan, even if I only planned a little because I was tired or wanted to slack off, was far more effective than not planning at all.

From February to June, I mostly solved a lot of past KICE problems and focused on reviewing concepts. I had so much time that I didn't need to rush, so I went through everything slowly and thoroughly. It felt like there was way more I didn't know than I expected. Especially in biology. In the concept lectures, there were stuff marked with stars and circles that was so unfamiliar I wondered whether it had even been in the textbook, and I picked those concepts up again during this time.

For the March and April joint academic assessments, retake students can't take them alongside high school seniors (hereafter 'current students'), so I took them the day after they were held. Maybe because I'd studied for an extra year, I got grade 1 in everything except Korean History on both.

For reference, in June and September you can take the exams at an academy or a school, but you have to apply about a month in advance. You also have to pay a fee. Honestly, apart from early admissions, this is the only disadvantage retake students have compared to current students.

Summer

If you don't slack off during this period, you can pretty much get into the university you're aiming for.

And then I scored a big win on the June mock exam. Except for math. I dozed off during math. So on top of 21, 29, and 30, I ended up also getting 18, 20, 22 (!), 26, and 27 wrong, a truly spectacular situation.

But I started thinking, 'I got grade 4 because I dozed off, and if I hadn't, I would've gotten at least grade 2,' and in July I got grade 1 in every subject again. This was when I should have realized that the grade cutoffs for the academic assessments (March, April, July, October) mean nothing, but instead this is exactly when I started getting seriously lazy. Part of it was that my room was hot and had no air conditioner, so I started studying in the living room, where the TV was, but the decisive factor was that I started getting overconfident in my skills.

They say all retake students lose motivation around this point, and that period I thought would never come for me came anyway. The planner I'd filled out every day got emptier and emptier, and some days I just spent the whole day glued to my phone and laptop. All while thinking things like, if I took the CSAT right now, I'd totally ace it.

Still, there was no denying that the September mock exam was coming, so I slowly started working on private mock exam packs. Once it was the end of August, that is.

So how will this exam taker do in September? Make your prediction before scrolling down.

(Censored)

Fall

Overall, I scored worse than on the 2017 CSAT.

Why? Was the concept review I'd worked so hard on until June not enough? Or was I just not good enough?

Neither. I'd made absolutely absurd mistakes evenly across every subject. Most of the 16 problems I got wrong were truly ridiculous mistakes. To give just one example of how ridiculous, on problem 3 of Chemistry I,

Bond a, which was clearly a solid line…

Believe it or not, I read it as a dotted line and got it wrong.

I seriously wondered how I'd gotten all the hard problems right (except math 21) and yet gotten wrong problems that other people couldn't get wrong even if they tried, and in the end I concluded it was because I'd slacked off from June to August and lost my feel for solving problems.

So what do you do then? You have to get used to solving problems again. From this point on, I started studying mainly with mock exam packs, to get used to solving problems again and to train the ability to solve the hard problems, the so-called 'killer questions,' within the time limit. I'd probably run into killer questions while doing past exams, but I felt that 'being able to solve it' and 'being able to solve it within the time limit' are different things. In the end, the CSAT is a battle against the clock.

I also started taking classes at single-subject cram schools. Single-subject cram schools in Daechi-dong, Mokdong, or Bundang are not only cheaper than retake academies, but if you pick well, you get to solve pretty high-quality private problems every week. You don't see many retake students at single-subject cram schools, so you might feel a bit out of place, but hey, it's only for three months.

Oh, and please don't ask about early admissions. I used all six applications on essay-based admissions. I got rejected from all six. Thank you.

As a side note, anxiety can be either an obstacle or fuel depending on how you use it. More precisely, it's the best fuel when it's balanced with confidence. After the September mock exam, I was extremely anxious about whether I'd even do better on the CSAT than last year, but if I'd only been anxious, I'm not sure I could have stayed calm on the CSAT. What I knew for sure was that when I studied diligently from February to June, my June mock exam scores were so good it was hard to believe I'd averaged grade 3 on the 2017 CSAT (except for math). If you do it, it works. September didn't work because I didn't do it.

And so I ran full speed all the way to the CSAT.

The CSAT Postponement

The day the postponement was announced, I was in despair and furious that I had to do this for a whole 7 more days. But you can't blame anyone for a natural disaster, so while it made me angry, I just think of it as one of the prices I paid for not choosing Earth Science.

The science electives are great subjects for raising your score in a short time. During those 7 days, I focused on studying for them.

CSAT Day

I took the 2018 CSAT at the same test site as the 2017 CSAT. I got up early that day, left at 5:30 a.m., arrived early at 6, dozed off in the car for a bit, and entered the classroom at 7:30. For breakfast I had a single banana, which is easy on the stomach but high in calories, and I brought an enormous amount of chocolate and ate some after every period.

Managing your condition and mental state on CSAT day is really important. Right off the bat, the passage on the first page of period 1 Korean just wouldn't sink in. In period 1 especially, the sound of other test takers flipping the page after finishing page 1 is really distracting, so I just did page 2 first and then page 1. That way, I didn't have to worry about the page-flipping sounds.

For lunch, I ate what I usually eat, just a bit less so I wouldn't get sleepy. The chocolate takes care of the calories anyway. Chocolate is delicious. It's not like eating a lot for one day is going to make you balloon by several kg, and if my brain graciously wants to keep spinning, of course I have to feed it. What else can I do?

It was hard overall, but except for the first page of Korean, I don't think I was that nervous. If you keep practicing under real exam conditions right up until the CSAT, it feels like you're taking a mock exam even though it's the real thing. It totally feels like a mock exam; the test paper just doesn't have the words 'mock exam' on it.

After each subject, I'd get anxious wondering whether I'd solved things correctly, but the OMR sheet was already turned in, so I just forgot about it and took the next subject at ease. Of course, during the breaks, I worried like crazy.

After every exam, including the science electives, was over, the way home felt lighter than last year.

Winter Again

After getting home, I nervously graded my answers that evening. The scores were so good I couldn't believe they were mine. Thankfully, this time it was in the good direction.

It didn't quite feel real. On the math OMR card, I'd erased and corrected answers with correction tape several times, and I was anxious right up until the day before scores were released, worrying that the tape might have peeled off or the ink might have smudged.

But it was a pointless worry.

Excluding Korean History, I went up a total of eight grades compared to the 2017 CSAT.

I do have the lingering regret that I could maybe have gotten grade 1 in everything if I hadn't slacked off in the summer, but I was still really happy. I kept repeating to myself, 'I'm glad I did the retake.'

I'd never really achieved anything properly through hard work before, so in the sense that I learned that if you have the will and just do what you set out to do, it happens, 2017 was definitely the most meaningful year of my life so far.

Right now, I've submitted my regular admissions applications and I'm waiting for the results. I think it'll go well.

That's how I lived last year.

Gacha (loot boxes) is an evil invention.

If you're wondering why I'm suddenly talking about gacha, it's because you can hardly talk about games these days without mentioning "randomized items." Of course, most of the games I play have randomized items too. But I'm pretty far from the kind of wise consumer who debates the ethics of randomized items, so I'll go in the completely opposite direction and talk about "How much do I have to spend to collect every character?" (Shut up and take my money) in a few games.

Probability basics

In statistics, there are some concepts used to express probabilities mathematically. Random variables, probability mass functions, and expected values are among them.

A random variable is a number that has values and probabilities. It's usually written in uppercase. For example, the number you get from rolling a die can be called a random variable $X$.

A probability mass function is a function that maps a random variable's values to their probabilities. It's written like $P\left(X=x\right)$. Put simply, $P\left(X=x\right)$ is the probability that $X$ equals $x$. Taking the die roll mentioned above as an example,

is how we could write it.

And the expected value is, literally, the value you expect from a random variable. Also called the mean, the expected value is written as $E\left(X\right)$. For the faces of a die, the mean is $E\left(X\right) = 3.5$.

But imagine a die with something like a piece of metal stuck inside, so that one face comes up abnormally often. For example, say 6 comes up with probability $\dfrac{95}{100}$, and each of the others only with probability $\dfrac{1}{100}$. Can we still say that the mean is $E\left(X\right) = 3.5$ after many rolls?

Nope. In this case it'll land on 6 almost every time, so the mean will be close to 6 if anything, not 3.5. That's why, when computing the mean, i.e. the expected value, you have to multiply the values by their probabilities. Here, the expected value can be computed like this.

5.85 seems a bit more believable than 3.5!

Anyway, generalizing this, when $P\left(X=x_i\right) = p_i \left(i=1, 2, \ldots, n\right)$ we can write it as follows.

Also, as you can see, since $E\left(X\right)$ is made up of a sum of ${x_i}{p_i}$s, $E\left(aX+b\right)=aE\left(X\right)+b$, $\sum E\left(X\right)=E\left(\sum_{}^{} X\right)$, and so on also hold.

Getting every card – with no rarity weighting

I'll go through a few different games, but let's start with SOUND VOLTEX. SOUND VOLTEX is a rhythm game, but pulling high-rarity cards is almost essential for progressing through the story. The cards are divided into rarities, and people say you can really feel that duplicate cards are deliberately set to show up more often, but since the actual rates aren't disclosed, I'll assume there are no per-rarity rates and every card has the same chance of appearing.

First, let's make a few assumptions.

1. Each card pull costs 1,000 won.

2. Cards are pulled one at a time, and you check the card before pulling the next one.

3. There are $n$ kinds of cards in total. Each kind appears with probability $\dfrac{1}{n}$.

4. Once you've pulled all $n$ kinds, you stop pulling.

5. In the game, if you pull an already-owned card 10 times, the next one is guaranteed not to be a duplicate, but we'll ignore that here.

Then, on average, how many cards do we need to pull in total to get every kind? In other words, if we let the number of cards we need to pull be the random variable $X$, what is $\left(X\right)$?

Trying to compute it directly feels hopeless. Let's think of an easier way. If we let the random variable $Y_i$ be the number of pulls it takes to get a new kind of card when you've already collected $i-1$ kinds, we can think of it as $X = Y_1 + Y_2 + Y_3 + \ldots + Y_n$.

This way, $P\left(Y_i = k\right)$ means that, having already pulled $i-1$ kinds, you pulled a new kind on the $k$-th pull. So for $k-1$ pulls you got one of the $i-1$ kinds you already had, and on the last one you got one of the $n-\left(i-1\right)$ remaining kinds. That is,

Now that we have a formula, we can find the expected number of pulls needed to get a new kind of card when there are $i-1$ kinds. Theoretically, you might never get a new kind even after infinitely many pulls, so $k$ can effectively range from 1 to infinity. Therefore,

The expression is messy, so let's substitute $\dfrac{i-1}{n} = r$ and keep going:

Here, since $r$ is less than 1, the power series above can be computed using the sum of an infinite geometric series. Differentiating both sides of the identity $\sum_{k=1}^{\infty} r^{k} = \dfrac{1}{1-r}$ with respect to $r$ gives $\sum_{k=1}^{\infty} kr^{k-1} = \dfrac{1}{{\left(1-r\right)}^2}$, and using this to simplify,

we get a pretty simple formula. Finally, substituting $r = \dfrac{i-1}{n}$ back in and simplifying,

is what we get.

At the start we split $X$ into $n$ $Y_i$s, so we can write $X = \sum_{i=1}^{n} Y_i$. By the definition of expected value mentioned earlier,

so substituting $E\left(Y_i\right) = \dfrac{n}{n-i+1}$,

is what we get. If we now substitute $u = n-i+1$, i.e. $i = n-u+1$, the range of $i$ from 1 to $n$ becomes the range of $u$ from $n$ to 1, and since a sigma gives the same result even with the range reversed, the formula becomes

There's no other way to simplify $\sum_{u=1}^{n} \dfrac{1}{u}$, so let's be satisfied here and leave it to Wolfram|Alpha.

Applying it

Now all that's left is plugging in numbers! Suppose a card set has 31 cards in total and cards only come from those 31. Then when $n = 31$, $E\left(X\right)$ is

which means you can collect every card by putting in about 124,845 won! Of course, in the actual game, pulling an already-owned card 10 times guarantees the next one isn't a duplicate, and since we ignored that, the number does feel noticeably inflated.

Producing every idol – with rarity weighting

But many games aren't that easy on you. That's because they assign probabilities to rarities too.

A prime example is THE IDOLM@STER CINDERELLA GIRLS STARLIGHT STAGE, which has cards in 4 rarities: Normal, Rare, S Rare, and SS Rare. It's a rhythm game where you form a unit of 5 idols, and SS Rare idols have much higher total appeal stats, which directly affect your score, and much better skills too. A deck of 5 SS Rares scores far better than a deck of 5 S Rares, so SS Rare idols are essential if you want high scores. And most decisively, the illustrations are really pretty, which triggers the urge to collect them.

However, the game announces that the chance of getting an SSR is 1.5%. That means 98.5% are S Rare or lower. So how much money do you need to get every SSR idol?

Let's make a few assumptions.

1. Scouting an idol once takes 250 Star Jewels. 0.85 Star Jewels cost 1 yen.

2. Idols are scouted one at a time, and you memorize the idol's name before scouting the next one.

3. There are $n$ SS Rare idols in total. Within the rarity, each idol appears with probability $\dfrac{1}{n}$. Limited idols are not treated as limited.

4. The probability of an SS Rare idol appearing is $p$.

5. Once you've scouted all $n$ SS Rare idols, you stop scouting.

Like we did for SOUND VOLTEX, let's split the random variable $X$ into $n$ $Y_i$s. But this time, we don't consider non-SSR idols. As before, $P\left(Y_i = k\right)$ means that, having scouted $i-1$ idols, you scouted a new idol on the $k$-th try. For $k-1$ tries you got one of the $i-1$ SSR idols you already had or an SR-or-lower idol, and on the last one you got one of the $n-\left(i-1\right)$ SSR idols you haven't scouted yet.

Here, the probability of scouting one of the $n-\left(i-1\right)$ remaining SSR idols is $p\left(1-\dfrac{i-1}{n}\right)$. Scouting one of the $i-1$ SSR idols you already had or an SR-or-lower idol covers every case except scouting one of the $n-\left(i-1\right)$ SSR idols you haven't gotten yet, so its probability is $1 - p\left(1-\dfrac{i-1}{n}\right)$. Therefore,

To make it easier to compute, let $p\left(1-\dfrac{i-1}{n}\right) = s$:

Letting $1-s=r$,

we get exactly the same form as last time. The only difference is the expression inside $r$.

Again, theoretically it might never show up even after infinitely many pulls, so doing the same calculation as before,

is what we get. Computing $E\left(X\right)$ as well,

so, just like the earlier computation with $\sum_{i=1}^{n}\dfrac{1}{\left(n-i+1\right)} = \sum_{u=1}^{n}\dfrac{1}{u}$,

is what we get. So we can see that the expected value is inversely proportional to the appearance rate.

Applying it

According to a site called Deresute SSR Ownership Rate, there are currently (August 13, 2017) 127 SSR idols in total (70 regular, 57 limited). Also, since the SSR rate is 1.5%, $p = \dfrac{3}{200}$.

Ignoring limited idols and assuming all 127 can come out of the gacha, when $n = 127$,

so on average you'd need 11,483,625 Star Jewels, which, going by the efficiency by purchase amount, means you can collect every SSR idol by spending 13,353,052 yen on average ($\approx$ 135 million won).

On the other hand, if we only consider the 70 regular idols, when $n = 70$,

so in this case you need 5,638,300 Star Jewels. Therefore, you can collect all the regular SSR idols by spending 6,633,294 yen on average ($\approx$ 67.0 million won).

During the Cinderella Fes at the end of June, the SSR rate was fixed at 3%. In that case $p = \dfrac{3}{100}$, so if you only pull during Fes periods, since the cost is inversely proportional to the appearance rate, you can now expect to scout everyone for half the prices listed above.

There are also ways to get Star Jewels besides paying, though they're a pretty small fraction compared to the amount you need, so taking those into account it might cost less than the prices above.

Getting every hero – considering rarity weighting and purchase-only characters

Crusaders Quest is an unusual game. Excluding "Legendary Heroes," which can't be obtained from the gacha, 1–3★ heroes are classified as "Normal Heroes" and 4–6★ as "Advanced Heroes." Heroes having ranks is no different from other games, but with a bit of effort heroes can be promoted to a higher rank. Promotions into 2–4★ are completely random, but promotions into 5–6★ are fixed. For example, the 3★ Gacha Ranger B can promote into the 4★ Violet, but once she's the 4★ Violet, promoting her always gives the 5★ Puppeteer Violet and then the 6★ Magic Puppeteer Violet.

But Advanced Heroes are further divided into "Promotion Heroes" and "Contract-only Heroes." Contract-only Heroes come out randomly from the "Golden Contract," which costs 5–6 gems. So how much do you need to get every Contract-only Hero?

The conditions this time are as follows.

1. We assume heroes are contracted consecutively. Ignoring the price of the first contract, each contract costs $5$ gems. 1 gem costs 550 won.

2. Heroes are contracted one at a time, and you check the hero's name before contracting the next one.

3. There are $n$ heroes of 4★ or higher in total. Each hero appears with probability $\dfrac{1}{n}$. Of these, $m$ are exclusive heroes.

4. Once you've contracted all $n$ kinds of heroes, you stop contracting.

5. In the game, contracting 10 at a time guarantees the last one is 4★ or higher, but we won't consider that here.

6. In the game, certain heroes get boosted contract rates for limited periods, but we won't consider that here.

Earlier, the expected value for scouting all $n$ idols of a rarity with probability $p$ was

If we treat "all Contract-only Heroes" as yet another rarity within 4–6★, the probability of contracting a Contract-only Hero within 4–6★ is $\dfrac{m}{n}$, so without any more complicated calculation, the expected number of contracts to get every Contract-only Hero is

There we go.

Applying it

The probability of getting a 4★ or higher hero from a Golden Contract is 19%. Also, according to the hero tier list, Crusaders Quest currently (August 13, 2017) has 43 Promotion Heroes and 58 Contract Heroes, excluding event and Legendary Heroes that can't be obtained from contracts. So setting $n = 43 + 58 = 101$, $m = 58$, $p = \dfrac{19}{100}$,

so on average you can get every Contract Hero by buying 21,505 gems, i.e. spending 11,827,750 won. Of course, this game has tons of ways to get gems besides paying, and we didn't account for the guaranteed contract heroes, so the actual spending is expected to be much lower than this.

Wrapping up

I expected large values going into the calculations, but I was really surprised when the numbers came out way beyond what I'd expected.

Especially for THE IDOLM@STER CINDERELLA GIRLS STARLIGHT STAGE, after calculating that collecting every idol takes tens of millions of won on average, you might think you'd be better off buying a car. But then again, a car won't dance and sing, so I think it has its own meaning.

Finally, none of the games mentioned require you to collect every character to progress without much trouble, so unless you're planning to collect them all, please just take these prices as "wow, the numbers get this big."

An ‘easy to remember and secure’ password?

If you use the internet, sooner or later you'll have to sign up for some service. And to sign up, you usually have to come up with a new password. It used to feel easy to make one, but now they want you to use uppercase, lowercase, numbers and special characters all at once, which is just mind-boggling.

Let's fire up a password generator. I made a 10-character password for internet banking and got bet8qU_r#u, which looks strong at a glance. But it doesn't look very easy to remember. It's a bank password, so writing it down somewhere makes me worry someone might see it, and memorizing it looks like it'd take quite a while.

An ‘easy-to-remember password’ and a ‘secure password’ seem to contradict each other. But is that really so?

Secure passwords

• If your passwords are already secure enough, feel free to skip this part and jump to ‘Easy-to-remember passwords’!

Why do we make ‘secure passwords’ in the first place? Usually it's to keep people we don't want from logging into our accounts. By ‘people we don't want’ I mean those who can figure out our passwords on their own – generally, hackers.

First, let's assume the sites we sign up for store passwords encrypted. (Honestly, every site should. Any web developer building a site that stores passwords in plaintext in 2017 deserves to be fired on the spot.)

So how can a hacker figure out a password? Even if they get hold of our encrypted password, there's no way other than bruteforcing.

Encryption works like this. Suppose I set the admin password for this site to shift.moe123. Then the server (if it uses the SHA-256 algorithm) doesn't store the password as-is, but stores something like this:

98086156AA56FE8A7D5AC35D4EA21A49A776505B869CC76829CCD93BAC91A3F9

This is called a hash. Each password has a different hash. So to check whether a password is correct, the server hashes what the user typed and checks whether the values match. For example, the hash of shift.moe123 is always the same as the hash above.

And even a tiny change to the password makes the hash completely unrecognizable. For instance, the SHA-256 hash of shift.moe124, with just one character changed, is

66CFE1B558388800107E5E0CE4AADE6866F8FCE147D7D41108D7E930AD923DD5

The two hashes look completely unrelated.

There are… two ways to recover the original password from a hash. You can try inputs at random, or you can analyze the encryption algorithm. With the latter, as of now, you could crack a single hash by investing an astronomical amount of money over several decades. Naturally hackers don't find that worth it, so they start brute-forcing.

Brute-force strategies

Suppose a hacker gets hold of a database containing information on every user of a site – including password hashes. Who's the target? Usually they'll generate hashes somehow and take over the accounts of whoever they happen to hit. Any account will do; as long as they can log in, it's worth something, whether that's spamming posts on an online community or making financial transactions.

First, the hacker will try the passwords people use most often. Passwords like 1234, 123456 and qwerty are classic examples. These are the first ones to get hit. According to the site above, 91% of all users still use one of the top 1,000 passwords on that list. You can typically try about 2.6 million SHA-256 keys per second, so if you're using a password from that list, it could be exposed in less than 0.001 seconds.

These days, though, sites block these passwords right at sign-up. On such sites, nobody uses them in the first place, which means there's nothing for the hacker to gain.

The next thing these hackers try is random word guessing. They combine words from a dictionary and try them all from start to finish. If your password is made only of dictionary words, it depends on how many words are in the dictionary, but with 300,000 English words, a one-word password would take about 0.115 seconds and a two-word password up to 9 hours and 35 minutes. Again, the hacker only needs to hit something among tons of data, so 9 hours and 35 minutes is a very short time, well worth investing.

If word guessing doesn't yield much, they start trying every character at random. But this has a bit of a drawback: each extra character in the password multiplies the number of attempts needed.

Say we first try to guess passwords made only of digits. There are 10 digits, so there are 10 possible characters per position. So to guess a one-digit password, you need 10 tries. Two digits would take $10 \times 10 = 100$ tries, and a password of $n$ digits would be cracked in $10^n$ tries, right?

We said you can try 2.6 million per second, so a 4-digit password takes $\dfrac{10^4}{2,600,000} \approx 0.000385$ seconds and an 8-digit password $\dfrac{10^8}{2,600,000} \approx 38.466$ seconds. Every extra digit makes it take 10 times longer. So what if we mix in lowercase letters?

There are 26 lowercase letters, so mixing them with digits gives 36 possible characters per position, and a password of $n$ characters would be cracked in $36^n$ tries. A 4-character password takes $\dfrac{36^4}{2,600,000} \approx 0.6460$ seconds, and an 8-character password $\dfrac{36^8}{2,600,000} \approx 1,085,042.3$ seconds, or about 12 days, 13 hours and 24 minutes. Same 8 characters, but what took under a minute with only digits now takes nearly two weeks just by mixing in lowercase letters.

Now let's put the times in a table.

That's why many sites recommend mixing digits, lowercase, uppercase and special characters in your password.

The problem is that once you've made a really complex password mixing digits, lowercase, uppercase and special characters, it's hard to remember.

Easy-to-remember passwords

So what counts as ‘easy to remember’?

What's hard or easy to remember differs from person to person, but in general, giving a password some meaning seems to make it easier to remember. Instead of a weird meaningless string, for example... I'm hungry right now, so let's make a password out of a food name. You can test how long it would take to crack a password here.

Here's BBQ Chicken, which has been getting a lot of flak lately for raising prices. We could come up with the password #Golden_Olive_Chicken. Plugging it into the site above, it says cracking this password would take 176 quintillion ($=1.76\times10^{20}$) years. There are no digits, but uppercase, lowercase and special characters are mixed nicely, and it's easy to remember while being a whopping 21 characters long. Logging in while hungry might be a bit rough, but it looks like a plenty strong password!

Or you could come up with a password from song lyrics.

This song came out over 4 years ago already. Time really flies... We could go with something like I'm_a_mother_father_gentleman_130412. The lyrics alone might be easy to guess, so I tacked the release date on the end. It's a strong, easy-to-remember 36-character password with special characters, uppercase, lowercase and digits. It would take $1.82\times10^{53}$ years to crack.

Or you can make a password by just typing a Korean sentence on the keyboard. For example... ‘웃으면서 미래의 이야기를 합시다’ (‘Let's talk about the future with a smile’) becomes dntdmaustj_alfodml_dldirlfmf_gkqtlek. It only has lowercase letters and special characters, but it's long enough that it takes $9.0\times10^{39}$ years.

Double consonants give you uppercase letters (on an English keyboard, holding Shift while pressing a key makes it uppercase), so ‘대한민국의 주권은 국민에게 있다’ (‘The sovereignty of the Republic of Korea resides in the people’) becomes eogksalsrnrdml_wnrnjsdms_rnralsdprp_dlTek. A whopping 41 characters, taking $5.86\times10^{56}$ years!

This is how you can make passwords that are both easy to remember and strong. Why not remake your weak or hard-to-remember passwords right now?