0
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ A runtime error is not the same as a time-limit-exceeded message from an online judge. Please clarify which is the case. \$\endgroup\$ – Mast Oct 15 '18 at 5:41
  • 2
    \$\begingroup\$ You've used single-character variable names all over the code. This is unreadable. If you want us to review your code, there's no reason to make it unnecessarily hard. \$\endgroup\$ – Mast Oct 15 '18 at 5:44
2
\$\begingroup\$
  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.

\$\endgroup\$
-3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review. I don't understand your answer, because I can't read it. Could you try and increase it's readability by using proper English? Please use full sentences to tell us what you've found, what you've guessed and what you recommend. \$\endgroup\$ – Mast Oct 15 '18 at 5:49
  • \$\begingroup\$ ok will i take this advice as a note. \$\endgroup\$ – Aman Mittal Oct 15 '18 at 5:58
  • \$\begingroup\$ also i wanted to convey the same message as you wrote above that tle is not same as nzec(runtime error).moreover i got tle by using this approach thats why i was recommending to make a sum array to make time complecity O(n).Icouldn't elaborate more as this is a live contest and can only give you a hint \$\endgroup\$ – Aman Mittal Oct 15 '18 at 6:00
  • \$\begingroup\$ @AmanMittal As the contst has ended, can you please suggest me a solution to it now? I still haven't figured it out.. \$\endgroup\$ – Sandesh34 Oct 17 '18 at 17:55
  • \$\begingroup\$ Please refer to discuss.codechef.com/questions/137183/spread2-editorial. \$\endgroup\$ – Aman Mittal Oct 19 '18 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.