 # CHEFSTR1 - Editorial

Author: Aryan Agarwala
Tester: Encho Misev
Editorialist: Rajarshi Basu

Cakewalk

Implementation

# PROBLEM:

We are given a list of N numbers A_1,A_2, \dots A_n. We have to go from A_i to A_{i+1} in the i^{th} step. What is the total number of integers we skip in the process?

# EXPLANATION:

The solution for this is just essentially counting in constant time the number of integers we skip in each iteration:

• S_i = |A_{i+1} - A_i | - 1
• notice that we have to take modulus here, since we can go to a smaller integer as well.

• ANS = \sum\limits_{i=1}^{n}{S_i}

# FINAL TIPS:

Don’t forget to use long long ints !!

# SOLUTION:

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

int main() {
int t;
cin >> t;
while(t--){
int n;
cin >> n;

long long arr[n];
for(int i=0;i<n;i++)cin >> arr[i];

long long ans = 0;
for(int i=1;i<n;i++)ans+=(abs(arr[i]-arr[i-1])-1);

cout << ans << '\n';
}
}
4 Likes

I think that it should be abs(A[i+1]-A[i])-1

1 Like

DO this in python :

# cook your dish here.
for _ in range(int(input())):
x = int(input())
arr = list(map(int,input().split()))
l = []
for i in range(len(arr)-1):
if arr[i+1] > arr[i]:
l.append(arr[i+1] - arr[i])
elif arr[i+1]<arr[i]:
l.append(arr[i]-arr[i+1])
m = len(l)
print ((sum(l)) - m)


oops thats right, fixing it.

Can anyone tell why this code is showing wrong answer?

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

void solve()
{
long long n,c=0;
cin>>n;
long long a[n];
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n-1;i++)
{
c+=abs(a[i+1]-a[i])-1;
}
cout<<c<<"\n";
}

int main()
{
int t;
cin>>t;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
while(t--)
solve();

return 0;
}


Use that fast io before taking t as input. There’s no point in making the ios_base unsynchronised with stdio after having already taken an input.

1 Like

why long long int is required?

2 Likes

Because the sum can be greater than 10^9. That’s why long is required

2 Likes

okay,thanx!

2 Likes

Thank you @jay_1048576 . It’s working.

Can someone please tell why was i getting partially correct during contest

int n;
cin>>n;
while(n--){
long long T;
cin>>T;
long long a[T];
for(long long i=0;i<T;i++){
cin>>a[i];
}
int sum=0;
int diff=0;
for(long long j=0;j<T-1;j++){
diff=abs(a[j+1]-a[j])-1;
sum=sum+diff;
}
cout<<sum<<endl;
}


It should also be max(^that, 0), to deal with A[i + 1] = A[i] case.

1 Like

Such cases don’t exist. See the 4th constraint.

1 Like

sum needs to be long long, not i and j

Use long long for the variables sum and diff.

1 Like

yaaaa corrected it Thanks

Thanks difference = 0
sum1=0
for i in range(int(input())):
f = int(input())
a = list(map(int,input().split()))
length = len(a)
for k in range(length-1):
difference = abs(a[k]-a[k+1])-1
sum1+=difference
print(sum1)
sum1=0

#Here's what i've done in Python 3

#include<iostream>
#include<vector>
using namespace std;
int main(){
long long t;
cin>>t;
std::vector<long long> v;
v.reserve(t+1);
while(t--){
long long n,res=0,prev;
cin>>n;
n--;
cin>>prev;
while(n--){
int z;
cin>>z;
res+=abs(prev-z)-1;
prev=z;
}
v.push_back(res);
}
cout<<*v.begin();
for(auto e=++v.begin();e!=v.end();e++){
cout<<endl<<*e;
}
return 0;
}


It is showing error:
Runtime Error
SIGABRT

Error
terminate called after throwing an instance of ‘std::bad_alloc’