Блог пользователя pllk

Автор pllk, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +736
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Thank you for the problems

»
3 года назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +140 Проголосовать: не нравится

Sample explanations please.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +74 Проголосовать: не нравится

    Yes, we are working on it

    • »
      »
      »
      13 месяцев назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      I copied the content of "Nested Ranges count" to chatGPT. Something like this may be automated for all problems.

      It gave this nice explanation:

      The input contains 4 ranges: [1,6], [2,4], [4,8], and [3,6].

      The first line of the output gives the number of ranges that each range contains, in the order they were given in the input. Range 1 contains ranges 2 and 4, and no other ranges. Range 2 is contained in range 1, and no other ranges. Range 3 is contained in no other ranges. Range 4 contains range 3, and no other ranges. Therefore, the first line of the output is "2 0 0 0".

      The second line of the output gives the number of ranges that contain each range, in the order they were given in the input. Range 1 is contained by no other ranges. Range 2 is contained by range 1, and no other ranges. Range 3 is contained by range 4, and no other ranges. Range 4 is contained by no other ranges. Therefore, the second line of the output is "0 1 0 1".

»
3 года назад, # |
  Проголосовать: нравится -60 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

yanire Yoav Noam13 almogwald inbarin Back to the grind?

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Why does trying to hack Digit Queries give internal error?

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

How to sort problems by difficulty level?

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +72 Проголосовать: не нравится

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

by category
»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Nice good sir.

»
3 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится
    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.
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +31 Проголосовать: не нравится
    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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

please add some decent questions of constructive algorithms to practice

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

best problemset for beginners and intermediates. thankyou!

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

You are doing a great Job. Thank you!

»
3 года назад, # |
  Проголосовать: нравится +105 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +33 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

orz pllk

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Official editorials of the problems may be a good idea.

»
3 года назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank you for the amazing problem set!

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -14 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Hint
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится

          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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

I think it would be lot more helpful if you guys will consider different time limits for different languages like it is in codechef and codeforce. Example — My linkedlist java solution for Josephus problem 1(https://cses.fi/problemset/task/2162) give tle while the same algo in cpp got accepted.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    I don't think CF has different time limits for different languages.

    And, at least IMO, language multipliers are a terrible idea, as described here.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится

      I dont know much about cf but it is in cc. And bro sometime in cses my o(n) solution doesn't get ac, but the same logic in cpp works really fine. Though java is pretty fast then also this happens.

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Why do I need to log in to see statistics? https://cses.fi/problemset/stats/

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -25 Проголосовать: не нравится

    it is what it is.. accept it or stop using cses

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I have stopped. If needed I will just look at the problems and check whether I know the idea for solving it or not. Because I don't want to brainwash myslef because of TLE(which is not my fault)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    We have had some problems with bots, so we have had to restrict some pages at the moment (for example, bots that fetch statistics too often).

»
23 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi pllk
https://cses.fi/problemset/task/1194 Monsters

I spent some time trying to cover the following test case, because I erroneously interpreted the statement of the problem.

Test Case

Of course this is all my fault, because I misunderstood the problem statement, but in case there are more people like me, maybe it's worth stressing the fact that A must choose its entire path before making its first step.

Thanks for the website btw, it's a great resource!

  • »
    »
    23 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    The problem states "Your plan has to work in any situation; even if the monsters know your path beforehand". I think that's clear enough.

    • »
      »
      »
      23 месяца назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Of course you're right.

      My problem was that I misinterpreted the word plan. A's plan is to walk down and then either dash left or right depending on where M happens to be. And M can't do anything against this plan.
      But of course A must plan its entire path beforehand.

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

New tests have been added to both Fixed-Length Paths I & II hacking most solutions.

Are there any plans on 'hacked' notifications?

»
8 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

CSES problemset is just perfect, no tags, no editorials. It simply leaves us all by ourselves to find the solution which is what CP is all about. I can’t thank you enough.

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

when is it useful to do CSES problems? If I am rated 1150 is it useful to do CSES problems? Which sections?

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

nice

»
2 месяца назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Can anyone explain what the point of the question "Grundy's game" is?

As far as I know there is no legitimate solution that runs in the time limit--you either need to guess the answer and/or write a full solution locally.

Why not just lower the bounds of the problem--CSES is supposed to be educational.