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);
        }

    }
}