MISSSUMS - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

SIMPLE

PROBLEM:

Given a positive integer N. Output any array A of length N, such that

  • A_i+A_j\ne A_k for all 1\le i,j,k\le N
  • 1\le A_i\le 10^5 for all valid i.

EXPLANATION:

The array [10^5-1,10^5-2,\dots,10^5-N] is a valid solution, for the given constraints on N.

Proof

It is trivial to show that the requirement 1\le A_i\le 10^5 holds for all valid i. All we are left to do is prove A_i+A_j\ne A_k for all valid i,j,k.

A_i+A_j=(10^5-i)+(10^5-j)=2\cdot10^5-i-j\\ \implies 2\cdot 10^5-i-j>2\cdot 10^5-2\cdot N> 10^5\\ \therefore A_i+A_j > 10^5 > A_k

Thus, we have shown the correctness of our solution.

TIME COMPLEXITY:

O(N)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here

Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

2

Another approach, we could make the series as first n odd integers, it’ll always be less than 10^5 for the given constraint ( nth odd number = 2*n-1), and no two elements in the array would sum to any other element in the array ( sum of odds is even, if all are odd, their sum would be even all the time, we don’t have any even in the array)

11 Likes
3

I used the approach of prime numbers but i excluded 2 just to make the loop working. So the loop will start from 3 to 10^5 and if the number is prime number then i will print it.

4

n odd nos also a valid ans

5

i was about to say this , the solution provided here only takes one approach into consideration .

the array consisting of elements a[i]=2*a[i-1]+1 also provides the desired solution

6

There can be multiple approaches for a single problem

7

yes the tester has provided only one solution, tbh

8

yes, this can also be the solution

9

can anyone tell me why i am getting WA

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
static void arr(){
int n= sc.nextInt();
ArrayListv = new ArrayList<>();
for(int i = 0; i<n; i++){
v.add((long) (i+3));
}
for(int i=0;i<n;i++){
System.out.print(v.get(i)+" “);
}
System.out.print(”\n");
}
static Scanner sc = new Scanner(System.in);
public static void main (String[] args) throws java.lang.Exception
{
int tc=sc.nextInt();
while(tc–>0)arr();

}

}

10

The code you provided is not running on Code chef IDE, maybe you did not paste the correct code. Never mind I went through your code by your profile and found you have used wrong logic.
For input: 8
Your output: 3,4,5,6,7,8,9,10
But we need Arr[i]+Arr[j]!=Arr[k]
Here in your output we clearly see 3+5=8

1 Like
11

Another solution: take the numbers from N to 2N-1. Interestingly this has the same maximum as just taking the odd numbers.