Qualifying for ICPC World Finals 2020 - An experience (Part 1 - Online Qualifications)

Hello everyone,

Today, I'll be writing on the journey to qualifying for the ICPC World Finals 2020. This blogpost has been on my mind for a while, but we have been thinking of delaying it uptil after the actual world finals. However, with the coronavirus crisis going on, I thought it'd be a good time to get my (our) thoughts on paper while they're still relatively fresh in our minds!

I'll be talking about a few things in this post (it will be long) - How we prepared, our emotions and problem solving strategy during the contest (a replay, if you will). I will mostly cover the entire India ICPC cycle from October 2019 to January 2020. First, let's get a bit of background in our team structure:

1) Shubham - A 3rd year electrical engineering student.
Strengths: Fast to solve problems, good typing speed, maths background.
Weaknesses: Doesn't code heavy datastructures much, lacks knowledge in this area. Not comfortable with HLD/Centroid or suffix structures

2) Shriram - A 3rd year electrical engineering student.
Strengths: Can think of weird solutions which turn out to be correct.
Weaknesses: Does not practice writing code much. Sometimes this leads to hard-to-find bugs.

3) Tushar - A 3rd year computer science student.
Strengths: Can code hard and lengthy data structures. Has practiced many hard problems.
Weaknesses: Does not practice writing code much. Finds it very hard to parse problem statements and many times makes mistakes due to this. Form is somewhat variable.

So now you have a rough idea of our team structure. Our team is named "BhagwanBharose", which roughly translates to "dependent on god", which was exactly our mindset going in!

The first leg of the ICPC cycle was the Preliminary online qualifications on 18th October. We all gather in Shriram's room for the contest, with some nervous energy. The qualification was a bad experience for us in 2018 - we messed up a bit and ended up 84th, which was enough to only allow us to qualify for 1 regional. We haven't practiced for over a month as a team now, which means that we dread it will happen yet again. To lighten the mood, I put on some Korean pop (which both Shriram and Tushar consider their religion) and start doing some weird dance moves, and all of us end up getting pumped up for half an hour with Twice on full blast. Literally, this IS our entire preparation, I muse silently.

Qualification Round Replay
The above contest can be found here

The online contest starts and we're in. I immediately look at the first few problems. It takes me a few minutes to realize the easiest problem, which is TRAINSET. I code it up quickly, and spend a minute re-reading the code (We learnt the hard way that morale really matters at the beginning. You want to spend a minute more and get AC instead of getting WA then AC). I think it looks correct, and it ACs.

Meanwhile, Shriram does DISCSHOP which ACs, and I tell Tushar about PENS, which seems to me a simple bitmask question. He understands and starts coding it up, while I look at SEGDIR. I get it in 10 minutes and it ACs as well. I look at BEAUTPAR and Shriram starts trying SPS, which seems to be the hardest question in the contest. Both me and Tushar encourage him to do so because the other problems seem very our-style and we should dispose of them quickly enough.

I get the idea for BEAUTPAR quickly, and I know it's something of the LIS sort - you take the prefix sums, and try to find an LIS (with starting value 0), and if this LIS length >= k, you have your desired sequence. However, it seems he is still doing PENS. I decide to get a look at SUMOR. I get a greedy idea, and I tell it to Shriram. He agrees that it looks natural, and I decide to code it and test it out. It gets AC, and we celebrate quickly.

 Tushar gets a WA on PENS and I decide to look at the code as I know the solution. It turns out he had missed a part of the solution I had in mind, and we correct that and get AC. I explain BEAUTPAR to him, and he starts coding it immediately. Meanwhile, I look at SPS, and Shriram moves to SHUFGRID.

It turns out that SHUFGRID is just a problem about maintaining some states in a markov chain type structure. Put simply, there are a few states - at the current square, in the same row, in the same column, and not in the same row or column. We just need to calculate transitions in these states.

I spend 30 minutes on SPS, not getting anywhere. Then, I start throwing everything and the kitchen sink at the problem, just trying out a lot of things and hoping that it gives the minimum. Meanwhile, 2 hours into the 3 hour contest, both Shriram and Tushar AC their problems, and we have 7 out of 8 with an hour to go. Both of them join me in SPS, where I already have a WA previously.

They find a case or two I missed, and I add some cases to cover that. I start adding more and more cases, and eventually I have some long code which works on every example we dream of. I keep submitting and getting WAs, and we don't solve it till the end of the contest. I think we have 9 WAs on this problem.

We end up 9th, which seems okay to us considering how rusty we are. We briefly celebrate with our friend Pranay, and vow to practice more from now on. Around 20 minutes later, my friends message me asking about my solution to SUMOR, saying that someone posted a counter-case on the forum which invalidates most solutions. I look at it, and my stomach sinks. It indeed fails our solution. I begin to get worried, wondering if we will only get to go to one regional again. I immediately call up other friends, and it turns out, their solutions fail too.

Soon, it turns out that there was a problem with the model solution, and thus this problem will be removed. After the ranklist released, we realize that we make both regionals anyway, thus it doesn't matter!

Anyway, this concludes part 1 of the blog. I decided to break this blog into 4 parts, wrt the 4 official contests we took part in this season, and also to increase anticipation. See you soon!

My First Semester

A small video summarizing my first semester at IIT Bombay through photos. 😄

View it here, or see it below.

My experience with NSS

So, in my first semester at IIT Bombay, I had to join one of NSO (National Sports Organization), NSS (National Service Scheme) and NCC (National Cadet Corps).

It was a tough choice, but I ended up with the NIC (National Innovation Club) department of NSS. At the end of the semester, we had to write a rough draft on our experience for the semester. Being the lazy person that I am, I tried to finish it as quickly as possible, while covering everything. So, if this seems not as well formatted as usual, I apologize. However,  I hope it makes for an enjoyable read! :)

You can read my report here (Because it's latexified and converting it back would take too long )


P.S. I've received word that some of my readers don't like the use of emojis, and from some of the readers I've heard that they do like it. So, I'll be opening a poll here - please do let me know!

The poll can be accessed on mobile devices by clicking the "View Web version" button down below.

The ending of a new beginning!

-Some of this content was written a few days back-

Today marks the day when my final crib session at IIT Bombay for the 1st semester concludes. This day holds many mixed feelings - It's the day when I can proudly say that I've survived a semester at IIT! Not very confidence - inspiring, I know (:P).

Around this time seems to be the right time to wonder about the memorable things this semester - what I've learnt, and maybe what I should change to get a better experience out of Insti life (Yes, adopting the lingo already! :P ).

This semester is maybe (probably) the semester with the most amount of diverse courses throughout the 5 years that I'll be here. So, it was quite fun and hectic at the same time; There was a lot of learning that took place, but I was exhausted as well.

First, it's time to look back at the goals set before coming to the Insti:

Goal list 

1) Decent CPI - I would say probably check. :) While it's not going to be "stellar", it'll probably be good enough.

2) Learning and not forgetting -

Before I came to IIT Bombay, like most of the freshers, I talked to multiple seniors before this new journey of mine. There were a lot of expectations; I’ll get a great CPI while handling multiple extracurriculars, I’ll learn rather than mugging for marks, and I’ll spend a lot of times with friends at the same time, planning new outings everyday!

Needless to say, these are quite naïve thoughts – While I didn’t believe all of the above, suffice to say that everyone can daydream, right?

Something that really hit home for me was, sometimes when I asked a senior what was taught in say this – and that course, they would stutter a lot and say that the course was not really their strength and hence they don’t remember a lot. Well, I thought, I’ll do things differently. My aim for the semester was to gain a good enough understanding of the course material, that if 10 years down the line I had to present the course material, all I would take is maybe a day or two of brushing up – the concept would be deeply imbedded by then!

This sounds like quite an ambitious plan, and rightly so I believe. It’s really hard for me to even remember what was taught in school a year back – how would I go about achieving this?

The answer is that, I had to understand where everything came from! And when is this much easier to do? When you love a subject, of course! Now, here was my plan – I would choose a subject, focus on the part most interesting to me, and build everything around it. That way, there was atleast something from the course I would always remember, and I could build my peripheral stuff around it! Sounds ingenious, doesn’t it?

If you have doubts about the above approach, you’re probably correct. I’m just a student daydreaming – I have no idea what’s possible and what’s not. But, if you’re not remembering what you learn whilst doing your undergraduate degree, is it really worth the effort for a piece of paper?

Just something to think about while I expand on this topic and talk what was lacking in my approach in my next few blog posts :)

3)  Will do a lot of extracurrics along with acads - Unfortunately, this was probably not achieved. While I did some extracurrics, I didn't exactly do a lot - something that I should improve upon and prioritize accordingly for the next semester!

Sneak peak at something I created - a character called "AndaMan" (literally, Egg Man) who fights crime with his amazing omelette making skills and shoots eggs out of his palms. He also has his own theme song that states where he's from! (Hint: You can guess it quite easily :P)

4) Meet a lot of new people - Definitely a check! I met a bunch of great people at my first semester here. We've done quite some awesome stuff together and I hope to continue the same trend in the coming semesters :)

5) Going through the "DIY" approach: Actually sitting down and doing things by myself took me a lot more time than I'd expected; While it was relatively easy to be excited about doing stuff and checking out the relevant books in the library for say the first two weeks, beyond that it was hard to keep it up.

I only got around to doing this just before the endsem; I learnt the hard way that I wouldn't be scoring much without really digging into the topics. So, I spent a few days reading books, the old fashioned "classic" method~~

So, that's how my semester measured up to be in a nutshell. Next, I've planned a photo spammed post for the Electrical department trip to Lohagad Fort and a post on my thoughts and the things that I've learnt in this semester. Also, hope to add something on my plans for the vacations! I'll end with a wise quote from a friend (I'm looking at you, Kushagra!):

"Whatever you do, don't waste these vacations. Learn something useful"

I'm going to take this to heart. :)

A short note on Gliders! (& Changes to the blog!)

So, this week is pretty busy for all the freshmen students at IIT Bombay, what with the onset of the quizzing season and all! However, along with studies come extracurricular activities; and a few weeks back, I chose to attend an Aeromodelling Workshop by the Aeromodelling Club, IIT Bombay (their page is here). And I totally loved it!

Our team made a pretty basic glider, but I still learnt a lot about Aeromodelling! Here, I'd like to share what I understood from the workshop and basically how we proceeded about to make this glider successfully.

First, we learnt some Aeromodelling principles. The basic question is: How do planes work? Here, I finally felt that all those hours reading random answers on Quora was productive! The most popular theory, the equal transit theory, is infact incorrect. There is no constraint on the currents moving above and below to complete the trip in the same time.

 A few points that I've picked up from the article links I've attached at the end:

1) It's the engine which moves a plane forward, while the wings move it upward.

2) As a curved airfoil wing flies through the sky, it deflects air and alters the air pressure above and below it.

3) SxL is an important parameter for a glider, where S is the surface area of the tail and L is the length from the center of gravity of glider to the tail.

4) Using the lift equation and torque equations (for stability), we can derive certain area and length ratios which are ideal for flight. We shall use these numbers. [I've added the last 2 points on my own].

So, basically, we were given a few pointers on the number crunching part of the design.

Tail area ~ 20% of the wing area.
Fin area ~ 10% of the wing area.

For the wingspan, due to length constraints of the board we were given to construct our glider, we could choose a length anywhere between 35-45 cm. The ratio of the length to the breadth of the wing (which I believe is called the "Wing aspect ratio") should be between 5-8.

The Tail aspect ratio should be around 3-5 and the Fin aspect ratio should be 2-3. The body length should be around 6/10th to 8/10th the wingspan.

Based on these, and the above area considerations, here are the numbers we used for our glider:

Wings

b = 42 cm
c = 6.5 cm

Tail

bt = 14.78 cm ~ 14.8 cm
ct = 3.69 cm ~ 3.7 cm

Fin

bs = 8.3 cm
cs = 3.3 cm

So, our preliminary task was to cut up all the boards into the appropriate dimensions. Then, it was decided that the tail was slightly smaller than it should've been [according to our mentor eyeballing the dimensions] - so we made a slightly bigger one, although I do not remember the exact dimensions.

The main work left after this was to shape the wings to make it an aerofoil, or atleast close to one in shape. For this purpose, we used sandpaper to rub away all the extra material and make a smooth aerofoil. This was kind of crucial. After this step, we simply attached all the pieces to our fuselage and used a glue gun to stick them together!

Now, the main part left was to balance the aircraft. We used clay for the purpose. Basically, what we wanted was to use clay on the front part of the aircraft such that the center of mass lies approximately at 1/4th the breadth of the wing, on the fuselage. This is important because it makes the glider fly straight.

And after this, we were done! We made a pretty basic design, so our team was the first to finish. Although this was something really basic, I must say that I learnt a lot from this and I hope to get time to take part in such future events (especially RC Planes!).

Shubham out!

P.S. I got inspiration for that last one from watching Obama's final speech recently! Do check it out. :)

Links:

http://www.explainthatstuff.com/howplaneswork.html

https://www.faa.gov/regulations_policies/handbooks_manuals/aircraft/glider_handbook/media/gfh_ch03.pdf

Pics:

Our glider!

Team pic! Kushagra Juneja (left) and Me (right)!

P.P.S - I'd like to add that I've tried experimenting a bit with the blog. Now it's possible to subscribe to this blog via email (if anyone actually wants to! :P), via the option on the middle right. You probably can't view this on mobile devices; to do that, go to the bottom of the screen, click "View web version" and then you'll see it!

Also, I've added a Lyrics for the Week section! I'll be updating this every Sunday with some of my favourite lyrics! Hope you enjoy some of these songs after seeing them here! :)

The Path (A short, incomplete poem)

Hi guys!

While browsing through my older stuff, I found some poems I wrote long back. Most of them were cringe worthy (a forced adventurous one or a over sweet romantic one, for example) but I think I wrote a really deep one.

Unfortunately, I don't have the last 4 paras with me because I never really shared that with anybody and my old phone is now dead. However, I think it's better this way; the poem seems more open ended and offers multiple interpretations. Maybe, all's well that end's well?

The longer I walk down this dark, dark path

Lengthier evermore it seems to get

I shudder, for the night is frosty;

But I must go on; for that is my resolve.

The end cannot be seen; only sensed.

I steel my nerves and walk swiftly; 

For my mind is set;

my destiny lies in conquering

the uniaxial path in front of me.

It behoves ye, dear reader

to set upon thine path!

For great treasure lies at the end

A treasure, so exquisite, one of a kind;

Found and cherished by only those who toil;

Cannot be forged, borrowed or thieved.

Do not pay heed to those who criticize

Those who try to distract, pull you from the path;

You must be strong; for they are but spectators.

It is not their path to walk!

Well illuminated, it is, for them;

But it makes no difference.

They can but shout and jeer;

But they cannot substitute the treasure;

A treasure, unique to it's acquirer.

So, I hope this poem really raises some questions. Is this poem written to be interpreted in an allegorical manner? What does the treasure signify? 

Well, this is one of those "2 AM" poems, which just flow from the mind. So, maybe it makes sense or maybe it's all garbage. I think I have some idea of what I was trying to get at via this poem, but as a fun exercise I'll invite reader interpretations in the comments! :)

P.S. I've added a subscribe by email button on the right, in case anyone actually finds this subscribe worthy =D

What is music?

Music has had a great impact on my life in the past few years. This may seem a bit weird; why would something as trivial as music impact a person's life in a non-trivial way?

The answer lies in my philosophy that the music a person listens to, shapes the person in some way. Music to me is a golden fabric interwoven with beautiful tales, immersing the listener into a different world. As we grow older and more mature, we usually (I do not have a source for this yet! Anyone interested in conducting a statistical analysis?) transit to listening to more meaningful music than when we were younger. Thus, the music you listen to reflects your personality and embodies your inner soul.

I believe that the crux of a good song lies in the lyrics and the delivery, in that order. I often get goosebumps listening to songs satisfying both of these criteria. I believe that music often introduces us to new worlds and thoughts that would have otherwise remained unexplored in our subconscious forever. I've listened to songs that have completely turned my expectations from the genre on its head.

Some of the songs that I will remember for their meaningful content are the following (in no particular order and by no means complete);

1. Let her go - Passenger

This song is simply beautiful. It conveys the fact that we often under appreciate the people in our lives; only when they leave us can we feel the pain emitting from the void in our hearts. The delivery is just perfect, with a slow, romantic tune.

2. Hallowed be thy name - Iron Maiden

This song, to me, at first seemed nonsensical because I could not understand the lyrics properly (being a newbie to metal!). It took me a few listens to get the actual hang of the song. This song is quite philosophical and paints a clear mental picture of a prisoner in his cell about to be taken to the gallows. He starts wondering about his life and the existence of god.

3. Hope - Vicetone ft Obama (I know, right?)

This. Song. Is. Epic. Seriously. I someday hope (haha!) to be half as good an orator as Obama is. This song is a must-listen. 

4. Lose Yourself - Eminem

Well, we all know it. Eminem is pretty (in)famous for being generous with his expletives. But, this song was what lifted me at my low points. Sometimes, you have to be strong. You can't be satisfied with where you are and you need to stretch yourself to bring out your best. After all, you only have one life to live, right?

5. Stairway to Heaven - Led Zeppelin

Just deep. I discover new meanings almost every time I listen to this song. 

x-----------------------------------------------------------------------------------------------------------------------x

As you can see, songs of quite varying genres can be meaningful. I've found that many songs of widely varying genres have molded me into a better person. You feel both the happiness and the pain of the singer as if it were your own. Some songs just connect with the self at a metaphysical level.

Some songs have guided me through my journey, motivating me through my lows and reminding me to keep pushing and working hard towards my goal during the highs. Music is love. Music is life. <3