rangerscowboys's blog

By rangerscowboys, history, 5 days ago, In English

Hello Codeforces!

On today's contest, Codeforces Global Round 26, I lost a ton of rating because of many Wrong Answers and I was very slow today. Does anyone have any tips for avoiding wrong answers? Does anyone have any tips for getting faster at solving the easier problems?

Also, for today's C1, it took me forever to come up with the idea for how to solve it. When I solved it, I was so frustrated because of how simple it was. Do any of you have a way of looking at problems that helps you solve it? I've noticed that easier problems tend to have a greedy/brute force solution to it. Do you notice any tendencies of greedy methods?

Thanks!

UPD: Even if you think that I am stupid and downvote, please answer my questions to the best of your ability. Thanks again!

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

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

be like rainboy :)

  • »
    »
    5 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    that does work for rainboy

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

    what do you mean?

    • »
      »
      »
      4 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      rainboy is so good that he doesn't even need to solve the easy problems. Best way to avoid WA.

»
5 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Your title is quite misleading. I clicked on ur blog to see the tips, but found out u r the one just like me who is searching for the tips. It would be nice if u just add a "need" before ur blog title so that others doesn't face the same issue.

  • »
    »
    5 days ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thanks for the suggestion!

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thanks for listening!

      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Hope you get back to pupil soon!

        • »
          »
          »
          »
          »
          28 hours ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Thanks for the good wish. I am finally back to pupil. Would u please give me some guidelines on how to reach the next rank like u?

          • »
            »
            »
            »
            »
            »
            26 hours ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Good job on pupil! 1999 place is crazy! In general, to reach specialist, you would probably try getting at least 4 problems in Div 3/4. Div 3/4 can really carry you to specialist, but since there is a lot of Div 2s coming up, you should try using the Div 2s. For Div 2, try solving the first 3 problems. For example, you could try practicing on Div 2 problem C from previous contests. Speed is another thing, especially when contests have a big line between two problems (problem difficulty difference is big), then speed is the next deciding factor that can determine how much you go up/down by. Please ask if you have any questions, and good luck on reaching specialist!

            • »
              »
              »
              »
              »
              »
              »
              25 hours ago, # ^ |
              Rev. 4   Vote: I like it 0 Vote: I do not like it

              4 problems on a Div 4 isn't enough. You have to aim for 5(but you have to be very speedy) or 6(time probably doesn't matter for this) to achieve specialist.

              On a Div 3, you have to aim for at least 5 problems. There was one time where I solved 5 problems very slowly, yet I still went up by 10 rating when my rating was 1430.

              On a Div 2, solving the first 3 problems is great, but for specialists, you need to solve the 3 within the first 1.5 hours assuming the problems are "regular" difficulty.

              Of course, this all varies depending on the contest.

              • »
                »
                »
                »
                »
                »
                »
                »
                25 hours ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                You realize they are a pupil right?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  25 hours ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I realize that, but I'm saying that this is the necessary results to reach specialist.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  24 hours ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I put these numbers as a lower bound, yours is for going up at specialist. For whoever is reading this, hope this message helps you understand.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  24 hours ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  You have to aim higher to achieve success :)

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rangerscowboys (previous revision, new revision, compare).

»
4 days ago, # |
  Vote: I like it +9 Vote: I do not like it

i think that u should not focus on speed too much as you develop it with time, try to solve more problems,for example yesterday i was so slow (usually my goal is to solve 3 problems but quickly)i could not do that but i solved 4 problems which was better

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rangerscowboys (previous revision, new revision, compare).

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

guessforces!

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

    yeah guessing is good option, dont solve anything, just guess the solution

»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Well, do more virtual contests, and try to thing about edge cases while implementing, also you shouldn't care about your rating at all, you shouldn't get demotivated about a single -58 when you know that you can do better

»
3 days ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

Forget about greedy, think DP. If DP doesn't work, guess the greedy.

Seems to work fine for the current meta.

My approaches for the global round were:

A — think about max and min values, try something with them

B — think about backtrack (dp) then realize that the choices don't change anything, turns into greedy

C — DP

D — Just do what the statement asks for fast enough

E — solve the samples by drawing them and guess the DP

F — guess that the local conditions are sufficient and code the DP

as you can see, lots of DP and guessing.

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

    In general, is there up to a certain problem where it is good to think about greedy? (Like the easier ones such as A and B)

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      It depends on the problem. If someone says "How many times do we need to pick option 2 ? We only need to pick it once. How can we calculate the final value for every position we can pick?" I see it more as a "I'm too lazy to give you a practical approach for this problem so here's a brain-teasing specific approach for it". Why think about the specific problem if you can simply solve it with a general approach that works for many other problems?

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

        Ah ok. For C1 I did greedy, but DP was definitely possible. DP is probably the thing I am worst at, do you have any places that I can practice DP? Even though I learned DP, I don't really practice it and now I've kind of lost my DP skills lol. Also, should I know all types of DP?

        • »
          »
          »
          »
          »
          3 days ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          So since you seem to be asking seriously here's my actual opinion:

          The most important skill in CP (and even more so in learning DP) is being able to solve problems through some sort of bruteforcing. I include backtracing as bruteforce, and that's kind of the basis of DP if you learn top-down dp. The reason for it being important in general is that I believe that many problems can be solved by simply first understanding the problem and then trying to get some correct solution ignoring the complexity. That usually leads to a fast enough solution either through some observation that you don't have to try every choice in the bruteforce or just leads to it directly. It especially works for the first few problems in div2, because the way to make the solution faster isn't locked behind knowledge of some data structure/algorithm.

          We have an example of how I put that into practice here: problem B from the global round. If I don't know how to solve the problem, a good first step is imagining what a backtrack solution would look like for the problem. Then the problem solves itself. A similar approach is "try testing everything and then notice what's useless to test" that appears in problems where you could solve it by nesting fors but that's too slow, then you do the same thing but faster.

          As for how to practice dp: master how to write backtrack solutions, then dp solutions should come naturally once you understand what you need to do (make the function depend only on the parameters that are given and possibly some fixed variables). Then solve lots of dp problems. You might encounter problems that bottom-up dp makes it easier to reason about the solution, when you've seen enough problems just spend some days coding only bottom-up dp and force yourself to learn it. There's no skipping solving problems by yourself.

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

            Ah ok. Thank you!!!

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

            what would you suggest if one has to start by iterative dp? I personally like it way more and also find it more intuitive but I can't solve it.

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

              Learning both ways doesn't hurt. It gives you more options when coding, there are times that recursive dp is easier to implement.

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

                backtrack = complete search it's iterative and recursive version ?

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

            Can you please list common types of DP?

          • »
            »
            »
            »
            »
            »
            17 hours ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you so much. I want to know if you have any approach for constructive problems, and long implementation that is usually required by Div2D?

            And also, many times after the contest in Div2C, I see some corners case that give the wrong answer. And many times, in contest where I could not solve Div2C, after when I see the case that give the wrong, I could easily what was the problem. Do you have any techniques to guess theses testcases, or how to ensure that your code cover all cases?

            • »
              »
              »
              »
              »
              »
              »
              9 hours ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              Usually if your implementation is long for such problems it means that it's not good. Look at stronger participant's code and compare yours to theirs in order to see what you're doing wrong.

              As for corner cases, it fits exactly what I did for B. Prefer an approach that's clearly correct and doesn't need corner case treatment. Sometimes that means thinking DP instead of greedy, sometimes it requires rethinking how you understand the problem a bit. It's impossible to list all cases where that applies, looking at stronger contestants' code can also be extremely helpful here. If you can't simplify your solution, then you can try to stress test to find cases that break your solution. 2 hours is a lot of time for 3-4 problems, you can spare some time to stress test if you're stuck.

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

    orz

»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

to reduce WA and panic over solving fast, I always repeat this to myself "always solve it in the mind then start coding it"

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

    Hmm, that is a good idea, but sometimes I want to go immediately into coding so I can get speed. I might do virtual contests to see when I can go without my mind and see when I have to use paper to think about it.

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

No

»
16 hours ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

During a contest, you can make sure your code is correct before submitting it. For example, you can generate several testcases, and check them by yourself or a simple bruteforce solution. This is very helpful.

And more, you can think more deeply before you start coding. You can try to solve the problems in mind first.

More important, when you practise the past problems, you can try to reduce the number of unaccepted submissions.

  • »
    »
    6 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hmm ye maybe after questions A and B, I can start generating test cases

»
6 hours ago, # |
  Vote: I like it +2 Vote: I do not like it

Do not force solutions and do not underestimate the problem.

»
102 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

cows?