WEIRDO - Editorial

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;
}
10 Likes

nice problem.never thought of using log!

5 Likes

Loved the editorial and problem as well

2 Likes

For each 1≤l<r≤|s|1≤l<r≤|s|, the substring sl,sl+1,…,srsl,sl+1,…,sr contains at least as many vowels as consonants. The letters ‘a’, ‘e’, ‘i’, ‘o’, ‘u’ are vowels, while the other letters are consonants.
====================================MEANS====================================
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.

2 Likes

U can see my code : https://www.codechef.com/viewsolution/27811491

Read from line 334

the logarithms trick got shit done for me. Thanks Pal!

Can Anyone explain this part. I am not getting this part

Can Please help what is wrong in this!!!
Please.

https://www.codechef.com/viewsolution/27883656

I’m wrong at something but can’t find please help me regarding this.
Thanks in advance

https://www.codechef.com/viewsolution/27888817

Here’s my code and I don’t know on which test cases is my code failing. Please help.
The code has comments to explain each prcocess.
https://www.codechef.com/viewsolution/27889671

You are not correctly sorting the recipes into Alice and Bob. The problem states that Alice’s recipe should have “atleast as many vowels as consonants for each substring
You are considering the whole string and not each substring.
Consider the string: aababa
In this case, the substring bab has more consontants than vowels, and hence it belongs to Bob
However, your code classifies Alice’s recipe.
Go through the explanation above by @jawa2code on this thread. That will solve your problem.

3 Likes

Thanks Michael. This editorial made my evening/

1 Like

Thanks a lot @shridharravi97

1 Like

Hello Shridar, can you please help with understanding how the sub-string is taken into consideration. The condition you mention can be found using regular expression, however I am having trouble understanding how for example, ‘aba’ will be Alice recepe ? sub-string ‘b’ has more consonants than vowels. I am not getting this condition for sub-string 1≤l<r≤|s. Can you please help.

basically the mask is keeping track if a char is already counted in the string or not the binary represntation will tell if the char is already counted or not
000000…111 we know that ‘a’ ‘b’‘c’ is already counted for the particular string so no need to count
u can also create a boolean array of length 26 for each correponding char and mark true if its already counted and if its false increment it and mark it true

Yes, ‘aba’ will belong to Alice’s recipe since the condition holds true for every substring

Since l<r we can never have a substring of length 1.

2 Likes

A good question and an excellent editorial along with awesome code. Masking and Logarithm made my day. Thanks a lot.

1 Like

@ssrivastava990 I have modified your code , instead of log I have used boost library but its not giving correct answer
Link to solution

#include<bits/stdc++.h>
#include<boost/multiprecision/cpp_dec_float.hpp>
using namespace boost::multiprecision; 
using namespace std;
#define bigf50 cpp_dec_float_50
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<cstdio>
#define MAX 10000001
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstring>

#include<cstdlib>
#include<cassert>
#include<unordered_map>
#define ll long long
#define lld long double
#define lli long long int
#define fd(n)       fixed<<setprecision(n)
#define pb push_back
#define INF 1000000000
#define mod 1000000007
#define MOD 1000000007
//#define mp make_pair
#define loop(i,n) for (lli i = 0; i < n; i++)
#define FOR(i,a,b) for (lli i = a; i < b; i+=1)
#define loop_rev(i,n) for (lli i = n-1; i >= 0; i--)
#define FOR_REV(i,a,b) for (lli i = a; i >= b; i--)
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define F first
#define S second
#define mii map<lli,lli>
#define vi vector<lli>
#define vvi vector<lli>
#define itr :: iterator it
#define WL(t) while(t --)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (a/gcd(a,b))*b
#define abs(x) ((x < 0)?-(x):x)

#define print(x) printf("%lli\n",x);
#define print2(x,y) printf("%lli %lli\n",x,y);
#define print3(x,y,z) printf("%lli %lli %lli\n",x,y,z);

#define scan(x) scanf("%lld",&x);
#define scan2(x,y) scanf("%lld %lld",&x,&y);
#define scan3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z);

#define scanarr(a,n) for(lli i=0;i<n;i++)    cin>>a[i];
#define scanvector(a,n) for(lli i=0;i<n;i++){ lli x ; cin>>x; a.push_back(x);}

#define printarr(a,n) for(lli i=0;i<n;i++)   printf("%lli ",a[i]); printf("\n");
#define printvector(a,n) for(lli i=0;i<n;i++)   printf("%lli ",a[i]); printf("\n");

#define YES printf("YES\n");
#define Yes printf("Yes\n");
#define yes printf("yes\n");
#define NO  printf("NO\n");
#define No  printf("No\n");
#define no  printf("no\n");

#define endl '\n'

#define deb(x) cout<<#x<<" "<<x<<endl;

bool is_even(lli n){ return(n%2==0);}

bool is_odd(lli n){ return(n%2==1);}

bool is_vowel(char ch){ return(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');}


bool ALICE(string s){
    if(s.length()==2){
        lli flag=0;
        if(is_vowel(s[0]) || is_vowel(s[1]))
            flag=1;
        if(flag)
            return true;
        return false;
    }
    
    else{
        lli mylen = s.length();
        lli flag=0;
        loop(i,mylen-2){
            flag=0;
            if(is_vowel(s[i]))
                flag++;
            if(is_vowel(s[i+1]))
                flag++;
            if(is_vowel(s[i+2]))
                flag++;
            if(flag<=1)
                return false;
        }
        return true;
    }
}



lld antilog10(lld x){
    return(pow(10,x));
}

int main(){
fastIO
lli t=1;
cin>>t;
while(t--){
        lli n;
        cin>>n;
        string arr[n];
        loop(i,n){
            cin>>arr[i];
        }
        vector<string>vec1,vec2;
        loop(i,n){
            if(ALICE(arr[i]))
                vec1.pb(arr[i]);
            else
                vec2.pb(arr[i]);
        }
        lli szvec1 = vec1.size();
        lli szvec2 = vec2.size();
        
        lli freqa[26]={0} , totalfreqa[26]={0} , freqb[26]={0} , totalfreqb[26]={0};
        
        loop(i,szvec1){
            map<char,lli> tempo;
            for(lli j=0;j<vec1[i].length();j++){
                totalfreqa[vec1[i][j]-'a']++;
                tempo[vec1[i][j]]=1;
            }
            for(auto xt : tempo){
                freqa[xt.first - 'a']++;
            }
        }
        
        loop(i,szvec2){
            map<char,lli> tempo;
            for(lli j=0;j<vec2[i].length();j++){
                totalfreqb[vec2[i][j]-'a']++;
                tempo[vec2[i][j]]=1;
            }
            for(auto xt : tempo){
                freqb[xt.first - 'a']++;
            }
        }
        bigf50 logansa = 1,logansb=1;
        loop(i,26){
            if(freqa[i]){
                logansa *= freqa[i]/(pow(totalfreqa[i],szvec1));
            }
            if(freqb[i]){
                logansb *= freqb[i]/(pow(totalfreqb[i],szvec2));
            }
        }
        // cout<<logansb<<endl;
        // cout<<logansa<<endl;
        bigf50 finalans=0;
        bigf50 ratio = 0;
        if(logansb==0){
            ratio = 2e7;
        }
        else{
            ratio = logansa/logansb;
        }
        if(ratio>1e7){
            cout<<"Infinity\n";
        }
        else{
            finalans = ratio;
            cout<<fd(12)<<finalans<<endl;
        }
    }
return 0;
}
1 Like

Why getting wrong answer, even after using boost library cpp_dec_float_50 ?