MikeMirzayanov's blog

How to come up with the solutions: techniques
By MikeMirzayanov, history, 9 years ago, translation, In English

As I work with students I often face the situation when if a problem doesn't seem clear to a student at the first sight, it makes them unable to solve it. Indeed, you always hear about specific methods and techniques. But you don't hear about how to think in order to apply them. In this note I'll try to sum up my experience of solving programming contest problems. However, some pieces of advice will also be applicable for olympiads in mathematics and your first steps in academic research.

So you've read a problem and you don't know how to solve it. Try the following techniques, some of them can often come handy.

Technique 1: "Total Recall"

Try to remember some similar problems that you had to solve. Quite many problems do not have a brand new idea. So probably, you can use your experience of solving a similar problem to solve this one.

Technique 2: "From Specific to General"

Let's say that you've found the solution for the problem (hurray!). Let's consider some particular case of a problem. Of course, you can apply the algorithm/solution to it. That's why, in order to solve a general problem, you need to solve all of its specific cases. Try solving some (or multiple) specific cases and then try and generalize them to the solution of the main problem. Such specific cases can be regarded as the simplifications of the problem, i.e. we can reason by the following principle: "if I don't know how to solve a complex problem, I think I'll simplify it and find the solutions of the simplified version".

The popular examples of simplifications (specific cases):

  • you get a problem for a tree. Consider its variant where the tree degenerates into a path;
  • the problem has weights? Consider a variant where all the weights are equal either to one or to an arbitrary number, or there are only two distinct weights (and so on).

Note that the solution of a specific case almost always isn't easier than the solution of a general one, so you need to try and find a solution that would be as easy and effective as possible.

Technique 3: "Bold Hypothesis"

Don't be shy of making bold hypotheses that seem true to you. You do not have to prove your solutions during contests, tap your inner intuition. When you've come up with your hypothesis, try to prove it — it may either work out well or give you an idea of how to disprove it. Do test the hypothesis on a wide set of tests as it would be a pain to waste time on implementing a solution based on a hypothesis and only after that disprove the hypothesis.

Examples:

  • the solution always exists;
  • item the number of states isn't large.
Technique 4: "To solve a problem, you should think like a problem"

I'm serious, put yourself in the shoes of the character of the problem, imagine that it's your job to handle the input sets. Think about how you'd act in this case. Try to process some small samples on your own. If the problem is about a game, play it. Sometimes I try to visualize a process or a model for better understanding. It's a little like how movies show the way scientists think. Try to think in images, imagine the solution, see it unfolding.

Technique 5: "Think together"

This technique is only applicable to team contests. In group of two or three persons start saying some clear facts about the problem. For example: "if n is even, then the answer is always 0", "if n is prime, then the solution should go like that", and so on. Sometimes your teammates will pick up ideas and develop them and this strategy can get you through the problem.

Technique 6: "Pick a Method"

Try coming through popular algorithms or methods that can apply to the problem in any way. It is useful to see the problem limits. Having picked a method, try thinking on the solution assuming that the problem is solved using this method. Your reasonings should be somewhat like this: "Let's assume that the problem is solved by divide and conquer. Then let us solve this problem recursively for the left and right half. Now all that's left is to find a way to unite these solutions. I wonder how we can do that..."

Technique 7: "Print Out and Look"

Quite often (especially in problems with a small input: one/two numbers) there are some patterns in the composition of the solution. To see a pattern, you sometimes need to write some naive method of solving a problem, generate answers for a large number of tests on large limits and meditate on your answers for a while. In order not to keep the computer busy, a good strategy is to print out the acquired results and meditate this time on the print outs.

Sometimes it is a good idea to print not only the answer, but also some extra information, such as a manner of acquiring a solutions.

Technique 8: "Google"

This technique can only be used if the round/contest rules allow it. If the problem is about sequences, then you can look for solutions (see technique 7) on the site https://oeis.org/. It helps to understand the formal model of the problem and google the correct mathematical terms.

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

Comments Comments (32)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it +49 Vote: I do not like it

A bunch of answers on Quora (including one from me).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    Hello, I have nothing but respect for you; just pointing out that you probably meant "Quora" :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -32 Vote: I do not like it

      these things you could send via messages, saying like this is kinda rude

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it +50 Vote: I do not like it

        Sorry, I'm a total beginner at using CodeForces tools.

        That said, considering your contribution score, I'm sure you're the resident authority on manners. :)

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

          that escalated real quick!

          → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        Why? If he was replying to me, I would have seen nothing rude. He was so polite & English is not my native language.

        → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Technique 2 appears to be unformatted on my browser. Anyway, thanks so much for this!

Thanks for the edit! :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    It isn't missing, it's added at the end of the first one by mistake.

    See the end of the 2nd line "##### Technique 2 ...."

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

      You're totally correct. Thanks for pointing that out :)

      → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for editorial!

→ Reply
»
9 years ago, # |
  Vote: I like it +56 Vote: I do not like it

you know you are at the right online judge when CEO himself makes time to write tutorials.<3 CF <3

→ Reply
»
9 years ago, # |
  Vote: I like it -41 Vote: I do not like it

" Google " is most helpful technique!

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    MikeMirzayanov actually put that in btw. Sorry for all the downvotes m8 :)

    → Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Here's another technique to find solution which I think isn't covered here. Assume that you already have generated some data or you've already solved a part of the problem. Now using those, can you solve the rest of the problem? If yes, then solve the first part now. It's kind of fast prototyping.

→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +45 Vote: I do not like it

The Feynman Algorithm is another way to do it:

  1. Write down the problem.
  2. Think real hard.
  3. Write down the solution.
→ Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can you please shed some more light on technique 4, preferably using examples? Also, one example of technique 2 that can really show the power of boiling down specific problem's solution into a general solution would make it great.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you know any examples for 3rd and 4th techniques ?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the Technique 7, I wonder that in C++ using Code::Blocks, complier GCC, is there any way to pause the black window when we run a program, so that we can look the numbers we printed out?

I mean, if I print out all of the numbers I want to look, the numbers will be full of the black window and they will be quite hard to check. I want to check them step by step at different moments.

In Pascal, we can use readln;.

In Code::Blocks, I tried system("pause");, getchar();, but they didn't work.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    What's your OS? What exactly do you mean by "system("pause") didn't work"?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My OS is window 10, but I think it doesn't matter. And system("pause"); is a command in C++, included in library . It will pause the black screen until we press any key, sometimes it works, sometimes it dosen't.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        It matters. system("pause") is not a C++ command, it's a C++ function system which calls OS' command which you pass as an argument. You can write system("dir") as well and your program will print listing of current directory, but that works on Windows only. On Linux you will write system("ls") to achieve similar effect.

        Would you mind testing the following program? Does it always pause when you run it in Code::Blocks?

        #include <stdlib.h>
int main() {
    system("pause");
    return 0;
}

        By the way, I believe that Code::Blocks should automatically prevent console window from closing if you chose "Console Application" as project type in the beginning. You can also try running the application in debug mode or put a breakpoint on the last operation in main.

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Another suggestion is here. The post tells you how to enable program to auto-exit after termination, you need the exact opposite, I believe that you can figure what to do yourself (of course, if the settings are still here in the latest version of Code::Blocks).

        → Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Wonderful Tips and Techniques. Thanks a lot.

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thank you for these pieces of advice!

→ Reply