ANTITRI - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: iceknight1093
Tester: wasd2401
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given N and L. Find an array of length N containing distinct integers from 1 to 10^9, such that (A_i, A_j, L) cannot be the edges of a triangle for any i and j.

EXPLANATION:

The statement conveniently included a link to the triangle inequality, which is the crux behind solving this problem.

For any three integers x \leq y \leq z, the triangle inequality states that they can form the sides of a non-degenerate triangle if and only if x+y \gt z.

We don’t want a triangle, so the inequality should fail.
That means:

  • If A_i and A_j are both \leq L, A_i + A_j \leq L should hold, since L will be the largest among them.
  • Otherwise, let A_j be the larger one among A_i and A_j. Then, A_i + L \leq A_j must hold.

This tells us that:

  • No two elements of A_i that are \leq L should have a sum that exceeds L.
    • So, it’s enough if the sum of the two largest numbers \leq L doesn’t exceed L.
  • If A_i \gt L, then its previous smaller element should be \leq A_i - L.
    • That is, differences between ‘large’ numbers should be at least L.

These ideas give us two different strategies for choosing elements.

  • First, we can try to take 1, 2, 3, \ldots, K, as long as K+(K-1) \leq L.
    This way, the sum of two ‘small’ numbers will never exceed L.
  • Second, we can try to take something like L, 2L, 3L, 4L, \ldots, NL, where all of them are ‘large’ but the differences between them are L.

Let’s analyze where these fail to attain N elements.

  • The first idea fails if L is “too small”, i.e, when you can’t take 1, 2, 3, \ldots, N.
    • This happens only when N+(N-1) \gt L, meaning L \lt 2N-1.
  • The second idea fails only when L is too large, since the maximum number we create is N\cdot L, which can exceed 10^9 (for example when L = 10^9 and N = 1000).

To fix the issues, combine the ideas!
If L \geq 2N-1, use the solution [1, 2, 3, \ldots, N].
Otherwise, L is small, and L, 2L, 3L, \ldots, NL will fit in 10^9; being at most 1000\cdot 1998 = 1998000 for N = 1000 and L = 1998.

TIME COMPLEXITY:

\mathcal{O}(N) per test.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, l = map(int, input().split())
    if l >= 2*n - 1: print(*list(range(1, n+1)))
    else: print(*list(range(l, n*l+1, l)))
2 Likes
2

include <bits/stdc++.h>

using namespace std;

int main() {
// your code goes here
int t;
cin >> t;
while (t–) {
int n, l;
cin >> n >> l;
if(l>2){
vector v(n+1,0);
v[1]=1;
v[2]=2;
int sum=0;
int z=n+1;
for(int i=3;i<=n;i++){
int x = v[i-2]+v[i-1];
if(x+v[i-1]<l){
v[i]=x;
sum++;
}
else{
z=i;
break;
}
}
v[z]=l;
for(int i=z+1;i<=n;i++){
v[i]=v[i-2]+v[i-1];
}
for(int i=1;i<=n;i++){
cout<<v[i]<<" “;
}
cout<<endl;
}
if(l<=2){
vector v(n+1,0);
v[1]=1;
v[2]=2;
for(int i=3;i<=n;i++){
v[i]=v[i-2]+v[i-1];
}
for(int i=1;i<=n;i++){
cout<<v[i]<<” ";
}
cout<<endl;
}
}
return 0;
}
What is wrong in this idea??
Can anybody help pls: