Prove Him Wrong - 1651B

 Problem Link

Algorithm Used: Constructive Algorithms, math

Time Complexity: O(N)

In this problem, an integer N is given. Find a sequence of N integers, such that no integer > 1e9 and 2 * difference of any two integers (indices are different) is at least the sum of the two integers.

I solved this problem by just writing down solutions to some values of N, and then finding out the pattern. (and coming up with the logic behind the pattern afterwards) 

The pattern: the ith integer is 3 * i-1th integer. If the ith integer exceeds 1e9, then there is no solution.

Here's the logic behind why this pattern works:

Let one integer in the sequence = x, and another integer = y

In order to find a solution for the largest possible value of N, we need to accommodate as many values into the array[N] as possible. For this, the sum of the two new numbers should be smallest valid sum. This smallest possible sum is simply x + y. (at least sum of two integers)

Assuming y >= x:

 y must be > than x, because if the two integers are the same, then their new sum will be (y - y) = 0. This is definitely less than the required sum. 

When the difference between x and y is multiplied by 2, that gives us x + y. (the multiply by two is there because we need two new integers)

x + y = (y - x) * 2

x + y = 2y - 2x

y = 3x

(see where the "multiply by 3" logic comes into play?)

This also fits the assumption that y > x

Code

#include <bits/stdc++.h>

using namespace std;

int main() {

    int T;

    cin >> T;

    while (T--) {

        int n;

        cin >> n;

        long long highest = 1;

        int cpy = n;

        while (cpy--) {

            highest *= 3;

            if (highest > 1e9)

                break;

        }

        if (cpy > 0)

            cout << "NO\n";

        else {

            cout << "YES\n";

            highest = 1;

            for (int i = 0; i < n; i++, highest *= 3)

                cout << highest << ' ';

            cout << '\n';

        }

    }

}