PROBLEM LINK:
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;
}