My OSN-P (Compsci Province-level Olympiad) Experience

Alright, this is supposed to be a quick blog so I guess I’ll just whip everything up really quickly. Oh, and, if you haven’t, you can read my previous blog about OSN-K because that’s the whole reason I’m here.

Oh boy, I would like to skip talking about this exam (because I can barely do it) if it’s possible but I do have some memorable stuff from it.. x) And I hate how you can’t know your code verdict in OSN-P.

---

At School

I took my OSN-P exam with some senior friends from my school earlier today. I guess I’m a bit pissed off with the exam date because we held several school events to celebrate Indonesia’s independence day today and so I couldn’t chip in. However, on the flip side, I got to bypass the flag ceremony held today—those often make me feel short of breath, so I’m grateful of that.

Some other OSN-P participants and I spent time “preparing” ourselves in a room near teachers’ office. Since the computer science exam starts at 1 PM, we had plenty of time to do stuff. We held a small programming match with problems rated as the easiest ones in CodeForces, but I literally struggled with the first one because I tried to outsmart the by-nature naive problem ahaha. Afterwards, I decided to watch some random science/compsci YouTube videos I can find, listen to some songs, and drank a cool beverage I grabbed from one of the food/drink stands for the independence event.

And then, at around 11 AM, we packed our luggages and made our way to the school where the exam will be held. Everyone from my city went there to do the OSN-P exam. We were brought to the canteen to eat something first but one of the seniors said that they would like to avoid eating anything to prevent getting sleepy. I thought it would be a great idea too, and so I didn’t eat anything before doing the exam.

The Exam

We entered the exam room a bit earlier to set up everything correctly (our proctoring device, laptop, etc). I have prepared everything from home, except for one thing: setting up the Wi-Fi hotspot from my laptop for my phone (as the proctoring camera). I had just 5 minutes left, and since for the exam I used (Artix) Linux, and we all know it—there’s no way one can figure out how to configure networking in just a short amount of time. Fortunately, I still have plentiful of mobile data left, so I had to sacrifice about 2 gigabytes of mobile data just for the Zoom meeting..

Also, I didn’t expect the scene set-up to take forever. I hadn’t gone to the restroom yet, but there was no time left. I didn’t get the urge to pee yet or anything, so I started the exam anyway.

The String Problem

So this was roughly the first problem of the exam:

Congratulations on passing to OSN-P! As a way to congratulate you, Mr. Dengklek will make you a “pretty OSN-P string”.

A “pretty OSN-P string” is a string that:

• Consists of at least one letter of each O, S, N, and P.
• Does not contain letter(s) other than P after a single letter P.

Example: “OSNSPP” is a pretty OSN-P string, but both “OSSSP” and “OSNPS” are not.

Your task is to determine the length of the longest possible pretty OSN-P string Mr. Dengklek can make for you by deleting one or more letters from a given string S. If it isn’t possible to create such string, output “-1”. Otherwise, output the length of the string.

Okay, that’s a cute problem. Actually, it looked like a question from last year, so I tried to think about it the same way I would with last year’s problem. And the great part is that, it works just fine.

Initially, I kept track of the amount of O, S, and N characters up to the i-th index of string S so I can count the length when I meet a letter P. However, I realized that that list alone is not enough, since to maximize the length of the target string, you’d want all the extra trailing P letters after finding one P letter, too. I then added the amount of P characters up to the i-th index of string S. So now, I can just add the amount of O, S, and N characters by the amount of P characters from the current index to the last index whenever I encounter a letter P. The maximum length from all those possible configurations would be the answer.

All good, but it took me plenty of time because of my stupid coding mistakes. One of them is:

best = max(best, cnt[i-1]) + 1 + (p[n-1] - p[i]);

Why is the + 1 + (p[n-1] - p[i]) expression outside the max function 😭 yeah but thankfully I noticed that right away. I hope that I didn’t miss any edge case for this one..

Exploring Other Problems

I knew it was going to be hard onwards after I finished that first question, so I hunted for something doable. Was there any? … No, I wouldn’t say so, but I decided to bet on this one:

Factorization Problem

This was roughly the third problem of the exam:

Mr. Dengklek has a budget of N. In a store, he can buy one or more trays of eggs, where all the trays have size of M × M and each costs M. M is an arbitrary prime number. To make matters easier, Mr. Dengklek will buy trays with just one size. After buying the trays of eggs, he will end up with N/M trays of M × M eggs and he would like to sell the eggs back. Mr. Dengklek would be able to arrange the newly bought eggs in several rectangular configurations all with different rows a and heights b (resulting in tray of size a × b). Note that a × b tray and b × a tray are considered different. Because he doesn’t know what the customer’s preferred tray configuration, he wants to buy the tray of eggs that can result him in the most amount of possible row and heights configurations.

What’s the tray size of the eggs that Mr. Dengklek should buy? If there are more than one possible answers, pick the one with smallest tray size.

For example, if Mr. Dengklek has a budget of 60, then he can buy 30 of 2×2 eggs, 20 of 3×3 eggs, or 12 of 5×5 eggs. Each configuration will respectively result in 2² × 30 = 120 eggs, 3² × 20 = 180 eggs, and 5² × 12 = 300 eggs. For the 120 eggs, he has 16 possible configurations. For the 180 eggs, he has 18 possible configurations. For 300 eggs, he has 18 as well. Because the 3×3 tray is smaller and still give the most amount of configurations (18), he should pick eggs of 3×3 sized tray to buy.

Ah, a math problem. To know the possible tray sizes of eggs Mr. Dengklek can buy, I can just do a prime factorization. Then, a factor-counting function can determine the amount of configurations he can make after buying the eggs. Now, I just have to find the tray that gives the most number of factors. Since the algorithms can be run in O(√N) time, I’m pretty sure the program can run safely below the 2 seconds limit.

Well, guess what, factor-counting and prime factorization were my FIRST ever look at competitive programming problems. If you look at TOKI’s competitive programming book, the intro example codes were all about those discrete math problems. It took me a few days just to get the hang of the example implementations back then. I wondered if I could write the same functions in just an hour or less this day..

I slowly traced the problem and wrote the solution. However, I forgot how to write a factor-counting function midway x) after several times doing factorization by hand, I eventually figured it out though.

So, all good, right?

*tries test case 3 with N = 1000000007*

It’s slow?! I thought that my functions are all O(√N).

Oh, wait, the number of eggs Mr. Dengklek can end up with may be so humongous to the point where the square root of it is no longer small enough for the calculation to finish quickly. Also, integer overflow is concerning at this point. I had to do something. I broke down the equation of the total eggs he’ll end up with, and factorized each terms separately by using a hashmap to accumulate the exponents of each factors before finally counting the number of factors the number has by looping through the hashmap once.

And then, after several trial and errors, I finished the code! I Hope it really does work for large N

Other Problems

As for the rest of the problems in the exam, I was completely clueless 💀 I’m not even sure if most of them are DP or can be solved by greedy, but I think most of them are indeed DP.

Freezing

The exam room got cold really quickly. We didn’t wear shoes inside the room; I could feel my feet freezing slowly. However, not just that: being in a cold place is an enemy against my typing skill. Maybe I actually coded a bit slower in the exam, I don’t know.

After a while of freezing, I suddenly got the urge to pee. I had to tell the supervisors that I need to go for a bit but apparently they said I only get 3 minutes. And, guess what? The restroom was crowded 😭 I dreaded in panic, but thankfully, half of them weren’t going to pee at all (Universe pranking me?) and I only had to wait for 2 people in line.

I then returned to my chair, still hopeless about the rest of the problems x)

Going back Home

Yeah I pretty much couldn’t figure out any solution in the last hour that I had. How sad. I guess that I’m a bit disappointed, but honestly, everyone I know of was only able to answer just one or two problem(s) as well.

We then drove back to our school after the exam, but the car was completely silent for the most part. I had no idea why my friends didn’t talk much. Anyway, I had to tell everyone about the exam so I didn’t bother to talk a lot to them either, hhaha.

End Thoughts

I actually came out of the room just as happy as before the exam started.

Well, for one, now I can do TWO problems in a contest! I usually can only do one before 💀 (holy crap, that’s actually pathetic). And then, there’s also me proving to my past self that I am able to write code faster than ever! And besides, I still have next year. No biggie.

But also, I think I really enjoyed the companionship of competitive programming friends. That meant a whole lot more to me than the competition itself. I attended trainings with them for this OSN-P, and honestly, there’s always nothing better than having people to talk to about your stupid algorithm with O(2^N) time complexity and stack overflow potentials ;) I can’t see them anymore next year, and that’s unfortunate. I wish all the best for them.

So yeah. That’s probably it for this year! I’m proud as always to see myself improving. I wish that I won’t have to attend training sessions alone next year, will I?