BNSONSTR - Editorial

editorial
, ,
26

My solution of same time complexity O(N∗σ(N)) gave TLE. Can someone please look at it. @taran_1407 @cubefreak777
Submission Link

27

My solution’s complexity was the same as editorial but why it gives TLE? @cubefreak777

28

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.

`

29

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?

30

Avoid using long long int it will pass.

32

Same result

34

@cubefreak777 when can we find out that long long will give TLE ?

35

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);
             }
36

True, the time limit was too tight I think, even people who used long longs instead of int didn’t pass.

37

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.

2 Likes
38

thank you

39

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);
}
40

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 :thinking:

41

Same goes with AC with 0.48ms and TLEd.
Both pairs have the same difference

42

Run this test-case on the TLE code.

1
4
0111
1 Like
44

extremely sorry for linking the wrong submission :pensive:
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 …

45

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.

1 Like
46

Woah!
I never took operations like modulo as being a reason for TLE.
Thanks a lot for your help !

1 Like
47

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

48

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.