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

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

Hello Codeforces

Recently someone asked for a tutorial about using polygon to prepare problems, I couldn't find such tutorial so I decided to write one. You can find the tutorial here.

This tutorial is beginner friendly, I tried to explain every step in details and through the tutorial I have created a complete simple problem. I hope you will find this tutorial interesting and helpful. If you want READ access for the problem created in this tutorial you can write a comment with your polygon handle on this blog or simply send me a message.

You can also check some of my previously written articles about Competitive Programming at:

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

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

Thanks for the tutorial. I was searching this for weeks. Wrote also a blog post but got ignored recently. Thank You Very Much.

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

If anyone needs help with Polygon, please feel free to message me. I've been using it a lot over the last couple of weeks, and I'd be happy to try and help anyone who needs it.

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

    Hey, I have an issue with a type of a problem. Say the given problem expects a time complexity of O(N) while the input is of O(N^2), how to manage such problems? Can you please help me.

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

      I'm not sure what is the specific problem, so I cannot make a specific judgment on what would work. One possibility is for you to have T queries on the same input, where each query has intended O(N) solution, so the overall complexity is O(NT). Another possibility is to figure out some way to compress the input. However, you can't directly read in O(N^2) input since input would dominate the time complexity of the algorithm, so the algorithm would end up being O(N^2) anyway.

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

        The problem I wanna set can't have T queries on the same input :/ Well, I'll give you an example, https://practice.geeksforgeeks.org/problems/row-with-max-1s0023/1 consider this problem. I have modified it to make a new one. Now, is there any way out here? Thanks a lot though!

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

          You can make the problem interactive and allow the contestant to query array indices, and you can limit the amount of queries they can make.

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

            Ahh well, that's a beautiful idea. Thanks a lot! Just on a note, there is no way I can make polygon ignore the input time? Also, can i make interactive problems on polygon?

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

              I don't think there's a way to ignore the input time.

              Yes, you can set interactive problems on Polygon.

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

Actually i have a problem like this. So basiclly, i want a pretest in my contest. So for every problems I only put the sample tests in the Test section in polygon. Later i will add more test (from File) and the rejudge. But the problems is that the contest will not update the new Test. How can I fix this?