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

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

I'm glad to announce that we have today released a new version of the CSES Problem Set. It has many new problems and a new feature: hacking. You can access the problems here:

https://cses.fi/problemset/

New problems

The problem set has now 200 problems — compared to the original problem set, there are over 100 new problems.

The problems are now divided into sections according to their topics, so it is easier to practice a specific technique. The last section contains more difficult problems that require creative problem solving skills.

Hacking

There is a new feature: you can now hack submissions and improve the quality of tests.

After solving a problem, you can view the solutions by other users and try to hack them by giving a test case where the solution fails. If your hack is successful, the new test case will be added to the test data and all submissions will be regraded.

Future plans

In the future, we will add many more problems, and our goal is to create a comprehensive problem set that has 1000 high quality problems. We will also gradually add model solutions that describe different ways on how to approach the problems.

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

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

There still seems to be some inconsistency between my profile and the leaderboard. The former shows 51/200 solved tasks, while the leaderboard only shows 50/200. Can you please look into this?

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

    Thank you for reporting this, this should be fixed now.

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

      I believe the error was caused due to the deletion of the Longest Border problem, but out of curiosity, is there any way that we can see problem statements that were archived, such as the aforementioned one?

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

        You are right, this problem was replaced by Finding Borders which is a more general better problem. Sometimes such replacements are needed to improve the quality of the problem set.

        At the moment there is no way to see archived problem statements or submissions, but it would indeed be interesting to see them, and this may become possible in the future.

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

Don't you hacking can be misused to make website judging too slow by adding lots of test data. I feel some limit like 500 or 1000 should be put on maxtests as per the capability of website.

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

    I believe the hacking will work nicely. However, we will monitor the situation and add restrictions if something unexpected happens.

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

Are you also planning to upgrade to the C++17 version? I feel it is a nice feature that is lacking currently.

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

While I appreciate the effort, I don't like the fact that there are so many platforms and a lot of problems are repeated. It means a lot of time was wasted.

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

    Well, there are also many books about programming, many songs about love, etc. :)

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

      Books teach in a bit different way. Many problems are exactly the same. A lot of setters spend time preparing the same thing including tests.

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

        Let's assume that I'm planning to use 1,000 hours to further improve the CSES Problem Set. If this time will be wasted, what should I do instead of that?

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

          I don't like the idea of creating more problem sets, that's all. My suggestion then would be: spend 1000 hours to put links to some problems in your book. Can be from CF.

          That being said, doing anything for the community is great.

          EDIT: I have a better idea. It would be even better to create editorials for existing problems instead of adding new ones. Then it's at least a good place to practice.

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

            Creating editorials is definitely a good idea, but I think it is more important to first add some more problems.

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

        Why he should find problems from some obscure sites, instead of just making it?

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

          Because it saves time. How is cses.fi less obscure than CF? I actually don't want to create accounts in 20 platforms.

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

            I'm not sure if it would actually save time. It may be very difficult or impossible to find a specific problem from some other site.

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

            Finding or remembering things out of OJs may be harder than you think. If it was easy, BOJ 1659 wouldn’t appear in IOI :p

            And I completely understand that pllk wants to control test quality and user experience.

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

              He wants to do it and so do tens of other platforms.

              There should be one system with thousands of problems. You could choose any subset of problems and recommend it to your students. A good start would be if everybody switched to making problems in Polygon.

              Test quality? I'm almost sure every platform would allow him to improve the test data. I don't get the point about user experience. I don't think that everybody should create their own platform because they can control user experience better.

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

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

                  Exactly. That's why I don't like new platforms. And note that I don't propose starting a new one. But everybody should use Polygon because it's superior to anything else.

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

                  It's possible that he used Polygon to create problems but then upload to CSES =).

                  Anw there are cases where you may want to have full control of the problems by adding to your own OJ, e.g. univ courses where you don't want students to copy-paste code from other students; or you want to use your own plagiarism checker.

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

      many books about programming, many songs about love, etc

      Are you serious?

      That many songs are about love, but their lyrics are not the same. That many songs about love don't sound the same.

      Programming is quite wide thing. That many books are about programming, but not all books cover the very same topics. Also different authors describe that topics in different ways. Their books are not the same. A reader finds some books more clear, other books less clear.

      But setting the EXACT SAME problem in different platforms has no use.

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

        I wouldn't focus too much on individual problems. A single problem is nothing special, but a problem set can be a work of art.

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

          What are you talking about?

          Errichto told his point of view. You answered him with your arguments about many books about programming, many songs about love, etc. I showed your arguments are poor. I didn't interfere directly in your dispute with Errichto.
          You wouldn't focus too much on individual problems than don't focus! Did I tell anything against it?

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

          Please Java time limit? It's not an individual problem. Do something.

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

        I see my comment is misunderstood, so I'll tell again. pllk, thank you for your problemset, I told nothing against it, I just told that many books about programming and many songs about love have nothing to do with repeated problems and comparing them makes little sense.

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

But is it rated? Don't downvote please, it's my birthday tomorrow

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

Would it be possible to add support for PyPy? I generally enjoy solving tasks in python, especially codegolfing with it, but with the 1 s TL it is many times really hard / impossible to get cpython to pass.

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

    We discussed this with our team and consider adding PyPy support, more information will follow.

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

    PyPy is now available in CSES. You can select the interpreter (CPython or PyPy) when submitting a code.

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

On the task Sum of Four Values, I think the judge may be wrong... specifically, the output section asks for any solution, but I think the judge checks whether the provided answer is identical to its own.

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

The statement for Grid Paths says "from the upper-left square to the lower-right square," but the diagram and test data match "from the upper-left square to the lower-left square."

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

Its really helpful now to filter the problems based on tags. Maybe you can add some more problems on DP :)

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

you can now hack submissions and improve the quality of tests

when you're lazy to make strong tests

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

    Laziness is surely one factor, but it is often surprisingly difficult to create good tests before seeing what people will submit :)

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

There seems to be an issue with Palindrome Reorder. I can see an AC submission which just prints the input back without forming a palindrome.

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

    You are right, the grader has now been fixed and all submissions have been regraded. Thanks!

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

Can't something be done for the multiplier of some slower languages? 50% of my Java Solutions get TLE.

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

    I think it's still fairer that every language has the same limits. It would be really difficult to decide what the multipliers would be.

    You should be able to solve at least most of the problems in Java if you use efficient I/O and avoid creating lots of objects etc.

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

      But for sure not all and that makes it not very enjoyable. Sorting category is not doable (failing first 2/3 problems because of language was enough for me), unless I want to implement and tweak my own sorting algorithm (and I'm not saying I would be able to solve them after that as java sorting algorithms should be already optimized enough)

      At least William Lin did first 150 on the stream, so I could check that my solution was correct

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

        At the moment 194/200 problems have been solved using Java. Only the following problems haven't: 1148, 1149, 1159, 1161, 1189 and 1742.

        Note that the sorting algorithm in Java (when sorting a primitive type array) may use O(n^2) time on some inputs. That is one possible reason why your code is too slow, another reason is I/O.

        However, I don't recommend to use Java in competitive programming, unless you want extra challenges because of some features of the language.

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

          TL;DR
          Why can't you give Java extra time? I thought the purpose of the problem set was to be a collection of problems which can be used to practice the techniques explained in the books, not a collection of problems which forces everyone to either use cpp or learn some way to optimize their language. Thanks to the 1s TL, when I'm trying to solve a problem, I spend more time thinking about whether or not I'll be able to get away with a solution with some optimizations than actually thinking on the solution itself.

          If you'd like to get a sense of our frustration, try solving some problems in the Sorting and Searching category. In particular, try Traffic Lights. I've tried all the optimizations I can think of (other than rewriting TreeSet) and I still TLE.

          I think it's still fairer that every language has the same limits. It would be really difficult to decide what the multipliers would be.

          Isn't it fairer for Java to get buffed time limits? If you believe that all languages should have the same limits, consider giving 2s for each problem. It'll make a lot of Java solutions that TLE but should AC get their rightful verdict. Also, is it that hard to decide what the multipliers should be? 2x or even 1.5x for Java suffices.

          You should be able to solve at least most of the problems in Java if you use efficient I/O and avoid creating lots of objects etc.

          Yes, obviously. You can obviously solve most of the problems in Java if you try hard enough to optimize it (an extreme example would be rewriting all of Java Collections). However, how hard do you have to try?

          In CF, fast IO (as in anything that buffers input) and not doing some really stupid stuff (like sorting an array where almost all elements are nulls) suffices. You can implement the intended solution and it'll pass easily.

          In CSES, the fastest IO (DataInputStream) seems like a must. You have to find various ways to optimize Java, which seems pretty unfair to me, especially when compared with cpp users.

          At the moment 194/200 problems have been solved using Java. Only the following problems haven't: 1148, 1149, 1159, 1161, 1189 and 1742.

          Simply because a problem has been solved with a language doesn't mean that that language shouldn't get extra time for that problem. Do you think it's fair that cpp users can just use their std::set and solve problems easily while java users have to either use TreeSet but heavily optimized or even write their own TreeSet?

          Note that the sorting algorithm in Java (when sorting a primitive type array) may use O(n^2) time on some inputs. That is one possible reason why your code is too slow, another reason is I/O.

          You have indeed listed some possible reasons that Java TLEs. However, I believe the main reason is due to the time limit. Even using the fastest I/O and avoiding QuickSort still easily leads to TLEs.

          However, I don't recommend to use Java in competitive programming, unless you want extra challenges because of some features of the language.

          Once again, I thought this problemset was meant to practice our knowledge of the contents in the book, not to teach us which language is better for CP or to force us to learn how to optimize our language.

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

            just use c++ lol

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

            Different languages have different features. If you use Python, there is no tree set structure at all. Is it fair for Python users that they can't solve those problems without creating own data structures?

            I don't want to say that you should use C++, but I would like to ask: why do you want to use Java? The syntax in C++ and Java is almost the same, but you will have extra challenges (both in CSES and other systems) if you use Java.

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

              Different languages do indeed have different features. However, how hard is it for these differences to be overcome? The lack of library is possibly the most minor difference. You can go online and search for a good implementation. However, the difference in speed and time limit can't be overcome as easily. I have to either take a completely different approach or make some (usually heavy) optimizations. Clearly, this is much harder than a copy and paste. And also, it seems that most people that I talk to think the major disadvantage in Python is speed, not library. Given that Python users have PyPy, can Java users get extra time?

              As to why I use Java. I started off with Java and I still find it easier to use. Although I know that I will eventually need to make the transition, I'm still using Java right now. However, to repeat again, I thought the CSES problemset was meant for us to practice the techniques explained in the books, not to force all users of languages slower than cpp to transition into cpp.

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

                I think it is fair that everybody has the same languages available and the same time and memory limits.

                Increasing time limits for Java would be unfair to others. Java code can be very fast if you have proper I/O and only use primitive types and arrays.

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

                  I'll be more specific as to my request.

                  Increase TL for Java in select problems such that a reasonable solution (e.g. one that is suggested by the book) passes.

                  I am not asking for you to (however you can do this if you want):
                  1. Increase TL for Java and Java only
                  2. Make all solutions that AC also AC in Java
                  3. Give Java (and possibly other languages) a global multiplier

                  Here is an example that would satisfy my request:
                  Give Java (and possibly other languages or maybe even all languages) extra time (either globally or for select problems) such that reasonable solutions don't TLE.

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

it's tough for learners like us. how do we know the solution if we cant solve it. there's no point not knowing the solution.

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

Is there a way to reset password? I'm pretty sure I have an account, but can't recall the password.

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

Is there any way to hide the tags shown on the website? I want to try the problems on my own first without any hints.

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

    Do you mean the section titles? At the moment it is not possible to hide them, but thanks for suggesting this. It is true that they may provide hints.

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

Can you please have code of others viewable ?

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

    It wouldn't be pleasant. As there is a statistics of the users which sorts them by solved problems, it motivates people to solve more problems to achieve higher places. The simplest example is me; if there weren't any statistics/ranking, I wouldn't be solving them.

    If you stuck, you could always post a blog about the problem, but I suggest you think about it for some good time. Don't forget that googling the problem is a thing to do before posting a blog, or else you will probably end up with having several downvotes.

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

In the problem Nearest Smaller Values, according to the constraints $$$1 \leq x_i \leq 10^9$$$ but in test cases 4, 5, 9 and 10 some $$$x_i$$$ are negative.

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

I'm pretty sure the checker for Labyrinth is wrong. Currently the solve count is 0/109.

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

    You are right, thanks! It is now fixed and all submissions will be re-evaluated soon.

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

The statement for Monsters says $$$1 \leq n,m \leq 2500$$$, but when i try making n=1001 i get invalid input(the same test with n=1000 and the last line removed doesn't get invalid input)...

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

    Also for monsters, my output is exactly the same as the expected one for test 10, but it fails with wa.

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

    The statement had incorrect bounds — the upper bound has to be 1000. Thanks!

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

The model solution for High Score seems to be wrong; everyone has WA now.

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

Hey, the latex for these are not properly formatted (e.g. this one)

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

There was rejudging of the problem String Transform recently, added new test case bb#aaa. Alas, correct output is expected as ab#ab, can you fix it, please?

UPD: Seems no original string exists corresponding to the input case bb#aaa.

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

    I was the person who submitted that string for hacking. I should have verified that a valid original string exists (the checker should have too ¯\_(ツ)_/¯). I am sorry.

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

    Thank you for reporting this, this test case has been removed and hacking is temporarily disabled for this problem until the checker has been fixed.

    Update: Now the checker should work and hacking is possible again.

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

I'm trying to do this dp problem (coins combinations II): https://cses.fi/problemset/result/244945/ . However, when I submit the code I get runtime error on some of the test cases. I tried some of the test cases that gave me runtime error locally, and everything went fine.

Here is my submission: https://cses.fi/problemset/result/244945/

PS: I used exactly the same compilation command specified here: https://cses.fi/howto/ and I have the same version of g++ (7.4.0)

Thanks for your great work !

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

Hello pllk. Would it be possible to have pdf versions of the problems? Or even just a single pdf containing all problems or maybe one pdf for each part of the problem set?

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

I really like both the competitive programmer's handbook and the cses.fi problemset.

However, I noticed that some problems can't be solved "normally" using python3 because the constraints are too large. For instance my python3 implementation of https://cses.fi/problemset/task/1192 takes 1.5s on some inputs.

I know the emphasis is on C++, but it wouldn't hurt to reduce the constraints a bit to make the problems solveable in all languages.

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

    Have you tried to choose PyPy instead of CPython when submitting a code? It should be faster.

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

      Yes, it is faster indeed, but it still fails for some inputs.

      I'm not saying it's impossible to find tricks to make it work in python, but I don't think it's the point, we just want problems on which to apply what is explained in the handbook.

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

        Well, one important point is that Python is not always a good choice in competitive programming and it may be more difficult to solve some problems using it.

        Regarding the problem you mentioned, there are several people who actually have solved it using Python and their implementations do not seem to have any special tricks. The fastest Python running time at the moment is 0.30 s.

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

If you add editorials for the problems, this platform will be the best place to practice cp.

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

I have developed a command line program just like "leetcode-cli" for CSES.

Github Repository

It supports

  • login
  • list problemset
  • view problem statement
  • submit problem
»
4 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

On Cyclic Array:

9 35 2 17 30 35 14 21 22 6 12

It says that the correct output is 6, but [30],[35],[14,21],[22,6],[12,2,17] is a division into 5 subarrays...

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

In the task Food Division, the sample explanation says

Explanation: Child 1 gives one unit of food to child 3, and child 2 gives one unit of food to child 3.

In fact, child 3 gives one unit of food to child 1 and one unit of food to child 2. I think the explanation confuses the arrays a and b.

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

    Thanks, now the explanation should be correct.

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

      By the way, it hasn't updated on my end yet. Is this expected?

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

        It should have been updated. Note that I changed the problem statement instead of the example — I think it's better that the first array has the current amount and the second array has the required amount.

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

Great site, great problems, great book. Thanks pllk.

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

Is there something special about Playlist's Test Case #12?

My std::map solution passes but unordered_map, gp_hash_table, cc_hash_table fails miserably on that test case.

I even used custom hasher, as described in Chilli's blog:

const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};
gp_hash_table<key, int, chash> table;

Code

EDIT: Niel's custom hash worked!

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

How does CSES problem set compare to cf problem ratings?pllk

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

    I think you can't compare them. Because CSES problems require more classical techniques than CF.

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

I successfully hacked a solution 4 days ago, but the page of the hack says "Test update status: Waiting confirmation from admin" and I can still see that solution on the hacking tab. What's going on?

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

    We have had some problems with hacking. Unfortunately, some users cheat by sending an incorrect solution and then "hacking" it and adding a useless test. There are some hacks in the queue and we will check them soon.

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

In Static Range Minimum Query I tried to hack my own solution with a sorted array test case. But it gives Invalid Input. Even the Example Test given gives Invalid Input when submitted as a txt file. Am I doing something wrong?

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

You can refer to my repository on github, where i have solved many of the CSES problems & am still updating those solutions. I would also be giving a small editorial of the general idea about the solution approach: Link : https://github.com/MojoAlpha/CSES-Problemset

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

In Inversion Probability, it's possible to make test cases such that the answer is very close to $$$\frac{n+0.5}{10^6}$$$ for some integer $$$n$$$, meaning that solutions using floating-point numbers can end up being incorrect(for example, one of my recent hacks has the answer of about 53.4183365000000000000943). I don't think forcing people to calculate the exact answer is a good idea; it would be better to change the problem to something like allowing a relative or absolute error of $$$10^{-6}$$$.

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

Another thing to add to this: on the test case

test case

the judge's solution is 90.384581, even though the exact answer is about 90.3845815000000000006058757, so the solution should be 90.384582.