Educational Codeforces Round 86 Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Tutorial

Solution (Roms)

for _ in range(int(input())):
    x, y = map(int, input().split())
    a, b = map(int, input().split())
    b = min(b, a + a)
    if x < y:
        x, y= y, x
    print(y * b + (x - y) * a)

1342B - Binary Period

Idea: adedalic

Tutorial

Solution (adedalic)

fun main() {
    val T = readLine()!!.toInt()
    for (tc in 1..T) {
        val t = readLine()!!

        val s = t.toCharArray().distinct().joinToString("").repeat(t.length)
        println(s)
    }
}

1342C - Yet Another Counting Problem

Idea: BledDest and adedalic

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int N = 40043;

int len;
int p[N];

void build(int a, int b)
{
	len = a * b;
	p[0] = 0;
	for(int i = 1; i <= len; i++)
	{
		p[i] = p[i - 1];
		if((i % a) % b != (i % b) % a)
			p[i]++;
	}
}

long long query(long long l)
{
	long long cnt = l / len;
	int rem = l % len;
	return p[len] * 1ll * cnt + p[rem]; 
}

long long query(long long l, long long r)
{
	return query(r) - query(l - 1);
}

int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
	{
		int a, b, q;
		cin >> a >> b >> q;
		build(a, b);
		long long l, r;
		for(int j = 0; j < q; j++)
		{
			cin >> l >> r;
			cout << query(l, r) << " ";
		}
		cout << endl;
	}
}

1342D - Multiple Testcases

Idea: BledDest

Tutorial

Solution (pikmike)

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;


int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	vector<int> c(k + 1);
	forn(i, k) scanf("%d", &c[i + 1]);
	
	sort(a.begin(), a.end(), greater<int>());
	int ans = 0;
	for (int i = k, g = 0; i >= 1; --i){
		while (g < n && a[g] == i) ++g;
		ans = max(ans, (g + c[i] - 1) / c[i]);
	}
	vector<vector<int>> res(ans);
	forn(i, n) res[i % ans].push_back(a[i]);
	
	printf("%d\n", ans);
	forn(i, ans){
		printf("%d", int(res[i].size()));
		for (auto it : res[i])
			printf(" %d", it);
		puts("");
	}
	return 0;
}

1342E - Placing Rooks

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 200043;

int add(int x, int y)
{
	return (x + y) % MOD;
}

int sub(int x, int y)
{
	return add(x, MOD - y);
}

int mul(int x, int y)
{
	return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
	int z = 1;
	while(y > 0)
	{
		if(y % 2 == 1)
			z = mul(z, x);
		x = mul(x, x);
		y /= 2;
	}
	return z;
}

int inv(int x)
{
	return binpow(x, MOD - 2);
}

int fact[N];

int C(int n, int k)
{
	return mul(fact[n], inv(mul(fact[k], fact[n - k])));
}

int main()
{
	int n, k;
	cin >> n >> k;
	
	if(k > n - 1)
	{
		cout << 0 << endl;
		return 0;
	}
	
	fact[0] = 1;
	for(int i = 1; i <= n; i++)
		fact[i] = mul(i, fact[i - 1]);
	int ans = 0;
	int c = n - k;
	for(int i = c; i >= 0; i--)
		if(i % 2 == c % 2)
			ans = add(ans, mul(binpow(i, n), C(c, i)));
		else
			ans = sub(ans, mul(binpow(i, n), C(c, i)));
	ans = mul(ans, C(n, c));
	if(k > 0)
		ans = mul(ans, 2);
	cout << ans << endl;
}

1342F - Make It Ascending

Idea: Neon

Tutorial

Solution (Ne0n25)

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)

typedef pair<int, int> pt;

const int INF = 1e9;
const int N = 15;

int n;
int a[N];
int sum[1 << N];
int dp[N + 1][1 << N][N + 1];
pt p[N + 1][1 << N][N + 1];

void solve() {
	scanf("%d", &n);
	forn(i, n) scanf("%d", &a[i]);
	
	forn(mask, 1 << n) {
		sum[mask] = 0;
		forn(i, n) if (mask & (1 << i))
			sum[mask] += a[i];
	}	
	
	forn(cnt, n + 1) forn(mask, 1 << n) forn(pos, n + 1)
		dp[cnt][mask][pos] = INF;
	
	dp[0][0][0] = 0;
	forn(cnt, n) forn(mask, 1 << n) forn(pos, n) if (dp[cnt][mask][pos] < INF) {
		int rmask = mask ^ ((1 << n) - 1);
		for (int nmask = rmask; nmask; nmask = (nmask - 1) & rmask) {
			if (sum[nmask] <= dp[cnt][mask][pos])
				continue;
			if ((nmask >> pos) == 0)
				continue;
			int npos = pos + __builtin_ctz(nmask >> pos) + 1;
			if (dp[cnt + 1][mask | nmask][npos] > sum[nmask]) {
				dp[cnt + 1][mask | nmask][npos] = sum[nmask];
				p[cnt + 1][mask | nmask][npos] = mp(mask, pos);
			}
		}
	}
	
	int acnt = 0, apos = 0;
	forn(cnt, n + 1) forn(pos, n + 1) if (dp[cnt][(1 << n) - 1][pos] < INF)
		acnt = cnt, apos = pos;
		
	vector<pt> ans;
	
	int mask = (1 << n) - 1, pos = apos;
	for (int cnt = acnt; cnt > 0; --cnt) {
		int nmask = p[cnt][mask][pos].x;
		int npos = p[cnt][mask][pos].y;
		forn(i, n) if ((nmask ^ mask) & (1 << i))
			if (i != pos - 1) ans.pb(mp(i, pos - 1));
		mask = nmask, pos = npos;
	}
	
	
	printf("%d\n", sz(ans));
	forn(i, sz(ans)) {
		int from = ans[i].x;
		forn(j, i) from -= ans[j].x < ans[i].x;
		int to = ans[i].y;
		forn(j, i) to -= ans[j].x < ans[i].y;
		printf("%d %d\n", from + 1, to + 1);
	}
}	

int main() {
	int tc;
	scanf("%d", &tc);
	forn(i, tc) solve();
		
}

for (int i = 0; i < n; i++) { if (t.empty()) t.push_back({m[i]}); else if (t[p].size() < c[m[i]]) t[p].push_back(m[i]); else { if (p == 0) p = t.size(); p--; if (t[p].size() < c[m[i]]) t[p].push_back(m[i]); else { t.push_back({m[i]}); p = t.size() - 1; } } }

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"); } }

Comments (155)

Show archived | Write comment?

ticmis

5 years ago, # |

Thanks! It answered my questions!

→ Reply

aakash10399

5 years ago, # ^ |

-6

Quite literally xD

_NoobMaster__

+11

thanks for the editorial. C was bit tricky.

JOF

+36

Can anyone please elaborate inclusion-exclusion part for E?

Russell_Emerine

← Rev. 4 →

+120

Suppose we just try to place the rooks in the $$$c$$$ columns we've chosen. There are $$$c^n$$$ possibilities, because we can place each rook in any of $$$c$$$ columns and there are $$$n$$$ rooks. (We will see this is when $$$i=0$$$.)

However, we've accidentally counted some arrangements where some columns aren't used. Let's subtract all arrangements where one column is empty. We choose the empty column ($$$c \choose 1$$$), and the rooks go in the remaining columns ($$$(c-1)^n$$$). Like in the first case, some other columns might be empty; we just know for sure the column we've chosen is. So, there are $$${c \choose 1} (c-1)^n$$$ combinations we want to subtract. (This is $$$i=1$$$.)

Now, consider combinations where two rows are empty. For each pair of rows $$$a$$$ and $$$b$$$, we've already subtracted those combinations in the case $$$i=1$$$. Actually, we've subtracted them once for the case where $$$a$$$ is for certain empty, and once for the case where $$$b$$$ is for certain empty. We've overcompensated, so we will add back in the combinations where two rows are empty, so add $$${c \choose 2}(c-2)^n$$$. ($$$i=2$$$)

I think we need another iteration to clarify why we can just alternate. For $$$i=3$$$, consider rows $$$p$$$, $$$q$$$, and $$$r$$$. (__r i p n a m e s p a c e s lol__) We've accidentally added it once at $$$i=0$$$, subtracted it for $$$p$$$, then $$$q$$$, then $$$r$$$ for $$$i=1$$$, added it for $$$p, q$$$, then $$$p, r$$$, then $$$q, r$$$ for $$$i=2$$$. So, we need to unadd it back.

And just keep going.

So, it turns out it works because of that weird alternating binomial property. But we don't really need to know that, as long as we can find the pattern.

+38

The "alternating binomial property" can be proven easily enough. The number of combinations we've already counted so far for some $$$i$$$ is $$$\displaystyle\sum_{j=0}^{i-1} {(-1)^j {i \choose j}}$$$. (See case $$$i=3$$$ in my other post for the reasoning.) This is just $$$\displaystyle\sum_{j=0}^{i} {(-1)^j {i \choose j}} - (-1)^i {i \choose i}$$$. The summation is just a binomial expansion, so this simplifies to $$$(1-1)^i - (-1)^i {i \choose i} = 0^i - (-1)^i = -(-1)^i$$$, This means we have overcounted by that much, so we add $$$(-1)^i$$$ to the answer to correct it.

_vagabond

can E's solution be also written as S(n,n-k)*(n-k)! .where S(i,j) is stirling number?

Exactly

alphatrance

How did you conclude that?

I mean it's true from the mathematical perspective, but is there any intuition for it?

Josik

In our case, $$$S(n, n-k)$$$ represents number of ways to distribute $$$n$$$ rooks into $$$n - k$$$ nonempty columns. This number doesn't consider the order of columns (e.g. distribution $$$[[1,2],[3]]$$$ is the same as $$$[[3], [1,2]]$$$). However, these are two different distributions for us. That is why we multiply the number by $$$(n - k)!$$$, the number of permutations of $$$(n - k)$$$ columns.

lemongrab

← Rev. 3 →

Wait what does $$$n-k$$$ mean, $$$n-k$$$ may be negative here! Although I also was thinking about stirlings. First some background on what I understand:

In particular if $$$k \neq 0$$$ (for $$$k = 0$$$ answer is $$$n!$$$) then we calculate all ways for $$$n$$$ rooks to span all $$$n$$$ rows, call it $$$W$$$. Our answer will be $$$2W$$$ (replace row with column)

Now as you say, since $$$k\neq 0$$$ some columns will be repeated. So we group them by columns. Stirling number $$$S(n,p)$$$ will give set of all partitions of $$$n$$$ into $$$p$$$ groups. Now pairings in this question depends on the size of groups right, say $$$p = 2$$$ and $$$n = 4$$$ then there may be 3-1 partition or 2-2 partition where in the first case pairings will be $$$\binom{3}{2}$$$ and in second case it will be $$$\binom{2}{2}\cdot\binom{2}{2}$$$ so how stirling will help here

Please tell me if I misunderstood it, Thanks a lot.

Nice, detailed explanation. It was too hard for me to get this inclusive-exclusive approach by myself.
Just one note about this part: " We've accidentally counted it once at i=0, subtracted it for p, then q, then r for i=1, added it for p,q, then p,r, then q,r for i=2. So, we need to add it back. " Isn't it supposed to be subtraction for i = 3, not add it back ? If it is so , than I got it.

lucasxia01

Yes, he meant subtracting it for i = 3.

Oh, oops! Thanks, I'll correct that.

utsavparakhiya

We want k pairs so lets group first (k+1) elements, they will have n options, next rook will have n-1, next will have n-2 and so on.

So the answer is n*(n-1)*(n-2)*...*(k+1)

What is wrong with this answer??

zucker42

I don't know if I understand your answer, but I think you don't account for arrangements where two different attacking pairs are in different columns.

For example, I don't think your way counts the following arrangement for $$$n = 4$$$, $$$k = 2$$$.

R . . .
R . . .
. R . .
. R . .

fishlicker

Hey this is a very clear explanation thank you. I was wondering if you came up with a to define sets that fulfill this expression. For example if you let S(i) be the set of configurations where at least i columns have no rooks, we have

$$$S(i) = {c \choose i} \cdot (c - i)^n$$$

And $$$S(n) \subset S(n - 1) \subset ... \subset S(1) \subset S(0)$$$ which implies $$$S(0) / S(1)$$$ is the answer. This is incorrect because $$$S(i)$$$ double counts some configurations and throws them away. I was wondering if you had a set definition that worked?

dorado7

← Rev. 2 →

Thanks for the explanation.

rraj0510

Consider n=3, k=1

|r| | |

| |r| |

here, in both the arrangements column 1 has 2 rooks, column 2 has 1 rook and column 3 has no rook.

How have we considered the above two cases different? It seems we just distributed n rooks in c columns each being non-empty. I cannot understand. Please explain!

Pluviophile_

Hey Russell_Emerine so as you said to place $$$n$$$ rooks in $$$c$$$ columns initially we get $$$c^n$$$ arrangements, what I think this is is that for every rook we have $$$c$$$ options to place to but why don't we consider the permutation among the rows? Say, for example, a column contains $$$k$$$ rooks then these $$$k$$$ rooks can be spread throughout $$$n$$$ rows so arranging $$$k$$$ rooks in that column(which has $$$n$$$ rows) hence $$$C_{k}^{n}$$$ possibilities for that column similarly why are we not considering the arrangement of those rooks among the rows for each column? I hope you understand my question, Thanks in advance.
I might sound like a novice but am not good at combinatorics so I'd be grateful for any help :)

CP_Sucks

This is because the rooks are not distinct, it dosen't matter if first rook goes to first row, or last row both cases are same configurations. Only thing that matters is all rows should be filled. So we won't consider nCk

But the thing is there might be less than $$$n$$$ rooks in a row in the arrangement, so in that case, the arrangement does matter, consider it like we know every row is gonna be filled but which row must be filled with which column varies hence my question.

There can be no case where there is less than n rooks, this is the first assumption we are taking that, all rooks must be in all different rows so that they attack all non empty cells(columns as well as rows). After that assumption we are just playing around with the column positions. If that was the case the question would be much harder to solve.

I don't think you understood my query, I know all $$$n$$$ rows are filled but which rows is filled in which column will differ, every $$$(n-k)$$$ column will have at least $$$1$$$ rook, but rest rooks are distributed arbitrarily among them, hence a column will have less than $$$n$$$ rooks for sure so I was wondering about arranging them in $$$n$$$ rows, but nevermind I understood my flaw, thanks for your time.

Even I had the same doubt but got cleared somehow.

Just consider assigning numbers to each rook (virtually) R1, R2, R3, ...Rn denoting the row number to which this rook will belong.

Note: since all rooks are similar, it does not matter which rook is assigned which row number.

So, consider n-3, k=1

|r1| | |

| |r2| |

|r3| | |

and

|r2| | |

| |r3| |

In this way we consider them different. Since we were assigning column to each rook independent of the other. we have already counted this. I hope this was useful.Give a thumps up if you agree.

Ohh now I understood thanks buddy, rraj0510 so we assign each rook an id corresponding to its row that rook is to be placed in that row only that way all possibilities are covered with $$$c^n$$$, Now I got the intended intuition.

_greymatter

what about the arrangements of rooks within each of these columns, how is that accounted for ?

https://codeforces.me/blog/entry/76633?#comment-612402

thanks!

ghoshsai5000

Hey, I just wanted to ask if the rooks are numbered ?

For example, if there are 3 rooks and 3 columns,

Does it make any difference if the rooks go to columns {1, 2, 3} respectively instead of {2, 1, 3} ?

Naithani

4 years ago, # ^ |

In the 3rd and 4th paragraph you mean COLUMNS, not rows??

Russell does a good job of explaining IE if you're not familiar. If you are familiar, if we take the IE formula from wikipedia:

$$$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|-\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|+\sum _{1\leqslant i<j<k\leqslant n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.$$$

Let $$$A_i = $$$(arrangements such that column i is empty), then

$$$\left|\bigcup _{i=1}^{c}A_{i}\right|$$$

represents the number of ways to arrange the rooks among $$$c$$$ columns with an empty column among those $$$c$$$ columns. Therefore, the number of ways such that there is no empty column is

$$$\binom{c}{0} c^n - \left|\bigcup _{i=1}^{c}A_{i}\right|$$$

, which when simplified will give you the formula.

A cleaner way for me to think about this entire problem, that doesn't directly use IE (but uses IE under hood) is that first I choose the k empty columns, then I have to group the rows together which have rooks that attack each other, then I have choose a column for each group of rows. The first choice is $$$\binom{n}{k}$$$, the second choice can be calculated with a Sterling number of the second kind $$$S(n, n - k)$$$, and the third is $$$(n - k)!$$$. Alternatively, $$$S(n, n - k) * (n - k)!$$$ is the number of ways we can assign $$$n$$$ rows to $$$(n - k)$$$ non-empty columns.

Then $$$ans = 2 * \binom{n}{k} * S(n, n - k) * (n - k)!$$$ which gives the same formula.

vivek8420

My solution with explanation in comments, https://codeforces.me/contest/1342/submission/78619750

PRESS_F_2_PAY_RESPECT

Please someone tell me faster approaches for Problem C.

doubleux

+10

if $$$a \leq b$$$, and lcm(a,b) is L. Then from b to L-1 every number satisfies. Therefore we don't even need to check which numbers are good between 0 and L-1 individually and it will always be (L-b). Then just answer each query in O(1) time. Here is my code for reference.

abufarhad

would you please explain this proof ?

I tried to prove it Here See if that makes sense!

liveoverflow

instead of lcm(a,b) can we have a+b?

I don't think that'll work.

WATCH24HRS

hey! I also tried a very similar approach to the questions, so basically I exclude the numbers in which the condition ((x%a)%b == (x%b)%a) is satisfied from the range [l,r]. These numbers would be of type in (N*lcm(a,b)+max(a,b)-1) for N in {0,1,2,3...}. Now I just need to calculate numbers like these which lie in [l,r] and subtract it from the total (l-r+1).

Is this approach right? If so could you please help me with why this solution is getting a wrong answer (https://codeforces.me/contest/1342/submission/78349599)?

Thanks a ton in advance!

Your code fails on this Test case:

1
1 1 1
1 1

I fixed it, but still, I am getting a wrong answer verdict. https://codeforces.me/contest/1342/submission/78359260 I really am stuck, is it an implementation problem or is the logic incorrect? Sorry to bother yet again!

Hey! Thanks for the help! Actually I figured it was an implementation mistake! Thanks a ton again!

bobbilyking

that's what i thought too but my implementation kept on not working :( do u know where i went wrong code

Zealotrahl

Hi, please can you give an idea of why taking the range between l and r is incorrect in comparison to your solution, taking first 1 to l-1, and 1 to r. I can not find a counterexample.

Here is my submission: 112327238

UPD: AC 112369657

r5shivamchaudhary

+12

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

swapnilr

Yes, that is exactly what I did. Although worst-case complexity will be same, since $$$LCM(a,b)=a*b$$$ if $$$a$$$ and $$$b$$$ are co-prime.

aditya.vallabh

Yes, C can also be solved using LCM(a, b). Here's my solution with no pre-processing and O(1) space: 78178389

HP21

Hey @aditya.vallabh , nice solution. Can you explain these two lines *** if(l%lcm < a) { res += a — l%lcm; } if(r%lcm < a) { res -= a — r%lcm — 1; } ***

dedsec7

Basically all the numbers which fall in the range of [k*lcm, k*lcm + max(a,b)] (k is any integer) have equal moduli. If l or r falls in the middle of such a range, the numbers either have to be included or excluded which is handled in these two statements.

musafir_v

Can you please provide the proof for your statement dedsec7

_RAYUGA_

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

ivatopuria

ab % a == 0 so we have ( (0 + x ) mod a ) mod b

nikeshthapa255

just take any two a and b and print 1 to 100 numbers satisfying the property and you will see a pattern.

And I guess it will give you a good intution towards the problem.

adiagr

3 years ago, # ^ |

Helped me alot! Thankyou

amane-ame

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.

I don't quite understand how your algorithm is different from the reference solution. Do you have code? I'm also quite surprised that $$$O(n^2 4^n)$$$ works because I had quite a lot of trouble not getting TLE for my $$$O(n^2 3^n)$$$ solution (I had to use a profiler to shave constant factors).

Vladislao

+41

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:

$$$ x \equiv x\% b\pmod{a}.$$$

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.

Access_271

Can you please explain how to deduced then what we want is x−r′=qb to be a multiple of a from x≡r′moda ?

98596

Because $$$x \equiv qb + r'$$$ so $$$x - r' \equiv qb$$$. Also $$$x \equiv r' \mod a$$$, so $$$x - r' = qb$$$ must be a multiple of $$$a$$$.

That's exactly what I did

hippie

Excellent explanation! Can someone further explain: This amounts to have q a multiple of a / gcd(a, b)? Thanks!

oppoman

please tell me if you found the answer

nipul1

Really amazing solution and explanation. Thanks

Voga

"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?

Everule

Let's say $$$X = x + kab$$$

If $$$(X\%a)\%b = (X\%b)\%a$$$ then $$$((x+kab)\%a)\%b = ((x+kab)\%b)\%a$$$ that means $$$(x\%a)\%b =(x\%b)\%a$$$

(Recall that $$$p + tq \mod q = p\mod q$$$)

So if $$$X$$$ satisfies the condition, so does $$$X \mod ab$$$

AquaBlaze

← Rev. 7 →

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!.

Hi, I replied on a similar comment above concerning with stirlings. I am unable to solve this question for some time now. Here is what I understand:

--- If $$$k \neq 0$$$ (for $$$k = 0$$$ answer is $$$n!$$$) then we calculate all ways for $$$n$$$ rooks to span all $$$n$$$ rows, call it $$$W$$$. Our answer will be $$$2W$$$ (replace row with column)

Since $$$k\neq 0$$$ some columns will be repeated. So we group them by columns. Stirling number $$$S(n,p)$$$ will give set of all partitions of $$$n$$$ into $$$p$$$ groups. Now pairings in this question depends on the size of groups right, say $$$p = 2$$$ and $$$n = 4$$$ then there may be 3-1 partition or 2-2 partition where in the first case pairings will be $$$\binom{3}{2}$$$ and in second case it will be $$$\binom{2}{2}\cdot\binom{2}{2}$$$ so how stirling will help here

← Rev. 12 →

EDIT : You need to find number of arrays that has n−k distinct numbers, not k. My bad ;_;

Let's consider only the case some columns are repeated (we can multiply the answer with 2 to make up for the other case.)

We will place the rook of row $$$i$$$ at column $$$A[i]$$$.

For example, if $$$n = 4$$$ and $$$k = 2$$$, we will have something like this $$$A = (1,1,2,2)$$$ or $$$A = (4,4,4,1)$$$ or $$$A = (3,1,1,1)$$$

Now, you can see that in case $$$k = 2$$$, there are 2 distinct numbers.

Which means if we want k pairs of rooks fighting, we need to build an array that has k distinct numbers.

That means if you want to find how many ways we can place the rook for $$$(n,k)$$$, Just find how many ways we can build an array that has $$$k$$$ distinct numbers instead.

Combinatorics time! :

How many ways can we choose k distinct numbers? $$$C_{n,k}$$$

How many way can we arrange n different index into k distinct numbers?

That is when our stirling number comes to a play.

$$$Stirling(n,k)$$$ = How many ways can we arrange n different index into k indifferent boxes

To make k indifferent boxes into k different boxes is just to multiply it with k!

So, $$$Stirling(n,k) *(k!)$$$ = How many ways can we arrange n different index into k distinct numbers

Therefore, the number of arrays that has $$$k$$$ distinct numbers is $$$C_{n,k}*Stirling(n,k) *(k!)$$$

And the final answer is $$$2*C_{n,k}*Stirling(n,k) *(k!)$$$

(The $$$Stirling(n,k)$$$ can be calculated in $$$O(k*log(n))$$$ time using the formula in the wikipedia.)

Thank you for reply, I think my confusion was because of given constraint in question that $$$k \le \binom{n}{2}$$$ whereas in reality $$$k \le n-1$$$. I was thinking that if $$$3$$$ rooks appear in a col then pairings is taken as $$$\binom{3}{2}$$$. But it is only $$$2$$$. In general if there are $$$m$$$ rooks in a col then pairings is $$$m-1$$$ right!

This confusion got cleared when I read your second line with sample $$$A$$$. Now everything makes perfect sense. So reflecting my understanding, I now see if we have all $$$n$$$ in a col then we always get $$$n-1$$$ attack pairs. If we split it in 2 col then we have $$$n-2$$$ pairs of attacks no matter what the distribution.

In general we need $$$k$$$ pair attack so we have $$$S(n,n-k)$$$ ways to make partition into $$$n-k$$$ group. Now multiplied by $$$\binom{n}{k}$$$ to signify which col those group denotes. Upto this is ok. Why multiply by $$$(n-k)!$$$ also

Don't worry dude now I got it, We use $$$(n-k)!$$$ to shuffle between which group from partition corresponds to which selected col.

DrLector

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?

cs18b012

Sorry, made a small error in the previous version.

Try the example, $$$M = [1, 1, 2, 2]$$$ and $$$C = [2, 1]$$$

The correct answer is we can group like $$$[1, 2], [1, 2]$$$ but your greedy leads to the groups $$$[1, 1], [2], [2]$$$.

If you go from largest element to smallest element, I believe the greedy works but you have to worry about TLE on a case with $$$\sqrt{n}$$$ distinct values with $$$\sqrt{n}$$$ each (I used some similar greedy with optimization).

+19

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

LightYagami674

If an element doesn't fit into current t[p] , you do a p-- . So how do we know that current i will either belong to p-1 or p+1(new testcase). Don't we have check over entire p = 0 to p-1 and then add it into new testcase ?

yash1402_

I think solution is working once from top to bottom and then goes bottom to top...
Here is my thinking why does an element either belong to p or p-1 or p+1 (i.e, creating new testcase)...If we observe first larger elements of sizes of array are fixed from top to bottom.
Like this, arr_sizes = [3,3,3,2,2,2,2,1,1,1] and arr_k = [3,2,1]
So after first top to bottom session, ans = [[3],[3],[3]] and p=2
Now array size changes to 2, here we have three choices, p,p+1,p-1
So we added 2 to p So now ans = [[3],[3],[3,2]]
Again we have to add 2, we can add new testcase i,e. p+1 and ans = [[3],[3],[3,2],[2]] (Wrong answer) but it would not generate minimum answer. We cannot add 2 to p and make ans = [[3],[3],[3,2,2]] (Wrong answer) since there should only 2 array>=2
We have all arrays filled up with exact size except last one, so now we will look for upper half, now it's time to move bottom to up
ans = [[3],[],[]] p=0 (Go top to bottom)
ans = [[3],[3],[]] p=1
ans = [[3],[3],[3]] p=2
ans = [[3],[3],[3,2]] p=2
ans = [[3],[3,2],[3,2]] p=1 (Go bottom to up)
ans = [[3,2],[3,2],[3,2]] p=0
ans = [[3,2],[3,2],[3,2],[2]] p=3 (We hit p==0 condition pf code)
ans = [[3,2],[3,2],[3,2],[2,1]] p=3
ans = [[3,2],[3,2],[3,2],[2,1,1]] p=3
ans = [[3,2],[3,2],[3,2,1],[2,1,1]] p=3 (Go bottom to up)

This shows when we move from top to bottom we are make all inner vectors of same sizes. When we hit to the end we make the last vector size greater then all vectors and when that vector is filled we go bottom to up for making such vectors of same size as last one....
It was a great observation by Russell_Emerine. I wish if would have done that..
Hope you get the intuition

decoder__

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

The upper bound is because we can distribute all the numbers $$$\geq k$$$, then all the numbers $$$\geq k - 1$$$, etc. For the lower bound, assume by way of contradiction that we use $$$ans$$$ testcases and there is some $$$i$$$ such that $$$\lceil g_i / c_i \rceil > ans$$$. Then by the extended pigeonhole principle, one of the testcases must have more than $$$c_i$$$ arrays of size $$$\geq i$$$, which is a contradiction (alternatively, you can think of it like trying to distribute the g_i cases among $$$ans$$$ testcases is impossible).

sthfaceless

How to solve E with FFT?

supersayajin

Please help on this one, it has fft tag and no one's talking about it.

A solution based on this is described here.

rough_notebook

for the problem D I am not able to understand why my solution https://codeforces.me/contest/1342/submission/78247111 is correct while https://codeforces.me/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

I don't understand your solution method at all, but could it be floating point rounding error?

Thanks for your help, Yes it was floating point rounding error. Thanks again.

Priyansh31dec

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.

awoo

I mean there's really no more detail to that. You want to place these $$$g_i$$$ arrays somewhere. What's the minimum number of testcases required to do that if you can't put more than $$$c_i$$$ in each of them? So you put $$$c_i$$$ into the first one, $$$c_i$$$ into the second one and so on until you have no more arrays left. You will use exactly $$$\lceil \frac{g_i}{c_i} \rceil$$$ testcases with that.

That idea by itself does not really account for the placement of individual arrays of these sizes exactly, so the actual construction is more complicated than the proof for the minimum bound.

Thank you

hrithik_v

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.

anupamm98

Same. I don't understand why. The restricted range should be [nl, nl+b) where l is the lcm and nl is a multiple of lcm and b is the larger of (a,b). Mine also fails at 2nd test case.

u_v

1 4 15 1 59 73

your output : 0 correct output : 1

How does https://codeforces.me/contest/1342/submission/78244632 pass but https://codeforces.me/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.

msporyshev

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

You probably need to remove the first innermost loop, which can be replaced with something like

int lower_than_j = s & ((1 << j) - 1);
if (lower_than_j == 0) continue;
msb = 31 - __builtin_clz(lower_than_j);

This also replaces the if statement.

Other micro-optimizations you could try is if you iterate over j from high to low, I think you can break instead of continue when msb == -1. Also, I think k's maximum value is __builtin_popcount(s) + 1 since you can't have more groups than on-bits.

It took me a while to not get TLE, though I had a slightly different setup. Hope this helps.

Thank you) But, unfortunately, it doesn't help. I have one of the submissions, where I precalculate msb for all masks and bits. The thing that helped was to change backward DP behavior (where I subtract submask) to forward DP (where I add submask of superset). It also changed some of the if statements

R-d-G

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

Both work fine

I used the exactly same logic as in tutorial..used both increasing and decreasing but its not working.. what wrong with the code 78370972

sharath101

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 ?

The intuition is basically something along the lines of "add stuff in such a way that it's packed as tightly as possible". Like given the fixed number of testcases, put arrays of all big sizes so that each testcase has as few of them as possible. And the modulo does exactly this. It puts arrays like $$$1,2,\dots,k,1,2,\dots,k,\dots$$$, which only has $$$\lceil \frac{n}{k} \rceil$$$ arrays put in the worst testcase if there are $$$k$$$ testcases and $$$n$$$ arrays.

talrejamohit03

I think we can come up with the solution by thinking in this way. Taking just a single constraint, if suppose the count of arrays with size = k is 11 and constraint on k = 3, then we would need at least ceil(11/3) = 4 testcases. We would then distribute them as follows: tc0 = k k k ; tc1 = k k k ; tc2 = k k k ; tc3 = k k ; If we fill it in a circular manner, then we can fill the testcases in the most efficient manner satisfying the single constraint. Expanding to more than one constraint, if we take maximum of all such ceil(count/constraint), "ans" , we can distribute all arrays with whatever be the sizes among 0 to ans-1 testcases in a circular manner satisfying all the constraints.

striver_79

Video solution for C.

okwedook

+24

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

My submissions to F

I don't even understand now, how do my optimizations work.

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?

arthou

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://codeforces.me/contest/1342/submission/78195420

andreas

Your solution is not O(q) per test case, since you calculate the gcd: https://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency So it's around O(q + log(a))

$$$почему$$$ $$$столько$$$ $$$грусти?$$$

Ari

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

$$$\frac{n!}{a_1!a_2! \dots a_m!}$$$

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

$$$\displaystyle\sum_{a_1 + \dots + a_m = n} \frac{1}{a_1!a_2! \dots a_m!}$$$

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.

wh1te_whale

-11

I am not very familiar with NTT. Can you please share some resources to learn about it.

Hey I am not understanding some comments in this regard: Why are we choosing $$$n-k$$$ columns? I mean there may be case where $$$k > n$$$ in that case how can we select $$$n-k$$$ columns. Also am I correct in saying that your answer will be multiplied by $$$2$$$ because same thing be done by replacing row with column?

AnandOza

I wanted to see if there was a simpler closed form for the PIE summation in the editorial, and looked to this comment for inspiration.

Your polynomial set off my $$$e^x$$$ detector, so I thought it would work out pretty simply and proceeded as follows: we want the coefficient of $$$x^n$$$ in $$$n! (e^x - 1)^m$$$, which we can find by differentiating $$$n$$$ times and dividing by $$$n!$$$.

I expanded this to $$$\sum_{k=0}^m \binom{m}{k} e^{kx}x^k (-1)^{m-k}$$$, and differentiating $$$n$$$ times gives us $$$\sum_{k=0}^m \binom{m}{k} k^n e^{kx} (-1)^{m-k}$$$, which looks awfully familiar. So that didn't work, but gave a different route to the same destination. xD

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 :)

spookywooky

This is because (ab%a)%b==0

Can you explain why this property creates cycle from 0 to ab-1 then ab to 2ab-1 and so on??

Well, because the cycle has length ab. Because if we add ab to x, the result of the formular is the same.

This is more or less the definition of the length of the cycle. Which number do we have to add to allways get the same result? Answer is: That one which allways creates result 0, because 0 is the neutral element of addition.

kevin1kevin1k

First, since both a and b divide ab, ab % a = ab % b = 0. Thus (ab % a) % b = 0 % b = 0 = 0 % a = (ab % b) % a. Note that the above holds if we replace ab with lcm(a, b).

The_Alchemist

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???

because if you chose array of size 1 then you have no. of arrays of size>=1 is 1. just next if you choose 2 then you have no. of arrays of size>=2 is 1. and then if you choose 2 again then no. of arrays of size>=2 is 2 now. but it is mentioned that no. of arrays of size>=2 can't exceed 1 ( as c[2]=1 ).

I hope you get it now..

← Rev. 6 →

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.

BledDest

We usually set the limits in harder problems depending on the behaviour of the model solution. In this problem, the model solution runs in $$$1.4$$$ seconds on the worst case (and it may be even faster on $$$64$$$-bit compiler, which cannot be used in Polygon), so we thought that it was fine that the time limit is $$$5$$$ times larger than the runtime of our solution.

$$$f(n) = n^2 3^n$$$ is just a close estimate of the number of required operations, since some states may be unreachable (for example, a state where $$$cnt$$$ is greater than the number of $$$1$$$-bits in the mask is impossible).

rky673

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.

opsopsops1

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

Don't use ceil, It's always better to not mess with floating points as much as possible. If you wanna find the ceil(p/q) use (p+q-1)/q instead.

Also you're ceil doesn't work because your cnt[i+1]/cnt[i] is converted into an integer(int/int) before it is ceiled. Use ceil((float)cnt[i+1]/cnt[i]) and your code will work.

ScaryTerry

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

stunareeb_09

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

1 4 15 1 63 79

your output: 17 correct output: 5

dmkz

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?

This would work if we treated all rooks as equal. But they are not — each row contains exactly one rook, so each rook is uniquely represented by its row index (so they are different).

This formula does not distinguish, for example, between these sets of positions: $$$[(2, 1), (1, 2), (3, 2)]$$$ and $$$[(1, 1), (2, 1), (3, 2)]$$$.

zhuuxa

← Rev. 5 →

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:

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

PLEASE, correct me if I am wrong.

"The third line contains k integers c1,c2,…,ck (n≥c1≥c2≥⋯≥ck≥1); ci is the maximum number of arrays of size greater than or equal to i you can have in a single testcase."

in input you are not following constraints... it is mentioned that n>=c1>=c2>=c3...>=ck>=1..

Ah Sorry , I didn't notice that. Thank You.

chef_spam

In your second array $$$[2, 2, 3, 6]$$$, there are three elements that are $$$\geq1$$$, which violates the input (there's also a typo as the size is three, not two).

Got it..! :) Thanks. (Corrected the typo).

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.

you need to place n rooks only, in your case rooks are 4.

walleeva

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

tnx bro it helped :)

Fortin

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.

zjsdut

Can you please explain why that inequality holds?

adzo261

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

hitch

I might be wrong but something similar has happened to me before, when you check for a value in the map, even if it's not an entry in the map, an entry for it gets created against the value 0/NULL, so when you're traversing the map, you also go through the new entries.

munditva

@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.

cryo_coder123

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.

suun

Another solution for D using priority queue

Code

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';
	}
}

arvindr9

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).

_pastor_

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?

jarvis307

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

zh_zhumash

4 years ago, # |

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

AjaySabarish

Good contest

sriram2000na

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

abhi821005

A better understanding of this C problem is in the editorial. its ,this way

instead of a*b , just take upto lcm(a,b)

explaination:: take t=lcm(a,b) for numbers :: 1,2,3,4.....t,t+1,t+2,t+3.....2*t,2*t+1,2*t+2......3*t,3*t+1.....4*t,...

NOTE:: t=lcm(a,b);

the question is why lcm(a,b)? soln:: is right in the editorial. lcm(a,b)%a%b==0 same for lcm(a,b)%b%a. this is the 2nd leat value after 0 for which it becomes 0. but 0 is not there in the range the value of l and r is from 1 to 1e18.

so, use a prefix array for which this holds true;

len = a * b;// here just do lcm(a,b)-->tym will be less p[0] = 0; for(int i = 1; i <= len; i++) { p[i] = p[i — 1]; if((i % a) % b != (i % b) % a) p[i]++; }

Ayushman_123

3 years ago, # |

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

adityagamer

10 months ago, # |

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 $$$

awoo's blog