Thanks! It answered my questions!

thanks for the editorial. C was bit tricky.

Can anyone please elaborate inclusion-exclusion part for E?

Please someone tell me faster approaches for Problem C.

Can we build the array required in C with LCM(a,b) instead of building it for a*b ?

How ((ab + x) mod a) mod b = (x mod a) mod b . Can anyone please explain !

The problem F can be passed by $$$\mathrm O(n^24^n)$$$ algorithm. Enumerate a set $$$s$$$ to be removed, then denote $$$f(i,\,S)\;(0\leq i\leq n-|s|,\,S\in s)$$$ as the minimum $$$a_i$$$ when the set of elements which is used is $$$S$$$. The transfer is very simple.

There's another approach to solve C (in fact it solves a harder version of it). Let's suppose we are given $$$a,b$$$ and the interval $$$[l,r]$$$ in each test case. It suffices to solve the problem for the interval $$$[0,r]$$$ and the interval $$$[0,l-1]$$$ and substract.

Notice that if we fix that $$$a\leq b$$$ then $$$(x \text{ mod } a) \text{ mod } b$$$ is just $$$x\text{ mod } a$$$. Therefore, if one wants that $$$(x\text{ mod } a)\text{ mod } b = (x\text{ mod } b)\text{ mod } a$$$, this amounts to verify that $$$x\text{ mod } a = (x\text{ mod } b)\text{ mod } a$$$ or equivalently, that:

So, we want to know how many $$$x\in [0,r]$$$ are such that the above congruence is true.

From the division algorithm, we have that there is a $$$q$$$ and $$$r'$$$ such that $$$ x = qb + r'$$$ and $$$0\leq r'<b$$$. The congruence above translates into $$$x\equiv r' \mod{a}$$$, and then what we want is $$$x-r'=qb$$$ to be a multiple of $$$a$$$. This amounts to have $$$q$$$ a multiple of $$$\frac{a}{\gcd(a,b)}$$$, let's say $$$q= n\frac{a}{\gcd(a,b)}$$$ where $$$n\in \mathbb{Z}_{\geq 0}$$$.

So now we want to know how many $$$x\in [0,r]$$$ are such that there is an $$$n\geq 0$$$ satisfying $$$x = n\frac{ab}{\gcd(a,b)} + r'$$$ where $$$0\leq r'<b$$$.

This can be solved in many ways: a naive $$$O(b)$$$ algorithm would be to notice first that $$$\frac{ab}{\gcd(a,b)}=\text{lcm}(a,b)$$$, and then observing that clearly for all $$$n\in \left[0,\left\lfloor\frac{r}{\text{lcm}(a,b)}\right\rfloor-1\right]$$$ and all $$$r'\in [0,b)$$$ those $$$x$$$ work. Then for $$$n=\lfloor\frac{n}{\text{lcm}(a,b)}\rfloor$$$ iterate in $$$O(b)$$$ to take into account those $$$r'\in [0,b)$$$ that work.

There's another approach to solve C (in fact it solves a harder version of it). Let's suppose we are given $$$a,b$$$ and the interval $$$[l,r]$$$ in each test case. It suffices to solve the problem for the interval $$$[0,r]$$$ and the interval $$$[0,l-1]$$$ and substract.

Notice that if we fix that $$$a\leq b$$$ then $$$(x \text{ mod } a) \text{ mod } b$$$ is just $$$x\text{ mod } a$$$. Therefore, if one wants that $$$(x\text{ mod } a)\text{ mod } b = (x\text{ mod } b)\text{ mod } a$$$, this amounts to verify that $$$x\text{ mod } a = (x\text{ mod } b)\text{ mod } a$$$ or equivalently, that:

So, we want to know how many $$$x\in [0,r]$$$ are such that the above congruence is true.

From the division algorithm, we have that there is a $$$q$$$ and $$$r'$$$ such that $$$ x = qb + r'$$$ and $$$0\leq r'<b$$$. The congruence above translates into $$$x\equiv r' \mod{a}$$$, and then what we want is $$$x-r'=qb$$$ to be a multiple of $$$a$$$. This amounts to have $$$q$$$ a multiple of $$$\frac{a}{\gcd(a,b)}$$$, let's say $$$q= n\frac{a}{\gcd(a,b)}$$$ where $$$n\in \mathbb{Z}_{\geq 0}$$$.

So now we want to know how many $$$x\in [0,r]$$$ are such that there is an $$$n\geq 0$$$ satisfying $$$x = n\frac{ab}{\gcd(a,b)} + r'$$$ where $$$0\leq r'<b$$$.

This can be solved in many ways: a naive $$$O(b)$$$ algorithm would be to notice first that $$$\frac{ab}{\gcd(a,b)}=\text{lcm}(a,b)$$$, and then observing that clearly for all $$$n\in \left[0,\left\lfloor\frac{r}{\text{lcm}(a,b)}\right\rfloor-1\right]$$$ and all $$$r'\in [0,b)$$$ those $$$x$$$ work. Then for $$$n=\lfloor\frac{n}{\text{lcm}(a,b)}\rfloor$$$ iterate in $$$O(b)$$$ to take into account those $$$r'\in [0,b)$$$ that work.

"The property given in the statement holds for x if and only if it holds for x mod ab." , couldn't get this line. Can anyone explain?

The equality to the solution of problem E is actually Stirling Number of the second kind(How many possible ways can we put n different things into k indifferent boxes such that the order of things in each box doesn't matter and each box must have atleast one thing?) multiplying it with k!.

I have used the following greedy approach for problem D. Start iterating from the smallest element and assign all the frequencies of it in one array till the time the capacity of array allows or we have exhausted all the frequencies. If we have exhausted the frequency of that particular element, move on to the next element, if the capacity of the array is allowed.

It fails on test case 11. Can anyone please help me figure out what's wrong with the approach?

I have a weird solution for D that's more complicated but also simpler than the editorial's. Instead of precalculating the bounds, I construct the answer directly.

I have a vector<vector<int>> $$$t$$$ that will represent my testcases, and a position $$$p$$$ that will represent the testcase I'm adding to. $$$p$$$ will always go from the back of $$$t$$$ to the front. Also, I will add in each array in order of decreasing length.

Suppose I want to add in an array of length $$$m$$$. $$$t[p]$$$ consists only of arrays of length greater than or equal to $$$m$$$, so they all contribute to $$$c[m]$$$. If there's still room for $$$m$$$ there, go ahead and add it. If there isn't (i.e. $$$|t[p]|=c[m]$$$), we can for the sake of argument consider $$$t[p]$$$ "filled up" and decrement $$$p$$$, or set $$$p$$$ to the back of $$$t$$$ if $$$p=0$$$. Note that we can only move on from a $$$t[p]$$$ when it is filled up.

Now, $$$p$$$ is one less. The last time $$$t[p]$$$ was filled up was when $$$p$$$ cycled through $$$t$$$ earlier. The $$$c$$$ at that time was either less or equal to now. If it was less, great! there's more room for our $$$m$$$. If not, we know the whole $$$t$$$ has been travelled through with the same value of $$$c=c[m]$$$. This means we can't place $$$m$$$ anywhere in $$$t$$$ because all the testcases are filled to the same $$$c$$$! Our only option is to add a new testcase and place $$$m$$$ there. Set $$$p$$$ there too.

Make sure to account for when $$$t$$$ is completely empty as well.

Since we only add testcases when it's impossible to place $$$m$$$ anywhere else, the solution must be optimal. Furthermore, for every $$$m$$$ we only use append and size operations on at most two distinct locations $$$p$$$, so every $$$m$$$ is $$$O(1)$$$. This means the runtime of the main process is $$$O(n)$$$, and total runtume with sorts and everything is $$$O(nlog(n)+k)$$$, just like in the official solution.

Find it here: 78200438

Can anyone explain the editorial of 1342D — Multiple Testcases.

Specifically how it is proven Let the number of the arrays of size greater than or equal to i be gi. The answer is a maximum ⌈gi/ci⌉ over all i from 1 to k. You can prove that you can't fit gi arrays in less than ⌈gi/ci⌉ testcases with the pigeonhole principle

How to solve E with FFT?

for the problem D I am not able to understand why my solution https://mirror.codeforces.com/contest/1342/submission/78247111 is correct while https://mirror.codeforces.com/contest/1342/submission/78247043 is wrong. the only difference is the 2 solution is that I have used 1e10 as a multiplier in the first and 1e11 in the second . since the constraints were 2*1e5 I don't think replacing 1e10 with 1e11 should be an issue , but it turns out it is . It will be really helpful if anyone can explain reason behind failure of later second submission

In the Editorial for Problem D. I am not able to understand this thing, "Let the number of the arrays of size greater than or equal to i be gi. The answer is a maximum ⌈gi/ci⌉ overall i from 1 to k". Can somebody explain how is this working? I am able to form some intuition about it after reading the Editorial but it is still not completely clear to me. If somebody can explain it in a little more detail it will be highly appreciated.

I am unable to find what is wrong in my code. I have calculated all values from l to r for which (x%a)%b == (x%b)%a using lcm(a,b) and simple multiplication and then subtracting it from (r-l+1). But my code is stuck at 2nd test case. Here is my code code.

How does https://mirror.codeforces.com/contest/1342/submission/78244632 pass but https://mirror.codeforces.com/contest/1342/submission/78244302 fails? There is only one line change, and that line never gets executed. The 'cout << "???"' line never gets executed, since the test passes.

Can anyone help with TL on problem F?) https://mirror.codeforces.com/contest/1342/submission/78328093

for D problem : Multiple Testcases Why do we need to assign indexes by sorting in decreasing order ..will doing so in increasing order work?

for D problem: why do we need to assign indexes by sorting in decreasing order..will doing same in increasing order work?

For D, why does inserting the (i mod ans)th testcase always optimally construct the testcase array? Like is there any proof or intuition to understand/come up with it ?

Video solution for C.

War. War never changes. Can you do something about it Neon?

C- Yet Another counting problem

An alternate O(1) for each query solution. Let's denote a as the smaller one of (a,b) and b as larger one of (a,b). Any number lying in the range [0, b) would satisfy ((xmoda)modb)=((xmodb)moda). Let's denote LCM of a and b as l. The range [0,b) would imitate itself for the range [l, l+b), [2l, 2l+b), [3l,3l+b).... So we can count the multiples of l in the given range and also find the restricted range by adding b to it. It is also possible that a multiple of l might fall outside the given range but yet some numbers fall in the range [nl, nl+b), so we need to take extra care for that.

My code doesn't work. Maybe somebody could help me figure out the mistake in the logic?

You can do C in $$$O(1)$$$ per query and $$$O(q)$$$ per test case with no precomputation required. I believe in the small problems like A,B,C the intended solution should be the fastest one. Even if the explanation is a bit longer and not that beautiful. Here is my solution. https://mirror.codeforces.com/contest/1342/submission/78195420

.

Here's a terrible overkill solution for E, as an alternative to inclusion-exclusion. We want to count the number of ways to distribute $$$n$$$ rooks into $$$m = n - k$$$ fixed columns, such that all of them remain non-empty and there's one in every row. Assume that we fix the ordered tuple $$$a_1, a_2, \dots, a_m$$$ of how many rooks we place in each column. Then the number of ways to place the rooks is

This formula counts the number of ways to arrange the $$$n$$$ rooks if they're labeled and then eliminate the order from all rooks in the same column. Thus the problem is reduced to calculating

Which we can interpret as the coefficient of $$$x^n$$$ in $$$\left(x + \frac{x^2}{2!} + \dots + \frac{x^n}{n!}\right)^m$$$. We can calculate this in $$$O(n \log^2 n)$$$ with binary exponentiation and NTT, which is enough to pass with a few constant factor optimizations.

Can anyone explain me why ((ab+x) mod a) mod b == (x mod a) mod b
I am a beginner and don't know much about modular arithmetic... If there are some proofs of modular arithmetic that I should know as a competitive programmer can you please mention such resources
Thanks in advance :)

In problem D what's wrong for test case 1 if I give the answer as 4 1 2 2 3 as c1 can have 4 elements greater than 1???

For problem F. Why did you decide to put such bounds on your max test? I calculate the following lower bound on your max test number of operations -- $$$4500 \cdot f(5) + 400 \cdot f(8) + 50 \cdot f(10) + 25 \cdot f(11) + 15 \cdot f(12) + 7 \cdot f(13) + 2 \cdot f(14) + f(15)$$$, where $$$f(n) = n^2 3^n$$$. That is, according to my python $$$9 ~163 ~838 ~367$$$. Why did you put 7 seconds on that?

Cause my solution jumps between TL and AC just when I change backward DP to forward DP and change a couple of if statements correspondingly.

Can anyone correct me if I'm wrong or say that I'm right? In Ques C, we may notice that all numbers $$$x\in[k\cdot \operatorname{lcm}(a,b), k\cdot \operatorname{lcm}(a,b)+\operatorname{max}(a,b)-1]$$$ where $$$k\in \mathbb{Z}$$$ follow $$$(x \mod a)\mod b = (x \mod b)\mod a$$$. We can count all other numbers in the range $$$[l,r]$$$ in $$$\mathcal O(1)$$$ time. Thus, the time complexity can be reduced down to $$$\mathcal O(q)$$$ per test case.

I have an issue about ceil. Can anyone tell me why the submit is incorrect? https://mirror.codeforces.com/contest/1342/submission/78388627 Thank you.

Problem E has fft tag, how to solve it using fft?

Can somebody Please Explain Why I am getting WA on Problem C Submission.

Problem E

How to calculate the number of ways to distribute the rooks into $$$c$$$ columns? One of the options is to choose the columns we use (the number of ways to do this is $$$C_n^c$$$), and then use inclusion-exclusion to ensure that we are counting only the ways where each column contains at least one rook.

Why "each column contains at least one rook" not equal to $$$C_{n-1}^{c-1}$$$ — number of distributions of $$$n$$$ not different items into $$$c$$$ not empty groups?

In Problem D

Input

7 7
1 2 3 4 5 6 7
2 3 2 1 2 1 1

In the above input, the editorials output is:

4
2 7 3
2 6 2
2 5 1
1 4

which says we need min 4 testcases, i think the min number would be 3 using the following distribution of arrays:

3
2 5 7
3 2 3 6
2 1 4

PLEASE, correct me if I am wrong.

Can anyone explain the E part second test case as for 3x3 chessboard and exactly 3 pairs why
|R|R|.|
|R|.|.|
|R|.|.|
is not one of the valid solution? I think in this 3 pairs are attacking each other.

In case anyone need div2 D explanation,code and example Here

I was surprised that $$$O(n^23^n)$$$ solution passed in F. I have $$$O(n^22^n+n3^n)$$$ solution.

Notice, that if $$$cnt_1 > cnt_2$$$, then $$$dp_{cnt_1,mask,pos} < dp_{cnt_2,mask,pos}$$$ for any $$$mask, pos$$$ in valid state. Thus, there is no need to recount from all dynamics states. For each $$$mask$$$ and $$$pos$$$ find the largest $$$cnt$$$, that $$$dp_{cnt,mask,pos}$$$ valid, and update $$$dp_{cnt,smask,pos}$$$ for all $$$smask$$$ that don't intersect with $$$mask$$$.

We need $$$O(n^22^n)$$$ for find largest $$$cnt$$$ for each $$$mask$$$ and $$$pos$$$ and $$$O(n3^n)$$$ for update dynamic.

For Div2D, I converted given array into a map sorted with descending order keys, and then I traverse the map from largest key to smallest, trying to make a set of testcases,while decreasing the frequency of which I am using and deleting those whose freq becomes 0.
I keep on doing this until, map becomes completely empty.
I am getting runtime error on tc 1, which is working fine locally.
Can anyone suggest how to carefully iterate over a maps keys from desc to asc order while deleting some keys based on some condition ?
I think the logic is correct, becoz if I use array instead of maps, while increasing the time complexity since I loop from max no to 1 everytime, I am getting TLE on tc16.

Solution with map

@Neon: For problem F, what does order stand for in the statement "Suppose we don't have any constraints on the order of elements," Is it for the number of elements?

Also in the statement "This runs in O(n*(3^n)), if we use an efficient way to iterate on all masks that don't intersect with the given mask.",how did you derive the O(n*(3^n))

I am pretty new to competitive programming and your reply would be of great help to me.

For the forth problem, can somebody explain and help me figure out whats wrong in my code. I am getting WA for the test case 11. Though i am correctly determining the minimum number of testcases required, but maybe doing some mistake in filling the arrays for the test cases.

int main(){
	BOOST();
	int n,k;
	cin>>n>>k;
	vector<int>mi(n);
	vector<int>ci(k+1);
	for(int i=0;i<n;i++)cin>>mi[i];
	for(int i=1;i<=k;i++)cin>>ci[i];

	sort(mi.begin(),mi.end());	
	int size=INT_MIN;
	int cnt;
	for(int i=1;i<=k;i++){
		cnt=n-(lower_bound(mi.begin(),mi.end(),i)-mi.begin());
		size=max(size,(cnt+ci[i]-1)/ci[i]);
	}
	
	vector<int>final[size+1];
	int flag=1;
	int cntr=0;
	while(flag<=size){

		final[flag].pb(mi[cntr]);
		int left=ci[mi[cntr]]-1; // left denotes how many more numbers i can still fill after filling mi[cntr]
		for(int i=cntr+1;i<n;i++){
			if(left==0){     // if left==0, then break;
				cntr=i;
				break;
			}
			final[flag].pb(mi[i]);
			left=min(left-1,ci[mi[i]]-1);  // every time we take minimum of the numbers we can fill after filling mi[i]
		}
		flag++;
	}

	printf("%d\n",size);
	for(int i=0;i<size;i++){
		printf("%d ",(int)final[i].size());
		for(auto &x:final[i])
			printf("%d ",x);
		printf("\n");
	}
}

Another solution for D using priority queue

int n, k, c[MAX];
vector<int> m;
vector<vector<int>> ans;

struct cmp {
	bool operator()(int i1, int i2) {
		return ans[i1].size() > ans[i2].size();
	}
};

int main() {
	FAST; cin >> n >> k;
	m.resize(n); 
	for (int i = 0; i < n; i++) cin >> m[i];
	for (int i = 1; i <= k; i++) cin >> c[i];
	sort(m.begin(), m.end(), [](int i1, int i2) {
		return i1 > i2; });

	priority_queue<int, vector<int>, cmp> pq;
	ans.resize(1);
	pq.push(0);

	int cnt = 1;
	for (int i : m) {
		int idx = pq.top(); pq.pop();
		if (ans[idx].size() + 1 <= c[i]) {
			ans[idx].push_back(i);
		}
		else {
			ans.resize(cnt + 1);
			ans[cnt].push_back(i);
			pq.push(cnt);
			cnt++;
		}
		pq.push(idx);
	}

	cout << ans.size() << '\n';
	for (vector<int> v : ans) {
		cout << v.size() << " ";
		for (int i : v) cout << i << " ";
		cout << '\n';
	}
}

From the editorial for F (first paragraph): "To model transitions, we simply iterate on the mask of elements that will be merged into a new one, and check if its sum is greater than the last element we created."

I'm kind of lost here. Is there any mathematical formulation of the DP transition that could potentially clarify this? (trying to upsolve this since this is the only problem in the contest idk how to do).

if you don't know the formula for ceil function it is given in D

i'm confused about the prefixes. in some cases, you'll have ends hanging from both the left and right, and because the mod is not uniformly distributed, if you calculate it by "the amount of mods that worked previous to this index" then what will happen if you have like 5 integers hanging from the left and 7 from the right? the 7 can be calculated easily true but what about the 5 on the right? if you calculate it using prefixes, then instead of getting the correct index you'll get prefix[a*b-5]. or do additive shifts not affect mods at all, and therefore there's no hanging left integers?

Hello!!

I was attempting Problem D and my approach was as follows:- I first sorted the array a in increasing order and then started traversing in the reverse direction. If for some a[i] I could find a test case whose size is less than a[i]'s capacity then I will add that element to that test case and if no such test case exists then I will make a new test case.

It is getting wrong answer at Testcase 17. I would appreciate if someone could help with the bug in my logic. (Neon BledDest adedalic awoo)

Here is my solution: 80590063

https://ideone.com/VTSzgt alternative solution for problem C with time complexity O(log(a)) for query(because of gcd)

Good contest

Can someone help me with C. My idea for this problem was the value of (x%a)%b and (x%b)%a repeats itself for every lcm(a,b) distance. So i thought i could iterate through the first lcm(a,b) numbers(from l) and add all the multiples till r to the answer. But it TLEs... can someone help on improving the complexity of my solution. Thanks in advance!!
Link to My Submission

in C a*b can be replaced by lcm of a and b also.

Whats wrong with my solution for problem E?

Let c = n-k. Number of ways such that c columns are filled = (Number of ways such that <= c columns are filled) — (Number of ways such that <= c-1 columns are filled)

So formula is $$$ \binom{n}{c}c^n - \binom{n}{c-1}(c-1)^n $$$