Help with a code. Two similar codes but different outputs

general
1 
     #include<bits/stdc++.h>
    #define INF 1e9+7
    #define endl "\n"
    #define fi first
    #define se second
    #define mp make_pair
    #define pb push_back
    #define ll long long
    #define ld long double
    #define vll vector<ll>
    #define all(x)	x.begin(),x.end()
    #define fileopen freopen("input.txt", "rt", stdin);
    #define fileclose freopen("output.txt", "wt", stdout);
    #define Fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
    #define hash visited.max_load_factor(0.25);visited.reserve(512)

    using namespace std;


    int main()
    {

        Fio;
        

        ll t;
        cin>>t;

        while(t--)
        {
            ll n;
            cin>>n;

            vll v(n);

            for(int i=0;i<n;i++)
            {
                cin>>v[i];
            }

            sort(all(v));

           

            ll cnt=0;
            ll grp_cnt=0;
           

            for(int i=0;i<n;i++)
            {
                if(grp_cnt==0)
                {
                    grp_cnt=i;
                }
                if(i-grp_cnt+1 >= v[i])
                {
                    
                    cnt++;
                    grp_cnt=0;
                }
            }
            cout<<cnt<<endl;
        }

    
        
    }


    #include<bits/stdc++.h>
#define INF 1e9+7
#define endl "\n"
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
#define ld long double
#define vll vector<ll>
#define all(x)	x.begin(),x.end()
#define fileopen freopen("input.txt", "rt", stdin);
#define fileclose freopen("output.txt", "wt", stdout);
#define Fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define hash visited.max_load_factor(0.25);visited.reserve(512)

using namespace std;


int main()
{

    Fio;
    

    ll t;
    cin>>t;

    while(t--)
    {
        ll n;
        cin>>n;

        vll v(n+1);

        for(int i=1;i<=n;i++)
        {
            cin>>v[i];
        }

        sort(all(v));

       

        ll cnt=0;
        ll grp_cnt=0;
       

        for(int i=1;i<=n;i++)
        {
            if(grp_cnt==0)
            {
                grp_cnt=i;
            }
            if(i-grp_cnt+1 >= v[i])
            {
                
                cnt++;
                grp_cnt=0;
            }
        }
        cout<<cnt<<endl;
    }


    
}

For the input:
3
2 3 3
Correct Output(Second code):
1
Wrong Output(first code):
0

In the second code, i am storing the values in index 1 to N
In first code, i am storing the values in index 0 to N-1
But i am getting a different output. Why is this happening?

Question: https://codeforces.com/contest/1355/problem/B

2

Please consider pasting the code and formatting it, instead of pasting the picture.

In the first case you are using the values in index 1 to n. So you must be sorting sort(v.being() + 1, v.end()). But you’re sorting all of v. Hence v[0] also comes into the sorting and it messes up your whole vector.

Another thing: Your group count if condition must be different when you’re using 1 based indexing and 0 based indexing.

3 Likes
3

Okay, will do that and remove the picture.

But aren’t vectors initialized by 0 by defualt, so it shouldn’t make much difference right? Also, the one where i have used index 1 to N is the correct answer.

4

I edited my comment. Check it out. Substitute i = 0 and i = 1 and see.

In the second case groupcount = i + 1
And the other condition is i - groupcount +2 >= v[i]

Because of 0 based indexing.

3 Likes
5

Yes this worked but i am still not clear why this works. I mean, difference between two index in 0-indexed or 1-indexed is same right?

Eg: 2-0+1 is same as 3-1+1 OR in this case i-grp_cnt+1 would have been 2-0+1=3 and i-grp_cnt+2 would be 2-1+2=3 (when “i” is in the last condition).

Or am i wrong?

6

You’re using group count == 0 as a base condition. Let’s say now i = 0 and group count == 0 is true. Now your assigning group count as 0 again. Assume the second if condition is false. Now if your first code your group count will be 1. But here the group count will be 0 (but for a different reason). So in the next iteration you’ll go inside the first if, when you don’t want to.

3 Likes
7

Also this will help you colour format your code.

3 Likes
8

Yes understood completely. Thank you very much!

1 Like