Finding sum of array without going through it

general
1

In SnackDown 2018, there is a question Spread the Word(Code SPREAD2). There you have to loop through an array of people(I cannot think of anything better) and sum the number of people they can tell about SnackDown iteratively. Here is my code which is getting a TLE. Please help.

#include <iostream>


int main()
{
	int t,n,know,to_know,days,sum,i;
	scanf("%d",&t);
	while(t--)
	{
		//n;
		scanf("%d",&n);
		int people[n];
		for(int i = 0; i < n; ++i)
        {
            scanf("%d",&people[i]);
        }
        know = 1,to_know = people[0],days = 0;
        while(n-know)
        {
            sum = 0,i = know;
            for(; i < know+to_know&&i < n; ++i)
            {
                sum += people[i];
            }
            know = i;
            to_know += sum;
            days++;
        }
        printf("%d\n",days);
	}
	return 0;
}
2

You’ll get to know the correct approach after 7:30 pm tomorrow.

Till then, try hard. And avoid asking for hints on forums.You might get banned for this.

1 Like
3

OK, thanks for the warning! I just saw std::accumulate(). Let’s try that! :wink:
PS BTW, I can ask for answer/approach/hints if it is not part of a competition or competition is over, right?

4

Well, I did this, but now SIGSEGV???


...
int t,n,know,to_know,days,sum;
...
  while(n-know)
  {
       sum = std::accumulate(people + know,people + (know+to_know < n? know+to_know : n) , to_know);
       know = (know + to_know < n ? know + to_know : n);
       to_know = sum;
       ++days;
   }
...

PS Waiting for answer after 7:30 pm tomorrow. :wink:

5

@jal_super123 Yes. You can ask any query after contest is over.