Why it show time limit exceed still i am doing in given time
Chef and Bulb Invention
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
int n , p ,k;
cin>>n>>p>>k;
unordered_map<int , int>m;
for( int i=0; i<n; i++){
m[i%k]++;
}
int modulo = p % k;
long long int sum = 0;
for ( int i=0; i<modulo; i++){
sum+=m[i];
}
vectorans;
for( int i =0; i<n; i++){
if(i%k == modulo){
ans.push_back(i);
}
}
long long int cnt = 0;
for(int i=0; i<ans.size(); i++){
cnt++;
if( ans[i] == p){
break;
}
}
sum+= cnt;
cout<<sum<<'\n';
}
}
Chef and Bulb Invention Practice Coding Problem - CodeChef
It gets TLE because of the constraints.
Your apprach can get to loop billions of times. That’s why. (Take into consideration that Competitive Programming will always take the worst scenario)
… Do you want the solution? I can, but before spoiling you, I can say this problem can be solved in complexity O(1). You don’t need to loop. You just have to understand the concept of module.
You know how many possible modules there are.
You can know in which module p is. The problem literally tells you where p is.
Looping might be a good idea if you don’t know where your target is. But you know.
Do you need to loop to find it?
[Side technic: This problem is figuratively telling you this: Computers make your life easier, but that doesn’t mean you shouldn’t think ahead of the computers. It’s told you here:
So he has N gases numbered from 0 to N−1 that he can use and he doesn’t know which one of the N gases will work but we do know it.
If you can solve the problem yourself, do it yourself. If you can’t, let the computer do it for you. If the computer can’t, then (again) do it yourself.
According to you code, I can see you understand module concept, this is why I refuse to give you the solution. I will give you hits or advice because I believe you can find the answer youself.
1 Like