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.
Please can someone suggest the mistake in my code based on the above editorial.
I traverse the array twice from left to right and then twice from right to left to get the distance from nearest non zero element.
Can’t figure out which cases it is failing. Test cases are being passed;
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi (3.141592653589)
#define mod 1000000007
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int main(){
fast
int test;
cin>>test;
for(int t=1;t<=test;t++){
int n,k;
cin>>n>>k;
vector<int> arr(n);
int s = 0;
for(int i=0;i<n;i++)cin>>arr[i],s+=arr[i];
if(s==0){cout<<"0\n";continue;}
vector<int> zer(n,0); // array to keep track of dist of closest non - zero element
int dist = 1;
for(int i=0;i<2*n;i++) // traverse array twice
{
if(arr[i%n]!=0)
{
dist = 1;
}
else
{
zer[i%n] = dist;
dist++;
}
}
for(int i=2*n-1;i>=0;i--)
{
if(arr[i%n]!=0)
{
dist = 1;
}
else
{
zer[i%n] = min(zer[i%n],dist);
dist++;
}
}
int ans = 0;
for(int i=0;i<n;i++)
{
ans += (arr[i] + 2*max(0, k - zer[i]));
}
cout<<ans<<"\n";
}
return 0;
}
For the Bonus problem, you can calculate the time when a particular Ai becomes >0, this can be done by using multi-source BFS.
queue q;
Push all the indexes that are != 0
apply simple BFS to get the times when the neighbors will become non - negative.
After this it’s simple maths.
