Hooray! Today we've survived another DDOS attack. The round was not perfect, but it was not ruined! ×

sorai_nai's blog

By sorai_nai, 7 weeks ago, In English

Given is the following statement.

Given a Problem $$$P$$$, Let $$$T$$$ be the set of all testcases for this problem,

Let $$$t^* \in T$$$ be a test-case such that for a given program $$$S$$$, if $$$S$$$ passes the verdict of $$$t^*$$$, it's guranteed to pass $$$\forall \; t \in T$$$. ( Hence it's a correct solution.)

In simpler terms, Is it always possible to create a test-case for a problem, such that if a solution passes the verdict for that test-case, then it can claimed that the solution is correct.

Prove the existence/non-existence of $$$t^*$$$.

(i.e Prove that it exists, or prove that it doesn't.)

Note : The Given Problem P could be any problem. i.e Prove/Disprove it for all problems that could exist.

  • Vote: I like it
  • -7
  • Vote: I do not like it

7 weeks ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

It is wrong. You could have a problem for which there are two (or more) ways in which the program fails and a test can only check for one of them. For example, you are given two integers $$$1 \le a,b \le 10^9$$$ and you need to output $$$a+b,a-b,a \cdot b$$$ and $$$\frac{a}{b}$$$. One way in which a program may fail is from overflow. Additionally, one can put in his/her code this:

if(a==82536234 || a==38475342) 

It is impossible to check in one test both these cases.

On the other hand, if you have a problem with multiple test cases per test, then you can cram every possible input in there and it will guarantee that the solution is correct.