pllk's blog

CSES Problem Set new year 2021 update: 100 new problems
By pllk, history, 4 months ago, In English

Today we have released a new version of the CSES Problem Set:

https://cses.fi/problemset/

CSES Problem Set is a collection of algorithmic programming problems that can be used to practice competitive programming. We have now added 100 new problems, and the total number of problems is 300. There are both easy and difficult new problems, and some of them cover advanced topics, such as treaps, suffix structures, and FFT.

In 2020, there were more than one million submissions to CSES, which is a new record. Thank you for your submissions and new test cases through hacking!

Our ultimate goal is to create a problem set of 1000 problems, so you can expect many new problems also in the future. If you have ideas on how to improve the problem set, you can discuss them here.

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

Comments Comments (61)
»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Thank you for the problems

→ Reply
»
4 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Great. Make it like one stop Platform where any beginner can blindly follow.

→ Reply
»
4 months ago, # |
  Vote: I like it +140 Vote: I do not like it

Sample explanations please.

→ Reply
»
4 months ago, # |
  Vote: I like it -60 Vote: I do not like it

Please add tutorial option in the problem statement page if possible.

→ Reply
»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

https://cses.fi/problemset/task/2413/ Counting Towers

I am missing a proper defintion on how to count distinct towers. Is a rotation or a reflection another tower?

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thanks, now the problem statement should be easier to understand.

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

yanire Yoav Noam13 almogwald inbarin Back to the grind?

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks a lot !

→ Reply
»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Why does trying to hack Digit Queries give internal error?

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks, now it should be fixed

    → Reply
»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

How to sort problems by difficulty level?

→ Reply
»
3 months ago, # |
← Rev. 3   Vote: I like it +72 Vote: I do not like it

For anyone else, like me, curious for a list of just the new 100 problems to look through:

by category
→ Reply
»
3 months ago, # |
  Vote: I like it -27 Vote: I do not like it

Thanks for this but i have a suggestion :

Do not increase numbers , but focus on quality . Create a problemset which cover all possible topics of Competitive Programming with minimum number of problems. Else there will be no difference a online judge and this set . You can add other practice problem to a different section .

→ Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice good sir.

→ Reply
»
3 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Thanks for doing this, I really appreciate your book and the problemset!

Couple of questions:

  1. Is there any way to hide problem "tags" like DP, Graphs, etc? The only thing that stopped me from solving CSES is that you know if the problem will be DP or Graphs or Math in advance, thus making it less interesting.

  2. Why 1000 problems? It feels great to solve everything, and this will be hard to do with 1000 problems, just from the time standpoint. 200 was perfect for this, 300 is not bad. I think it's possible to cover most essential topics/techniques, and still keep the problemset size small.

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it +25 Vote: I do not like it
    1. To make it more interesting, solve only Additional Problems. All others are just "implement classical algorithm". So even if you hide topics, they become obvious when you read problems.
    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    If you've started at the right time, after each expansion you only have to solve a 100 new problems :P

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    1. The idea is that the "tutorial" problems are divided into sections and then there are more difficult problems in the last section without hints.

    2. With 300 problems the problem set is already quite comprehensive, but there are still many good educational problems that are missing. I agree with your point that it may take really long to solve them all in the future.

    → Reply
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see hardly any solution is available on the internet which is quite understandable...is it not possible to add hints in some beginner questions. Cause many beginners like me leave the question if not able to solve..So provide some hints section in beginners level questions.

      → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please add some decent questions of constructive algorithms to practice

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, Constructive Algorithms are the most widely asked topic in these days contests.

    Add some good level Problems on Constructive Algorithms !!

    → Reply
»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

best problemset for beginners and intermediates. thankyou!

→ Reply
»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I think it would be great if there are discuss section like leetcode.

Some problems are quite hard for beginners like me to figure out the solution all by myself.

→ Reply
»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

You are doing a great Job. Thank you!

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The problems are really good. One suggestion: why not change the time limit for non-Cpp programs? I try submitting the solution in Java and it TLEs. Just converting it to cpp gets accepted.

→ Reply
»
3 months ago, # |
  Vote: I like it +105 Vote: I do not like it

I always dreamt of being 1st on the CSES leaderboard, but I never imagined being 2nd simultaneously!

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    "There are only two hard things in computer science: cache invalidation and naming things."

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

orz pllk

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice initiative.....

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Firstly, thank you for the helpful initiative!

I had a small clarification in this regard. The original post mentions the addition of problems based on some advanced concepts like treaps, suffix structures, and FFT. I just wanted to enquire as to if the book contains an explanation for these topics as well.

If not, can this please be done ?

Once again, thank you!

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    At the moment no, someday it will contain. Before that there are other sources that can be used to learn the topics.

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Official editorials of the problems may be a good idea.

→ Reply
»
3 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Our ultimate goal is to create a problem set of 1000 problems

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for the amazing problem set!

I think it is the best website for someone who want to learn some new algorithm

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please add the sample explanations for the sample test case? I am finding some problems a little difficult to understand like Prefix sum queries.

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

Suggestion: add hacking leaderboards or some other way of crediting hackers.

Perhaps add next to a testcase the name of the person who added it? There are a few possibilities.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    People will abuse it. Please take a look at educational round hacks.

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please help me out with the Counting Tilings problem?? I haven't been able to find any recurrence relation.Any hint??

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Hint
    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can I ask what does the mask represent? And how do we transition?

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        EDIT: okay this might be wrong, let me get back.

        till then here is a sub optimal way to solve the problem:

        dp[i][mask] = number of ways to fill the cols from ith to mth given that cells of the ith col represented by mask are already filled.

        final answer = dp[1][0] i.e. ways to fill from 1st till mth col given that no cell of 1st col is currently filled.

        when trying to calculate dp[i][mask] try out all possible ways to fill the ith col and recur for i+1th till mth col.

        the way you fill the ith col will decide the mask for the i+1 th col.
        time complexity should be (2^N)*(2^N)*M

        → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          When we transition, how do we ensure a upper half of the tile always match the bottom half of the tile?

          → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The above 2^n * 2^n * M solution will work, but we need to pre-filter the valid mask combination, otherwise we will get a TLE.

          I see some people using 3d DP, anyone can explain that approach?

          → Reply
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
          ← Rev. 5   Vote: I like it 0 Vote: I do not like it
          Spoiler
          → Reply
        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          This solution will work. As if you precalculate the set of valid mask for each mask. There will at most 89 valid mask per normal mask and even less. so that one 2^n factor in the time complexity will be just 89(worst case), which is enough to get accepted.

          → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we expect some sort of editorials and sample explainations for the existing problems in near future ?

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain problem Two Stacks Sorting? I can't understand its statement.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider having two stacks. Then we get numbers from left to right from input. We need to push each number onto one of the stacks.

    Also we need to create a sorted list, by poping elements from the stacks. We can pop at any time, from any stack.

    So, these rules imply that we never push a number onto a stack if there is a smaller number on top of that stack, because else we can never create the sorted list.

    → Reply
»
7 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Hi pllk!

Since there are more problems now please consider adding subcategories. For example in math section you can add: number theory, combinatorics, probability, etc.

→ Reply
»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

https://cses.fi/problemset/task/2137 Can somebody tell me about the solution of this problem? :(((

→ Reply