PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Akil Vohra
Tester: Yash Chandnani
Editorialist: Michael Nematollahi
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Logarithms
QUICK EXPLANATION:
For a string (recipe) to belong to Alice, it shouldn’t have two consonants next to each other or separated by only a single vowel. In other words, there has to be at least two vowels in between every two consonants.
After recognizing the above fact, calculate the score of Alice and Bob by implementing the scoring method mentioned in the statement. To avoid getting too big or too small numbers, use logarithms when multiplying or calculating powers.
EXPLANATION:
First, let’s see how to recognize if a string (recipe) belongs to Alice or Bob.
-
If there are two consonants next to each other, say at indices i and i+1, the range [i, i+1] has more consonants than vowels; hence it doesn’t belong to Alice.
-
In addition, If there are two consonants at positions i and i+2 separated by a single vowel, the range [i, i+2] contains more consonants than vowels; so in this case it doesn’t belong to Alice either.
It turns out that the above conditions are enough to check if a string belongs to Alice or not.
To rephrase the above conditions, a string belongs to Alice iff there are at least two vowels between every pair of consonants. The proof is as follows:
As described above, if the condition above is not satisfied it cannot belong to Alice. So it suffices to show that if the conditions above hold, the string belongs to Alice. That is, for every range [l, r] of the string where l < r, there are at least as many vowels as consonants.
- If s[l] is a vowel, then every consonant in [l, r] is preceded by a vowel (because there are no two consonants in a row). So we can conclude that there are at least as many vowels as consonants in this range.
- If s[l] is a consonant, s[l+1] and s[l+2] (assuming it’s within the range) are both vowels. In this case, the range [l+2, r] starts with a vowel and as argued in point one, has at least as many vowels as consonants. Hence, the range [l, r] has at least as many vowels as consonants as well.
Having figured out the above condition, we can easily check in O(|s|) if a string s belongs to Alice.
Now that we know which string belongs to whom, we can implement the scoring method described in the statement to find out the score of each person.
There’s one catch in the implementation of the scoring method. The resulting numbers can be very small or very big thanks to the large number of multiplications and divisions that we have. Too small\large in fact, that the precision of doubles (or long doubles for that matter) will not suffice. To work around this problem, instead of calculating the real scores, we calculate their logarithms and at the end convert it back to the actual number itself.
Just a little reminder that:
- log(a/b) = log(a) - log(b)
- log(a*b) = log(a) + log(b) and consequently log(a^k) = k \times log(a)
The total time complexity of this solution is O((\sum |S|) + (\sum L) \times log(MAX)), where MAX is the maximum value of x_c.
To see an implementation of this solution, refer to the editorialist’s code.
ALTERNATE APPROACH
Another way to get around the precision issue is the following:
First, identify the terms whose product is the numerator of the final quotient and add them to a vector vec_A. Similarly, form the vector vec_B for the denominator.
Note that each of these vectors will have O(L \times C) elements where C = 26 is the size of the alphabet.
Now set the final quotient q equal to 1. Then, as long as neither vec_A nor vec_B is empty, do the following:
- If q \lt 1, take an element from vec_A (while removing it) and multiply q by that element.
- Otherwise, take an element from vec_B and divide q by that element.
This way, we’re making sure the quotient doesn’t get too small or too big while exhausting vec_a and vec_B.
After taking the steps above, you can easily apply the remaining terms to q, breaking whenever it gets too big.
This approach will run in O(L \times C). Refer to the setter’s code to see an implementation (in Java).
SOLUTIONS:
Setter's Solution
import java.io.*;
import java.text.*;
import java.util.*;
class main {
public static boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
public static void main(String[] args) throws Exception {
DecimalFormat numberFormat = new DecimalFormat("0.0000000");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
int t = Integer.parseInt(br.readLine());
while(t-- != 0) {
int total = Integer.parseInt(br.readLine());
int alice_x[] = new int[26], bob_x[] = new int[26], alice_fx[] = new int[26], bob_fx[] = new int[26];
ArrayList<String> alc = new ArrayList<String>(), b = new ArrayList<String>();
int alice = 0, bob = 0;
while(total-- != 0) {
String s = br.readLine();
boolean flag = true;
for(int i = 1 ; i < s.length() - 1 ; i++) {
if(isVowel(s.charAt(i))) {
if(!isVowel(s.charAt(i - 1)) && !isVowel(s.charAt(i + 1)))
flag = false;
}
else if(!isVowel(s.charAt(i - 1)) || !isVowel(s.charAt(i + 1)))
flag = false;
}
if(s.length() == 2) {
if(!isVowel(s.charAt(0)) && !isVowel(s.charAt(1)))
flag = false;
}
int tmp_x[], tmp_fx[];
if(flag) {
tmp_x = alice_x;
tmp_fx = alice_fx;
alice++;
alc.add(s);
}
else {
tmp_x = bob_x;
tmp_fx = bob_fx;
bob++;
b.add(s);
}
boolean isCounted[] = new boolean[26];
for(int i = 0 ; i < s.length() ; i++) {
int index = s.charAt(i) - 'a';
if(isCounted[index] == false) {
tmp_x[index]++;
isCounted[index] = true;
}
tmp_fx[index]++;
}
}
int count;
ArrayList<Integer> numerator = new ArrayList<Integer>(), denominator = new ArrayList<Integer>();
for(int i = 0 ; i < 26 ; i++) {
if(alice_x[i] > 0)
numerator.add(alice_x[i]);
if(bob_fx[i] > 0) {
count = bob;
while(count-- != 0)
numerator.add(bob_fx[i]);
}
if(bob_x[i] > 0)
denominator.add(bob_x[i]);
if(alice_fx[i] > 0) {
count = alice;
while(count-- != 0)
denominator.add(alice_fx[i]);
}
}
double ratio = 1, limit_INF = 10000000, limit_ZERO = 0.0000001;
int i = 0, j = 0, N = numerator.size(), M = denominator.size();
while(i < N && j < M) {
if(ratio > 1)
ratio = ratio / denominator.get(j++);
else
ratio = ratio * numerator.get(i++);
}
boolean isInfinity = false;
while(i < N && !isInfinity) {
ratio = ratio * numerator.get(i++);
if(ratio > limit_INF)
isInfinity = true;
}
while(j < M) {
ratio = ratio / denominator.get(j++);
if(ratio < limit_ZERO)
break;
}
if(isInfinity)
pw.println("Infinity");
else
pw.println(numberFormat.format(ratio));
}
pw.flush();
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void pre(){
}
int fx[2][26],x[2][26];
bool chk(char c){
if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u') return 1;
return 0;
}
void solve(){
int n;cin>>n;
fill(fx);
fill(x);
int a = 0,b=0;
rep(q,n){
string s;cin>>s;
int p1 = 0, p2= 0,p=0;
if(sz(s)==1){
x[0][s[0]-'a']++;
fx[0][s[0]-'a']++;
}
else{
if(chk(s[0])) p2++;
else p2--;
bool fg=0;
repA(i,1,sz(s)-1){
if(chk(s[i])) p2++;
else p2--;
if(p2<p1) fg=1;
if(chk(s[i-1])) p++;
else p--;
p1=max(p1,p);
}
bool vis[26];
fill(vis);
int ix = 0;
if(fg) ix=1,b++;
else a++;
trav(i,s) {
fx[ix][i-'a']++;
if(!vis[i-'a']) vis[i-'a']=1,x[ix][i-'a']++;
}
}
}
vi v1,v2;
ld ans = 0;
rep(i,26) {
if(x[0][i]) v1.pb(x[0][i]);
if(x[1][i]) rep(j,b) v1.pb(fx[1][i]);
}
rep(i,26) {
if(x[0][i]) rep(j,a) v2.pb(fx[0][i]);
if(x[1][i]) v2.pb(x[1][i]);
}
trav(i,v1) ans+=log2(i);
trav(i,v2) ans-=log2(i);
ans = pow(2,ans);
if(ans>1e7) cout<<"Infinity\n";
else cout<<setprecision(20)<<ans<<'\n';
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
pre();
int n;cin>>n;
rep(i,n) solve();
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
#define F first
#define S second
const int MAXN = 1e5 + 10;
int n, sz[2];
string s[2][MAXN];
int cnt[2][26];
bool isVowel(char ch){
return ch == 'a' || ch == 'e' || ch == 'o' || ch == 'u' || ch == 'i';
}
bool belongsToAlice(string t){
int lst = -1;
for (int i = 0; i < (int)t.size(); i++)
if (!isVowel(t[i])){
if (lst != -1 && i-lst < 3)
return false;
lst = i;
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(12);
int te; cin >> te;
while (te--){
cin >> n;
sz[0] = sz[1] = 0;
for (int i = 0; i < n; i++){
string t; cin >> t;
if (belongsToAlice(t))
s[0][sz[0]++] = t;
else
s[1][sz[1]++] = t;
}
ld prod[2] = {0., 0.};
for (int w = 0; w < 2; w++){
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i < sz[w]; i++){
int mask = 0;
for (char ch: s[w][i]) {
int x = ch - 'a';
cnt[1][x]++;
if (!(mask>>x&1)) {
cnt[0][x]++;
mask |= 1<<x;
}
}
}
for (int i = 0; i < 26; i++)
if (cnt[1][i])
prod[w] += log(ld(cnt[0][i])) - log(cnt[1][i]) * sz[w];
}
ld ans = prod[0] - prod[1];
ans = exp(ans);
if (ans > 1e7)
cout << "Infinity\n";
else
cout << ans << "\n";
}
return 0;
}