I have a small clarification on the problem CHEFSTEP ( CHEFSTEP Problem - CodeChef ).
It is a trivial problem which can be solved in O(N) time. We have to perform just the mod operation for N numbers (in each test case).
I first choose to solve it by just taking one integer at a time as input, processing it, and printing the output (which takes O(1) space complexity).
But when I do this I get TLE.
The same logic, if I input all the N elements in a array first completely, and process it for generating output, I got the solution accepted in 0.36 seconds.
So this takes O(N) space complexity.
Though both take O(N) time, the first solution (TLE) is more space efficient, but still TLE.
Can anyone help me please.
Ignore my post - @carre’s post below hits the nail on the head
Interesting one: with local testing on a large, dummy testfile, your AC solution (on my laptop) is a little over 2x faster than your TLE one, though this wouldn’t account for a TLE instead of an AC when your AC is only taking 0.36 seconds.
The reason the AC is faster is doubtless due to some low-level stuff like cache locality and suchlike: operating on an array of things in one fell sweep is going to be faster than read-tiny-bit-of-input-process-tiny-bit-of-input-output-tiny-result.
Can you try this variant of your TLE one? It should make the output slightly faster - perhaps enough to make your TLE into an AC. (On my laptop, the version below is roughly as fast as your AC solution):
#include<iostream>
using namespace std;
int main()
{
long long int t,n,k,d,index;
long long temp;
cin >> t;
while(t--)
{
cin >> n >> k;
string output;
output.reserve(n);
for(index=0;index<n;index++)
{
cin >> temp;
if(temp%k==0)
{
output.push_back('1');
}
else
{
output.push_back('0');
}
}
cout << output << endl;
}
return 0;
}
I think the problem can be related to the flushing of the output. As said here by default cin is tied to cout, that means that before every cin operation the output is flushed and that takes time.
In your TLE approach you are alternating cin and cout operations so you flush the output every time.
Solution: untie the input and output including this line
cin.tie(NULL)
Thank you so much, yes it is actually a tiny bit faster. So I think as we are storing it completely as a string and writing it only once on the output file for each test case, it is faster.
