ARRGAME - Editorial

https://www.codechef.com/viewsolution/37300016
Hi, I just made some changes to your code and it gets AC. The answer will be “yes” only when we have an odd segment. If there is only one segment and that is odd length, then the answer is ‘yes’. If there is more than one segment, then the 1st player chooses the longest odd segment, and then 2nd player chooses the largest vacant segment(odd or even does not matter). Now we just see if the length of segment chosen by 2nd is greater than or equal to (length of segment chosen by first + 1)/2.

1 Like

Can anyone please tell what I am missing?
https://www.codechef.com/viewsolution/37300895

Great man, Thanks for your support​:+1::+1:

Finally solved it…, CodeChef: Practical coding for everyone
#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int> v(n);
    map<int, int> mp;
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(v[i] == 0){
            cnt++;
        }else{
            if(cnt != 0)
                mp[cnt]++;
            cnt = 0;
        }
    }
    int mx_even = 0;
    int mx_odd = 0;
    for(auto it : mp){
        if(it.first &1)
            mx_odd = max(mx_odd, it.first);
        else{
            mx_even = max(mx_even, it.first);
        }
    }
    // find the second largest odd length zero-interval;
    int mx_odd2 = 0;
    for(auto it: mp){
        if(it.first &1 && it.first < mx_odd){
            mx_odd2 = max(mx_odd2, it.first);
        }
    }
    if(mx_odd){
        if(mx_odd == 1){
            if(mp[mx_odd] > 1 || mx_even > mx_odd){
                cout << "No\n";
            }else{
                cout << "Yes\n";
            }
        }
        else{
            if(mp[mx_odd] > 1 || (mx_odd && mx_odd2 > mx_odd/2) || mx_even >mx_odd/2){
                cout << "No\n";
            }
            else{
                cout << "Yes\n";
            }
        }
    }else{
        cout << "No\n";
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int tt;
    cin >> tt;
    while(tt--){
        solve();
    }
    return 0;
}


indent preformatted text by 4 spaces

I learnt from previous contests,was stuck for an hour in a previous contest.Yeah and in codeforces it doesnt matter i think ,if you are printing YES or Yes

Why WA?

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
long int n,max1=0,max2=0,cnt=0;
cin>>n;
int x;

f(i,n)
{
    cin>>x;
    if(x)
    {
     if(max1<=cnt)
     {
         max2=max1;
         max1=cnt;
         cnt=0;
         continue;
     }
        if(max2<=cnt)
     {
         max2=cnt;
         cnt=0;
         continue;
     }
    }
     else
     {
      if(i==n-1 && max1<=cnt)
     {
         max2=max1;
         max1=cnt+1;

     }
     else if(i==n-1 && max2<=cnt)
     {
         max2=cnt+1;
     }
     cnt++;
     }
    //cnt++;

}
//cout<<max1<<endl<<max2<<endl;
//if(max1>max2 && max2>=max1/2) cout<<"NO"<<endl;
if(max1>max2 && (max1%2) && ((max2<(max1+1)/2) || (!max2))) cout<<"YES"<<endl;
else
 {
     cout<<"NO"<<endl;
 }

}//while


return 0;}

Actually in the worst case loop will run N times … so it can be O(N^2)

    vector<int> v(n);
    int z1 = 0, z2 = 0, count = 0;
    for(int i = 0; i < n; i++)
    {
        cin>>v[i];
        if(v[i] == 0)
            count++;
        else
            count = 0;
        
        if(count >= z1)
            z2 = z1, z1 = count;
        else if(count < z1 && count > z2)
            z2 = count;
    }
    
    if(z2 == 0)
        res[i] = z1%2;
    else
    {
        if(z1%2 == 1 || z2 <= (z1-1)/2)
            res[i] = 1;
        else
            res[i] = 0;
    }

Here z1 is the largest zero segment and z2 is the 2nd largest zero segment
Please help…

1 Like

Very nicely written editorial

#include <bits/stdc++.h>

using namespace std;

int main() {
long long int t;
cin >> t;
while (t–) {
long long int n;
cin >> n;

long long int max_size = 0;
long long int prev_max_size = 0;
long long int temp = 0;
int x;
int count = 0;
for (long long int i = 0; i < n; i++) {
  cin >> x;
  if (x == 0) {
    temp++;
  } else {
    if (temp > prev_max_size) {
      prev_max_size = temp;
    }
    if (temp >= max_size) {
      prev_max_size = max_size;
      max_size = temp;
    }
    temp = 0;
  }
}

if (max_size % 2 == 0) {
  cout << "No" << endl;
} else if (max_size == prev_max_size) {

  cout << "No" << endl;
} else if ((max_size / 2 + 1) <= prev_max_size) {
  cout << "No" << endl;
} else
  cout << "Yes" << endl;

}
}

my solution , passing all cases

2
13
1 0 1 0 0 0 1 0 0 0 0 0 1
8
1 0 0 1 0 0 0 1

Your code is giving wrong answer for these test cases

Thanks for answering the question.Now i got the question correctly .

Your code does not include the condition when segment with maximum length of zeroes is odd and the second maximum segment with length equal to or greater than (length of maximum string +1)/2

my code prints no but still not able to pass 2nd subtask…can you give some more testcases pls.

#include
#include
#include
#include
#include
#include<math.h>
#include
using namespace std;
typedef long long int ll;
#define mxint 1000000007
const int mod = int(1e9+7);
long long int t[2000001];
/* why this code for arrgame is give wrong answer on testcase 1 of subtask 2 only and all other test cases are passed */

int main()
{
    ios_base::sync_with_stdio(false);
  cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int arr[n];
        int f1=0,index;
        int sum=0;
        for (int i =0;i<n;i++) {
            cin>>arr[i];
            if(arr[i]==0)sum++;
        }
        int mez=0,moz=0,secmoz=0;// mez=maximun_even_zero_segment
        //moz=maximun_odd_zero_segment 
        // secmoz=second_maximun_odd_zero_segment
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            if(arr[i]==0)
            cnt++;
            else
            {
                if((cnt%2)==0)
                {
                    mez=max(mez,cnt);
                    cnt=0;
                }
                else
                {
                    if(cnt>=moz)
                    {
                        secmoz=moz;
                        moz=cnt;
                        
                        cnt=0;
                    }
                    cnt=0;
                    
                }
                cnt=0;
            }
        }
//cout<<index<<endl;
     //  cout<<secmoz<<endl;
     //  cout<<moz<<endl;
     //  cout<<mez<<endl;
     if((secmoz==0)&&(moz!=0)&&(mez==0))
     {
         if((sum%2)==0)
         cout<<"No"<<endl;
         else
         cout<<"Yes"<<endl;
     }
        else if(moz==0)cout<<"No"<<endl;
        else if(moz==0&& mez==0)cout<<"No"<<endl;
        else if(moz==1&&mez==0)
        {
            if(sum>1)
            cout<<"No"<<endl;
            else if(sum==1)
            cout<<"Yes"<<endl;
        }
        else if(mez<=(moz/2))
        {
            
            if(secmoz<((moz)/2))
            cout<<"Yes"<<endl;
            else
            cout<<"No"<<endl;
        }
        else
        cout<<"No"<<endl;
    
    }
}

why this code for arrgame is give wrong answer on testcase 1 of subtask 2 only and all other test cases are passed

my code passes your test case but it doesn’t pass 1st test case of second subtask and while all other test cases passed …
please see the code

Your code fails for this test case
1
13
1 0 0 0 0 0 0 0 1 0 0 0 1
ans-Yes

1 Like

thnx sir …now my code got accepted …only error in secmoz :+1:t6:
my accepted code below–>
click to see solution

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#include<math.h>
#include<string>
using namespace std;
typedef long long int ll;
#define mxint 1000000007 
const int mod = int(1e9+7);
long long int  t[2000001];


int main()
{
    ios_base::sync_with_stdio(false);
  cin.tie(NULL);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int arr[n];
        int f1=0,index;
        int sum=0;
        for (int i =0;i<n;i++) {
            cin>>arr[i];
            if(arr[i]==0)sum++;
        }
        int mez=0,moz=0,secmoz=0;// mez=maximun_even_zero_segment
        //moz=maximun_odd_zero_segment 
        // secmoz=second_maximun_odd_zero_segment
        int cnt=0;
        vector<int>v;
        for(int i=0;i<n;i++)
        {
            if(arr[i]==0)
            cnt++;
            else
            {
                if((cnt%2)==0)
                {
                    mez=max(mez,cnt);
                    cnt=0;
                }
                else
                {
                    if(cnt>=moz)
                    {
                        moz=cnt;
                        
                    }
                    v.push_back(cnt);
                    cnt=0;
                    
                }
                cnt=0;
            }
        }
        if(v.size()>1)
        {sort(v.begin(),v.end()); secmoz=v[v.size()-2];}
        
        //cout<<index<<endl;
     //  cout<<secmoz<<endl;
     //  cout<<moz<<endl;
     //  cout<<sum<<endl;
     if((secmoz==0)&&(moz!=0)&&(mez==0))
     {
         if((sum%2)==0)
         cout<<"No"<<endl;
         else
         cout<<"Yes"<<endl;
     }
        else if(moz==0)cout<<"No"<<endl;
        else if(moz==0&& mez==0)cout<<"No"<<endl;
        else if(moz==1&&mez==0)
        {
            if(sum>1)
            cout<<"No"<<endl;
            else if(sum==1)
            cout<<"Yes"<<endl;
        }
        else if(mez<=(moz/2))
        {
            
            if(secmoz<=((moz)/2))
            cout<<"Yes"<<endl;
            else
            cout<<"No"<<endl;
        }
        else
        cout<<"No"<<endl;
    
    }
}

cook your dish here

t = int(input())

for _ in range(t):
n = int(input())
ls = list(map(int,input().split()))

res = []
i = 0
while(i < n):
    if(ls[i] == 1):
        i += 1
        continue;
    ptr = i;
    while(ptr < n and ls[ptr] == 0):
        ptr += 1
    res.append(ptr-i)
    i = ptr
    
# print(res)
if(len(res) == 0):
    print("NO")
elif(len(res) == 1):
    if(res[0]%2 == 1):
        print("YES");
    else:
        print("NO");
else:
    a = -1
    b = -1
    id = -1
    for i in range(len(res)):
        if(res[i] > a):
            a = res[i]
            id = i
    
    for i in range(len(res)):
        if(res[i] > b and id != i):
            b = res[i]
             
    if(a%2 == 1 and b <= (a-1)//2):
        print("YES")
    else:
        print("NO”)

Can anyone correct my code
Its giving WA
But logic is all correct.

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

PLEASE CORRECT ME WHERE I AM DOING WRONG, ITS PASSING FOR TASK 1