I am a frustrated 4th year non CS nerd at some IIT. Got placed recently. AMA

My hands are tremulous as I write these words. This cold clutch of dreary emptiness is devouring my soul as another contest passes with more negative rating coming my way. As I see my fragile dreams breaking right in front of me, I contemplate if my inane endeavors were ever worth pursuing. I wonder if I will ever be able to recuperate from this.

The last contest was a blunder. I was only able to solve 1 question after 1 hour of thinking. Can you believe that? You can check it here

Under the duress of my inexorable downfall, I feel the urge to announce an acrimonious renunciation of CP. I understand that such a sordid deed would be pernicious in the long run and hence I am reluctant.

In this era of uncertainty, I don't know if I would be able to get a job even after reaching candidate master. Hell, I don't even know if there would any companies visiting my campus this year. The ephemeral kick of solving that one problem in a contest does not soothe the distraught mind for long. Moving on, is a simple thing, what it leaves behind is hard.

Hard times call for hard men, and with that quote, let us look at a few images with deep meanings.

I hope you appreciate the underlying meaning behind these images.

After all, we are all bhediyas in search for our TCS.

Is this contrition? Is this an awakening? Is this goodbye?

I don't know.

Cheers,

MainuCodingBadiPasandAe (Ex-shitposter at Codeforces)

As you all know, that majority of Codeforces users are Indian. Hence, it is important that the community is welcoming to the under-privileged section of India. As a community, we should work for the upliftment of the unfortunate lesser beings, and so I suggest a reservation-like rating system, which will not only uplift the needy, but also make Competitive Programming a more popular thing in general:

Denote $$$s$$$ as the depth of the user in the caste strata (1-indexed)

1) General Category: Start with 0 rating, normal rating delta

2) Other (inferior) Categories: Start with rating = $$$1200 + 200 * s$$$,

The delta changes shall be defined by:

$$$\Delta > 0 \Rightarrow \Delta * s$$$

$$$\Delta < 0 \Rightarrow \Delta / s$$$

Additionally, people with profile photo of god (Ambedkar) shall be exempted from negative delta for up to 5 contests

Further, it should be a mandate to have an equal representation of all categories in higher ranks like candidate master and above. The following scheme is proposed:

• No more than 45% of candidate-masters should be from general category

• If the current number of lower caste individuals in Master league is < 55%, inferior caste individuals from candidate master will be floated up to Master

• If the current number of lower caste individuals in Candidate Master league is < 55%, inferior caste individuals from Expert will be floated up to Candidate Master

Furthermore, the highest rank shall be replaced with the color $$$\color{blue}{\text{BLUE}}$$$ to embrace the glory of the Bheem army and to welcome an era of inclusion in the community.

Note that in the given scheme, no harm is done to the general category, only the representation of inferior castes is increased. Let us join hands and make codeforces a more inclusive community, and help the unfortunate lesser intelligent individuals have a fair share of representation.

Hello freinds, if you are doing codeforces, then you must think how to do progess. So for that you need to read useful codeforces blogs so that you intelligence is get increases.

So without furhter ado, I present to you a list of useful codeforces blogs for beginners. Experienced coders stay away!

• Must do topics for newbies: https://codeforces.net/blog/entry/92248

• Binary Search use cases for beginners: https://codeforces.net/blog/entry/114253

• Ultimate data structure guide to solve any problem: https://codeforces.net/blog/entry/53168

• Seeking motivation during tough times?: https://codeforces.net/blog/entry/107368

• Optimized approach for a well known problem: https://codeforces.net/blog/entry/106189

• Linear Time FFT (pupils and above only please): https://codeforces.net/blog/entry/112849

Hello friends. The year 2023 is midway and so I have prepared the top log2(10) optimizations of 2023 for your viewing pleasure. Without forthor ado, let us begin.

OPTIMIZATION OF DIJKSTRA ALGORITHM TO RUN IN Θ(E + V) FOR HAMILTONIAN GRAPHS: In the relaxation condition of djikstra algorithm, we will binary search for the nearest node with distance greater than current distance in the hamiltonian graph and so we will reduce time complexity by factor of log V (becoz of binary search) so TC becomes : O((E / logV) * log V + V) = Θ(E + V)

KOSARAJU OPTIMIZATION TO WORK FOR CYCLIC GRAPHS: we can use the property of binary search to quickly decompose cycles into directed edges then we will use our little mfriemd binary search on the dfs stack to find the topological order.

OPTIMIZATION OF SPARSE TABLE TO ANSWER RANGE MAXIMUM FREQUENCY QUERIES IN Ω(log N): we will simple use binary search for reducing time complexity from O(N) to Ω(log N)

OPTIMIZATION OF CONVOLUTION ON NESTED INTERVALS TO RUN IN O(log(r + l) * 3.77742307 ^ (r — l + 1)): now you may be thinking how is this possible. I say there is something called binary search. so we will use him.

HONORABLE MENTION:

OPTIMIZATION OF BITSET USING BINARY SEAARCH: needless to say we can optimize bitset using nested binary searches to reduce complexity by log N on every nested binary search, as nest limit tends to inifniity, this allows us to solve all problems in Ω(1) in the limit n -> infinity

thank you for your attention mriemds,

With respect. mainucodingbadipasandae

Literature: https://arxiv.org/pdf/0909.4437.pdf http://www.amazon.com/Optimizing-energy-consumption-wireless-networks/dp/3659121207 http://www.superknjizara.hr/index.php?page=autor&idautor=13819 http://www.jucs.org/jucs_23_3/generating_politician_profiles_based http://authors.elsevier.com/a/1SQGc5aecSN1Bg https://arxiv.org/pdf/1705.07279.pdf https://codeforces.net/blog/entry/53168

Hey guyz, 👋

Me wanna tawk 'bout ChatGPT and how he gonna CRASH competitive programin scene! 😂😂😂

Ya'll seen how smrt this AI is? 🤓 He can make txt like no one else and he keep learnin' more evryday. 🧠💡 Bet he gonna solve all problms in secnd and make us look like fool. 🤯🤯🤯

Me skared, guys. 😱 Wat if ChatGPT becum coding god and tak over all competitions? We be left with only tears and bad codin skils. 😭😭😭

But maybe me overthinkin'. 🤔 Maybe ChatGPT be chill dude and let us have some fun too. 🤣 Or maybe he just roast us in responce. 😡 Who know? 😂😂😂

Eithr way, me pumped to see wat ChatGPT bring to the table. 👀 Lets get ready for rise of the AI overlords! 🤓🤓🤓

-195959656: Passes

-195731060: TLE on 27

What happens when this happens in an actual contest though. Is the solution judged multiple times, before the final verdict, or you just say you had a bad day?

I remember the second code passing the system tests before the hacking phase. The complexity is same as the intended one

Hell guys, today I gonna teach you to do linear time FFT.

Below is the problem:

Q) Given array of n integers, do First Four Traversal on array.

eg. array is [1, 2, 3, 4, 5, 6, 2, 1], then FFT of array is [1, 2, 3, 4].

So in first, it look very dangerous problem, but on meticulous scrutiny of the underlying scheme, we find easy solution.

• So to solve, we iterate over the array from left to right. While left to right is happening, store first 5 elements of array in an array x[5] = [1, 2, 3, 4, 5].

For those thinking why 5, there is actually a very high IQ reason behind it. So maybe not everyone get it, so I not telling it in this blog.

• Now what we are gonna doing is, we are find the circular-convolution of the array with itself, xc = x[0:5] ⋆ x[0:5]. This is the very easy technique, so I hope all will be able to find auto-circular convolution.

For up example, xc[5] = [45, 50, 50, 45, 355].

• Now we will using the easy technique: Discrete Fourier Transform (DFT) to calculate X(5) of xc[5]. This step is easy so I am skip

• Next we can find the square root of X(5) and take the inverse DFT of the sequence i[5].

• Then we can simply print the first 4 element of i[5].

For those thinking why 4, there is actually a very high IQ reason behind it. So maybe not everyone get it, so I not telling it in this blog.

Prove of algorithm: Got same output. Hence proofed.

Time complexity analysis: Linear

Pardon my choice for variable naming (I was projecting), but I fail to understand why the same code gives me WA with G++20 but AC with G++17

G++20: https://codeforces.net/contest/1768/submission/188128207 G++ 17: https://codeforces.net/contest/1768/submission/188129998

Further, on debugging with G++20 for the case:

1
2
2 2

I found that mysteriously, a[0] becomes equal to 1 after the following for loop from the code is executed:

        for(int i = 1; i <= n; i ++) {
           if(cnt[i] > 2) {
                pos = 0;
                break;
            }
            if(cnt[i] == 2) {
                if(no_bitches.empty() || *no_bitches.begin() > i) {
                    pos = 0;
                    break;
                }
                dual[i] = *no_bitches.begin();
                no_bitches.erase(no_bitches.begin());
            }
        }

You can try it on custom invocation too. I don't change the input array a after taking in input, so I don't know how that happens... Can anyone explain?

I was solving CSES — Towers and came with an alternate problem which I think can be solved using DP somehow:

You are given n cubes in a certain order, and your task is to build towers using them. Whenever two cubes are one on top of the other, the upper cube must be smaller than the lower cube.

You must process the cubes in the given order. You can always either place the cube on top of an existing tower, begin a new tower or discard the current cube. You may discard at most K cubes. What is the minimum possible number of towers?

Constraints:

(Don't worry about the constraints, if you can think of any polynomial-time solution, please let me know)

1 <= N <= 1e5,

1 <= cube sizes <= 1e9

0 <= K <= N

eg. N = 4; cubes = [3, 8, 2, 1]; K = 1

Output: 1

==> Discard cube with size 3 or 8 and use the rest to build 1 tower

Any ideas to solve this efficiently?

Hello freinds, I recently got a very good intranship that payed very good. I also have got 900+ rating on codeforce after 5 months of rigorous practice. I hope that when i continue in this speed i become pupil by 2024.

Do you want to know how i accomplish all this?

It is due to the motivation quotes i created when i am depress. Now all of you can grind hard and become 900+ rating in just 5 months (wow).

- 1) Sometimes I wonder which would be worse: To Live As A cheater, Or To Die As A newbie? -

Did you got the deepness of the quote? Let me know in the cement section.

- 2) We live in a society where intrigued newbies are obliged to learn binary search while pupils learn FFT. -

Do you understood this one? It is quite deep actually.

- 3) The rating you own, ends up owning you. -

All of the quotes are 100% original and built by me (promise). Which was the bestest quote you think? Let me know.

Can we hit 100K likes within the next 2 days for part 2.

In next blog I teach you how to get high paying job.

Hello friends, after the recent success of my blog — Very Funny Jokes, CEO of codeforce take my blog and save it in his laptop so you cant see it. I has recive many request to make second part. I am overwelm by the request so I say ok lets make part 2. Make sure to hit the upvote button before starting the blog.

Joke Number 0 ( ;) Programmer reference (0 indexing (hit like if you get it (comment if do not got it)))):

Nobody:

Literally nobody:

Le Me in the exam paper, after writing 4 word be like:

Memory Limit Exceeded XD

Joke Numer 1:

What scare people:

0) Kid: Ghost

1) Teen: The eternal uncertainty in life, and the contrition that follows, believing things could have been different if you tried harder.

2) Men: Wife

3) Ultra Legend: Running on test case 237 (lmao)

Hit upvote if you also face this.

joke Number 2)

Le Teacher: Ok class, today we are going to execute our code.

Kid named "our code": My time has come.

(Did you understood it? Let know in the cument section down.)

Sorry guys, no joke on womans (teacup emoji) this time because last time I make joke on woman (teacup emoji) on part 1, CEO become angry. :(

How many jokes did you got? Let me know!

Hit like or commit 2 hate crimes for part 3 :)

Hello guys I was only able to solve 1 problem in prevous Div4 contest. Can you belive that :(

That too take a lot of time :'-(

Please send help. How to solve more problem

Recently I have been seeing a lot of misogynistic posts regarding CP and just programming in general. People are targeting women just because they have special programs in companies to improve women representation in software development industry. These people also claim that women cheat in CP contests and online assessments.

To those people, I want to ask you something,

Do you feel the same way when there is a seat reserved for the specially abled?

Do you feel the same way when you see people winning medals in paralympics?

People say stuff like "Oh okay, you need women representation, increase women representation in bricklaying or sanitation too, why just the cushy, modern, high-paying office jobs". Oh the misogyny! You only want females to take the low paying jobs that nobody likes to do, just to satisfy your male ego.

These people ask why are there 10x more male garbagemen than female garbagemen. XD Bozo, why do you think it's called garbage"men".

Stop complaining about these things. Let use end this misogyny!

Hello frends, in this blog I teach you how to find k_th element in an array of size n. This blog is going be very advanced so please if you are new to progrmaming stay away.

eg. arr = {1, 3, 2, 9, 5, 6, 11} and k = 2 then programs must return 3

Approach:

Define dp(i, j, k) = number of inversions in the array formed by concatenating prefix arr[0 .. i] and arr[j .. n-1] such that the smaller number in the inversion pair is >= k (0 <= i < j < n)

The transitions is trivial, so I am skipping those.

then the answer can be found by returning the value of arr[k — 1]

So, many of you must be confused as to what to ask at the end of your Amazon interview.

Fear not! I have found a curated list of questions that you can ask: