(This blog post is an update on my competitive programming journey, and hopefully serves as inspiration to others who enjoy programming as well)

It's summer in the states, and I'm back on the grind. Although I'm now a rising high school senior. I still like grinding competitive programming and learning new algorithms. Although I've been through ups and downs, I'm back! And for the first time in a while, without nagging teachers telling me to turn in assignments on time, or friends trying to ask me for answers, I've felt like I can chill this summer and do some codeforces.

Oddly enough, I started competing in every contest I know.

I made a leetcode account, and started competing there.

(I've only done 3 contests, 2 weekly and 1 biweekly) — and it didn't show up at the time I've written this blog.

Done some atcoder (It's hard to wake up, since it's 7 am at the states)

Although I'm not very good when I don't get enough sleep lol.

Done some codechef (I actually really enjoyed codechef, and I have to not miss any more contests in the future.

Now, doing a bunch of contests doesn't always help, but learning from these contests have helped me inch my way slowly to expert. Every time I couldn't solve a problem, I immediately learn from it and the editorial after the contest ends. That's all I have, but programming is fun, and participate in as many contests as you can! Because as long as there are problems you can't solve, you still can learn something from each and every contest.

The following will be a very dramatic rendition of my silver contest. Read the end if you don't care.

As Spiderman No Way Home just hit the theaters in the Americas, I sat in my chair and took the USACO silver contest. My heater was not working properly, but it's Texas, it's like only 50 degrees. (Fahrenheit)

First problem, finding an optimal placement of cows on a number line? Oof... gonna skip that.

Problem two, interesting, a graph problem of which I have to create edges on a graph with a minimum cost. I can definitely do that. Ideas came flooding in my head. I have to connect node 1 and node N, but how do I do that optimally?

Ahh! node 1 and node N are in their own set. Then the question is just finding the right union between those sets with the lowest cost. I could just DSU it. Find the set with the smallest size and binary search the larger set to find the optimal placing. Problem 2, solved (2hr 50 min remaining). Time is ticking.

Problem 3, hmmmmm..................................................... Scrolls down Yeah it was made my ben qi so it must be hard. Given a bunch of intervals of a and b, find the number of possibilities of each number from 0..2M (K) which fulfill the condition

a1+a2<=k<=b1+b2 using two intervals

with (a1, b1) and (a2, b2) being pairs of intervals

First, I started rearranging the variables, yeah was didn't work. Waittttt a minute, M is only 5000, meaning I can do an algorithm that is O(M^2) time! Ok ok ok ok, what can I do?

Let's simplify the problem, what if B was infinity? Than every k greater than or equal to a1+a2 would work. Wait, this sounds like prefix sums.

Well, I know that A will always be less than B, so I can make big prefix sum representing the amount of possibilities that fulfill the condition for each K. I'll count all the times an interval starts with a certain A, then do the same for B. In my prefix sum, I'll have two for loops.

vector p(2*M+5); for i...M for j....M p[i+j]+=acnt[i]*acnt[j]; p[i+j+1]-=bcnt[i]*bcnt[j];

Where i and j represent different starting points for a There are acnt[i] * acnt[j] different possibilities for pairs of intervals that satisfy a1+a2<=k.

Where i and j represent different ending points for b And bcnt[i]*bcnt[j] represent the different possibilities that are greater than k, thus I have to subtract them.

Problem 2 Down (50 min left)

Oh damn, I only have 50 min on the hardest problem. Despite it being freezing temperates in Texas, I pushed forward and stared the problem in the face.

Ok, Farmer John and Farmer Nhoj have cows on a number line, and you have to place Farmer John's cows so John's cows are closest to the grassy fields. If John's cows are closest to a certain field, he gets a tastiness score. Given points on a number line with fields and their tastiness scores, find the placements of N cows that allow for the max tastiness score.

Let's simplify the problem.

We want to maximize the number of points with the least amount of Johns cows. Well, there are 3 different types of sections that we can maximize points in. Everything left of Nhoj's first cow and everything right of Nhoj's last cow can be taken with just 1 of John's cows.

Now here's where it gets complicated, what do we do with those middle sections? After a bit of thinking, I realized that the best possibilities are the following.

Directly in the middle of the section, (just in case if the best fields are in the middle) Close to the leftmost field in the section (just a bit closer than Nhoj's leftmost cow) Close to the rightmost field in the section (just a bit closer than Nhoj's rightmost cow)

Through a lot of trial and error, I figured it out.

I in-contest promoted on a silver contest and then preceded to tank gold. But it's fine, I'm going to grind CF, Atcoder, and USACO. Times are sometimes tough, but today the winter winds were somewhat warm to me.

I hope this was somewhat inspirational because a lot of people are stuck in silver, but I hope that everyone and promote and have high ratings in the future.

Plat is next baby!

Someone dmed me and asked me how I was doing. First off, today was a great day, with a long break due to high school in the States, thanksgiving has allowed me to do some codeforces rounds!

At first, I dropped quite a bit in rating (even going back to newbie!). However, I pushed through and today it paid off. All the stars aligned. It was like magic. I didn't even get a single wrong answer. It was almost too easy.

137th without unofficial, and 62nd with only trusted individuals. Pretty awesome.

As for training, after I had school, I would try to push myself and do some challenging problems. Also, I started reading more. When I was waiting in my school's lunch line, I would read about anything computer science-related. Binary Tree, Heaps, Hashing, things that are not just competitive programming related, just to have fun. I think a lot of people look towards results too much. (As do I) But especially with this year, I've learned to really enjoy computer science.

As for the contest itself, I used many different algorithms. I tried a binary search, sliding window, bfs, all of these were used in the contest. I had a lot of fun. (D has a complicated problem statement lol) There was a sense of feeling "hot". I love basketball, and when you start making a bunch of shots you feel a hot streak. Same thing here. It felt amazing.

If you feel stuck, keep ongoing. (The hardest part is the beginning) But wait till you get that hot streak and you'll love programming and solving problems.

As for where I was, I had to do school lol. I have SATs to study (it's a standardized test for many students in the states), and AP classes to cram. I'm not a super super bright student, but I really want to go to MIT and meet some of the greats like Benq, Ksun, Ecnerwala, and William Lin. So, I really push myself in anything programming-related. I love computer science and hopefully, I can do my best in whatever setting I am given.

If you wanna see me in video format, check out my Youtube Channel, where I talk about stuff going on in my school concerning computer science. If you have any suggestions, please feel free to contact me in any way.

https://www.youtube.com/channel/UC8JIgUYIazvuC4REzNlTOcg <- Youtube

Happy Coding! And Have a great Holiday Season!

Kinda sad, but I'm probably going to going back to pupil. I messed up pretty badly on the second problem and was overthinking during the process.

On the third problem, there was an interesting solution that involved a greedy approach that was pretty cool, but on the fourth problem, I got too greedy. I had 30 min on the clock, definitely not enough time for a C problem, but I thought of an O(N) solution that could pass both D1 and D2. Maybe, just maybe I could do it...

Pretests Failed

When it was the last moment, I hurried and tried the brute force approach involving doing all possible edges (using information from Union Find), but couldn't make it in time. I was really close. I knew that the optimal solution had to involve a tree, and required all vertices to be in their own set. Sadly, this info was not enough.

Oh well, I will get specialist back soon, and I'll learn from my mistakes. It was still a fun contest nevertheless, and happy with what I've got.

Oh yeah, I've got school now so I may not be able to practice that much, and I can't do the div 3 this week. RIP

Practice makes perfect, and cyan feels better than green. (Skip to the end if you don't wanna hear an interesting story)

A while ago, I made a post about almost being specialist. After a month of getting stuck on pupil, I was starting to think I was not fit to advance in my competitive programming journey. Doubts fell like droplets on a rainy day...

But I still practiced... Day after day I would do my daily dose of problems, learning cool new algorithms along the way. Maybe DSU? BFS? DP? Probabilities? Every day I was equipping my toolbelt for the journey. Every day I would challenge myself to a slightly harder task. Although I had to admit, in the back of my head, I was wondering when I will ever use these Data Structures and Algorithms.

Then the day came. In today's contest (Round #736 Div1+Div2), I briskly solved A (as I usually do) and took my time on B. (it was implementation, so it was a little annoying). Then I met C.

C was an interesting graph problem. I was thinking, dfs and brute force, but I saw that N was up to 1e5 so it wasn't possible. Then I found some crucial observations. I realized every update only changes the answer by 1. Then I found that I could make the problem a directed graph. More observations followed. Soon, I simplified from an O(n^2) algorithm that involved simulation to an easy greedy O(n) solution. Oh man. I loved it.

Then I found D, D was interesting. A twist from problem A. After a bit of doodling and writing testcases, I found myself using RMQs (or sparse tables). I barely cared for RMQs, and thought I would never need them, but the algorithm needed an O(1) GCD query, so maybe just maybe it was right. And it was.

After the contest I realized I was top 700, I was so happy. It was worth it in the end. Challenge yourself, and high ratings will come.

If you are stuck in pupil or newbie, the most common reason is you aren't challenging yourself. Do harder problems and most of all, have fun with it. It's going to be a long ride, so might as well enjoy it.

If you are better than me and have a higher rating, I hope you smiled at this blog post, and watch out, because I may even pass you soon.

As always, Happy Coding!!

Also my tags aren't going to be bad, I'll just put #contest or something generic, so it's not instagram-like

Today was the day thought I would get specialist

I was almost there

But FST happened

And I just got 1 point

Oh well, at least I had fun.

Either way, I'm doing tomorrow's contest baby!!!!!