Um_nik's blog

By Um_nik, history, 13 months ago, In English

More tips to use while studying under my tutoring here.

Stop caring about the rating

Unless there are prizes involved, your position in the standings makes no difference. I can feel awful after winning a contest if I know that I could solve one more problem. Or I can feel OK losing a bunch of rating points knowing that I solved everything I could.  Because rating is just a number. It is highly volatile and it depends on other people, not only on your skill. But solving problems is totally up to you. And you should evaluate yourself not based on some random metric, but on your honest feeling whether you performed up to your expectations. Your sense of self should be under your control, don't get hung up on some imaginary value, you cannot reduce your progress to a single number.

Don't use more than one account

Rating is just a number. Do not be afraid to lose your colour. You’ll get it back in no time if you continue to improve.

You don’t need a second account for shitposting either. If you think something you are doing is shit and you don't want it associated with your main account you shouldn't do it at all. Either be proud of your trolling (and do it from your main account) or don't do it.

Write contests (duh)

You may think that you are not ready to write some contests, that you need more practice solving problems without time restrictions. And yeah, practice is a necessary part of progress, but you will never learn how to function under pressure without writing contests. The best way to learn how to do X is to try to do X.

Delete rating predictor

What is even the point of it? Does it help you make a decision of what to do? What problem to solve? What problem to hack? No. It may give you motivation, but it may also break your motivation by giving you a false sense of security.

And besides, rating is just a number. Your sole goal during the contest should be to solve as much as you can. As fast as you can, as optimal as you can, and hacking on the side comes later. Focus on solving. Focus on the next problem. That is it. Round is just a series of intervals where you focus on the new problem.

Rating is way too random to be tied to your sense of achievement. Be proud of yourself for solving problems, not for your place and rating change.

Write AtCoder

No explanation needed. Just do it.

Do not force ideas or algorithms on problems

Basically this: On "is this greedy or DP", forcing and rubber bands

You can (and should) try to think “Can I do greedy? Can I do dp?” and similar. What you shouldn’t do is to believe that the problem must be solved with any particular algorithm and only try to come up with a way to make this particular algorithm work.

One very special example of this is guessing solution or complexity from constraints and/or underlying objects. Yes, it is useful information to know which complexity is expected. But you can’t determine it with 100% certainty from the constraints, and that doesn’t dictate which algorithm to use.

And do not choose an algorithm first and solve the problem later. Algorithms are tools you use to implement the solutions efficiently. If someone asks you to help assemble furniture, you don’t say “I’ll take my allen wrench, that’s all I need” without reading the manual. There are significant differences in problem solving, of course. First of all, you don’t have the manual, you should write the manual yourself, that’s called solving the problem. And second, all your toolbox is in your head, so it doesn’t cost you anything to bring the whole toolbox to the problem.

Do not write a segment tree if you don’t know how to calculate the answer for one query with $$$n < 1000$$$. Do not take your allen wrench out of the toolbox before seeing the screw with hex socket.

Ask yourself questions

When reading the problem statement:

  • Why is this limitation here? How would the problem change if it is not here?
  • What is unusual?
  • What the problem asks me to do?
  • Can I reformulate it as some standard problem? as a play on some standard problem? as a special case of some hard (NP-complete maybe) problem?

While solving the problem:

  • How would I solve an easier version of this problem? Decrease limitations. Change the underlying object to something simpler: [graph] → [connected graph] → [cactus] → [unicycle] → [tree] → [bamboo/array] or [star]; [matrix/grid] → [array]. Is there some observation that would work for the general version too?
  • How to answer one query?
  • How would I solve a small case on paper? How would I solve it without time or memory limitations?

Before implementing the problem:

  • What’s the complexity?
  • Do I understand the problem correctly?
  • What functions do I need?
  • Which places are tricky? What do I need to remember to implement them correctly?
  • Which place is the heaviest by implementation? Can I do it simpler?
  • Which place is the slowest? Where do I need to be careful about constant factors and where I can choose slower but simpler implementation?

If not AC:

  • Did you remember to do everything to handle the tricky places you thought about before?
  • Is the solution correct?
  • Do I understand the problem correctly?

If you have a test on which the solution gives wrong answer:

  • Is the solution doing what it was supposed to do?
  • Is the problem in the code or in the idea?

If stress-test cannot find the counter-test:

  • Do I understand the problem correctly?
  • Is my stupid solution definitely stupid? Does it use any assumptions/observations from the main solution?
  • Am I generating all possible test variants? Does the problem have multitest, and if so, am I generating multitest?

After getting accepted:

  • What could I have done better?
  • What areas took me more time than I would like?
  • Are there any tricks to simplify the implementation?

Don't solve by topic

Don't even look at problem tags. They are spoilers that prevent you from progressing.

But Um_nik, the best way to learn how to do X, is to do X. I want to be good at DP, therefore I need to solve DP problems.

True statement, wrong conclusion. What you want to be good at is not only solving DP problems, but most importantly recognising DP problems. And you consistently skip that step when you solve problems by topic. You immediately go from reading a problem to putting it in DP terms, you don't experience the realization that problems can be solved as DP, you don't gain knowledge of how those problems present themselves in your mind.

So, when you solve the problem without any hints about the topic (for example, in the contest setting), you don't know how to make the first step, even though you may be able to do everything after that.

Upsolve to your next level

Let's say you want to be able to solve ABC div2 during the round. Well, the best way to do that is to always solve ABC, but not necessarily during the round. Upsolve! You can do it on your own or with an editorial. If there is a hard implementation point that you cannot figure out, try to understand someone else's code for that problem.

It’s not a replacement for solving archives, it’s addition. Archives have a lot of problems (duh) and most of them are old (duuh). That can create an incentive for you to skip “random half” of problems, which is not actually random, but the problems you subconsciously didn’t like. By upsolving you are making sure that you are covering topics that appear in the current meta.

The best way to learn how to do X is to try to do X.

Don't try to create problems that MUST have a specific solution

I don't know how to help you be a good problem setter. But I know one thing. Creating a problem to fit a solution doesn't mean that that solution will be optimal for the problem. You may create the most convoluted data structure out there for something that in the end can be better solved with a simple greedy. And if you try to impose restrictions on your problem to prevent simple solutions, you are making your problem uglier or giving away your solution via restrictions.

You can still find inspiration anywhere you wish, and starting from a solution is a good way for beginners to get into problem setting. It is also a fun way of getting familiar with some new topic, even if you don't end up with any actual problems, you still learn more about mathematical models surrounding similar settings. But if you come up with a problem, you should immediately forget about your solution. Well, you should remember it, yes, but treat it as A solution, not THE solution. It is just some idea that you had, but it may not be the fastest or prettiest way to solve your problem.

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

| Write comment?
»
13 months ago, # |
  Vote: I like it +228 Vote: I do not like it

Another Pro Tip : Don't be scared of People in red and black...

  • »
    »
    12 months ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    And don't follow People in red and black blindly, don't reply "funny words" under Um_nik's blog like me. Downvoting is coming.

»
13 months ago, # |
  Vote: I like it -45 Vote: I do not like it

New work by Um_nik! Ohhhhh

»
13 months ago, # |
  Vote: I like it -28 Vote: I do not like it

Umnik sir you can teach us various tricks and useful techniques but what you wrote is just give me contribution blog. You are a legendary grandmaster who can teach us many things try to write educational blogs

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    Thanks to all mentally challenged commentators for keeping the blog in recent actions. Gimme the contribution, I'm addicted.

    The tips in this blog are much more useful than any trick or technique (except maybe for binary search).

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

    Wtf, he said Don't use more than one account and you are writing this from alt account?

»
13 months ago, # |
  Vote: I like it -28 Vote: I do not like it

Congrats Um_nik for being the top contributor to Codeforces.

»
12 months ago, # |
  Vote: I like it +29 Vote: I do not like it

You don’t need a second account for shitposting either. If you think something you are doing is shit and you don't want it associated with your main account you shouldn't do it at all. Either be proud of your trolling (and do it from your main account) or don't do it.

Once a grandmaster tried that, and got banned. Rest is history.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the great tips ! but I just want to ask how to make problems , I am not finding a good way to make a new problem which is completely different from some problem I've solved before

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do you suggest writing AtCoder?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks a lot for the advice

»
5 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

"Write contest" means solve and participate in contests, not actually come up with problems right? Most of my experience comes from Project Euler where you have unlimited time and the only reward for speed is being in the Top 100.