Sorry Guys my Solution should have given TLE on the basis of contraints given in the question. Worst Case Time Complexity is O(n^2). This can be verified by the code given below.
n = 10**3
a = [0 for i in range(n)]
a[n//2] = 1
counter = 0
while 0 in a :
check = [False for i in range(len(a))]
for i in range(len(a)):
if a[i] != 0:
check[i] = True
for i in range(len(a)):
if check[i]:
if i == 0:
a[len(a)-1] += 1
a[i + 1] += 1
elif i == len(a)-1:
a[len(a)-1] += 1
a[i-1] += 1
else:
a[i-1]+= 1
a[i+1] += 1
counter += 1
print(counter)
Dear setters/testers, were the weak testcases intentional?
If so, I am sure many of us would like to know why.
If not, we would like to know how such a basic and important testcase (essentially a filter against bruteforce solutions) was not present.
To Every Ones who are thinking that their solutions should have given TLE.
Here Is your Satisfaction Line:-
IF any of the one element in the array is non-zero and you are iterating in the order of
O(N*K) while keeping check of the number of zero elements remaining in the array.
It will take maximum N/2 iterations to make the whole array non-zero. And then its just formula stuffs left.
So Your code will take at most O(N/2*N) i.e. around 10^9 which I think the problem setter has ignored
But If You want to check the upper bound of your code
Make a TEST CASE of N=10^5 elements with a non-zero element being at the center of the array and take K=10^9.
I tried doing something like this during contest, but using disjoint set for keeping all segments together, but i found myself doing a real mess so changed perspective and found the intended solution, which is way simpler to code. Anyways it was a really nice problem.
Canât believe there wasnât a systest to TLE this kind of solutions, since itâs literally simulating the problem. But i guess luck is a skill too, good job.
@thakur_2312
Our goal is to know at what time the element will start adding up the total sum . It will add only if it is positive .So as we know total number of zeroes before and after the element we can find the time at which it will become positive(my be never) by finding minimum from both side , because the zeroes will decrease from both side . Now after if become positive it will add 2 to the total sum every remaining second .
Very weak test cases my friendâs solution got AC though he get wrong answer in these test case
Input
1
6 2
0 0 0 2 0 0
Output
6
I got output 10 which is correct when calculated by own
it went disastrous for me when it gave me TLE
Please it my humble request to CC to make some good test cases
If I talk precisely O(N/2*N) is around 5 * 10^9, which I donât think can pass in 1 second. It is always around atmost 10^8 operations that can pass in 1 second.
And I also run that test case you have mentioned on my local machine and it is taking more than a minute.