CMX1P03 - Code To Get Her - Code Mates x1 Editorial

I read the discussion title and thought it was related to human trafficking :rofl: :rofl:

3 Likes

Hi, I didn’t have much time today so couldn’t really spend time on the contest unfortunately : /

Could you tell me why this gives TLE?

import numpy as np 
SIZE = 26
def binomialCoeff(n, k): 
	res = 1
	if (k > n - k): k = n - k  
	for i in range(k): res *= (n - i);res = int(res/(i + 1)) 
	return res
def countSubsequences(str1, str2):
	freq1 = np.zeros(26, dtype = np.int);freq2 = np.zeros(26, dtype = np.int) 
	n1 = len(str1);n2 = len(str2)
	for i in range(n1): freq1[ord(str1[i]) - ord('a') ] += 1
	for i in range(n2): freq2[ord(str2[i]) - ord('a')] += 1
	count = 1
	for i in range(SIZE):
		if (freq2[i] != 0):
			if (freq2[i] <= freq1[i]): count = count * binomialCoeff(freq1[i],freq2[i])
			else: return 0
	return count
for _ in range(int(input())):
	S = input();ans = {}
	for _ in range(int(input())):
		name = input()
		print(countSubsequences(S,name))
		#ans.add(name,countSubsequences(S,name))
		ans[name] = countSubsequences(S,name)
	if(max(ans.values()) > 0): print(max(ans,key = ans.get))
	else: print("No Research This Month") #sample testcases passed, TLE
def past(arr,W,i):arr[i - 1] += W;return arr
def present(arr,L,R): print(sum(arr[L - 1:R]))
N = int(input()); arr = list(map(int , input().split()))
for _ in range(int(input())):
	input_ = list(map(str , input().split()))
	if(input_[0] == "past"): past(arr,int(input_[1]),int(input_[2]))
	else: present(arr,int(input_[1]),int(input_[2])) #sample testcases passed, TLE

even this code got TLE for the ‘dark’ problem

In this function, the calculations are being done on large numbers, which is taking considerable amount of time. Hence, resulting in TLE.
You’ll have to use modular arithmetic. Please read the editorial.

1 Like

okay thank you

For Dark, the expected time complexity was O(Q*LogN). Editorial for Dark is available here.

1 Like

lol :joy:

1 Like

Can anybody help me why my code is wrong?
Link : CodeChef: Practical coding for everyone
I have tried to follow the same logic as editorial but can’t seem to find my mistake

editorial for CodeChef: Practical coding for everyone ?

@sb_kmb Editorial for Code Together (CMX1P01): CMX1P01 - Code Together - Code Mates x1 Editorial

1 Like

@mayureshpatle can you please point out the mistake in my code :
https://www.codechef.com/viewsolution/37343577

I have used the same C++ code given at geeksforgeeks with some changes :

may be i am doing mistake with applying the mod…please help…any help is greatly appreciated

@nalingoyal In function binomialCoefficient, the values of n and k are large, so there will be an overflow during calculation. Use the method mentioned in the editorial.

1 Like

@mayureshpatle i did as u suggested…i checked for overflow in binomial cofficient function…but i didnt get AC …plz have a look.
https://www.codechef.com/viewsolution/37370795

@nalingoyal \frac{A}{B} \mod M \neq \frac{A \mod M}{B \mod M}.

\frac{A}{B} \mod M = ((A \mod M)*B^{-1}) \mod M, here B^{-1} is the modular multiplicative inverse of B under modulo M.

To use this, you will have to calculate \text{numerator} \mod M and \text{denominator} \mod M differently. Also, since M=998244353 is prime, you can use Fermat’s Little Theorem to calculate the modular multiplicative inverse of B under modulo M, which will be equal to B^{M-2} \mod M.

Hence, the result will be:

((\text{numerator} \mod M) * ((\text{denominator} \mod M)^{M-2}\mod M)) \mod M

Have a look at the ncr() function in Python 3 Solution provided in the editorial, it uses the same approach that you are trying to implement.

Also, you can read more about Modular multiplicative inverse here.

1 Like

it is not resolved yet.plz help
lli power(lli x, unsigned long long int y, unsigned long long int mod)
{
if (y == `0)
return 1;
long long int p = power(x, y/2, mod) % mod;
p = (p * p) % mod;

return (y%2 == 0)? p : (x * p) % mod; 

}
// Returns value of Binomial
// Coefficient C(n, k)
lli binomialCoeff(lli n, lli k)
{
lli res = 1,den=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;
	den*=(i+1);
	       den %=mod;
lli inv=power(den,mod-2,mod)%mod;
return (res*inv)%mod;
} 	

}

my solution: CodeChef: Practical coding for everyone

@anon80320319 I had to spend a lot of time on debugging your code. And, finally found the bug. The problem is with this statement:

result = (result*(fact[x[i]]*binaryExp((fact[c[i]]*fact[x[i]-c[i]])%mod,mod-2))%mod)%mod;

Let’s make it look a little simpler,

Let, a = fact[x[i]]
b = (fact[c[i]]*fact[x[i]-c[i]])%mod
c = binaryExp(b, mod-1)

Now, put these symbols in your statement

result = (result * (a * c) % mod)% mod;

Now you can guess the error. :relieved:

result * (a * c) % mod has same execution sequence as (result * a * c) % mod, and each of result, a & c can have values upto 998244353, hence, this will result in long long limit overflow.

The correct statement should be of the following form:

result = (result * ( (a * c) % mod ) )% mod;

Just, replace the statement, with the following one, and your code will be accepted.

result = (result*((fact[x[i]]*binaryExp((fact[c[i]]*fact[x[i]-c[i]])%mod,mod-2))%mod))%mod;

You see, the problem was just because of a pair of parentheses, and it was quite tough to spot the error, so I would suggest, rather than writing a large expression in a single statement, you should always evaluate it by dividing into simpler forms. This will make your code more readable and easy to debug. :slightly_smiling_face:

1 Like

You’re violating this condition

print the name having maximum score, if there are more than one such names, then print the one which appeared first in the list.

P.S. There’s one more error in your code,

lli inv=power(den,mod-2,mod)%mod;
return (res*inv)%mod;

These two statements should be placed after the closing bracket, i.e outside the loop’s body, you’ve written them inside the loop’s body.

1 Like

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

Thank you very much :smile:

please help me in finding reason of WA