How do programmers test their algorithm in TopCoder or other competitions?

Question

Good programmers who write programs of medium and high complexity in TopCoder or ACM ICPC competitions must ensure that their algorithm is correct before submission.

Although they are equipped with sample tests to ensure that the output is correct, how does this guarantee that the program will work correctly? They can write their own test cases, but in all cases it will not be possible to find out the correct answer using manual calculation. How do they do it?

Update: It seems that it is impossible to analyze and guarantee the result of the algorithm, given the severe limitations of the competitive environment. However, if there is any guidance, the more general features that are adopted when solving such problems should be sufficient to answer the question. Something like best practices.

Answer 1

In competitions, the best programmers have enough experience to read the question, and think about some test cases that should catch most of the input options.
It usually catches most errors, but it is NOT 100% safe.

However, in real life, critical applications (for example, critical systems on airplanes or nuclear reactors) have methods that ensure that some piece of code does what it should do.

This field is a formal check - it is too complicated and time consuming but it is used for some systems because errors cannot be made.

---

Additional Information:
A formal check consists mainly of two parts:

• Manual verification - here we use proven systems, such as Logic of Chorus and manually prove that the program does what we want it to do.
• Automatic model validation - modeling a problem as a state machine and using model verification tools to make sure that the module is doing what it should do (or not do something "bad").
  The definition of “what this should do” is usually done using temporal logic .
  This is often used to validate hardware models. For example, Intel uses it to ensure that it does not receive a floating point error again.

Answer 2

Imagine this, imagine that you are the best programmer. You know that you know a lot of algorithms, and don’t think to think twice when implementing them. You know how to change an already known algorithm to suit the needs of the problem. You are strong with estimating time and complexity, and you expect that in the worst case scenario, your adapted algorithm will work in time and memory constraints.
At this level, you just think and use the notebook for about five to ten minutes, and before you start coding, you will get a super-clean algorithm. When you finish coding, you will get to compilation and, as a rule, there is no compilation error. Because the code is so intuitive to you. Then, based on the algorithm used and the data structures used, you expect that there may be one of the following problems.

• corner case
• overflow problem

The angular case is basically similar to what you encoded for the general case, however, when they say N = 1, the answer is different. Therefore, you usually write it as a special case. Overflow occurs when intermediate values ​​or results overflow data type restrictions.

You note any problems that are currently occurring, and use this data during the call phase (as in TopCoder).
Once you have verified these two, click on "Submit."

Answer 3

There is a time element in the Top Coder element, so it is not possible to check each combination within this limit. They probably do their best and rely on experience for the rest, as is done in real life. I do not know that it can ever be guaranteed that a significant portion of the code will be error-free.