Editorial- Easiest Ever || D2C102

PROBLEM LINK:

Contest

Author and Editorialist: Pankaj Sharma
Tester: Jatin Kashyap

DIFFICULTY:

CAKEWALK.

PREREQUISITES:

Basics of Maths.

PROBLEM:

You are given an integer N.
Your task is to find any two integers A,B such that 1\leq A , B \leq 2*N and difference of A and B exactly equals to N i.e. A - B = N.

QUICK EXPLANATION:

Check

Answer is A = N + 1 and B = 1

EXPLANATION:

Let’s try to brute force i.e. generate all pairs of (A, B) such that between 1 \leq A, B, \leq 2*N and run two loops to check whether A - B == N or not.

Code
#include<iostream>
using namespace std;
int main()
{

  int t;
  // Input number of test cases
  cin >> t;

  while (t--) {
    int N;
    // Input N
    cin >> N;
    for (int A = 1; A <= 2 * N; A++)
    {
      bool foundAnswer = false;
      for (int B = 1; B <= 2 * N; B++)
      {
        if (A - B == N) {
          cout << A << " " << B << "\n";
          foundAnswer = true;
          break;
        }
      }
      if (foundAnswer == true) {
        break;
      }
    }
  }
  return 0;
}

Above code will result in TLE i.e. Time Limit Exceeded error as N can be 10^9 and T can be 10^5 and 1 second = 10^8 operations but we are performing around 10^{14} operations as N * T = 10^9 * 10^5 = 10^{14}

So we need to think about something different.

We if closely observe
A - B = N can be written as A = N + B
Now A \leq 2*N
So , N + B \leq 2 * N
So, B \leq N

Hence B lies between [1, N] and A lies between [N + 1, 2 * N].
Minimum value of N can be 1.
So B = 1 and A = N + 1 will be a valid answer.
Also A = 2*N and B = N is also a valid answer.
But A = 2 and B = N + 2 fails on case when N = 1 as B becomes greater than 2 * N

Time Complexity:

The time complexity is O(1) per test case.

SOLUTIONS:

Setter's Solution
#include<iostream>
using namespace std;
int main()
{
 
  int t;
  // Input number of test cases
  cin >> t;
 
  while (t--) {
    int N;
    // Input N
    cin >> N;
    int A = N + 1, B = 1;
 
    // Print A,B in newline
    cout << A << " " << B << "\n";
  }
 
  return 0;
}
 
Tester's Solution
import java.util.*;
class test{
public static void main (String args[]){
Scanner sc=new Scanner(System.in);
for(int i=sc.nextInt();i>0;i--)
System.out.println((sc.nextInt()+1)+" 1");
}
}
Editorialist's Solution
#include<iostream>
using namespace std;
int main()
{

  int t;
  // Input number of test cases
  cin >> t;

  while (t--) {
    int N;
    // Input N
    cin >> N;
    int A = N + 1, B = 1;

    // Print A,B in newline
    cout << A << " " << B << "\n";
  }

  return 0;
}

For doubts, please leave them in the comment section, I’ll address them.

Hi, can you please make the submissions visible.
@admin @pankajsharma1