codechef KOL15C

QUESTION LINK - https://www.codechef.com/problems/KOL15C

my code is generating TLE, can't understand what to do
#include<stdio.h>
int main()
{
	int  N,U,a,b,i;
	scanf("%d%d",&N,&U);
	int A[N];
	for(i=0;i<N;++i)
	{
		A[i]=0;
	}
	while(U--)
	{
		scanf("%d%d",&a,&b);
		for(i=0;a*i+b-1<N;++i)
		{
			A[a*i+b-1]++;
		}
	}
	for(i=0;i<N;++i)
	{
		printf("%d ",A[i]);
	}
	return(0);
}
codechef c

Asked by: Shubrojyoti_Karmakar on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.

3 Answer(s)

Yes, Normal Brute force will result in TLE. Because since your N is of order 10^5 and number of updates is 2*10^5 thus in worst case scenario your code will be performing 2*10^10 iterations. Time Complexity of your code is O(U*N). Thus will result in Time Limit Exceeded Error.

To solve this we have a standard algorithm called Mo's Algorithm which is a special case of Square Root Decomposition. The time complexity of this algorithm is O((U+N)*sqrt(N)). Which will easily pass in 1 sec.

Happy Coding :)

Rishabh_Sethi last updated on April 7, 2019, 6:34 p.m. 0 Reply Upvote

I don't this MO's is necessary over here.

Just find the range of L and R (depending upon x) where update is required for each query and then add +1 to arr[L]

and add -1 to arr[R+1].

Do this for all the queries.

At the end do a prefix sum to get the final array.

A similar question was done in Wednesday's class.

Shubham_Kumar_Gupta last updated on April 7, 2019, 6:34 p.m. 0 Reply Upvote

sorry i misread the question.I thought the question asked to update all indices.But the questions asks to update only those indices which satisfies the equation.

@lostground97 is right.

Shubham_Kumar_Gupta last updated on April 7, 2019, 6:34 p.m. 0 Reply Upvote

Instruction to write good question

1. Write a title that summarizes the specific problem
2. Pretend you're talking to a busy colleague
3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.

codechef KOL15C

Enter your answer details below:

Enter your comment details below:

3 Answer(s)

Instruction to write good question