CMPRSS Editorial

PROBLEM LINK:

Practice
Contest

Tester: Kasra Mazaheri
Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

You are given a strictly increasing sequence of integers A_1,A_2,…,A_N. Your task is to compress this sequence.

The compressed form of this sequence is a sequence of ranges separated by commas (characters ‘,’).

A range is either an integer or a pair of integers separated by three dots.

For each maximal contiguous subsequence (a,a+1,…,b) of A such that b≥a+2, the compressed form of A must contain the range `a...b` ;

if b≤a+1, such a sequence should not be compressed into a range.

You need to output the compressed form of A.

DIFFICULTY:

Cakewalk

CONSTRAINTS

1 \leq N \leq 100

A is sorted

EXPLANATION:

Since we have our array (sequence) sorted, let’s find our ranges starting from the first (smallest) element.

We start with an iterator pointing to the first element, then we keep moving this iterator forward while the numbers are increasing by exactly 1. We stop in case we encounter an increment of more than 1 or in case we exhaust the list.

We should check how many times the iterator has moved, if it moved for 2 or fewer moves then we don’t need to compress anything. Otherwise, we compress the range by appending the starting element of the iteration process and the one before the element we stopped at (of course we plug in dots between them).

After appending the range into our compressed list, we start a new iteration process (similar to the one we started with at the first element) from the element we stopped at.

It’s highly recommended to check implementations for more details.

Complexity: O(N)

Editorialist solution
#include<bits/stdc++.h>
using namespace std;
int main(){
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		int arr[500];
		for(int j = 1 ; j <= n ; j++)
			cin>>arr[j];
		sort(arr+1,arr+1+n);
		bool f = 1;
		for(int j = 1 ; j <= n ;){
			int i = j + 1;
			while(i <= n && arr[i] == arr[i-1] + 1)
				i++;
			if(!f) cout<<',';
			f = 0;
			if(i - j > 2)
				cout<<arr[j]<<"..."<<arr[i-1];
			if(i - j == 2)
				cout<<arr[j]<<','<<arr[j+1];
			if(i - j == 1)
				cout<<arr[j];
			j = i;
		}
		cout<<endl;
	}
}
Tester Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 109;
int q, n, A[N];
int main()
{
	scanf("%d", &q);
	for (; q; q --)
	{
		scanf("%d", &n);
		for (int i = 1; i <= n; i ++)
			scanf("%d", &A[i]);
		for (int i = 1; i <= n;)
		{
			if (i > 1)
				printf(",");
			int j = i + 1;
			while (j <= n && A[j] - A[i] == j - i)
				j ++;
			if (j - i >= 3)
				printf("%d...%d", A[i], A[j - 1]), i = j;
			else
				printf("%d", A[i]), i ++;
		}
		printf("\n");
	}
	return 0;
} 
2 Likes

#include
using namespace std;
int main()
{
int t,n;
cin>>t;
while(t–)
{
cin>>n;
int a[n+1];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int c=0;
a[n]=0;
for(int i=0;i<n;i++)
{
if(a[i+1]-a[i]==1)
c++;
else
{
if(c!=1&&c!=0)
cout<<a[i-c]<<"…";
else if(c==1)
cout<<a[i-c]<<",";

		cout<<a[i];
		if(i!=n-1)
		cout<<",";
		c=0;
		
	}
	
}
cout<<endl;

}

return 0;
}
Why am I getting a runtime error :frowning:

Why does my code give WA - CodeChef: Practical coding for everyone
@chefvijju

Can anyone please tell me why i getting NZEC for below solution.
https://www.codechef.com/viewsolution/30870345

can anybody please give a understandable solution

Solved it using stacks…
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(false);
#define endl “\n”
#define gc getchar
void scanint(int &x)
{
register int c = gc();
x = 0;
for(;(c<48 || c>57);c = gc());
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}
int main()
{
fast;
int t;scanint(t);
while(t–)
{
int n;
scanint(n);
int a[n];
stack s;
for(int i=0;i<n;i++)
{
scanint(a[i]);
if(s.empty()) s.push(a[i]);
else
{
if(s.top()+1==a[i]) s.push(a[i]);
else
{
int l=s.size();
int x=s.top();
while(s.size()!=1)
{
s.pop();
}
int y=s.top();
s.pop();
s.push(a[i]);
if(l>2)
{
cout<<y<<"…"<<x<<",";
}
else if(x==y) cout<<x<<",";
else cout<<y<<","<<x<<",";
}
}
}
if(!s.empty())
{
int l=s.size();
int x=s.top();
while(s.size()!=1)
{
s.pop();
}
int y=s.top();
s.pop();
if(l>2)
{
cout<<y<<"…"<<x;
}
else if(x==y) cout<<x;
else cout<<y<<","<<x;
cout<<endl;
}
}
return 0;
}

HERE’S A SIMPLE CODE FOR Y’ALL…

#include <bits/stdc++.h>

using namespace std;

int main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);

int t; cin>>t;
while(t--){
    int n; cin>>n;
    int arr[n];
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    string s = "";
    int mn = 1001;
    int mx = -1;
    int k = n;
    while(k--){
        int count=0;
        for(int j=mx+1; j<n; j++){
            if(arr[j]+1==arr[j+1]){
                count++;
                mn=min(j, mn);
                mx=max(j,mx);
            }
            else{
                if(mn==1001)
                    mn=j;
                mx++;
                break;
            }
        }
        if(count>=2){
            string fs=to_string(arr[mn]);
            string ls=to_string(arr[mx]);
            string cchk = to_string(arr[n-1]);
            if(ls != cchk){
                s += fs + "..." + ls + ",";
            }else{
                s += fs + "..." + ls;
            }
        }
        else{
            for(int z=mn; z<=mx; z++){
                string zs=to_string(arr[z]);
                if(z!=n-1){
                    s += zs + ",";
                }else{
                    s += zs;
                }
            }
        }
        mn = 1001;
        string c = to_string(arr[n-1]);
        string b = to_string(s.back());
        if(b==c){
            break;
        }
    }
    cout << s << "\n";    
}
return 0;

}

1 Like

In python programming it’s very easy