My IOI 2020 Programming Journey | By Silver Medalist Udit Sanghi

8 min read

Warning: Long blog. The format and some stuff will be similar to http://www.sidhantbansal.com/My-Cp-Journey-Part-1, you should read that as well. Also, there may be minor spoilers regarding some problems. 

Warning: Long blog. The format and some stuff will be similar to http://www.sidhantbansal.com/My-Cp-Journey-Part-1, you should read that as well. Also, there may be minor spoilers regarding some problems. 

I first got introduced to programming in 2015 at the end of grade 6. I was playing some mobile games when a friend of my father told me about how games are made and stuff. I played around with JavaScript on Khan Academy after that for a few weeks but then got bored, so I quit (maybe because I found coding in itself boring without the problem-solving aspect).

Grade 8:

Around July 2016, I was told about IOI by a friend of mine, Atharva (brother of Akshat Bubna). I learned python on Codeacademy and did elementary stuff on HackerRank, and later CodeChef. At the end of the month, there was an introductory workshop to competitive programming in IIITD, which I attended and was very interesting. I took part in IIITD’s coding competition named Procon Junior. I didn’t even know basic loops and stuff properly then. Still, I managed to qualify for the second round and solved one problem in that as well. 

I kept doing CP that year. I also prepared for ZIO (Zonal Informatics Olympiads). I practiced many CodeChef problems, and enthusiastically took part in its competitions (Lunchtime, CookOff, and Long Challenge). 

There was an INOI workshop conducted by IIITD in October that year for six days, which I was very excited for, but sadly due to some unfortunate reasons, I could not attend the first two days. Naturally, I could not understand anything in the rest of the workshop, which was very frustrating. (Although when I learned the things myself, I found them easier because I knew the ideas subconsciously). However, I met some great fellow participants I had seen in CodeChef rankings like Aulene, Vivek, Yogesh, and Istasis. There were coaches like Jatin Yadav, and Anup Kalbalia also gave his routine lecture. 

I learned C++ after this. I also focused more on learning the standard algorithms/data structures since I only solved implementation problems until then. ZIO took place in November, and I cleared that easily. INOI was in January. I prepped hard for that; I solved all the past year ZCO, INOI problems, and a lot of DP, graph problems on Codeforces. Then came the day of INOI. There were two problems. I had 50 on one problem and 15 on the other. A minor modification would have made 15->60, and I would have qualified. The cutoff was 100. After this, I kept practicing and learned more stuff. In class 8, I had a lot of free time, so I did CP almost the entire day(except during exam weeks) after returning from the brutal tortures of school.

Grade 9:

Around March 2017, I became blue on Codeforces, which was nice.

Around July, I attended IPC camp(1 week) organized by CodeChef. Although it was way too advanced for me to grasp anything, the coaches’ side lectures helped where they taught relatively less advanced stuff. I also met many pro people.

 I kept taking part in various competitions throughout the year. Near the end of the year, I became purple on Codeforces. 

I also cleared INOI pretty easily this time.

In class 9 also, I had a lot of free time, so I did CP almost the entire day.

^^ Me in some competitions

2018 turned out to be the worst year of CP for me.

First, I had to spend February on my school exams.

Grade 10:

In march-April, the two months before IOITC, I got addicted to CS:GO. So, I didn’t prepare well for it.

IOITC 2018:

tl;dr: I came 5th

I didn’t expect to get into the team before the camp this year. It took place in May for ten days. Every day we had a practice contest and a few lectures in the evening. Most of the classes were pretty easy stuff but some very nice. I won most of the practice contests, so that gave me a little bit of confidence that I can still qualify for the team. Then there were the TSTs for three days.

Day 1: P1 was a simple greedy problem, and I  solved it. P2 was a hard graph problem taken from a Russian Maths Olympiad. Nobody solved this. P3 was a fracturing search problem. I don’t think any of us knew it at that time, so no one solved. I was 4th after day 1.

Day2: This was supposed to be an easy day. Adhyyan AKed it. I couldn’t solve a single problem. P1 was a simple combinatorics/graph problem that I somehow generalized into a very difficult problem and tried to solve that instead, which wasn’t possible. P2 required dealing with overflows and floating-point stuff, and I couldn’t debug that. P3 was an excellent graph problem. I was 6th after day 2. 

Day 3: I didn’t know it during the contest obviously but turns out there was no way I could have done a come back that day since P1 was geometry, P2 was wrong and P3 was taken from some pr0 research paper stuff (no one got a +ve score in P3). 

I came 5th at the end.

I also got bronze this year at APIO. I was pretty sad after missing the team by so little. I didn’t do much CP that year, just some Codeforces contests when I got time but no other practice. Firstly, I had to go to my tuitions for most of my day because I really struggled in school(I have trouble remembering/memorizing stuff), and in 10th, there were “boards.”  

I focused for a couple of months on Math Olympiad. I was able to solve all the non-geometry problems in RMO and 1.5 problems in INMO.

Apart from this, I took part in Google Code-In, where we work for an open-source organization for 3 months, and the top 2 people get trips to Google HQ along with some huge prizes. I worked crazy hard for these three months managing it and my school/tuitions and slept for 4 hours a day. I enjoyed it a little bit but nowhere close to competitive programming. I expected to win after this, but I was named backup winner(sort of 3rd place). I was devastated after this, primarily because I felt I had done a lot more work than the winners. I even asked the mentors why they said that I didn’t communicate much with them. (I get that communication is an essential part of open source, so I’m not challenging their decision here. The mentors were great/helpful throughout the three months, and it was a good new experience for me. I was just totally depressed after this.)

So, weirdly after this, somehow, I got back into CP. 😀 

There was around a three-month period between my 2nd-preboards and my board exams(no school also), and since I had performed well in 2nd-preboards, I got to do a lot of CP during the first 1.5 months of it. I also went to Snackdown in February for four days, stayed in Taj Hotel, and met some of the world’s best competitive programmers. These were the best four days of my life.

^^ Snackdown

Grade 11:

After my boards ended, I became yellow on Codeforces.  For my 11th grade, I had a choice between going to school or going to JEE coaching. Since I didn’t want to handle school again for two more years, I went with JEE coaching.

For a few weeks, I did a lot of CP, but then JEE coaching started. I wasn’t very focused on JEE at that time so I could manage only a few hours for CP. 

IOITC 2019: 

tl;dr: I came 5th again

I was expecting to get into the team this year. I did pretty well on the practice contests again.

Day1: P1 was a simple DP bitmask problem. Somehow, only three people solved P2 was nearly just a convex hull implementation problem. I couldn’t implement that in-contest. Only six people could. P3 was a math problem. I had the right idea about this. I could not implement it in time. No one solved this. Had I implemented some brute subtasks, I would have been in the team. I was rank seven after day 1. 

Day 2: I solved the first two problems. P3 was a nice tree problem. I solved some subtasks of that. I was rank three after day 2.

Day 3: P1 was a simple tree problem I couldn’t solve. In P2, we had to ask some queries to get some information. I wrote a randomized algo towards the end, which gave full points. It was definitely correct, but I didn’t prove how many queries it would take. I was expecting it to pass two subtasks, but surprisingly it passed all. They told me they’d be trying to break my solution since they can’t prove it. P3 was some tedious DS problem no one solved.

After the contest: Anay had covered a considerable gap of 130 points and made a remarkable comeback. If my solution passes < 2 subtasks, he will qualify; otherwise I would. I would moderately confident it wouldn’t exceed queries for the 2nd subtask. They couldn’t create a case or break my solution logically either. They had, however created tests that broke others’ query limits. BUT, for some reason, those tests gave my code WA(not query exceed). We couldn’t figure out the reason why tho.

I ended up coming 5th again by one subtask difference. From then on, I started implementing subtasks for each problem even if I knew the full soln. I also got silver this year at APIO

I was totally broken down after this. I had to do JEE for the next two years now. 

The good news was now JEE turned out to be pretty fun and both my batchmates and my teachers are the best people I’ve ever met.

So, I went like this for the rest of the year. I just did some Codeforces rounds in between when I got time for relaxing.

Grade 12:

So this year, COVID happened.  My focus on JEE decreased since online classes started. My performance kept getting worse. So, I started spending more time on CP. 

I grinded oichecklist. Here is mine.

I didn’t code much in April-May. I just solved problems in my mind and saw/verified solutions. I started spending a lot more time from June onwards. 

I spent around 4-5 hours a day during June/July doing CP. This year the camp didn’t take place, but TSTs were held 21-23 Aug.

I talked to my coaching teachers about taking a break from JEE to prepare for TSTs this year, and they were very supportive.

So, I diverted everything towards TSTs. I spent ~15 hours a day during this period.

I became orange on Codeforces before my TSTs.

IOITC 2020:

tl;dr: I came 2nd so qualified for the team

The competition this year was by far a lot more tough than the previous years. The problems this year were also very nice. The quality was comparable to other major OIs(like APIO, JOI, CEOI, etc.) except for IOI. The problem set however I felt wasn’t very diverse.

Day 1: P1 was a tree problem with a nice observation with tight TL. Solved it after optimizing for a few hours. P2 was a medium level DS problem(with a very nice alternative soln). Couldn’t solve it. P3 was a total implementation hell problem. No one could do that. I was 7th after day 1.

Day 2: P1 was a simple DP on trees. P2 was a straightforward Li Chao Tree/Dynamic CHT problem, and I solved these two within an hour. P3 was a nice problem with two main observations. I didn’t get anything for a while, so I wrote some special cases for one subtask. I got the first observation during the last 30 mins. I coded brute after this. I got another subtask. I didn’t have time to code full solution since, without the 2nd observation, the implementation would have been really tedious. I was amazed to see eight people got a full score that day. I was rank eight after day 2. (My rank also decreased because some solutions of day one got broken down). The top 3 were 82 points above me and 4th place was 50 points above me.I just believed I had a chance because Anay did that last year.

Day 3: P1 was a very nice problem. I got 52 quickly but spent a lot of time afterward thinking for the full soln as I thought I was really close. I had half the contest time left now. P3 had a hard to understand statement but was a pretty simple DS problem after understanding it. P2 was another very nice problem. I first wrote the exponential brute. I then did some assert(observations == true) stuff to verify some observations. Then I wrote a better brute. I had ~1.5 hours left now. I was freaking out. I managed to keep my calm. After this, I just had to add some binomial stuff to improve the solution. I did this in the last 20 mins. (Had I not got this part, I would have come 5th again, this time missing the team by 1 point). I finally got in this year.

Fun fact: Both me and Anay got 252 for the day 3 clutches. 

I became red on Codeforces after my TSTs. I also got silver this year at APIO. I continued my prep like this till IOI.

IOI 2020:

tl;dr: I won silver

Day 1: I got supertrees subtasks one by one. Got 96. Missed that 4 point meme subtask. Then I went on to try tickets. 41 points were easy. I tried a few random greedies for the next 14 points. Finally, one of them worked. After this, I wrote a DP for 67 and added DnC to get 90. I had the correct idea for 100 but didn’t work on it since it was completely different from my 90 point solution, and I thought 100 points would probably be some small state reduction from 90 points. I got five on plants and had no idea how to get more.  I tried some random heuristics for 11 points but didn’t work. I was ranked 51 after day 1.

Day 2: I was very ill before the contest. I had a fever. Red Bull was the savior. It kept me alive for 5 hours. I started with stations. Couldn’t debug subtask 3 for a long time. I hadn’t solved anything till about 2 hours and didn’t have any ideas either. Finally got an idea for mushroom and earned 80.43 points. Got 9 points on biscuits and later debugged stations to get 65.32 on that. It turns out, I had read the constraints wrong. Towards the end, I optimized mushroom to get 92.62. I ended up coming 113th on day two and 74th combined on both days. I won a silver medal.

Challenge Yourself

Last month, I participated CodeChef November Challenge 2016 and win 2nd prize as a high school student, which makes me delighted. Thanks to CodeChef...
acyume
1 min read

3 Replies to “My IOI 2020 Programming Journey | By Silver Medalist…”

Leave a Reply