In this HackerEarth Ratio problem solution, There are 2 types of chocolates in Chocoland denoted by A and B.

The cholates are lined up in a queue. You want to satisfy your friends by distributing some number of non-empty contiguous chocolates such that the ratio of a number of type A chocolates to a number of type B chocolates is the same for all the friends. You have to distribute all the chocolates and satisfy a maximum number of friends. Therefore you have to find the maximum number of friends that can be satisfied.


HackerEarth Ratio problem solution


HackerEarth Ratio problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll t,n,cnt0,cnt1;
vector<pair<ll,ll> >v;
string c;
int main()
{
freopen("input.txt","r",stdin);
freopen("out.txt","w",stdout);
ll i,j,k;
cin>>t;
while(t--)
{
cin>>n;
cnt0=cnt1=0;
v.clear();
for(i=1;i<=n;i++)
{
cin>>j>>c;
if(c=="A")
k=0;
else
k=1;
if(k==0)
cnt0+=j;
else
cnt1+=j;
if(v.size()==0)
{
v.push_back({k,j});
}
else
{
ll lst=v[v.size()-1].first;
if(lst==k)
v[v.size()-1].second+=j;
else
v.push_back({k,j});
}
}
if(cnt0==0||cnt1==0)
{
cout<<max(cnt0,cnt1)<<"\n";
}
else
{
ll cx=0;
ll cy=0;
ll ans=0;
for(i=0;i<v.size();i++)
{
j=v[i].first;
k=v[i].second;
if((cx==0&&cy==0)||(j==0&&cy==0)||(j==1&&cx==0))
{
if(j==0)
cx+=k;
else
cy+=k;
}
else
{
if(j==0)
{
if((cnt0*cy)%cnt1==0)
{
ll req=(cnt0*cy)/cnt1-cx;
if(req<=k&&req>=0)
{
ans++;
cy=0;
cx=k-req;
}
else
{
cx+=k;
}
}
else
{
cx+=k;
}
}
else
{
if((cnt1*cx)%cnt0==0)
{
ll req=(cnt1*cx)/cnt0-cy;
if(req>=0&&req<=k)
{
ans++;
cx=0;
cy=k-req;
}
else
{
cy+=k;
}
}
else
{
cy+=k;
}
}
}
}
cout<<ans<<"\n";
}
}
return 0;
}


Second solution

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.OutputStream;
import java.io.Writer;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
FastScanner in = new FastScanner(inputStream);
FastPrinter out = new FastPrinter(outputStream);
Ration solver = new Ration();
int testCount = Integer.parseInt(in.next());
for (int i = 1; i <= testCount; i++)
solver.solve(i, in, out);
out.close();
}

static class Ration {
public void solve(int testNumber, FastScanner in, FastPrinter out) {
int n = in.nextInt();
if (n < 1 || n > 100000) throw new AssertionError();
int[] a = new int[n];
int[] type = new int[n];
long allA = 0;
long allB = 0;
for (int i = 0; i < n; i++) {
a[i] = in.nextInt();
if (a[i] < 1 || a[i] > 1000000000) throw new AssertionError();
type[i] = "AB".indexOf(in.next());
if (type[i] < 0) throw new AssertionError();
if (type[i] == 0) {
allA += a[i];
} else {
allB += a[i];
}
}
if (allA == 0 || allB == 0) {
out.println(allA + allB);
return;
}
long g = MathUtils.gcd(allA, allB);
allA /= g;
allB /= g;
long haveA = 0;
long haveB = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
int add = a[i];
if (type[i] == 0) {
ans += getAns(allA, allB, haveA, haveB, add);
haveA += add;
} else {
ans += getAns(allB, allA, haveB, haveA, add);
haveB += add;
}
}
out.println(ans);
}

private int getAns(long allA, long allB, long haveA, long haveB, int add) {
if (haveA * allB < allA * haveB && (haveA + add) * allB >= allA * haveB && allA * haveB % allB == 0) {
return 1;
}
return 0;
}

}

static class FastScanner extends BufferedReader {
public FastScanner(InputStream is) {
super(new InputStreamReader(is));
}

public int read() {
try {
int ret = super.read();
return ret;
} catch (IOException e) {
throw new InputMismatchException();
}
}

public String next() {
StringBuilder sb = new StringBuilder();
int c = read();
while (isWhiteSpace(c)) {
c = read();
}
if (c < 0) {
return null;
}
while (c >= 0 && !isWhiteSpace(c)) {
sb.appendCodePoint(c);
c = read();
}
return sb.toString();
}

static boolean isWhiteSpace(int c) {
return c >= 0 && c <= 32;
}

public int nextInt() {
int c = read();
while (isWhiteSpace(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int ret = 0;
while (c >= 0 && !isWhiteSpace(c)) {
if (c < '0' || c > '9') {
throw new NumberFormatException("digit expected " + (char) c
+ " found");
}
ret = ret * 10 + c - '0';
c = read();
}
return ret * sgn;
}

public String readLine() {
try {
return super.readLine();
} catch (IOException e) {
return null;
}
}

}

static class MathUtils {
public static long gcd(long a, long b) {
if (a < 0) a = -a;
if (b < 0) b = -b;
while (b != 0) {
long t = a % b;
a = b;
b = t;
}
return a;
}

}

static class FastPrinter extends PrintWriter {
public FastPrinter(OutputStream out) {
super(out);
}

public FastPrinter(Writer out) {
super(out);
}

}
}