CV - EDITORIAL

Practice

Contest: Division 1

Contest: Division 2

Setter: Vivek Chauhan

Tester: Michael Nematollahi

Editorialist: Taranpreet Singh

Cakewalk.

PREREQUISITES:

None. Trying the problem would be enough.

PROBLEM:

Given a string S of length N, print the number of positions i such that i-th character is a consonant while i+1-th character is a vowel. The characters ‘a’, ‘e’, ‘i’, ‘o’, ‘u’.

EXPLANATION

The solution is to just check all positions i whether position i is a valid position or not. To check whether position i is valid, we need S[i] being a consonant and S[i+1] being a vowel. We can also see being a consonant as not being a vowel since each character can either be a vowel or a consonant.

This condition can be written as

 if !isVowel( S[i] ) and isVowel( S[i+1] ) ans++


Now, isVowel is a function which returns true when the character passed is a vowel. It can be checked using if-else condition or adding all vowels to set and checking if a character is present in a set of vowels.

Bonus Problem
Given a string S of length N, find the number of pairs of positions (a, b), a \leq b such that S[a] is consonant and S[b] is a vowel. N can be up to 10^5.

TIME COMPLEXITY

Time Complexity is O(N) per test case.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef int ll;
typedef long double ld;
const int N = 105;
ll inf = 1e16;
ll mod = 1e9 + 7;

char en = '\n';
ll power(ll x, ll n, ll mod) {
ll res = 1;
x %= mod;
while (n) {
if (n & 1)
res = (res * x) % mod;
x = (x * x) % mod;
n >>= 1;
}
return res;
}
bool isVowel(char c)
{
return c=='a' or c=='e' or c=='i' or c=='o' or c=='u';
}

int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

ll t;
cin>>t;

while(t--)
{
ll n;
cin>>n;
string s;
cin>>s;
s='a'+s;
ll res=0;
for(ll i=1;i<s.length();i++)
{
if(!isVowel(s[i-1]) && isVowel(s[i]))
res++;
}
cout<<res<<en;
}
}

Tester's Solution
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define F first
#define S second

bool mark[200];

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
mark['a'] = mark['e'] = mark['o'] = mark['i'] = mark['u'] = true;
int te;	cin >> te;
while (te--){
int n, ans = 0;
string s;
cin >> n >> s;
for (int i = 1; i < n; i++)
if (mark[s[i]] && !mark[s[i-1]])
ans++;
cout << ans << "\n";
}
return 0;
}

Editorialist's Solution
import java.util.*;
import java.io.*;
class CV{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), cnt = 0;
String s = n();
for(int i = 1; i< n; i++)
if(!isVowel(s.charAt(i-1)) && isVowel(s.charAt(i)))
cnt++;
pn(cnt);
}
boolean isVowel(char c){
switch(c){
case 'a':
case 'e':
case 'i':
case 'o':
case 'u':
return true;
default:return false;
}
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new CV().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{