POSSPEW - Editorial

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;
}

VERY NICE EDITORIAL. SUBMITTED IN ONE GO.

I used multisource bfs, my solution

https://www.codechef.com/viewsolution/51096063

2 Likes

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.

same concept i also used and got AC

1 Like

What is wrong in my approach. It is failing for one test case on submitting. Any help would help me a lot. My approach goes this way- I have calculated time required for zero elements to become non-zero and then finally traversed this array to calculate sum by adding 2*max(0, ans[i]) for every i in ans array which contains t for every element.

#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define pii pair<int, int>
#define vii vector
#define make make_pair
#define f first
#define s second
#define si unordered_set
#define sll unordered_set
#define mii unordered_map<int, int>
#define mll unordered_map<ll, ll>
#define ll long long
#define vi vector
#define vll vector
#define maxpq priority_queue
#define minpq priority_queue<int, vector, greater >
#define MOD (int) 1e9+7
#define take(n) int n; cin >> n
void pr(int x) {cout << x;}
void prl(int x) {cout << x << endl;}
#define for0(i, n) for (int i = 0; i < n; i++)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define tc(t) int t; cin >> t; while (t–)
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL),cout.tie(NULL)
#define prec(n) fixed<<setprecision(n)
#define ini(a, i) memset(a, i, sizeof(a))
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
int max(int a, int b) {if (a > b) return a; else return b;}
int min(int a, int b) {if (a < b) return a; else return b;}
const int dx[4] = { -1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const int N = (int)(5 * 1e5 + 10);
vector<vector> divs(N);
void pre(){
int i, j;
for1(i, N-1){
for(int j=i;j<N;j+=i)
divs[j].pb(i);
}
}
ll add(ll x, ll y) {ll res=x+y; return res>=MOD ? res-MOD:res;}
ll mul(ll x, ll y) {ll res=x*y; return res>=MOD? res%MOD:res;}
ll sub(ll x, ll y) {ll res=x-y; return res<0? res+MOD:res;}
ll power(ll x, ll y) {ll res=1; x%=MOD; while(y){ if (y&1) res=mul(res, x); y >>=1; x=mul(x, x);} return res;}
ll mod_ind(ll x) {return power(x, MOD-2);}

int main(){
//#ifndef ONLINE_JUDGE
//freopen(“input.txt”, “r”, stdin);
//freopen(“output.txt”, “w”, stdout);
//#endif

tc(t){
    take(n); take(k);
    int arr[n];
    bool flag=false;
    int start;
    ll sum=0;
    for0(i, n){
        cin >> arr[i];
        sum+=arr[i];
        if (arr[i]>0){
            if (flag==false)
                start=i;
            flag=true;
        }
    }
    if (flag==false){
        cout << "0\n";
        continue;
    }

    vi temp(n, 0); // to store time for zeroes to become non-zero.
    int count=1;
    for (int i=start+1;i!=start;i=(i+1)%n){ // first traversing left to right & putting counts in temp.
        if (arr[i]==0){
            temp[i]=count;
            count++;
        }
        else{
            count=1;
        }
    }
    count=1;
    for (int i=start-1;i!=start;i=(i-1+n)%n){ // now traversing right to left and updating temp only if value is smaller.
        if (arr[i]==0){
            temp[i]=min(temp[i], count);
            count++;
        }
        else
            count=1;
    }
    
    // now temp contains time taken for zero elements to become non-zero.
    // for (auto &i: temp){
    //     sum=sum+2*max(0, k-i);
    // }
    cout << sum << endl;
}

return 0;

}

int n;
void testcase(){
  int k;
  cin>>n>>k;
  int cur = n+10;
  int ans=0LL;
  vector<int>a(2*n),b(2*n,INT_MAX);
  for(int i=0;i<n;i++){
   cin>>a[i];
   a[n+i]=a[i];
  }
  for(int i=0;i<2*n;i++){
    if(a[i]==0) cur++;
    else cur=0;
    b[i] = min(b[i],cur);
  }
  cur = n+10;
  for(int i=2*n-1;i>=0;i--){
    if(a[i]==0) cur++;
    else cur=0;
    b[i] = min(b[i],cur);
  }
  for(int i=0;i<n;i++) ans+=(2LL*max(0LL,k-b[i%n])+a[i]);
  cout<<ans<<"\n";
  return; 
}

why I am getting WA

What is wrong with this code. It is failing the first testcase but passing the remaining testcases.
See only void solve function.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define MOD 1000000007
#define DEBUG(x) cout << '>' << #x << " : " << x << '\n';
#define mp make_pair
#define pb push_back
#define fastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define POB pop_back
#define F first
#define S second
#define cin(a,n) for(int i=0;i<n;i++){cin>>a[i];}
#define max(a, b) ((a < b)? b : a)
#define min(a, b) ((a > b)?b : a)
#define FOR(a,c)   for (auto (a) = 0; (a)<(c); (a)++)
#define FORL(a,b,c)  for (auto (a) = (b); (a)<=(c); (a)++)
#define FORR(a,b,c)  for (auto (a) = (b); (a)>=(c); (a)--)
#define FORB(a,c)   for (auto (a) = (c); (a)>=0; (a)--)

typedef long long int ll;
typedef map<ll, ll> MLL;
typedef set<ll> SL;
typedef vector<ll> VL;
typedef pair<ll,ll> PLL;
typedef vector<pair<ll,ll>> VPLL;
typedef map<int, int> MII;
typedef set<int> SI;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int>> VPII;

#define ordered_set_int tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset_int tree<int, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_set_ll tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset_ll tree<ll, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update>
// oset.order_of_key(x) -> number of elements which are STRICTLY smaller than x
// oset.find_by_order(x) -> returns an iterator corresponding to the xth position in the set. (0-based indexing)

template<typename T>
T ceil(T a,T b)
{
    return (a+b-1)/b;
}
template<typename T>

T floor(T a,T b)
{
    return a/b;
}
// use as - ceil<ll>(1221,2323);
ll power(ll x, ll y, ll p = MOD)
{
    ll res = 1;

    x = x % p;

    if (x == 0)
        return 0;

    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;

        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
ll modInverse(ll n, ll p)
{
    return power(n, p - 2, p);
}
/*-------------------------------------------------------------------------------------------------------*/

void solve();
int main()
{
#ifndef ONLINE_JUDGE
#ifndef CPH
    auto t1 = std::chrono::high_resolution_clock::now();
#endif
#endif
    fastIO;
    int t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
#ifndef ONLINE_JUDGE
#ifndef CPH
    auto t2 = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
    cout << "time taken: " << static_cast<double>(duration)/1000000;
#endif
#endif
    return 0;
}

ll a[100001],d[100001];

void solve()
{
    ll n,k;
    cin>>n>>k;
    memset(a,-1,sizeof a);
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        d[i] = INT_MAX;
    }

        ll p = -n;
        for(ll i=0;i<2*n;i++)
        {
            if(a[i%n] > 0)
            {
                p = i;
            }
            d[i%n] = min(d[i%n],i-p);
        }

        p=3*n;
        for(ll i=2*n-1;i>=0;i--)
        {
            if(a[i%n] > 0)
            {
                p=i;
            }
            d[i%n] = min(d[i%n],p-i);
        }

        ll sum = 0;
        
        for(ll i=0;i<n;i++) sum += a[i];

        for (ll i = 0; i < n; ++i)
        {
            sum += 2*max(0,k-d[i]);
        }

        cout<<sum<<'\n';
}

brute will not work O(n*k)
see the constraints…

thanks for this approach really surpriseful solution did’nt can be solve using BFS.

1 Like

https://www.codechef.com/viewsolution/51189796

Anyone please tell why tle is coming ?

Can anyone please explain the DP solution!?
Thanks!

Please Help !!
Whats wrong with this approach.

I’m taking each continuous sequence of zeroes and directly adding to sum what their net contribution will be, if any.
Separately doing same if zeroes at beg and end.

Getting WA
Any testcase it might fail in?

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main()
{
int t;cin>>t;
while(t–)
{
ll n,k;cin>>n>>k;
vector a(n);
ll z=0,sum=0,p=0;
for(int i=0;i<n;i++)
{
cin>>a[i];
sum+=a[i];
if(a[i])p++;
if(p)
{
if(a[i]==0)z++;
else
{
ll x=z;
z=(z/2)+z%2;
if(z<k)sum+=(k-z)(2x);
else z=k;
z=z*(z-1)/2;
sum+=z*4;
z=0;
}
}
}
if(p!=0)
for(int i=0;i<n&&a[i]==0;i++)z++;

      z=(z/2)+z%2;
      if(z<k)sum+=(k-z)*(2*z);
              else z=k;
      z=z*(z-1)/2;
      sum+=z*4;
              
  sum+=(p*2*k);
  
  cout<<sum<<"\n";

}
}

WHAT POSSIBLY IS WRONG WITH THIS CODE?

I TRIED ON EVERY CORNER CASE BUT IT IS GIVING CORRECT RESULT.
PLEASE SUGGEST SOME TEST CASES.

VERY GOOD EXPLANATION @taran_1407 !!!

What is wrong with my solution?
https://www.codechef.com/viewsolution/51173009

This code is giving TLE and i can’t figure out how to resolve it (without using STL)

#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
int arr[n];
for(int i=0; i<n; i++){
cin>>arr[i];
}
int arr2[n];
for(int i=0; i<n; i++){
arr2[i]=arr[i];
}
while(k–){
for(int i=0; i<n; i++){
if((arr[i]>0) && (i!=0) && (i!=n-1)){
arr2[i-1]++;
arr2[i+1]++;
}
else if((arr[i]>0) && (i==n-1)){
arr2[n-2]++;
arr2[0]++;
}
else if((arr[i]>0) && (i==0)){
arr2[1]++;
arr2[n-1]++;
}
}
for(int i=0; i<n; i++){
arr[i]=arr2[i];
}
}

    int sum=0;
    for(int i=0;i<n;i++){
        sum = sum + arr[i];
    }
    cout<<sum<<endl;
          

}
}

In the contest the test cases for the third question were weak O(n^2) solution also got accepted so this is completely unfair and the question should be revaluated for everyone

You’re basically describing an O(N^2) solution. There’s no way it will pass the systests…

I have clearly written that either there is no such test case or the problem setter has ignored the so-tight bound.

Also there are some solutions on various online judges, online cp platforms where solution of around 10^9 operations are being successfully accepted within time constraints of 1 sec.

So I wrote I think problem setter might have ignored or there is no such test case.