Sir Since I am a 3* coder I have only read that Time Complexity is the estimation of no of operations your code will take for a certain input
I think 4* coders had their defintion as it to be bounds of the for/while loops they are using in their code so sir I have nothing to say more…
you mean DFS,
actually it required shortest path from multisource so I don’t think it can be solved by using DFS only.
Nice Editorial !! Thank You !!
Great approach!
btw is this approach common for questions like these??
bro actually i am facing a difficulty to understand the problem i have one doubt if we have an array [0,0,0,2,0,0,0,5] and after one second it become [1,0,1,2,1,0,1,5] so after 2 second how it become [2,2,2,4,2,2,2,7] now i am writing the way i thought it but i have one little doubt so the 1 at the index 1 becomes 2 because adjacent element of 1 is 5 hence we add 1 into 1 and it become 2 the element at index 2 is 0 and both of its adjacent are 1 and one so we add 1 because of element present at index 1 and add other 1 because of 1 present at index 3 hence our element become 2 now if apply the same approach to all the element our array become [2,2,2,4,2,2,2,7] but i apply the my approach in [0,1,0,1,0,0] I get the array[1,1,1,1,1,0] and this is wrong array
@div_sahu55
I think it depend from person to person . There can be many other(may be easier) method to solve this question . I usually use this concept when for each element previous and upcoming sequence matters and it contribute the result .
Can please someone explain to me how to find the nearest non-zero element?
I partially understood what’s written in the editorial.
Why we have traversed the array twice in dp solution?
And how we can do this by ordered sets as stated in the editorial?
@akshansh_1
Well I think you confused yourself and did a silly mistake . For the array [ 0 , 1 , 0 , 1 , 0 , 0 ] when you apply your approach element at index 2 (ie 0) will become 2 , because both the adjacent number(element at index 1 and 3) are positive (ie x>0) hence both will add 1 each .
Can Somebody help ? Please!!
I have created 300 test cases but still, my solution & editors’ solution giving the same output. Then Why I am getting WA in the 2nd task (It will give TLE in task 1,3 but ignore that)
Can somebody explain me why O(N^2) solution worked ??
We struggled to get O(N) solution and there something else was going on.
If I have known that O(N^2) solution is also getting working, I would have getting a much better Rank.
This is the Second time it happened during one cook off round also.
Please Codechef problem setters Please make testcases strong and strong and then only let that problem in the contest.
can anyone help me whats wrong with this sol
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve();
ll mod(ll a) {
return max(a, -1 * a);
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“error.txt”, “w”, stderr);
freopen(“output.txt”, “w”, stdout);
#endif
int t = 1;
/*is Single Test case?*/cin >> t;
while (t--)
{
solve();
}
cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
return 0;
}
void solve()
{
ll n, k, sum = 0, c = 0, fstindex = 0, lstindex = 0, res = 0;
cin >> n >> k;
ll a[n];
vector v;
for (int i = 0; i < n; i++)
{
cin >> a[i];
sum += a[i];
if (a[i] != 0) {
if (c == 0) {c++; fstindex = i; lstindex = i;}
else {c++; lstindex = i;}
} else {v.push_back(i);}
}
vector lt;
ll lft = lstindex;
vector<ll> rt;
ll rgt = fstindex;
for (int i = 0; i < n; i++)
{
if (a[i] == 0) {lt.push_back(lft); }
else {lft = i;}
}
for (int i = 1; i <= n; i++)
{
if (a[n - i] == 0) {rt.push_back(rgt); }
else {rgt = n - i;}
}
reverse(rt.begin(), rt.end());
for (int i = 0; i < n - c; i++)
{
ll j, a, b;
a = mod(v[i] - lt[i]);
b = mod(v[i] - rt[i]);
j = min(min(a, n - a), min(b, n - b));
if (k >= j) {res += (k - j) * 2;}
}
res += (c * 2) * k;
res += sum;
cout << res << "\n";
}
I get correct output in 2nd task but getting wrong answer in 1st task. Can u please tell me which mistake i did in my code CodeChef: Practical coding for everyone
I have created 300 test cases but still, my solution & editors’ solution giving the same output. Then Why I am getting WA in the 2nd task (It will give TLE in task 1,3 but ignore that)
https://www.codechef.com/viewsolution/51206083
can you please find a mistake or testcase I will be very thankful ?
I’m not too sure how Java operators work, but in line 63 you’re doing a multiplication that can overflow int range, try changing that.
Can anyone tell me how ordered set can be used to find nearest zero for an element in O(nlogn) time?
Insert position of each non-zero element into an ordered set.
For each position p containing 0, using upper_bound can find the next position. Similarly we can find nearest position smaller than p.
Ohhh… you are right. Thanks, man.
ok thanks bro i get it now