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...