AROO21 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest

Author & Tester: Arnav Singh
Editorialist: Arnav Singh

DIFFICULTY:

EASY

PREREQUISITES:

GCD

PROBLEM:

A town consists of different streets namely a,b,…z. Its organization is given to us as a string. One normal robot could traverse only 1 street, and a jumping robot could cover the city in k-lengthed jumps (k > 1). A jumping robot could be used if and only if it covers all the streets of a specific type in its whole journey. Print the minimum number of robots used to cover every street of the city.

QUICK EXPLANATION:

  • Take a vector of vectors. In each vector, store the indices of a particular character,i.e, 1st vector contains the indices where streets of type ‘a’ is occurring.
  • Now, iterate through each vector, calculating the gcd of its elements.
  • If the gcd comes as 1 add the respective vector’s size to the answer and if not increment the answer by 1, since if gcd is greater than 1, that means a jumping robot could be introduced.

EXPLANATION:

If we focus on the condition of introducing “Jumping Robots”, we see that in its k - lengthed jump, it should cover all the occurrences of one street in one go. That indicates if we could somehow store the position of each street, we could find out if we could introduce jumping robots for a specific type of street or not.

We intend to make use of as many jumping robots as we can because that reduces the number of robots required to 1, which would otherwise be the total number of times that street has individually existed.

Initialize the answer variable with 0. After storing each index of every street in our vector of vectors, we can go through each vector and check the GCD of the elements. If the GCD comes out to be k, we could infer that if the jumping robot makes k-lengthed jumps, each occurrence of that street would be covered easily in one go. Note that the jumping ones need to skip atleast one street,i.e. k should not be equal to 1.

If k = 1, we need to use normal robots, therefore we would add the vector’s size to our answer, and if k greater than 1, only 1 jumping robot is sufficient, and we would simply increment our answer by 1. Print the answer.

SOLUTION:

C++ Solution 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define start int t; cin>>t; while(t--)

int main()
{

start
{
ll i,j,n,ans=0;
cin>>n;
string s;
cin>>s;
vector<ll> v[27];
for(i=0;i<n;i++)
{
v[s[i]-97].push_back(i);
}
for(i=0;i<26;i++)
{
if(v[i].size()>1)
{
ll d=0;
for(j=0;j<v[i].size();j++)
{
d=__gcd(v[i][j],d);
}
if(d>1)
{
ans++;
}
else
ans+=v[i].size();
}
else if(v[i].size()==1)
ans++;
}
cout<<ans<<"\n";}}
Python Solution 
import math
from sys import stdin, stdout 
import numpy as np

t = int(input())
for i in range(0, t):
    
    n = int(input())
    ans = 0
    s = input()
    ar = {}
    
    for j in range(26):
        y = j
        temp = []
        for k in range (0, n):
            x = ord(s[k]) - 97
            
            if x == y:
                temp.append(k)
    
        ar[j] = temp
    #print(ar)   
    for j in range(0, 26):
        
        if len(ar[j]) > 1:
            d = 0
            for k in range(0, len(ar[j])):
                d = math.gcd(d, ar[j][k])
            
            if d > 1:
                ans += 1 
            else:
                ans += len(ar[j])
                
        elif len(ar[j]) == 1:
            ans += 1 
            
    print(ans)

TIME COMPLEXITY:

Since we are iterating through all the n characters of the string, our time complexity would be O(N).

2 Likes