In this video,
we'll talk about process of Algorithm Problem Solving in general.
Identify the steps of the process,
and discuss them which could not seem obvious enough.
Well, what could be the steps?
Ensuring you start with reading the statement,
and that we already done with the example problem earlier.
After that, it may help to formalize it a bit.
If the statement is long enough,
it could be good to have a clean short mathematical formulation of what's happening.
After you've got the formulation of the statements,
you should invent a solution.
Of course, it's not a simple step,
and there is no general algorithm of inventing solutions.
But knowing different ideas in algorithms helps,
and also experience in mining of and having many solved problems in your past life.
After you invent solution,
you in fact should prove it and not just implement right away.
It may seem not obvious,
but on next slide we'll discuss why the proving is important in competitive programmimg.
After you are sure that your solution is correct,
you could go and implement it.
After that, you should throw up a test the solution you've implemented
because you may have gotten errors somewhere in implementation or in the fore steps.
If you found some bug, you could,
within the usual means of debugging,
find the place of it and fix it.
After all that, you could submit your solution to the AC system,
and hopefully get accepted.
If not, then you may test more and get
another bug and fix it or you may check that all your steps,
that all steps before, you've done correctly.
So, you've phrased the statement correctly,
you've invented the correct solution,
and you've implemented it just as you invented it.
Okay, so one of the questions you may ask me could be,
why do they need the proving the step at all?
Why don't you just implement the solution which you invented?
On our previous problem, we didn't see much need for proving something,
but it turns out, we often base our solutions on assumptions which are not correct.
It may be assumptions about data,
which are not actual statement to the statements,
but were just imagined.
But also be some ideas like,
they're sure it would work or the they're sure it will work fast,
so both correctness and efficiency of your solution depends on what ideas you use.
So, if you assume you found something or if you use any idea,
it should be either within the statements or you should prove it.
Of course, if it is something well known like a theorem in math or something like that,
then you need them to prove it, but anything you should be sure of.
Of course, there is
no universal algorithm not only in writing solutions but also in proving them.
Much later in this course,
we'll discuss how to prove greedy algorithms where
the problem probably not essential in the basic problems.
And those alone how to make time estimate.
So, when you invent a solution,
you should also check not only how it works,
but also it works fast,
and there's a technique for that.
Next, imagine the situation where you found some test case on
which the solution is not working, the usual thing.
The thing is that the error is somewhere in the code,
but in fact, it's not just that.
The error could be on any step of those which we've seen earlier.
It's could not just in implementing,
but also in understanding the statement or inventing a solution and proving it.
And if you detected an error on some step,
you should fix it in the first part in this step,
and then on all other steps,
get on them one by one.
So, if you found an error in a proof,
then you fix the proof, and after that you fix the implementations algorithm based on it.
And if you found an error in understanding statements,
you should first fix the solution,
then reproof it, and only then re-implement bugs, which I get affected by it.
Starting from the wrong step could be disastrous.
Let's say for example that we write
some program which takes an integer and outputs the integer.
And we saw that's on the test where the input is five, it's posted incorrectly.
So, we may just plug an if statement in the code,
which says, if the input is equal to five,
then print the answer to it.
But that's most likely to be a bad solution.
It will just hide the fact that your solution is not working on some test cases,
but it won't get your solution generally correct,
only correct on that particular test case.
So in fact, if you see such test case,
you should test that your proof of the solution is correct, and if it's incorrect,
then change it, and only after change in proof,
change the implementation that corresponds to it.