There is a typing mistake in the post. The date should be 21st June

yash_daga sir orz !..

AST_TheCoder kopsss bro

Contest starts in 30 minutes!

There is a mistake in Transfusion Chain problem.
Blood type O donors can also donate to recipients with blood types O, according to the test cases, but it is not mentioned in the statement.

In the second testcase of ARRAY_BREAK, if the arr is [1], then after applying any operation will it include the expected sum?

Like it will be (sum+1)/(cnt+1) or sum/cnt(unaffected by this)?

name it a probability(math) contest rather than a dsa or cp contest

MathChef :/

My O(K*N^2) submission is getting TLE on problem "Break this array".Runtime is too strict.

3 probability problem in a contest.. wth admin (:
also rating system skip the last contest rating which show on right side of problemset page, plz look at that.

How were people able to solve TRANCHAIN without even considering "blood group O can donate to O as well"?

I wasted the first 30 minutes on the first problem due to this typo.

Constraints of Guess game say that N >= 2 but for the first subtask it is N >= 1. How do you define the expectation when N == 1?

Unfortunately I just wrote my full solution to that but can't submit. Please allow practice mode.

i was getting 31/7 for the second sample test case in the problem break this array which equals 428571436 modulo 1e9+7. Can explain me what is the actual ans to it ?

Thanks for the Contest. Though it was a bit math-heavy, I learned something new today.

Probability — GCD combination question was really very good.

Can anyone explain me 2nd test case of ARRAY_BREAK?

Similar Question for Chef and Moves of GCD: Link

My submission: Link

Guess Game could also be simply done in O($$$NloglogN + T\sqrt{N}$$$). If we fix the small number $$$d$$$, the large number can have $$$\lfloor\frac{n}{d}\rfloor-1$$$ values. Also since the answer only depends on $$$d$$$, we can find the range of $$$d$$$ for which $$$\lfloor\frac{n}{d}\rfloor$$$ is constant and add their contribution to answer. It is well known that there are $$$O(\sqrt{n})$$$ distinct ranges.

In Question BREAK THE ARRAY I Dont Know where my code is bugging can anyone please figure it out. It is not able to run even in lower limits of 100 Yet other peoples have did the similar and got AC sub link :- https://www.codechef.com/viewsolution/98819410

There is an $$$O(n)$$$ solution to PARTITION without using segment trees. Consider the $$$O(n^2)$$$ dp

int brute(vector<int> a){
	int n = a.size();
	vector<int> dp(n,-inf);
	for(int i = 0; i < n; i++){
		int lar = -inf;
		for(int j = i; j >= 0; j--){
			lar = max(lar,a[j]);
			dp[i] = max(dp[i],(j == 0 ? 0 : dp[j-1]) + 1 - lar);
		}
	}
	return dp[n-1];
}

Transitions can be maintained using monotonic stack.

int efficient(vector<int> a){
	int n = a.size();
	
	vector<int> dp(n);
	vector<int> st     = {+inf};
	vector<int> best   = {-inf};
	vector<int> dp_max = {-inf};
	
	for(int i = 0; i < n; i++){
		int mx = (i == 0 ? 0 : dp[i-1]);
		while(st.back() <= a[i]){
			mx = max(mx,dp_max.back());
			st.pop_back();
			best.pop_back();
			dp_max.pop_back();
		}
		
		st.push_back(a[i]);
		best.push_back(max(best.back(),mx + 1 - a[i]));
		dp_max.push_back(mx);
		
		dp[i] = best.back();
	}
	return dp[n-1];
}

can someone tell what's wrong in my solution for subtask1 of "Break This Array", soln

I guess there is a problem while viewing solutions of some participants, can you please look into it. Example of one such user's submission

For Problem CAMOG, the editorial says. " We do the $$$2^k$$$ operation for each pair of (number, divisor) below $$$N$$$. It’s well-known that there are $$$\mathcal{O}(N\log N)$$$ such pairs, so a simple upper bound on complexity is $$$\mathcal{O}(2^6 \cdot N\log N)$$$. "

Could you explain why is the number of pairs $$$\mathcal{O}(N\log N)$$$ , I was thinking that it should be something like $$$\Sigma$$$ $$$x^{1/3}$$$. I read somewhere that $$$N^{1/3}$$$ is a good upperbound for the number of divisors.