Proofs & Constructive Algorithms

Let's look at the idea of proof in competitive programming.

In the contest you are given several problems, and some problems may require you to do brute force, or sometime you might be required to check some more test cases and you would reach the solution.

But sometimes, we might get the wrong answer (WA) and have to check the accuracy of the solution by proving the necessary solution.

So.. let's start with what is the proof?

As per wiki “A mathematical proof is an inferential argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion”

But, in layman’s way, the proof is a mathematical way to accurately describe a hypothesis (not so layman I guess)

But there are various types of proof

direct proof: where everything is described in a mathematical way and we reach to next step using purely mathematical theorems and axioms.

Inductive proof: (Proof by mathematical induction) Here, we prove a single base case, and the “induction rule" is proved that establishes that any arbitrary case implies the next case.

There are many more types of proof, but the one we are concerned about is proof by contradiction or reductio ad absurdum i.e. to assume something to be true and then after doing multiple operations if we encounter any logical contradiction we can prove the assumed sentence to be false, proving the opposite of the first sentence is true.

Let's look at an example,

We know there can only be one prime factor greater than √n.

Let's try to prove this using method of contradiction,

The only thing we need to prove is that “There is only a single prime factor that exists after √n."

Proof:

So, for this proof let us assume we have two prime factors p and q which are prime factors of n and greater than √n. (NOTE: This is the contradiction that we will later prove wrong)

So we can say that,

$$\displaylines{ p > \sqrt{n} \newline q > \sqrt{n} \newline \text{Multiply both equations, } \newline p \times q > \sqrt{n} \times \sqrt{n} \newline p \times q > n }$$

So the multiplication becomes, p * q which is greater than n.

Now you can clearly see that the multiplication of prime factors is greater than n and which is contradictory to the definition of prime factors.

The standard representation of any number can be expressed as

$$\displaylines{ p_i \text{ is a prime number} \newline n = p_1 \times p_2 \times ... \times p_k \ }$$

So you can clearly see, the multiplication of two prime factors can not be greater than n itself, ergo the assumption we had earlier was wrong. Proving the earlier statement to be true.

I hope you have a clear understanding of what is proof and how proof by contradiction can help you achieve the goal of proving. However, you don’t always need to prove the solution you have in mind. As Competitive Programming is all about using as less time as possible and solving as many problems as you can. So, while participating in a contest it is not recommended to prove the solution, but having an idea about how to reach the required proof is important.

Many times you will be required to create multiple sample cases and derive the sample output, eventually figuring out the pattern.

---

Let's look at a question from CodeChef that appeared in one of a recent contest

PROBLEM: Find an integer

The question is pretty straightforward. We have given two integers X and Y. Now we have to find integer N, which should satisfy two conditions:

$$\displaylines{ 1. (N + Y) \text{ is divisible by } X \newline 2. (N + X) \text{ is divisible by } Y }$$

Now how can we solve this problem?

Now, for this problem, you can try different values of X and Y. And see what can be the possible value of N.

#include<iostream>
using namespace std;

int main() {
    int X, Y;
    cin >> X >> Y;
    const int LIMIT = 1e3;
    for(int N = 0; N < LIMIT; N++) {
        if((N + X) % Y == 0 and (N + Y) % X == 0) {
            cout << "N: " << N << endl;
        }
    }
    return 0;
}

If you run this code for different values of X and Y. One thing you will realize is that difference between consecutive values of N is LCM(X, Y).

Coincidence?

I think not!

Let's take a look at LCM.

$$\displaylines{ \text{Assume, } \newline Lc = LCM(X, Y) \newline \text{so, } Lc \text{ is divisible by both X and Y}. \newline \text{If Lc is divisible by X} \newline \text{then we can write Lc as,} \newline Lc = X \times k \text{ } (constant) \newline Lc = Y \times k \text{ } (constant) }$$

So, if we want to find the lowest value which could be N for given X and Y.

So, one more observation can be made using this

$$\displaylines{ \text{if, } Lc \text{ is divisible by } X \text{ then } \newline Lc - X \text{ should also be divisible by X as } lc = X \times k }$$

Same goes for Y.

Now, let's consider our first value to be

$$\displaylines{ N = Lc - X - Y \newline \text{Now when we add Y to N} \newline N + Y = Lc - X - Y + Y \newline N + Y = Lc - X \newline \text{So X is divisible by N + Y} \newline \text{The same thing can be proven for Y } \newline \text{Y is divisible by N + X} }$$

Hence, we can say that N = LCM(X, Y) - X - Y. is our first solution.

Now, for multiple of LCM(X, Y)

$$\displaylines{ \text{in general, our answer could be } \newline N = k \times Lc - X - Y \newline \text{it can be easily proven that } \newline \text{We can add Lc as many times as we want} \newline \text{it still would not make any difference as } \newline \text{as Lc is divisible by X and Y} }$$

Now, you can solve this way to complete the solution. Now, one more thing N could be negative if LCM is not greater than X and Y. Solve that case, And try to come up with a solution. All the best:)

---

Now, let's look for constructive algorithms.

What are constructive algorithms?

Any question you see in a contest can be broken down into absolute mathematical proof but not always this proof is visible. So, sometimes what we need to do is take multiple sample cases and solve them. And once you have enough dataset, we can use that dataset to figure out the pattern between each value of the input to each value of output.

Now, you can never precisely say that the question belongs to the "Constructive Algorithm" tag (like TAG on Codeforces). But if you are not able to come up with an approach for a particular question, it is a good idea to try out multiple cases and figure out the pattern. As in the previous question, if you would have calculated multiple values for some X and Y, you would have easily noticed that the difference is the LCM of those two.

PROBLEM: Guess All

In this problem, K in length but for our simplification, we will consider N and an array arr

$$f(i) = \begin{cases} arr[i] & i\leq 0\le N - 1 \newline -\sum_{j=1}^{K} f(i - j) & N\leq x \ \end{cases}$$

So, if we calculate some values of the function f

$$\displaylines{ f(0) = arr[0] \newline f(1) = arr[1] \newline f(N - 1) = arr[N - 1] \newline \text{For, } N \newline f(N) = - \sum_{j=1}^{K}f(N-j) \newline f(N) = -[f(N - 1) + f(N - 2) + .. f(0)] \newline \text{Let us assume the sum of} \newline \text{all the elements in the array is } S \newline f(N) = -S }$$

Let's calculate further,

$$\displaylines{ f(N + 1) = \sum_{j=1}^{K}f(N + 1 - j) \newline f(N + 1) = - [f(N + 1 - 1) + f(N + 1 - 2) + .. f(N + 1 - N)] \newline f(N + 1) = - [f(N) + f(N - 1) + f(N - 2) + ... f(1)] \newline \text{You can cleary see that } f(N - 1) \text{ to } f(1) \newline \text{ is just the sum of all the elements} \newline \text{in the array except the first element} \newline \text{Also, } f(N) = -S \newline f(N + 1) = -[-S + S - arr[0]] \newline f(N + 1) = -[-arr[0]] \newline f(N + 1) = arr[0] }$$

If we keep on calculating we will realize that

$$\displaylines{ f(i) = arr[i], \space 0\le i \le N - 1 \newline f(i) = -S, \space i = N \newline f(i) = arr[i - N], \space N < i \le 2 \times N }$$

So, from all the above observations we can conclude that the value of i same as i % (N + 1). So, we can conclude that there are only N + 1 different values for this function. And for every value, we can just calculate i % (N + 1) and answer the question.

NOTE: The problem is similar to the interactive problem on Codeforces so please use flush and all the required functions as per the language.

Hope you liked the blog.

Subscribe for more.

Happy Reading!

teckBakers\iRatherFear