CHEFSTR1 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest Link

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

DIFFICULTY:

Cakewalk

PREREQUISITES:

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.

Our final answer is

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

FINAL TIPS:

Don’t forget to use long long ints !!

SOLUTION:

Setter Code
2 
#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
3

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

1 Like
4

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)
5

oops thats right, fixing it.

6

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;
}
7

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
8

why long long int is required?

2 Likes
9

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

2 Likes
10

okay,thanx!

2 Likes
11

Thank you @jay_1048576 . It’s working.

12

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;
        }
13

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

1 Like
14

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

1 Like
15

sum needs to be long long, not i and j

16

Use long long for the variables sum and diff.

1 Like
17

yaaaa corrected it Thanks

18

Thanks :slight_smile:

21 
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
22 
#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’
what(): std::bad_alloc

Thanks in advance