My Approach :
First make all elements Non - Zero (if at least one element is zero) . Then, if the sum of array elements is s and each element of array is non-zero. Answer will become s + 2nk where k is number of operations and n is number of elements.
P.S. This approach should have given TLE on the basis of the contraints given in the question. Maybe Test Cases were not proper.
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
const unsigned int M = 1000000007;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> tree;
bool checkzeroes(vector<ll> data){
for(auto elem : data){
if(elem == 0)
return true;
}
return false;
}
void solve()
{
int t;
ll n, k;
cin>>t;
while(t--){
cin>>n>>k;
bool check_non_zero = false;
vector<ll> data(n);
for(auto &elem : data)
cin>>elem;
for(auto elem : data){
if(elem != 0)
{
check_non_zero = true;
break;
}
}
if(!check_non_zero){
cout<<"0\n";
continue;
}
while(checkzeroes(data) and k > 0){
vector<bool> pts(n,false);
for(int i = 0; i < n; i ++)
if(data[i] != 0)
pts[i] = true;
for(int i = 0; i < n ; i++ ){
if(pts[i]){
if(i == 0)
data[n-1] ++ , data[i+1] ++ ;
else if(i == n-1)
data[0] ++, data[i-1] ++ ;
else
data[i-1] ++ , data[i+1] ++ ;
}
}
k--;
}
ll sum = accumulate(data.begin(),data.end(),0);
sum += (n*k*2);
cout<<sum<<"\n";
}
}
int main()
{
ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);
solve();
return 0;
}
I have solved it using prefix and suffix concept in O(n) . I calculated total zeroes before and after the element , from this we can simple know the time when it will become positive . https://www.codechef.com/viewsolution/51126119
I think only 2 numbers (according to my test case) which are zero get converted into non-zeros in each iteration. It approximately takes n/2 iterations (according to my test case) to make all elements of the array non-zero.
I also did this but I am getting wrong answer. Could you tell what is difference between my and your code .
My submission : CodeChef: Practical coding for everyone
Sorry Bro ! I found that my solution should also have given TLE. Maybe the test cases were not proper. Here is a Sample Code. For 10e3, it takes 500 iterations. It means complexity goes to O(n^2) and it should give TLE.
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)
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.