ARRPAL - Editorial

PROBLEM LINK:

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

Author: Jeevan Jyot Singh
Tester: Tejas Pandey
Editorialist: Nishank Suresh

DIFFICULTY:

1594

PREREQUISITES:

Observation

PROBLEM:

You are given an array A. In one move, you can add 1 to any prefix of A. Find the minimum number of moves needed to make A a palindrome, or report that it is impossible to do so.

EXPLANATION:

Consider a second array B, where B_i denotes the number of times 1 was added to A_i during our operations. That is, the i-th element of the final array is A_i + B_i.

It’s obvious that B is a decreasing array (B_i \geq B_{i-1} for every i \gt 1), and the number of operations performed is exactly B_1. Our aim is to minimize B_1.

The final array should be a palindrome. So, if we consider some index i (1 \leq i \leq N/2), we want

A_i + B_i = A_{N+1-i} + B_{N+1-i}

Now, note that performing a move on a prefix larger than N/2 is pointless and can always be replaced by a shorter move that achieves the same result (do you see how?).

So, we can assume B_i = 0 for i \gt N/2. In particular, our equation above for a fixed index i changes to

A_i + B_i = A_{N+1-i}

Notice that this fixes the value of B_i, so we just need to check whether the B_i we obtain this way is a valid array or not.

Hence, the final solution is as follows:

  • For each 1 \leq i \leq N/2, compute B_i = A_{N+1-i} - A_i.
  • If B is not a decreasing array, or any element of B is \lt 0, then it is impossible to make A a palindrome and the answer is -1.
  • Otherwise, the answer is simply B_1.

TIME COMPLEXITY

\mathcal{O}(N) per test case.

CODE:

Setter's code (C++)
#ifdef WTSH
    #include <wtsh.h>
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define dbg(...)
#endif

#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;

// -------------------- Input Checker Start --------------------

long long readInt(long long l, long long r, char endd)
{
    long long x = 0;
    int cnt = 0, fi = -1;
    bool is_neg = false;
    while(true)
    {
        char g = getchar();
        if(g == '-')
        {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if('0' <= g && g <= '9')
        {
            x *= 10;
            x += g - '0';
            if(cnt == 0)
                fi = g - '0';
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if(g == endd)
        {
            if(is_neg)
                x = -x;
            if(!(l <= x && x <= r))
            {
                cerr << "L: " << l << ", R: " << r << ", Value Found: " << x << '\n';
                assert(false);
            }
            return x;
        }
        else
        {
            assert(false);
        }
    }
}

string readString(int l, int r, char endd)
{
    string ret = "";
    int cnt = 0;
    while(true)
    {
        char g = getchar();
        assert(g != -1);
        if(g == endd)
            break;
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}

long long readIntSp(long long l, long long r) { return readInt(l, r, ' '); }
long long readIntLn(long long l, long long r) { return readInt(l, r, '\n'); }
string readStringSp(int l, int r) { return readString(l, r, ' '); }
string readStringLn(int l, int r) { return readString(l, r, '\n'); }
void readEOF() { assert(getchar() == EOF); }

vector<int> readVectorInt(int n, long long l, long long r)
{
    vector<int> a(n);
    for(int i = 0; i < n - 1; i++)
        a[i] = readIntSp(l, r);
    a[n - 1] = readIntLn(l, r);
    return a;
}

// -------------------- Input Checker End --------------------

int sumN = 0;

void solve()
{
    int n = readIntLn(1, 3e5);
    sumN += n;
    vector<int> a = readVectorInt(n, 1, 1e9);
    vector<int> d;
    for(int i = 0; i <= n / 2 - 1; i++)
        d.push_back(a[n - 1 - i] - a[i]);
    if(*min_element(d.begin(), d.end()) >= 0 and is_sorted(d.rbegin(), d.rend()))
        cout << d[0] << endl;
    else
        cout << -1 << endl;
}

int32_t main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
    int T = readIntLn(1, 1e5);
    for(int tc = 1; tc <= T; tc++)
    {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    assert(sumN <= 3e5);
    readEOF();
    return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin >> t;
	while(t--) {
	    int n;
	    cin >> n;
	    int a[n];
	    for(int i = 0; i < n; i++) cin >> a[i];
	    int b[n];
	    memset(b, 0, sizeof(b));
	    for(int i = 0; i < n/2; i++) b[i] = a[n - 1 - i] - a[i];
	    int bad = 0;
	    if(b[0] < 0) bad = 1;
	    for(int i = 1; i < n; i++)
	        if(b[i] > b[i - 1] || b[i] < 0) bad = 1;
	    if(bad) cout << "-1\n";
	    else cout << a[n - 1] - a[0] << "\n";
	}
	return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in reversed(range(n//2)):
        a[i] += ans
        if a[i] > a[n-1-i]:
            ans = -1
            break
        ans += a[n-1-i] - a[i]
    print(ans)
1 Like

When i was solving this in contest in java, for input, it was giving output as a box, and making it WA in each case…
image

ayyyoo why it gave WA. i check for palindrome or not if yes cout 0 else check if ascending or not if yes max-min else -1

bool check(ll a[], ll n){{
ll flag = 0;
for(int i=0; i<n/2 && n!=0; i++){
if(a[i] !=a[n-i-1]){
flag = 1;
break;
}
}
if(flag == 1)
return false;
else return true;
}

}

int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//this is fast I/O (inputput output) use header file <cstdio>
ll t;cin>>t;
while(t--){
    ll n;cin>>n;
    ll a[n];
    vector<ll>v;
    for(int i=0; i<n; i++){
        cin>>a[i];
        v.push_back(a[i]);
    }
    if(check(a,n))
        cout<<0<<endl;
    else{
        sort(v.begin(),v.end());
        int flag = 0;
        for(int i=0; i<n; i++){
            if(a[i]!=v[i]){
                flag = 1;
                break;
            }
        }
        if(flag == 1){
            cout<<-1<<endl;
        }
        else{
            ll maxi = *max_element(v.begin(),v.end());
            ll small = v[0];
            cout<<maxi-small<<endl;
        }
    }
}
return 0;

}

One test case is failing. Can anybody figure out where my code went wrong?

while (T-- > 0)
{
int N = io.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++)
{
arr[i] = io.nextInt();
}

	    boolean ok = true;
	    boolean diffZero = false;
	    if (N == 1)
	    {
	        pw.println(0);
	    }
	    else
	    {
	        int max_moves = arr[N-1] - arr[0];
	        if (max_moves < 0)
	        {
	            pw.println(-1);
	            
	        }
	        else
	        {
	            int left = 1;
	            int right = N-2;
	            while (left < right)
	            {
	                int diff = arr[right] - arr[left]; 
	              //  
	                if (diff < 0 || diff > max_moves || diffZero == true && diff != 0)
	                {
	                    pw.println(-1);
	                    ok = false;
	                    break;
	                }
	                if (diff == 0)
	                {
	                   diffZero = true; 
	                }
	                left++;
	                right--;
	            }
	            if (ok)
	            {
	               pw.println(max_moves);
	            }
	        }
	        
	        
	        
	    }
	    
	    
	}

Can anyone tell me where my code gone wrong?
Only 1 test case is failing…

#include
#define ll long long

using namespace std;

int main() {
// your code goes here
ll t;
cin>>t;
while(t–)
{
ll n;
cin>>n;
ll arr[n];
ll a = n-1,x=1,c1,arr1[n];
for(ll i=0; i<n;i++)
cin>>arr[i];
for(ll i=0;i<n/2;i++)
{
if(arr[i]-arr[a]>0)
{
x = 0;
}
arr1[i] = arr[a] - arr[i];
a–;
}
for(ll i=1;i<n/2;i++)
{
if(arr1[0]<arr1[i])
{
x = 0;
}
}
c1 = arr[n-1] - arr[0];
if(n==1)
{
cout<<0<<endl;
}
else
{
if(x)
cout<<c1<<endl;
else
cout<<-1<<endl;
}
}
return 0;
}

1
8
20 22 19 20 20 23 24 24
check for this I hope you understand

2 Likes

for this the answer should be -1 right?

yes

Why its failing on 1 test case
had done the same approach as the editorial

int32_t main(){
    int t=1;
    cin>>t;
    while(t--){
      int n;
      cin>>n;
      int arr[n];
      for (int i = 0; i < n; ++i)
      {
          cin>>arr[i];
      }
      if(n==1){
        cout<<-1<<endl;
        continue;
      }
      int arr1[(n/2)+1]={0};
       arr1[0]=int_max;
      int t=true;

      for(int i=0;i<n/2;i++){
       int k=arr[n-i-1]-arr[i];
      // cout<<k<<endl;
       if(k<=arr1[i] and i!=0){
        arr1[i+1]=k;
      }
      else if(k<0){
        cout<<-1<<endl;
          t= false;
         break;
      }
      else if(k<=arr1[i] and i==0){
        arr1[i+1]=k;
      }
      else{
         cout<<-1<<endl;
          t= false;
         break;
      }
  }
      if(t){
        int p=*max_element(arr1+1,arr1+(n/2)+1);
        cout<<p<<endl;
      }
    }
    return 0;
}

f’kin if else shit
could have passed that test case.

What did you fix ? My code was also failing on only testcase 1 for some reason ?

changed that else if(k<0){ cout<<-1<<endl; t= false; break; }

and if(k<=arr1[i] and i!=0){ arr1[i+1]=k; }

basically it was checking for k<= arr1[i] even if it(k) was negative so that if condition was executed first .
now changed that it else if part and brought that condition for checking in the first place so now my all test cases are AC.

#include <bits/stdc++.h>

  

using namespace std;

#define ll long long int

#define pb push_back

#define srt(v) sort(v.begin(),v.end());

#define srtr(v) sort(v.rbegin(),v.rend());

#define loop(i,a,n) for(int i=a;i<n;i++)

#define loopr(i,a,n) for(int i=a;i>=n;i--)

#define FIO std::ios_base::sync_with_stdio(0); cin.tie(0);

ll mod = pow(10, 9) + 7;

   

void solve()

{

    int n;cin>>n;

    vector<int>v(n),temp;

    loop(i,0,n) cin>>v[i];

    if(n==1) {cout<<0<<endl;return ;}

    loop(i,0,n/2)

        temp.pb(v[n-i-1]-v[i]);

    if(!is_sorted(temp.rbegin(),temp.rend()))

        {cout<<-1<<endl;return;}

        for(auto i:temp) cout<<i<<" ";

    // cout<<temp[0]<<endl;

}

  

int main()

{

   FIO

    int t;

    cin>>t;

    while(t--)

      solve();

}

why is my code is failing on one test case

YES

Why my code is failing fr only one test case??

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

int main() {
	// your code goes here
	int t,n;
	cin>>t;
	while(t--)
	{
	    int d=0,i,j,dmax=0;
	    bool flag=true;
	    int c=0;
	    int bf=0;
	 cin>>n;
	 int a[n];
	 for( i=0;i<n;i++) cin>>a[i];
	 i=0,j=n-1;
	 while(i<j)
	 {
	     if(a[i]+d!=a[j])
	     {
	         if(a[i]>a[j])
	         {
	             flag=false;
	             break;
	         }
	         else
	         {
	          d=a[j]-a[i];
	          dmax=max(d,dmax);
	         }
	     }
	     i++;j--;
	 }
	 if(!flag) cout<<-1<<endl;
	 else cout<<dmax<<endl;
	}
	return 0;
}