"Spread the Word" CodeChef challenge

Question

I am solving the "Spread the Word" problem on CodeChef:

Snackdown 2019 is coming! People have started to spread the word and tell other people about the contest. There are \$N\$ people numbered 1 through \$N\$. Initially, only person 1 knows about Snackdown. On each day, everyone who already knows about Snackdown tells other people about it. For each valid \$i\$, person \$i\$ can tell up to \$A_i\$ people per day. People spread the information among the people who don't know about Snackdown in the ascending order of their indices; you may assume that no two people try to tell someone about Snackdown at the same moment. Each person is only allowed to start telling other people about Snackdown since the day after he/she gets to know about it (person 1 can start telling other people already on day 1). How many days does it take for all people to know about Snackdown?

But my code exceeds the given time limit. It solves the problem in 1.01 seconds, but the time limit in there, is 1.00 seconds. I am attaching the code snippet written in C++ below:

#include<iostream>
using namespace std;
int main()
{
    int t,n;
    cin>>t; 
    for(int i = 0; i<t;i++)
        {
        int c = 0,f=0,p=1;
        cin>>n;
        int a[n];
        for(int i = 0; i<n; i++) cin>>a[i];
        f = a[0];
        while(p<n)
        {

            for(int i = 0; i<f; i++)
            {
                p += a[i];
            }
            c++;
            f = p;
        }
    cout<<c;    
    }
}

It would be a great help if someone modifies the above code into an efficient one!

Answer 1

1. Do not do using namespace std; This is a bad habbit that pollutes your namespace needlessly. You are only using std in exaclty 4 places. Its really easy to be better here.

2. Please use sensible names. Your t is the number of test runs, so name it numTests or something similar. In a month you will never know the meaning of a given variable.

3. Stay consistent in your code style. You have different styles of for loop. This is really confusing and quite frankly annoying to read.

4. The question is marked as c++ but you use plain old C here. Rather than a C-style array you should use a std::vector<int>

5. You are getting timeouts because you use a brute force approach. You should realize, that you can directly calulate the number of infomred people directly. At the first day it is a[0]. At the second day it is a[0] + a[0] + ... a[a[0]]. Consequently you can determine the number of newly informed people for every day just once and reuse that value.

Answer 2

its runtime error brother not because of time limited exceeded,it might be that in some case you are having array index out of bound exception,in this case f might exceed the maximum index value. still if there is a time limit exceeded issue just a hint make a sum array.