POSSPEW - Editorial

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
                a[i-1]+= 1
                a[i+1] += 1

    counter += 1

1 Like

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.


yes, you are right man

1 Like

i have tried all possible cases and my solution give correct ans but wrong ans while submit .can someone give test cases and their ans ?

1 Like

@henrychen222 it’s not int, it’s int64_t, containing all 64 bits integers possible, however your suggestion didn’t work

1 Like

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.

Happy Coding…

1 Like

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.

1 Like

What is possibly wrong with this one?


1 Like

what is wrong with my code

1 Like



1 Like

Can you explain a little bit how can we know this by knowing the zeros after and before i?

1 Like

i tried the same approach but its giving wrong answer .
please check this code

Nice problem. The Quick explanation is awesome @taran_1407.

1 Like

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
6 2
0 0 0 2 0 0
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

1 Like

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.

Absolutely Amazing!
can u please explain the part -
while(a[i]==0) { preffix[i]+=preffix[n-1]; i++; }

Edit: PS: ok i get it now, its for the cyclic order!

1 Like

what is wrong with this solution??https://www.codechef.com/viewsolution/51186855