Minions and Voting

general
1

Can someone help me in this question, I’m getting partial correct

Here is my partial correct solution.
https://www.codechef.com/viewsolution/43044692

2

The fact that you are counting the number of votes that the i^{th} minion gets while iterating is what makes the solution slow. This approach has a time complexity of O(n^{2}). If instead you just update the number of votes of the minions the i^{th} minion can give its vote to, that makes the solution fast enough because it allows you to break the loop the moment you can’t vote a minion on a particular side (refer to editorial for time complexity and further explanations :slight_smile: ).

YOUR AC CODE WITH THE ABOVE CHANGES MADE: 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        long long int s[n],sum[n],su=0;
        for(int i=0;i<n;i++)
        {
            cin>>s[i];
            su+=s[i];
            sum[i]=su;
        }
        vector<int> votes(n,0);
        for(int i=0;i<n;i++)
        {
            for(int j=i-1; j>=0; j--) {
                if(s[i] >= sum[i]-sum[j]-s[i]) {
                    votes[j]++;
                }
                else break;
            }
            for(int j=i+1; j<n; j++) {
                if(s[i] >= sum[j]-sum[i]-s[j]) {
                    votes[j]++;
                }
                else break;
            }
        }
        for(int v : votes) cout << v << " ";
        cout<<"\n";
    }
}
1 Like
3

I checked the editorial but didn’t understood from there.
Thanks BTW. :grin: :grin: