TFALL - Editorial

PROBLEM LINK:

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

Author: apoorv_me
Tester: sky_nik
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There are N balls on the x-axis. The i-th is at X_i and has power P_i.

A ball can be activated to move either left or right.
When it moves:

  • It will move P_i units in its direction.
  • If it hits another ball, it will disappear, and the newly hit ball will instead be activated in the same direction.
  • If it never hits a ball, it won’t disappear.

Is it possible to activate at most two balls such that in the end, at most two balls remain?

EXPLANATION:

Note that when Alice activates some ball, its movement will then further activate some range of balls.
Further, since a ball can only be activated once, the two ranges of activated balls cannot intersect.

On the other hand, we also want to activate every ball at the end of both moves.
This is only possible if one move activates some prefix of the balls, and the other move activates the remaining suffix - that is, for some i, one move should activate balls 1, 2, \ldots, i, and the other should activate balls i+1, i+2, \ldots, N.

Now, we need to check whether that’s possible.

Let’s look at the prefix of length i. Note that if we are to activate them all with a single move, we only have two options: either activate 1 to the right, or activate i to the left.
So, let’s precompute some values:

  • x_1, the last ball activated if 1 is activated to the right.
    This can be easily computed in \mathcal{O}(N) time by just simulating what happens when 1 is activated.
  • \text{left}_i, which is a boolean value that denotes whether activating i to the left will activate its entire prefix.
    This is fairly easy to calculate too: \text{left}_i is true if and only if ball i can reach ball i-1, and also \text{left}_{i-1} is true.
    \text{left}_1 is true by default.

With these two values in hand, observe that the prefix of length i can be activated if and only if one of these two conditions is true:

  1. x_1 \geq i
  2. \text{left}_i = 1

Similarly, we can compute x_N and \text{right}_i, which will tell us whether each suffix can be activated in a single move.

Finally, for each i from 1 to N, check if the prefix ending at i and the suffix starting at i+1 can both be activated in a single move each.
If this is true for any index i, the answer is Yes, otherwise it’s No.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int t; cin >> t; while (t--) {
    int n;
    cin >> n;
    vector<int> x(n), p(n);
    for (auto& xi : x) {
      cin >> xi;
    }
    for (auto& pi : p) {
      cin >> pi;
    }
    auto max_right = [&](int l, bool dir) -> int {
      while (l + 1 < n && x[l + 1] - x[l] <= p[l + dir]) {
        ++l;
      }
      return l;
    };
    auto min_left = [&](int r, bool dif) -> int {
      while (r > 0 && x[r] - x[r - 1] <= p[r - dif]) {
        --r;
      }
      return r;
    };
    cout << (max(max_right(0, true), max_right(0, false)) + 1 >=
             min(min_left(n - 1, true), min_left(n - 1, false)) ? "YES" : "NO") << '\n';
  }
}
Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    pos = list(map(int, input().split()))
    a = list(map(int, input().split()))

    pref, suf = [0]*n, [0]*n
    pref[0] = 1
    for i in range(1, n):
        if pref[i-1] == 0: break
        if pos[i] - a[i] <= pos[i-1]: pref[i] = 1
    suf[-1] = 1
    for i in reversed(range(n-1)):
        if suf[i+1] == 0: break
        if pos[i] + a[i] >= pos[i+1]: suf[i] = 1
    
    x = 0
    while x+1 < n:
        if pos[x] + a[x] >= pos[x+1]: x += 1
        else: break
    y = n-1
    while y > 0:
        if pos[y] - a[y] <= pos[y-1]: y -= 1
        else: break
    
    ans = 'NO'
    for i in range(n-1):
        if (x >= i or pref[i]) and (y <= i+1 or suf[i+1]): ans = 'YES'
    if x == n-1 or y == 0 or pref[-1] or suf[0]: ans = 'YES'
    print(ans)
3 Likes

Can somebody tell me what is wrong in my approach?

void soln()
{   
    fast();
    ll n;
    cin>>n;
    vi a(n);
    read(a, n);
    vi b(n);
    read(b, n);
    vi ri(n,0);
    vi le(n,0);
    if (n<=2){
        yes;
        return;
    }
    for(int i=1; i<n; i++){
        if (a[i]-a[i-1]<=b[i]){
            le[i]=le[i-1]+1;
        }
        else{
            le[i]=0;
        }
    }
    for (int i=n-1; i>=0; i--){
        if (a[i+1]-a[i]<=b[i]){
            ri[i]=ri[i+1]+1;
        }
        else{
            ri[i]=0;
        }
    }

    // lr
    for(int i=0; i<n-1; i++){
        if (le[i]+ri[i+1]>=n-2){
            yes;
            return;
        }
    }
    // rr
    if (ri[0]+1<n&&ri[0]+ri[ri[0]+1]>=n-2){
        yes;
        return;
    }
    //ll
    if (n-1-le[n-1]-1>=0&&le[n-1]+le[n-1-le[n-1]-1]>=n-2){
        yes;
        return;
    }
    //rl
    if (ri[0]+le[n-1]>=n-2){
        yes;
        return;
    }
    if (ri[0]>=n-2){
        yes;
        return;
    }
    if (le[n-1]>=n-2){
        yes;
        return;
    }
    no;

    return;
}

got confused with this line “while moving, it strikes another ball j, ball i will immediately disappear” i thought when a ball’s journey is over it disappears, and i missed this line “If ball j was previously activated, nothing happens, and the process immediately ends.”

i could not believe 60%+ acceptance because this makes the problem harder.
my bad.

would be very helpful if tester would explain it solution!!:slight_smile:

3 Likes
  • max_right(l, true) finds the rightmost ball that can reach l (by moving left);
  • max_right(l, false) finds the rightmost ball that l can reach (by moving right);
  • min_left(r, true) finds the leftmost ball that can reach r (by moving right);
  • min_left(r, false) finds the leftmost ball that r can reach (by moving left).

To activate everything you at least need to activate 0 and n-1. Either you activate 0 directly and push it right, or you activate some other ball, push it left and it eventually reaches 0. In the first case you cover a segment [0, max_right(0, false)], and in the second case you cover a segment [0, max_right(0, true)]. It makes sense to take the bigger one.

Similar logic applies to n-1: either activate directly, push left and cover the segment [min_left(n-1, false), n-1] or activate some other ball, push it right and cover the segment [min_left(n-1, true), n-1]. Once again, greedily take the larger segment.

Finally, check if the union of two segments covers everything.

4 Likes

I came up with an idea of connecting elements and then checked the number of connected components through DFS. If connected components are <=2 then YES otherwise NO. But It shows wrong on testcase 2,maybe I wasn’t connecting properly according to the condition. Can someone elaborate or explain idea for this with DFS!!it would be really appreciated <3

I spent a lot of time on this. This is the bese explanation I could come up with. If it helps :slight_smile:

#include <bits/stdc++.h>
using namespace std;

/*
* I need to create 4 functions basically.
* 1) Find the index that 0 can reach moving right
* 2) Find the index that can reach 0 moving left
* 3) Find the index that can reach n-1 moving right
* 4) Find the index that can n-1 can reach monving left

Now pick (leftmost) minimum index for n-1  
And maximum index (rightmost) for 0  

When we activate the leftmost and rightmost there should be no elements left between.
So, rightmost index >= leftmost index.
*/

int zero_to_r(vector<int>&x, vector<int>& p, int n){
    int l=0;
    while(l+1<n){
        if(x[l] + p[l] < x[l+1])break;
        l++;
    }
    return l;
}
int r_to_zero(vector<int>&x, vector<int>& p, int n){
    int l = 0;
    while(l+1 < n){
        if(x[l+1] - p[l+1] > x[l]) break;
        l++;
    }
    return l;
}
int last_to_l(vector<int>&x, vector<int>& p, int n){
    int r = n-1;
    while(r>0){
        if(x[r] - p[r] > x[r-1]) break;
        r--;
    }
    return r;
}
int l_to_last(vector<int>&x, vector<int>& p, int n){
    int r = n-1;
    while(r>0){
        if(x[r-1] + p[r-1] < x[r]) break;
        r--;
    }
    return r;
}

void solve(){
    int n; cin >> n; vector<int> x(n); vector<int> p(n);
    for(auto& xi:x) cin>> xi; for(auto& pi:p) cin>> pi;
    int r1 = zero_to_r(x,p,n);
    int r2 = r_to_zero(x,p,n);
    int l1 = last_to_l(x,p,n);
    int l2 = l_to_last(x,p,n);
    
    // cout<< r1 << " " << r2 << " " << l1 << " " << l2 << " ";
    
    int r = 1 + max(r2,r1);
    int l = min(l1,l2);
    
    if(r>=l) cout<< "YES" << endl;
    else cout<< "NO" << endl;
}
int main() {
	int t; cin>> t;
	while(t--){
	    solve();
	}

}
1 Like

I came up with the logic to find out how many balls can be activated from both left and right end both by first moving the balls to the left and then to the right.
leftLeft represents the quantity that tells how many balls can be activated in the prefix when balls are moving to the left.
leftRight represents the quantity that tells how many balls can be activated in the prefix when balls are moving right.
Similarly for suffix array.
max of leftLeft and leftRight gives the maximum number of balls that can be activated from the prefix.
max of rightLeft and rightRight gives the maximum number of balls that can be activated in the suffix.
The sum of maxLeft and maxRight should be greater than or equal to N, the number of balls for our condition of at most activating two balls.

A separate O(n) loop to calculate all 4 variables was fast enough to be computed within the TLE bounds.

well explained bro thanks

what is wrong in this code …

#include<bits/stdc++.h>
using namespace std;
define ll long long
define f(n) for (int i = 0; i < n; i++)
define read(z) ll z; cin>>z;
define v vector
include
using namespace std;

int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
read(t);
while(t–){
read(n);
v x(n),p(n);
f(n){
cin>>x[i];
}
f(n){
cin>>p[i];
}
int flag=1;
int indexfront=0 ;
f(n-1){
if(x[i]+p[i]>=x[i+1]){
}
else{
flag=0;
indexfront=i;
break;
}
}
if(flag){
cout<<“yes”<<endl;
continue;
}
flag=1;
// cout<<indexfront<<endl;
for(int i= indexfront+1; i<n ; i++){
if(x[i]+p[i]>=x[i+1] || i==n-1){

        }
        else{
            flag=0;
            break;
        }
    }
    if(flag){
        cout<<"yes"<<endl;
        continue;
    }
    flag=1;
    int indexback=0 ;
    for(int i =n-1 ; i>0 ; i--){
        if(x[i]-p[i]<=x[i-1]){
        }
        else{
            flag=0;
            indexback=i;
            break;
        }
    }
    if(flag){
        cout<<"yes"<<endl;
        continue;
    }
    flag=1;
    // cout<<indexback<<endl;
    for(int i= indexback-1; i>=0 ; i--){
        if(i==0 || x[i]-p[i]<=x[i-1] ){
            
        }
        else{
            flag=0;
            break;
        }
    }
    if(flag){
        cout<<"yes"<<endl;
        continue;
    }
    flag=1;
    
    if(indexback-indexfront==1){
        cout<<"yes"<<endl;
        continue;
    }
    int count =0 ;
    int index=-1 ;
    for(int i=0 ; i< n ;i++){
        if(i==n-1 || x[i]+p[i+1]>=x[i+1]){
            
        }
        else{
            index=i ; 
            break;
        }
    }
    for(int i= index+1; i< n ; i++){
        if(i==n-1|| x[i]+p[i]>=x[i+1]){
            
        }
        else{
            flag=0 ; 
            break;
        }
    }
    if(flag){
        cout<<"yes"<<endl;
        continue;
    }
    
    cout<<"no"<<endl;
 
}
return 0;

}