PROBLEM LINK:
Author: Rajendra Prajapat,Amitabh Paliwal
Tester: Amitabh Paliwal
Editorialist: Rajendra Prajapat
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Hashing, Strings
PROBLEM:
Given a string, If in this string there exist exactly 3 dashes(-) between every pair of numbers that add up to 11, then print “YES”, else print “NO”.
QUICK EXPLANATION:
We iterate over the string and collect the indices at which numbers are present, then we iterate over this new list and check whether exactly three dashes exist between all the indices at which the sum of values equals eleven or not.
EXPLANATION:
First store the indices of dashes in following way-
if(in[i]=='-')
{
B[i] = B[i-1]+1;
}
else
{
B[i] = B[i-1];
}
Then store the indices of numbers in another array of vectors of int type with size 12.
vector<int> vv[12];
if(in[i] >= '0' and in[i] <='9')
{
vv[in[i]-'0'].push_back(i);
}
Then traverse the string again and check the following condition-
if(in[i] >= '0' and in[i] <='9')
{
int x = in[i]-'0';
int y = 11-x;
int pkr =0;
while(!vv[y].empty() && vv[y].size()>pkr)
{
ones=1;
int lk = vv[y][pkr];
if(abs(B[lk]-B[i])!=3)
{
yes = 0;
break;
}
pkr++;
}
}
SOLUTIONS:
Setter's Solution
#include<iostream>
#include<string>
#include<vector>
using namespace std;
typedef unsigned long long ull;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
{
string in;
cin>>in;
int len = in.length();
vector<int> vv[12];
int B[len];
for(int i=0;i<len;i++)
{
if(in[i] >= '0' and in[i] <='9')
{
vv[in[i]-'0'].push_back(i);
}
if(i==0)
{
B[0]=0;
}
else if(in[i]=='-')
{
B[i] = B[i-1]+1;
}
else
{
B[i] = B[i-1];
}
}
bool yes = 1;
bool ones = 0;
for(int i=0;i<len;i++)
{
if(in[i] >= '0' and in[i] <='9')
{
int x = in[i]-'0';
int y = 11-x;
int pkr =0;
while(!vv[y].empty() && vv[y].size()>pkr)
{
ones=1;
int lk = vv[y][pkr];
if(abs(B[lk]-B[i])!=3)
{
yes = 0;
break;
}
pkr++;
}
}
}
if(yes and ones)
{
cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
}
}