We invite you to participate in CodeChef’s Starters123, this Wednesday, 28th February, rated till 6-Stars (i.e., for users with rating $$$< 2500$$$). This contest is organized by Jadavpur University Electrical Engineering Students' Forum for Algomaniac 2024.

Time: 8:00 PM — 10:30 PM IST

Algomaniac is the CP event of Convolution, the annual techno-management fest of the Department of Electrical Engineering, Jadavpur University. The contest will serve as an online preliminary round for an on-site final on March 17, 2024. To be eligible to participate in the finals, one must register on the Convolution 2024 website.

I could not find any article or blog on this idea, and felt having one could be helpful to many. There might be unwanted errors, so please feel free to to share any suggestions, corrections or concerns. For those who are unware of Binary Exponentation, this CP-Algorithms article or this video by Errichto can help get familiar with it.

Introduction

Now that we know the idea behind binary exponentiation; let us try expanding the idea. Say, we break the problem into two parts, $$$L$$$ and $$$R$$$, such that, once we have both the results, combining them gives us our final answer as $$$ans = L \odot R$$$, where $$$\odot$$$ is an associative binary operator. If we can find $$$R$$$ as a function of $$$L$$$ as in $$$R = f(L)$$$ fast enough, say $$$O(X)$$$, then our final answer can be found in $$$O(X\;log(n))$$$.

While looking up an editorial for a CSES task, I recently stumbled upon CSES DP Section editorial blog by icecuber. Noticing that a few new tasks had been added since the blog was posted 2 years back; I decided to take his permission and write this blog, which contains editorials to the newly added tasks and acts as a sequel to his blog.

I would like to thank dominique38 for being the most enthusiastic co-author possible, defnotmee for being the second most enthusiastic co-author (he wanted the title himself), Perpetually_Purple for helping me out and giving suggestions, AntennaeVY for suggestions on the understandability and formatting of the blog; and finally, icecuber himself for going over the blog and giving me confidence in the form of a final thumbs-up!

The editorials may at some point appear excessively lengthy, but that is intended. Since CSES tasks are meant to teach standard approaches and techniques; I wanted this blog to be able to act as a substantially self-sufficient resource to learn the involved technique instead of just telling what technique to use to arrive at the solution and giving the implementation in code.

I would urge readers to first try to solve the problems themselves; and only then refer to the editorials. This will maintain the purpose and spirit of the CSES Problem Set.

All the problems are from the CSES Problemset.

Introduction

Often in Competitive Programming, we have to choose between multiple algorithms/ approaches for a problem. How do we decide which algorithm is better and which algorithm to go for? Runnning an algorithm comes at the cost in the form of time taken or memory consumed. In this blog, we will try to compare algorithms or approaches based on their Time Complexity, which simply put is the time taken by them to run.

So how do we compare the algorithms? Do we calculate the exact time taken by them to run? Or do we try to predict the time taken based on our input? These approaches to calculate Time Complexity can be called as Experimental Analysis and Theoretical Analysis respectively.