My solution of same time complexity O(N∗σ(N)) gave TLE. Can someone please look at it. @taran_1407 @cubefreak777
Submission Link
Your solution runs in O(n*sqrt(n)) which will actually not pass the time limit as in total it performs 3.5 x 10^8 operations more than 10^8.
`
Well i my solution was O(2Nsigma(N)) and yet it didn’t passed. After removing the factor of 2, it passed. Isn’t the time limit too strict?
Avoid using long long int it will pass.
Same result
Nope, when there are too many ones, smaller d gives lesser flips. so it depends on the number of ones I guess.
for(char c : ar) {
if(c == '1')ones++;
}
ArrayList<Integer>list = printDivisors(n); //list of all divisors of N
for(int a : list) {
int max = Integer.MIN_VALUE;
int []dp = new int[n+1];
for(int i = 0; i < n; i++) {
if(i-a < 0) {
if(ar[i] == '1') {
dp[i]++;
}
}else {
dp[i] = dp[i-a];
if(ar[i] == '1') {
dp[i]++;
}
}
max = Math.max(max, dp[i]); number of ones alredy present for this d
}
int r = n/a; // required ones for this 'd' (divisor)
int d = r-max;
int c = ones-max;
min = Math.min(min, d+c);
}
True, the time limit was too tight I think, even people who used long longs instead of int didn’t pass.
Well it’s very hard to qualitatively predict when is a long long submission going to give TLE, at least I don’t know a way to do it. The best thing to do is to stick with int unless any variable exceeds 10^9 in your code otherwise go with long long.
thank you
Your solution is \mathcal{O}(N^2) it won’t pass in time. Because while doing string concatenation you’re creating a copy of the string and it is a linear-time operation. And for a string full of zeroes your code will do quadratic amount of operations.
while(s[0]!='1'){
s=s[n-1]+s;
s.erase(n,1);
}
Could you tell me then why this is passing while this isn’t??
The only diff. between them is that is tried to reach the starting position in the latter case, whereas in the former one, i checked only untill curr<n. There isn’t diff. though i think
extremely sorry for linking the wrong submission
But if i try to reach the starting point by doing a modulo, ig thats the same thing as moving while my curr<n, since eventually i will reach the starting index.
See TLEd …
Dude time limit is crazy tight…, Anyways your code is exceeding time limit as the inbuilt modulo operation is a computationally costly operation as compared to other arithmetic operations, I used a faster way to calculate modulo and your code passes in time.
Woah!
I never took operations like modulo as being a reason for TLE.
Thanks a lot for your help !
I implemented the same logic in python/pypy I was using set to store factorials and was getting TLE and then I switched to list and stopped getting TLE, can anyone shed a light on this one.
TLE - with set: CodeChef: Practical coding for everyone
Accepted - with list: CodeChef: Practical coding for everyone
As the test cases are only 100, I am finding all the divisors of n. So this is not a problem. In the calculation of dp part, my inner loop is running till m = σ(N). So how is this N*sqrt(N). I think it is same as editorial TC, O(N∗σ(N)) where σ(N) is divisor function. Please correct me if I am wrong.