YouKn0wWho's blog

By YouKn0wWho, 6 months ago, In English

Hi, around 3 years ago I compiled most of the Competitive Programming topics in one place here with relevant resources, templates, and problems. It got great responses, it now has 4000+ upvotes and the blog website has been visited 200k+ times! But it contained links to only 1-2 resources and problems per topic and it didn’t contain basic topics for beginners. Also, there was no way of tracking your progress.

This time I decided to improve it, by a lot. I took this project one month ago and it took me on average 6h-10h per day for the last one month to complete this project (also I was doing a full-time job). I hope it was worth it!

The new version is not just a blog, it is a full-fledged website with multiple features (I have hosted it on one of my existing websites):

topic_list

  • Topics: The website contains around 500 topics and tricks. Not all topics are real topics, some are useful tricks or even a problem that contains a reusable unique idea. Also, I have divided a parent topic into multiple subtopics. For example, under Segment Tree, you will find Normal Segment Tree, Dynamic Segment Tree, Persistent Segment Tree, etc as separate topics. This was needed because you should learn only one thing at a time according to your current level.
  • Difficulty and Importance: Now every topic has been assigned a difficulty level as well as importance/relevance. Like, let’s say you want to learn data structures, and it would be wiser to learn Segment Tree first before learning Splay Tree because of two reasons: Segment Tree problems are more frequent than Splay Tree problems and Segment Trees are easier to learn.
  • Resources: Now there will be more resources than before and ordered by which one you should go through first. I have also cited the original authors for each resource.
  • Templates: More topics now have example codes.
  • Problems: Mainly this part took 90% of my time. Under each topic section, now you will find a good amount of problems. For example, under Centroid Decomposition I have added 30+ problems. I have also assigned difficulty to the problems and tried to order them in a way so that you can go through them one after another in the given order. After collecting problems for all topics, it turned out that I had added a total of 3352 problems!
  • Topic Filtering and Searching: Now you can filter problems by difficulty and importance so that it becomes easier for you to find topics according to your expertise. You can also search a topic by its name to quickly find the topic, for that I have added a decent custom search bar.
  • Progress Tracking: You can mark the topics that you complete and also mark the problems that you solve, then the website will track your progress.
  • Activity Heatmap: I have added two heatmaps: one for topic completions and another for problem solves. If you wanna see your past activities, this might be useful for you.
  • Contributing System: Now you can also suggest resources, templates, and problems under a certain topic all from the website! Once you suggest a contribution, I will review it and add it to the public list.
  • Beginner Friendliness: Last time the topic list was not beginner friendly. But this time I have also added all the beginner stuff in an increasing order of difficulty starting from learning data types, functions, etc. So now even if you don’t know how to code, you can follow the topic list.
  • Leaderboard: A list of the top users based on the number of completed topics and solved problems.

Link to the website: smash me

To know how to follow the topic list visit the guideline page on the website. Also, keep in mind that while this list is a good place for knowing which topics exist and the resources and problems for them, you should not always do topic-wise practice. From time to time, you should solve random problems and do rating-wise practice. And of course please always participate in live contests.

Upcoming Features:

  • Team View: You will be able to create a team and see which topics are covered by your team members, in which topics your team is not strong enough, etc. UPD June 4: Implemented this feature.
  • Dark Mode: If there is enough interest, I can try to add a dark mode in the future.
  • Feel free to suggest more features that you want.

I am pretty sure there are some inconsistencies and bugs in the website and the collected problems. Feel free to let me know about those and I will try to fix them ASAP.

A few last words: I have been doing this CP thing for around 7 years now! I will mostly retire after the next World Finals (hopefully, as we became 3rd in the last Asia West Championship). Like before, all I want to say is, please don't forget to enjoy the journey and have fun while riding the boat. Whatever you do, try to pick something you love and try to be good at that. I hope my little contribution will help you with your incredible journey.

Best wishes, my friend blobheart.

Full text and comments »

  • Vote: I like it
  • +792
  • Vote: I do not like it

By YouKn0wWho, 22 months ago, In English

One thing is for sure. You do make mistakes. I also make miskates and that's what makes us human. But what we can surely do is — to try to minimize the errors that we make throughout our life.

I have compiled some of the mistakes that I made in my early Competitive Programming phase. I also mentioned how to avoid them. Also, in most cases, I will give you a chance to find out what the bug is before I reveal the culprit as I tried to make this blog interactive. The codes that I have used in this blog have been written in C++ as it is the most used language for CP.

So, if you are new to CP, stick with me as you might don't wanna repeat the mistakes that I made when I was a beginner.

Mistake 1

Check out the following code:

Code

The output should be $$$10^{18}$$$. But if you run the code, you will get a different output. Why?

Reason

Mistake 2

Check out the following code:

Code

Try to run this locally. What is the time complexity of this?

Is it $$$O(n)$$$?

Solution

Mistake 3

Check out the following code:

Code

Notice that it is guaranteed that total sum of n is <= 100000. So how many operations will the code take in the worst case?

Solution

Mistake 4

What is happening in the following code?

Code

The output is supposed to be 1 1 1 1 1. But it's not the case actually! It's 16843009 16843009 16843009 16843009 16843009 instead. Why?

Reason

Mistake 5

Don't use endl! If your code needs to print millions of newlines, then using endl turns out to be really slower than using '\n'. Why?

Reason

Mistake 6

Never use pow() function for integer calculations.

Why?

Mistake 7

Run the following code

Code

You might expect the output to be $$$-1$$$. But the output is actually 18446744073709551615! Why?

Reason

Mistake 8

Using cerr might be a good way to debug your code as it doesn't output to the standard output. But leaving the cerr instances in your code while submitting in OJ might be one of the worst ways of getting TLE.

Check this out for more.

Mistake 9

You should always use Fast IO that's for sure. But check out the following code.

Code

You might expect the output to be:

Expected Output

But actually, that might not be the case! For example, locally I am getting the following output:

Actual Output

Basically, the cout outputs and printf outputs seem to be working independently! Why?

Reason

Mistake 10

Look at the following code

Code

The output is not $$$4$$$! Why?

Reason

Mistake 11

Is the following code correct?

Code

If it's not, where is the problem?

Solution

Mistake 12

Consider the following code for calculating the maximum occurrence in an array.

Code

This code seems like it should work fast enough but in fact, for certain inputs, it will get TLE.

Why?

Mistake 13

Let's erase an element from a multiset.

Code

The output is not 1 1 2 2 3 4 5 5. It's actually 1 1 3 4 5 5! Seems like we have erased all occurrences of $$$2$$$.

Why?

Mistake 14

Run the following code:

Code

What will be the size of the map? $$$5$$$?

Check

Mistake 15

Let's compute the sum of natural numbers using set!

Code

The time complexity of this solution is clearly $$$O(n \, \log{n})$$$, right?

Right?

Mistake 16

Check out the following code:

Code

What is the time complexity of this?

Solution

Mistake 17

Let's look at the following simple code.

Code

Can you guess where the bug is?

Bug

Mistake 18

Consider the following code to count unique elements in an array.

Code

What's wrong with this code?

Bug

Mistake 19

Lots of mistakes can happen while doing modular arithmetic.

Example Mistakes
Where are the Bugs?

So while doing modular arithmetic, always make sure that after each operation, all your variables are $$$\ge 0 $$$ and $$$< MOD$$$, and you haven't done any overflow.

Mistake 20

Look at the following code:

Code

It doesn't output $$$3 \cdot 10^{12}$$$.

Why?

Mistake 21

Using sqrt() for integers directly might cause some precision issues and give you wrong results.

One of the best ways to compute square roots is the following:

Solution

You can do similar stuff for cbrt() too.

Mistake 22

Check this out.

Code

What is the time complexity of this solution?

Check

More Mistakes

  • Do not insert or erase from a container (set, vector etc) while traversing it using for (auto val: container) like syntax at the same time. Because for dynamic containers inserting or erasing from it might change the structure of the container. So traversing it parallelly might cause some unexpected behavior.
  • Use setprecision for printing floating point numbers, otherwise, you might get WA for precision issues.
  • Do not use rand() function to generate random numbers. Also, did you know that the maximum value rand() generates is 32767? Check out Don't use rand(): a guide to random number generators in C++ to learn what to use.
  • Create variables only when you need them instead of just declaring int a, b, c, d, e, f, g, h; and 69 other variables at the beginning of your code! This will help you catch unnecessary bugs when you use the same variable in two or more places.
  • Do not use long long everywhere as long long, at times, might be 2 times slower than int. Use long long only when it's necessary.
  • If you want to count the number of set bits in a long long number, then use the __builtin_popcountll function instead of the __builtin_popcount function.
  • In C++, the comparator should return false if its arguments are equal. You might get Runtime Error if you don't do this.
  • Speaking of Runtime Error, the most likely case of getting Runtime Error is not declaring the array sizes with enough large values. Check out the constraint of the problem to make sure of it.
  • long long x = 1 << 40 will still overflow as 1 is int and doing 1 << 40 will produce the result in int, but $$$2^{40}$$$ is way too large to be stored in an int variable. To fix this issue, use 1LL << 40 (basically set the type of 1 to long long first, check here).
  • While comparing two floating point numbers, instead of if (a == b), use if (abs(a - b) < eps) where eps = 1e-9 or something similar to avoid precision issues.
  • If you want to take the ceiling of a / b where a and b are positive integers, then do (a + b - 1) / b, instead of ceil(1.0 * a / b). For floors just use a / b as it will round down to the nearest integer.
  • If you want to take the floor of the log of an integer $$$n > 0$$$ (same as finding the highest set bit of $$$n$$$), use __lg(n). Clean, fast, and simple.
  • Slightly Advanced: While string hashing, do not use $$$2^{64}$$$ as your mod, and always use at least 2 different primes and mods. Check out Anti-hash test.

Non-technical mistakes

  • Instead of the Solve - Code structure, use the Solve - Design - Code approach. Try to design what you will code before jumping to the coding part right away. This will significantly lessen your wrong submission counts and will save lots of time.
  • You might use #define int long long and make your code pass, but you should understand why your solution was not passing in the first place. What I am trying to say is — Learn to control your code.
  • Solve problems out of your comfort zone and do not just stick to easier problems. Learning new things by solving problems is more important than just increasing your solve count without learning anything new. "Stop obsessing over the number of hours spent or problems solved. These numbers don't mean shit because the variance is so high and it is very easy to spend a lot of time and solve a lot of problems without learning anything." — Tähvend Uustalu (-is-this-fft-).
  • Do not skip on the Time and Space Complexity of your solution just because you got AC in the problem. This is really important for a beginner that will help you in the long run.
  • Specially on Codeforces, you might get AC by just guessing the solution. But you should learn to prove the solution if you want your brain to get anything out of the problem.
  • Not reading others' code is a great way to miss out on learning new techniques/ways to solve the same problem. You should always read the solutions of some of the best coders to know the different ways of solving a problem.
  • Do not bother about rating before learning the basics of CP.
  • Use a better coding style as it will be helpful in team contests and while debugging your solution. One example coding style is this.
  • One way to improve your coding practice is to break your solution down into smaller, more manageable pieces. Instead of attempting to write the entire solution at once, focus on writing and debugging one part at a time. This approach can make it easier to identify and fix errors, and can also make the coding process much easier.
  • Maybe you are not as good as you are thinking right now! Maybe your current practice method is not as good as you are assuming! Check out Self-deception: maybe why you're still grey after practicing every day for more.
  • Mistake on facing failures: "For me, failing in contests shows me that I still have much to learn so I try to learn new stuff and that's most of the fun. The rest is seeing practice paying off every once in a while. If everyone could have good performances all the time, nobody would have to practice to get better right?" — Tiago Goncalves(tfg). I agree with Tiago. I think the most fun part is to try to be better. It's not fun being good all the time and also it's not fun being bad all the time. The fun part is the transition from doing bad to doing good, the actual delta. And if you practice efficiently then you will certainly make progress.
  • Surround yourself with like-minded people as this way you will be able to learn a lot more than trying to learn everything alone.
  • Not being self-confident: Self-confidence is the key! If you think you can't do it, then you are already lost! "If you think you are beaten, you are, If you think you dare not, you don’t If you like to win, but you think you can’t, It is almost certain you won’t. If you think you’ll lose, you’re lost. For out in the world we find, Success begins with a fellow’s will— It’s all in the state of mind. If you think you are outclassed, you are, You’ve got to think high to rise, You’ve got to be sure of yourself before You can ever win a prize. Life’s battles don’t always go To the stronger or faster man, But soon or late the man who wins Is the man WHO THINKS HE CAN!” — Napoleon Hill, Think and Grow Rich.
  • Do not skip over anything from the solving part of the problem including understanding the solution, proving the solution, coding the solution efficiently, and time and space complexity of the solution, especially if you are a beginner. Every time you skip over any necessary parts of the solution incurs a debt to the CP god. Sooner or later, that debt is paid.
  • Remember that Getting AC is not the main goal, learning something new by solving the problem is the main goal.

Thanks for reading the blog. Feel free to add more mistakes that are common in CP in the comment section.

See you on a later episode, friend blobheart!

Full text and comments »

  • Vote: I like it
  • +634
  • Vote: I do not like it

By YouKn0wWho, 3 years ago, In English

Hi, I am super excited to be back with another list. This time it is a collection of some useful equations in Competitive Programming.

Motivation

Do you find it bad if you couldn’t solve a problem just because you didn’t know about a certain equation?

Do you find it difficult to take a quick look at an equation that you know exists but forgot about it while solving a problem?

Do you think that all the equations that are important in CP are just cluttered and you are too lazy to collect them in one place?

Well, then you are in the right place! I am here to solve all of the aforementioned problems. I believe you should not waste your precious time searching the internet for important equations. You should solve more problems. I am here to undertake the nasty task of collecting things.

Payment

Everything comes with a cost. You need to do something for me. That is you need to upvote this blog. Pretty easy!

Acknowledgement

Thanks to the following guys as they converted all the equations to Latex: Mahbubul Alam Sabuj(newb_ie), Irfan Ullah Munna (Shanto65), S.M.A Nahian (Nahian9696), Ashiqur Rahman Naeem (nayeem2021), Md. Imran Hossain(peripatetic), Jamilur Rahman(jamil314) and Mahmood (mah_mood).

About the List

I didn't add any explanations for any of the equations because it's not feasible to explain too many equations. So make sure to understand them by yourself or use google or just comment under this blog. The community will help.

The list also contains some small tricks as a bonus. As the list is long, it must have some errors. Feel free to point those out. Also, comment the missing equations that you think should be added to the list.

Enjoy!

Audience

This list is NOT for beginners. This is for people who already came across lots of stuff in Combinatorics, Number Theory, and Math but found it hard to keep track of the equations that you already know of. This list can be used as a reference. If you are a beginner or someone who is not experienced in Combi, NT, or Math, then stay away from this.

The Equation List

Link: blog.shahjalalshohag.com/equation-list/

Outro

A good life is just a series of good days. So make sure to have a good day, friend blobheart.

Full text and comments »

  • Vote: I like it
  • +327
  • Vote: I do not like it

By YouKn0wWho, 3 years ago, In English

Thanks for participating in my contest blobheart. I hope you liked the problems. I would love to hear your feedback in the comments.

If you find anything wrong in the editorial which is more likely to happen because I have written a rather long editorial to make you understand the solutions better, then comment below.

Also, don't forget to upvote to pay for the editorial. See you in my next contest!

Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code (1D1D DP)
Code (D&C DP)
Tutorial is loading...
Code
Tutorial is loading...
Code

Full text and comments »

  • Vote: I like it
  • +517
  • Vote: I do not like it

By YouKn0wWho, 3 years ago, In English

UPD: (28 April, 2022)

Donated Finally

আবার চলে এসেছি! (That's Bengali for "I am back! (in Terminator mode)")

I am super excited to invite you to participate in Codeforces Round 752 (Div. 1) and Codeforces Round 752 (Div. 2) which will be held on Oct/30/2021 17:35 (Moscow time). This round is rated for both divisions.

You will be given $$$6$$$ problems in each division and $$$2$$$ hours to solve them. All the problems are authored and prepared by me.

I would like to thank -

The statements are short and directly ask you what to do and I have tried to make the pretests strong. I highly encourage you to read all the problems.

Solve problems and help the poor! Yes, you heard it right, this time you can help the world by just solving problems. I will donate money based on the solve count of each problem by the following measure:

Donation Per AC

The total estimated money is half of what I will get from Codeforces for this contest(but you can make it more by just solving more problems!). I am a student, so pardon me if that's too little.

Also, did you know that you can still upvote my The Ultimate Topic List blog and make it to the top?

Finally, I would like to dedicate this contest to me! I want to thank me for believing in me, for doing all this hard work, for trying to do more right than wrong. I want to thank me for just being me at all times.

Score distribution:
Div.1: $$$750-1000-1750-2500- 3500-3750$$$.
Div.2: $$$500-1000-1750-2000-2750-3500$$$.

Good Luck! Love you blobheart.

UPD: Editorial

UPD: Congratulations to the winners.

Div.1:

  1. tourist
  2. djq_cpp
  3. Petr
  4. gop2024
  5. ecnerwala

Div.2:

  1. Rolling_Code
  2. Pecans
  3. fangzhijina2020
  4. whtdsjmr
  5. Graphcities

UPD: Here is how the donation amount looks like:

Donation

FYI I will get 400 USD for this contest. So the donation amount is indeed half of this as I have estimated before the contest, although didn't think that it would be this accurate.

I will update you again when I get the money from Codeforces, more likely after a few months as I haven't received my previous contest's payment yet which happened 3 months ago!

Also, thanks for being a part of this. You have just helped someone who is in need (I mean after I distribute the money).

Full text and comments »

  • Vote: I like it
  • +3156
  • Vote: I do not like it

By YouKn0wWho, 3 years ago, In English

This post took $$$4$$$ years to make. And this is the most significant thing that I have ever shared in my whole life.

Story

Hi, I have been doing CP for like $$$4$$$ years and from the very beginning what I have been feeling is a need for a comprehensive topic list that will contain all sorts of topics from easy to advanced with corresponding tutorials, problem lists and templates so that I wouldn't have to look at different sites, from here to there. So what do you do when you think something is missing from the world? Yeah, you create that thing! So here I am, sharing the ultimate topic list that you will need in CP.

When I say that it took me $$$4$$$ years to make it, I genuinely mean it. I have been collecting them from the inception of my CP journey and yesterday I thought that it got its almost complete shape. You may not imagine the sheer excitement hidden under each of the characters of this post.

Payment

You can pay me just by upvoting this blog and by being a better programmer and human being than what you are right now.

About the Topic List

I have added a few tutorials for each topic. You can also find more of them by just using your best companion — Google.

Added few problems for each topic. But you may notice that some of the topics don't have any problem attached. That's because under the attached tutorial section you will find lots of problems with that topic. If you want more problems, then you can do it just by using Google.

I have attached my template for each topic. You may not call it a template because some of them don't support the generalized use of the topic. But you can use them easily if you understand the topic and solve problems using that template.

Lastly, I tried to state the difficulty of each topic by numbers from $$$1$$$ to $$$3$$$ so that people can understand what are the best topics for them. The distribution is as follows:

  • $$$1$$$ — If your rating is $$$1600 - 1899$$$
  • $$$2$$$ — If your rating is $$$1900 - 2399$$$
  • $$$3$$$ — If your rating is $$$2400+$$$

If you are a beginner then just learn basic topics and solve problems.

Topic List

Link: smash me

Upd (May 12, 2024): the current and final version is deployed here: smash me

Contribute

You can comment the topic names that you think are missing right now and I am pretty sure some links are broken, do point those out if you find some.

Additional Comments

I really wanted to post this blog before I die. Seems like I managed to do that. It's funny that I had this constant fear of what if I die before sharing this blog with the world given that the amount of work I have given to create this is monstrous. But now I am so happy that I am alive at this moment.

Conclusion

The whole purpose of this project is to help you with this astounding journey of you trying to be better, trying to achieve the best of what you can imagine. Hope that my efforts won't go in vain. I am waiting to see you at the top of the building that you made by the bricks of your expectations. I am waiting to see you smile and to be happy. Don't forget to enjoy the journey and have fun while riding the boat.

Best wishes, my friend blobheart.

Full text and comments »

  • Vote: I like it
  • +4383
  • Vote: I do not like it

By YouKn0wWho, 3 years ago, In English

Hey everyone, I am sharing my personal code library where I compiled almost all the important templates that you will need in CP (saying almost just for courtesy). Most of the codes are originally written by me and some of them are collected from others but modified in a cleaner way. Link: https://github.com/ShahjalalShohag/code-library

It took me around 4 years to complete the list. Maybe each line is just a line to you but to me it tells a story of the excitements I had while learning those stuffs, the sleepless but fun nights I had to seek knowledge.

Why am I sharing this library?
  • Just so that your learning path becomes a bit smoother.
  • Knowledge hidden inside my head or codes in a private code-library will be useless when I am dead, so it's better to share those among people before I die.

Also, you can make me happy(as in to pay me) just by upvoting this blog and giving a star to the repository.

I believe that my coding style is pretty clean and readable, and furthermore, a few problem links are attached to most of the codes so that you can practice those problems. Best wishes, my friend blobheart.

Full text and comments »

  • Vote: I like it
  • +1334
  • Vote: I do not like it

By YouKn0wWho, 3 years ago, In English

The problem names are based on my favorite characters out there. Yes, 1554E - You are my most favorite character UwU.

I have tried to make the editorials as interactive as possible. Enjoy.

Tutorial is loading...
Code(C++)
Code(Python)
Tutorial is loading...
Code(C++)
Code(Python)
Tutorial is loading...
Code(C++)
Code(Python)
Tutorial is loading...
Code(C++)
Code(Python)

If you are wondering(as you always do 。^‿^。) about the checker:

Checker
Tutorial is loading...
Code(C++)

Full text and comments »

  • Vote: I like it
  • +328
  • Vote: I do not like it

By YouKn0wWho, 3 years ago, In English

কি অবস্থা মামা? (That's Bengali for "What's up dude?")

I am super excited to invite you to participate in Codeforces Round 735 (Div. 2) which will be held on Jul/29/2021 17:35 (Moscow time). This round is rated for future LGM participants whose current rating is $$$\le 2099$$$.

You will be given $$$5$$$ problems and $$$2$$$ hours to solve them. All the problems are authored and prepared by me.

I would like to thank -

The statements are super short and I have tried to make the pretests strong. I encourage you to read all the problems and solve them all.

I would like to dedicate this contest to the fallen king, my father, who died two months ago. May he and all the departed good souls rest in peace.

Scoring distribution: $$$750 - 1250 - 1750 - 2000 - 3000$$$.

Good Luck!

UPD1: Thanks for participating, I hope that you guys loved the problems, and sorry for B being a bit difficult than usual.

UPD2: Editorial

UPD3: Congratulations to the winners.

Div.1 + Div.2:

  1. turmax
  2. Karry5307_AK_NOI2024
  3. SSRS_
  4. Pyqe
  5. X_qaeq

Div.2:

  1. Karry5307_AK_NOI2024
  2. X_qaeq
  3. the_tool_er
  4. DecayingSylow
  5. Rednusa

Also, congratulations to the first solvers:

A: LiM_256, at $$$0$$$ mins!
B: RinShima, at $$$4$$$ mins!
C: xiaofan7, at $$$7$$$ mins!
D: 6945930042DucLA, at $$$7$$$ mins!
E: rainboy, at $$$23$$$ mins!

Full text and comments »

  • Vote: I like it
  • +2167
  • Vote: I do not like it

By YouKn0wWho, 3 years ago, In English

Hi!

We are thrilled to invite you to participate in the Replay of National High School Programming Contest 2021, tomorrow, June $$$14$$$, at 07:30 pm BST. To participate all you have to do is to create an account on Toph. You can register here.

The authors of the contest are upobir, _Ash__, YouKn0wWho, fsshakkhor, rebornplusplus, Shefin_, Hasinur_, jAckAL_1586, mainstring, Moshiur_, ishtupeed, Peregrine_Falcon, TarifEzaz, ihumaunkabir and shajia. Thanks to TarifEzaz for coordinating the round.

You will be given $$$12$$$ problems and $$$5$$$ hours to solve them. The contest will follow standard ICPC rules.

We tried to create very engaging problems, compact statements, and robust datasets for this round. Hopefully, the participants, with a rating of less than $$$2600$$$, will find the problems stimulating and interesting.

Also, there will be an editorial shortly after the round ends.

Good Luck!

UPD: The problems are available for practice here. Editorials are attached to each of the problems separately.

Full text and comments »

  • Vote: I like it
  • +97
  • Vote: I do not like it

By YouKn0wWho, 4 years ago, In English

I was experimenting on the following problem for quite a long time:

You are given two integers $$$n$$$ and $$$k(1 \le k\le n \le 10^5)$$$. You have to find the number of permutations with length $$$n$$$ that can be obtained as a suffix array of at least one integer sequence $$$a_1, a_2, \ldots, a_n$$$ s.t. $$$1\le a_i \le k$$$. Output it modulo $$$998, 244, 353$$$.

Definition of Suffix Array for an integer sequence

I didn't have any clue when I came up with the problem. It's really hard to find any specific properties of a permutation which will ensure that there exists a sequence which will generate the permutation as its suffix array.

So then I wrote a brute force over smaller numbers. And it turned out that there exists an OEIS sequence for this problem! And the solution to our problem is $$$F(n, k) = \sum_{i = 0}^{k}{(-1)^i(k-i)^n {n \choose i}}$$$

But there is a breathtaking twist! Before I describe it, let's look at the Eulerian numbers. What are they? The Eulerian number $$$A(n, k)$$$ is the number of permutations of the numbers from $$$1$$$ to $$$n$$$ in which exactly $$$k$$$ elements are greater than the previous element (permutations with $$$k$$$ "ascents").

It turns out that $$$F(n, k) = \sum_{i = 0}^{k - 1}{A(n, i)}$$$. That means the solution to our problem is exactly equal to the number of permutations with $$$<k$$$ ascents!

The twist here is that when I printed out the permutations in my problem, they are not the permutations with $$$<k$$$ ascents! That means there is a bijection between the permutations with $$$<k$$$ ascents and the permutations that can be obtained as a suffix array of at least one integer sequence $$$a_1, a_2, \ldots, a_n$$$ s.t. $$$1\le a_i \le k$$$.

So my two questions are:

  • How does the bijection exist?
  • Is there any specific property of a permutation which will ensure that there exists a sequence $$$a_1, a_2, \ldots, a_n$$$ s.t. $$$1\le a_i \le k$$$ which will generate the permutation as its suffix array?

Full text and comments »

  • Vote: I like it
  • +132
  • Vote: I do not like it

By YouKn0wWho, 4 years ago, In English

Hi!

I am thrilled to invite you to participate in CodeChef’s October Cook-Off, this Sunday, October $$$18$$$, from 9:30 pm to 12:00 am IST.

Followings are the basic information:

  • Participants in each division will be given $$$6$$$ problems and $$$2.5$$$ hours to solve them.
  • All problems have been cooked by me.
  • Statements are very short unlike this announcement!
  • Problems will have strong samples.
  • There will be an interactive problem in this round, so, you should know how to deal with them.
  • I hope your internet connection is good as some of the problems will feature awesome animations that I have created using Manim! Yeah, it means the problems will have better explanations.
  • In my last contest, only $$$103$$$ div2 participants managed to solve div2C which is not good at all. So this time I have tried to maintain a more balanced difficulty distribution.
  • I would like to thank teja349 for his brilliant coordination of this round.
  • amnesiac_dusk tasted the problems(I hope they taste sweet!). I want to thank him particularly for helping me with the preparation of a few problems.
  • Psychik is in charge of the editorials.
  • Needless to say, Xellos did the statement improvements.
  • Video Editorialists: Chirayu, agarwal19,darshancool25, manijuana, divesh2201
  • Translators: Mediocrity [Russian], Team VNOI [Vietnamese], solaimanope [Bengali], devils_code [Hindi], qingczha [Mandarin]

Prizes: The top $$$10$$$ Indian and top $$$10$$$ Global participants will receive CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Good luck!

Full text and comments »

  • Vote: I like it
  • +140
  • Vote: I do not like it

By YouKn0wWho, history, 4 years ago, In English

Greetings good people of Codeforces. I hope you're having a great week.

I invite you to participate in CodeChef’s July Cook-Off, this Sunday, 19th July, from 9:30 pm to 12:00 am IST.

Participants in each division will be given $$$6$$$ problems and $$$2.5$$$ hours to solve them.

We will also be hosting a live problem discussion sessions for Cook-Off problems with our panellist Rajarshi RestingRajarshi Basu on 20th July, 6 pm IST. You can register by clicking on the GOING button on the top right corner here. Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Joining us on the problem setting panel are:

  • Setters: Shahjalal YouKn0wWho Shohag, Rahul amnesiac_dusk Dugar

  • Admin: Teja teja349 Vardhan Reddy

  • Tester: Ildar 300iq Gainullin

  • Editorialist: Rajarshi RestingRajarshi Basu

  • Post-Contest Streaming: Rajarshi RestingRajarshi Basu

  • Statement Verifier: Jakub Xellos Safin

  • Mandarin Translator: Qingchuan Zhang

  • Vietnamese Translator: Team VNOI

  • Russian Translator: Fedor Mediocrity Korobeinikov

  • Bengali Translator: Mohammad solaimanope Solaiman

  • Hindi Translator: Akash Shrivastava

Prizes: Top $$$10$$$ Indian and top $$$10$$$ Global participants will receive CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.

Good Luck! See you on the leaderboard!

Full text and comments »

  • Vote: I like it
  • +140
  • Vote: I do not like it

By YouKn0wWho, 5 years ago, In English

So this problem just popped out of my head:

You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$$$$(1 \leq n \leq 10^5, -10^9 \leq a_i, b_i \leq 10^9)$$$. Find an array $$$c$$$ of size $$$n$$$ such that

$$$c_k = \max\limits_{i + j = k}(a_i + b_j)$$$

It looks like a classical problem but I couldn't able to find a working solution. Can anyone help?

Full text and comments »

  • Vote: I like it
  • +51
  • Vote: I do not like it

By YouKn0wWho, 5 years ago, In English

You are given an array $$$A$$$ of length $$$n$$$. Consider all $$$\frac{n * (n + 1)}{2}$$$ subarray sums of the array. Find out if all of them are distinct or not. Print "YES" or "NO".

Constraints: $$$ 1 \leq n \leq 10^5, \; 1 \leq A_i \leq 10^5$$$

Is it possible to solve this? How?

Full text and comments »

  • Vote: I like it
  • +68
  • Vote: I do not like it

By YouKn0wWho, 5 years ago, In English

I have three versions of this problem

Version 1
Version 2
Version 3

Full text and comments »

  • Vote: I like it
  • +96
  • Vote: I do not like it

By YouKn0wWho, 5 years ago, In English

Find the number of ways to select $$$k$$$ non-intersecting edges from a linear graph with $$$n$$$ nodes. In a linear graph every $$$i$$$ and $$$(i - 1)$$$ is connected by an undirected edge for each $$$i$$$ from $$$2$$$ to $$$n$$$.

Two edges intersect if they share some node. Two ways are different if there is some edge which is selected in one way but in the other.

Constraints: $$$1 \leq k < n \leq 10^5$$$

Full text and comments »

  • Vote: I like it
  • +22
  • Vote: I do not like it

By YouKn0wWho, 5 years ago, In English

Let's say we have to find the number of ways to partition a string into palindromic substrings of even length. We can solve this problem in $$$O(n log n)$$$ using Palindromic tree where we have to use an extended version of the palindromic tree consisting of series links. You can solve this beautiful problem using this idea.

But then I found out that if the question would have asked for the number of ways to partition a string into palindromic substrings of length $$$l$$$ such that $$$l \bmod p <= r$$$, then I couldn't solve it.

So here I am, asking you, is there any kind of generalized solution for this kind of problem? Maybe we can solve this problem for some small $$$p$$$?

Full text and comments »

  • Vote: I like it
  • +12
  • Vote: I do not like it

By YouKn0wWho, 5 years ago, In English

A. Perfect Points

Author: YouKn0wWho

Tutorial
Solution

B. String is not that Easy

Author: YouKn0wWho

Tutorial
Solution

C. XOR Partition

Author: YouKn0wWho

Tutorial
Solution

D. Permutations and Divisors

Author: YouKn0wWho

Tutorial
Solution

E. Playing On A Directed Graph

Author: YouKn0wWho

Tutorial
Solution

F. Ant-Man And The Polygon

Author: YouKn0wWho

Tutorial
Solution

G. Enormous Product

Author: YouKn0wWho

Tutorial
Solution

H. Subset AND

Author: YouKn0wWho

Tutorial
Solution

I. Distinct Permutations

Author: foyaz05

Tutorial
Solution

J. The Selection

Author: YouKn0wWho

Tutorial
Solution

K. Mr Makor And His Friends

Author: ovis96

Tutorial
Solution

L. Expected Oddness

Author: mk_Shahriar

Tutorial
Solution

Full text and comments »

  • Vote: I like it
  • +36
  • Vote: I do not like it

By YouKn0wWho, 5 years ago, In English

Greetings good people of Codeforces. I hope you're having a great week.

We are hosting a contest based on the problems of SUST Intra University Programming Contest 2019. The contest platform is Toph. It was originally hosted on SUST's online judge SourceCode.

The contest will be held on Friday, December 20, 2019 at 15:00 UTC+06.

You will be given 12 problems in total and 5 hours to solve them. The contest will follow standard ICPC rules.

The problem setters of the contest are ovis96, YouKn0wWho, foyaz05, avivilla, FrozenBlood, mk_Shahriar and Jubair_2147483647.

To participate all you have to do is to create an account on Toph. You can register here. The contest link is here: smash me.

We tried to create very engaging problems, compact statements and robust datasets for this round. We hope that EVERYONE will find the problems stimulating and interesting. You can also participate as a team.

Note to anyone who participated in the onsite contest, please refrain from sharing or discussing the problems here before the contest.

Also, there will be an interactive problem. If you don't know about interactive problems, please refer to this article.

Good Luck! See you on the leaderboard!

UPD: BUMP! 1 hour to go, buckle up!

UPD: Editorials

Full text and comments »

  • Vote: I like it
  • +64
  • Vote: I do not like it

By YouKn0wWho, 5 years ago, In English

Problem Link

Statement: Problem F. You can submit solution here.

Brief statement

We have an Arithmetic Progression $$$P$$$ where the first element is $$$A$$$ and the difference between the consecutive terms is $$$B$$$. So the $$$i^{th}$$$ element of $$$P$$$ is $$$P_i=A+i*B$$$.

Again we have an array $$$a$$$ of $$$K$$$ integers. We say that a number $$$S$$$ can be expressed by the array elements if there is a solution of the following equation

$$$\sum_{i=1}^{K}{x_i*a_i}=S$$$

Note that all $$$x_i$$$ must need to be non-negative.

We also have $$$Q$$$ queries of type $$$(L,R)$$$. For each query we need to find how many numbers $$$P_i$$$ ($$$L \leq i \leq R$$$) can be expressed using the elements of the array.

Constraints

  • $$$1 \leq K,Q \leq5 0$$$

  • $$$1 \leq a_i \leq 10^5$$$

  • $$$0 \leq A,B \leq 10^{15}$$$

  • $$$1 \leq L \leq R \leq 10^{15}$$$

  • $$$0 \leq P_R \leq 10^{15}$$$

My idea

This is actually a Congruence Shortest Path Problem. Using this idea we can express the numbers that can be expressed using the array elements as some Arithmetic Progressions. So now we have to find the intersection between two arithmetic progressions and we can find it using CRT.

Let $$$M=\min_{i=1}^{K}{a_i}$$$. Using the above idea I can solve the problem in $$$O(K^2*M+Q*M*log(10^{15}))$$$. But I am consistently getting TLE as the problem has $$$10$$$ test cases.

So here I am asking you to help me by offering a better idea that I can't refuse.

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it

By YouKn0wWho, 5 years ago, In English

These are the problems that I found while solving some other problems and some of them popped out of my head and guess what! Again I couldn't come up with a solution. So here I am, asking for your help. I heard you like solving new problems.

Problem 1
Problem 2
Problem 3

Full text and comments »

  • Vote: I like it
  • +16
  • Vote: I do not like it

By YouKn0wWho, 5 years ago, In English

Let's say we have a polynomial $$$P(x)$$$ in the field modulo $$$(10^9+7)$$$

$$$P(x)=\prod_{i=0}^{n}{(a_i*x^i+b_i)}$$$

For $$$n=10^5$$$ obviously we can't generate the whole polynomial explicitly. But I think maybe we can solve the following problems

  • Find the coefficient of $$$x^k$$$ in $$$P(x)$$$
  • Find the polynomial $$$P(x)\%x^k$$$

I don't how to solve them efficiently. That's why I am asking you guys. How efficiently can you solve the problems for some $$$k$$$?

Full text and comments »

  • Vote: I like it
  • +49
  • Vote: I do not like it

By YouKn0wWho, 5 years ago, In English

There's a string $$$S$$$ of length $$$N$$$ containing $$$1s$$$ and $$$0s$$$ only, you don't know the string but you know $$$N (N<=1000)$$$. You can ask at most $$$1024$$$ questions: is $$$P$$$ a substring of $$$S$$$? $$$P$$$ can be of any length. Then you have to know the string $$$S$$$.

This comment claims that this problem has a deterministic solution as well as a nice randomization solution. But I am thinking of the solution for a pretty long time and nothing popped out of my tiny brain. Can you help me?

Note: I am interested in the randomized solution more. But any solution will quench my thirst!

Full text and comments »

  • Vote: I like it
  • +27
  • Vote: I do not like it

By YouKn0wWho, 5 years ago, In English

I am stuck on this following problem for a pretty long time.

statement
input
output
sample
time limit

It will be really helpful if you can provide me with a solution.

Full text and comments »

  • Vote: I like it
  • +36
  • Vote: I do not like it