Need help with CMX1P03-"Code To get her"

help
#1

Problem: https://www.codechef.com/COMX2020/problems/CMX1P03/

please help me with my code ,i dont know where i am going wrong.
Approach: I have applied same logic and written same C++ code given at geeksforgeeks with minor changes according to problem.

My code: https://www.codechef.com/viewsolution/37343577

Please help me…

#2

it is most probabily because of the binomial function you are using,
admit you only copy pasted the functions and didn’t changed anything in them.

you need to append your binomial funtion to make it work with mod, here is code for that.

incase you don't know

To perform modular divisions, it is not as simple as modular multiplications.
you need to actually multiply the numerator with modular multiplicative inverse of the denominator.

a / b ==> (a mod m) * (modular inverse b) % mod
for a prime modulo m, modular inverse a number is
modular multiplicative inverse of b is
b raised to power (m - 2) mod m

for more info visit https://cp-algorithms.com/algebra/module-inverse.html

Code 
long long mod = 998244353;

long long power (long long a, long long b = mod - 2) {
  if (a == 0) return 0;
  long long ret = 1;
  while (b) {
    if (b & 1) (ret *= a) %= mod;
    b = b>>1;
    (a *= a) %= mod;
  }
  return ret;
}

// Returns value of Binomial 
// Coefficient C(n, k) 
lli binomialCoeff(lli n, lli k) 
{ 
	lli res = 1; 

	// Since C(n, k) = C(n, n-k) 
	if (k > n - k) 
		k = n - k; 

	// Calculate value of 
	// [n * (n-1) *---* (n-k+1)] / 
	// [k * (k-1) *----* 1] 
	for (lli i = 0; i < k; ++i) { 
		res *= (n - i);
                res %= mod;
		res *= power(i + 1);
                res %= mod;
	} 

	return res; 
}
1 Like
#3

Hello man,here is my code with improved binomial cofficient function but i still get WA :pensive:
https://www.codechef.com/viewsolution/37370795

#4

sorry i misunderstood.

1 Like
#5

I didnt get what u are suggesting.

as in the below code "ans " stores the score and it is always printed

while(q–)
{
string str2;
cin>>str2;
lli ans=countSubsequences(str1, str2)%mod;
cout<<ans<<endl;
if (ans>m)
m=ans;
mp[str2]=ans;
}
//cout<<m<<endl;

 if (m==0)
 {
     cout<<"No Research This Month"<<endl;
 }
 else
 {
     for (auto i=mp.begin();i!=mp.end();i++)
     {
         if (i->second==m)
         {
             cout<<i->first<<endl;
         }
     }
 }
1 Like
#6

can someone help me in finding reason of WA

#7

You are not maintaining order of input of names + you are printing multiple names with same score.

1 Like
#8

thanks man… i got my mistake…actually i thought Unorderd_map keeps the thing in the order they are inserted…but that was not correct…thanks for helping me…
people like you are the reason why i like codechef discussion forum so much :smiling_face_with_three_hearts:

1 Like