https://www.codechef.com/JUNE19B/problems/CHFING

help
, ,
1

Logic is correct when submitted with python but not c++14

Python code : https://code.hackerearth.com/818563H
c++14 code: https://code.hackerearth.com/59fa93J

2

you cant do like that
ans=(ans/2)%M
u have to first calculate inverse modulo of 2 and multiply with ans
ans=(ans*invmodulo(2,m))%m

u can study it from geeksforgeeks

1 Like
3

sry not working tried your way…but thanks for your advice

4

i think u did something wrong in it… otherwise it is the only right way to do this…

5

https://code.hackerearth.com/d10925p

6

Also check for overflow as in C++ using long long int was causing overflow

7

can anybody tell me what is the mistake only 1 TC is wrong . all other 3 are right.

8

My code using simple modular arithematic (no modular inversion).

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i(0);i<n;i++)
#define fast  ios_base::sync_with_stdio(0); cin.tie(0);
#define mod 1000000007
#define pb push_back
#define all(v) v.begin(), v.end()

int cl(int a, int b){
    if(a%b != 0)return (a - a%b + b)/b;
    return a/b;
}

int32_t main() {
    fast;


    int t;
    cin>>t;

    while(t--){
	    int n,k;
	    cin>>n>>k;
	    int terms = cl(k-1, n-1),ans;
	    ans = 2*(k-1) - (terms - 1)*(n-1);
	    if(terms&1){
	    	ans/=2;
		    ans%=mod;
		    terms%=mod;
	    }
	    else{
		    terms/=2;
		    terms%=mod;
		    ans%=mod;
	    }
	    ans*=terms;
	    ans%=mod;
	    cout<<ans<<"\n";   
    }
    return 0;
}

I took MOD at whatever stage I could to get AC in Case 2 Subtask 2
https://www.codechef.com/viewsolution/24623376

9

Hope this helps =>

#include <iostream>
#include <bits/stdc++.h>

#define ll long long int
#define MOD 1000000007
#define INV 500000004

using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        ll n,k;
        cin>>n>>k;

        if(k==1){
            cout<<0<<endl;
            continue;
        }

        ll a = k;
        ll s = n-1;
        ll t = (a-2)%s;

        ll cardinality = (((((((a-2)/s)+1)%MOD)*(((a%MOD+t%MOD)%MOD)%MOD))%MOD)*INV)%MOD;

        cout<<cardinality<<endl;

    }
    return 0;
}
10

raydioactive_9 : What is the use of INV?

11

Aren’t there some unnecessary MODs ?

12

https://code.hackerearth.com/d10925p

satyankar

13

i have taken that and inverse modulo into account but 1 tc is still WA .

14

It’s modular inverse of two, generally, modular equivalent of (ab)/c is (((a%mod)(b%mod))%mod * c’)%mod. This is because % is not distributive on division

15 
        ll x = (k-1) / (n-1);
        
        ll d = (n-1);
        ll a = (k-1);
        
        if((k-1)%(n-1))
        {
            x++;
        }
        
        ll ans = ( 2*(a%mod) - (((x-1)%mod) * (d%mod))%mod+mod)%mod;
        ans = (ans * (x%mod))%mod;
        ans = ans * INV;
        cout<<ans%mod<<endl;

correct solutiob : https://code.hackerearth.com/d10925p

I got all AC.

My doubt is that in above snippet i took inverse moduo of (2,M) but when i was calculating X = (n-1)/k-1 i did not use inverse modulo but took directly mod afterwards in calulating ans. This works why?? My concepts are somewhat lacking . Need help