yes, you are right i did same

could you please explain a bit more. Thanks.

I also did this only:)

you can also use 4,1 and 8. 96557902

This was my answer:
fill only one diagonal with 1.
then fill every up and down cell with 1 of this diagonal.
fill every other thing with 0.

for n = 5
11000
11100
01110
00111
00011

Problem B would have been slightly more interesting if instead of non-negative numbers, we were only allowed positive numbers.

So did I.

I used the number 9 instead.

lol

nCr Combination

Combination nCr=C(n,r)

It is combination.

Also, notice that $$$nCr \times r! = nPr$$$

It's for Combination Number

d = not prime number.
sum_row_col = d + n - 1 = prime number.
ex. n = 4
d 1 1 1     4 1 1 1
1 d 1 1     1 4 1 1
1 1 d 1 ->  1 1 4 1
1 1 1 d     1 1 1 4

A simple way to think of it is lets say we want a MEX of $$$x$$$.

Our array is something like $$$ .... x .... x .... x .... x .... x .....$$$ Notice that, for any array, adding a new number cannot make it not $$$x$$$, unless you add $$$x$$$. So if there exists a subarray with MEX of $$$x$$$, there must also be a subarray between the occurences of $$$x$$$, that has a MEX of $$$x$$$.

Now to query these subarrays, we will use a segment tree $$$S$$$. Lets sort the queries by $$$r$$$. Let $$$S_i$$$ be the last position of $$$i$$$. Now to check if subarray has a MEX of at least x, you can query, the minimum last index of the values from $$$(0,x-1)$$$. If that is greater than your $$$l$$$, then the subarray has a MEX of at least $$$x$$$. Since the subarray doesn't contain any $$$x$$$, the MEX cannot be larger, so querying it is equivalent to checking if MEX is $$$x$$$.

What actually is test 10?

Can you please tell what is actually test case 10 in C?

When the pretests are so weak, the round should be unrated.
I failed systest on C.

You can refer to my solution.

At the end, every citizen will be at one of the leaf nodes. So, they should follow this strategy: first, distribute all the citizens from the immediate parents of the leaves, to the leaves. Then distribute the citizens from the parent of the parent to the leaves in its subtree, then parent of parent of the parent of leaves, and so on, in a bottom to top manner.

How to distribute this? Let's see the first step: From immediate parent of leaves to the leaves. We'll try to minimise the maximum number of citizens that are at any leaf. To do this, we'll first try to make the number of citizens in every leaf equal the maximum number of citizens present in any other leaf which has the same immediate parent as this leaf. Once, all leaves under the same immediate parent have an equal number of citizens, we can can start distributing the remaining citizens from the parent to the leaves equally.

So, if a parent of leaves has $$$L$$$ leaves in its subtree, the total number of citizens in its leaves is $$$c1$$$, and there are $$$c2$$$ citizens initially in the parent, then the maximum number of citizens in any leaf after distribution is at least $$$\lceil \frac{c1+c2}{L} \rceil$$$. This is simply a result of the Pigeonhole Principle.

We'll store three values at each node: $$$max$$$, $$$sum$$$, and $$$count$$$. $$$max$$$ is the maximum number of citizens present in any leaf of our current node's subtree, $$$sum$$$ is the total number of citizens present in our subtree, and $$$count$$$ is the total number of leaves in the subtree. For a leaf $$$u$$$, $$$max[u]$$$ $$$=$$$ $$$sum[u]$$$ $$$=$$$ $$$a[u]$$$, $$$count[u]=1$$$.

For other nodes $$$u$$$, $$$sum[u]$$$ equals $$$a[u]+$$$ sum of all $$$sum[v]$$$ for children $$$v$$$ of $$$u$$$, $$$count[u]$$$ too is simply the sum of all the counts of the children. Now, $$$max[u]=maximum(\lceil \frac{sum[u]}{count[u]} \rceil, maximum(max[v]))$$$ over all children $$$v$$$ of $$$u$$$. $$$maximum(max[v])$$$ is the maximum number of citizens present in any leaf before distributing citizens from this node, and $$$\lceil \frac{sum[u]}{count[u]} \rceil$$$ is the minimum number of citizens that at least one leaf will have after distributing. The answer for a node $$$u$$$ will be stores at $$$max[u]$$$. So, we can implement using DFS.

The main idea is find the answer for every node as if that node were the root of the tree and the actual tree was only formed of the subtree of that node. For each node, we distribute all the citizens from it greedily, keeping the maximum number of citizens present in any leaf minimum possible. We solve it bottom to top: first for the highest level, then previous level, then previous, and so on.

Here's my attempt at rambling about my thoughts explaining the way I thought about it in a more formal way.

It's a little harder to think about adjusting the strategy for every time the people/bandit moves, so let's start by thinking about the final state and what each side can guarantee.

First, if there are $$$P$$$ people in total they will end up distributed in the $$$L$$$ leaves, regardless of the strategies there will always be one leaf with $$$\ge \frac{P}{L}$$$ people at the end. It is not unnatural to think the bandit can always walk towards the subtree with the highest ratio of people to leaves and get $$$\ge \frac{P}{L}$$$.

Let $$$P[u],L[u]$$$ be the total number of people,leaves at the subtree rooted at $$$u$$$. At the beginning we have a leaf will end up with $$$\ge \frac{P[0]}{L[0]} = r$$$ people. Next the bandit has to choose between some vertices $$$a_1,a_2,\dots, a_k$$$, notice the people already moved to one of this cities, so their subtrees have all the people $$$P[v_1]+\dots +P[v_k] = P[0]$$$ and clearly $$$L[0] = L[v_1]+\dots +L[v_k]$$$ as well. Intuitively, it makes perfect sense that one of the new ratios $$$\frac{\text{people}}{\text{leaves}}$$$ of a subtree has to be just as large as $$$r$$$, we distributed the people and leaves into several subtrees.

Formally, suppose that all ratios $$$\frac{P[v_i]}{L[v_i]} < r$$$. That is $$$P[v_i] < L[v_i] r$$$ and adding this inequalities we get $$$P[0] = P[v_1]+P[v_2]+ \dots P[v_k] \le r (L[v_1]+\dots +L[v_k]) = rL[0]$$$ but this is impossible as it gives $$$\frac{P[0]}{L[0]} < r $$$ and we defined $$$r$$$ exactly like that. That means we always have some ratio $$$\ge r$$$ in the subtree of one of his adjacent vertices. As we go down the tree following this procedure we'll eventually reach a leaf with ratio $$$\ge r$$$ and so he will get at least $$$r$$$ people in there.

So we have some progress, we just proved the bandit can always get $$$\ge \frac{P}{L}$$$ where $$$P$$$ is the total number of people and $$$L$$$ is the total number of leaves.

If you look carefully we did much more, there is nothing special about the starting vertex. The same argument shows that if we have a subtree with some ratio $$$\frac{P}{L}$$$ the bandit can get at least that many people at the end. Therefore, the bandit can always get $$$\ge \frac{P[v]}{L[v]}$$$ for any vertex $$$v$$$. In particular he can get $$$\ge r$$$ where $$$r$$$ is the maximum ratio $$$\frac{P[v]}{L[v]}$$$ among all vertices $$$v$$$.

At this point one thing is clear, the absolute minimum the bandit can get is closely related to the ratios between people in a subtree and the number of leaves. In particular we can always get $$$\ge r$$$ where $$$r$$$ is the greatest ratio people/leaves among all subtrees. However, for any of this to be actually useful we need to make sure the people can organize themselves in a way that doesn't allow the bandit to get more than this. We shouldn't be too scared as it again makes intuitive sense that the people can distribute themselves somewhat evenly among all the leaves.

What prevents the people from distributing themselves perfectly even among the leaves and leaving the bandit with only $$$\left\lceil \frac{P}{L} \right\rceil$$$ captures? If all the people in the city start in a leaf, we can't move any of them and the bandit gets all. Generalizing a little, if a subtree is charged with a lot of people its leaves will have a much higher average.

This motivates us to prove that the people can always distribute themselves in a way that at the end each leaf has $$$< \frac{P[v]}{L[v]}+1$$$ for the maximum such ratio $$$r = \frac{P[v]}{L[v]}$$$ among all vertices $$$v$$$, as we already showed the bandit can always get $$$ \ge r$$$. That will prove the answer is $$$\lceil r \rceil$$$ for the largest ratio.

Suppose we're at $$$v_i$$$, there are $$$a[i]$$$ people on it. We know there are $$$P[v_i]$$$ people on its subtree and $$$P[v_i] \le rL[v_i]$$$ as $$$r$$$ is the largest ratio.

We would like to distribute them as $$$p_1+\dots + p_j = a[i]$$$ among his child $$$r_1,r_2,\dots , r_k$$$. Our objective is once again preserving $$$\frac{P[r_i]+p_i}{L[r_i]} < r+1$$$ so we want $$$P[r_i]+p_i \le (r+1)L[r_i]$$$ or $$$p_i \le (r+1)L[r_i]-P[r_i]$$$. In other words, we can add up to $$$\lfloor (r+1)L[r_i]-P[r_i] \rfloor$$$ to the subtree rooted at $$$r_i$$$ while preserving the ratio condition. We now have to show this gives us enough margin to distribute all the $$$a[v_i]$$$ people standing on $$$v_i$$$. That is, we just have to prove: $$$\lfloor (r+1)L[r_1]-P[r_1] \rfloor+\dots + \lfloor (r+1)L[r_k]-P[r_k] \rfloor \ge a[i]$$$.

Notice that $$$L[r_i] \ge 1$$$ as each subtree has at least one leaf. Therefore $$$\lfloor (r+1)L[r_i]-P[r_i] \rfloor \ge \lfloor rL[r_i]+1-P[r_i] \rfloor > rL[r_i]-P[r_i]$$$ for each term in the sum as $$$\lfloor x \rfloor > x-1$$$ for all $$$x$$$.

Adding them all up we get the left side is at least $$$r(L[r_1]+\dots + L[r_k]) - (P[r_1]+\dots + P[r_k]) = r(L[v_i]) - (P[v_i]-a[i]) = rL[v_i]-P[v_i]+a_i \ge a[i]$$$ because $$$rL[v_i] - P[v_i] \ge 0$$$ is equivalent to $$$r \ge \frac{P[v_i]}{L[v_i]}.$$$

This finishes the proof that the answer is $$$\left\lceil \frac{P[v]}{L[v]} \right\rceil$$$ for the largest sch ratio. Hopefully this makes it a bit easier to understand. We just explicitly wrote out the details that formally prove our intuitions:

• The bandit can chase the largest ratio, locate the subtree that has it and start going down in its direction, once we reach it, every time we go down we just pick the subtree with the largest new ratio. No matter what the people do he will always end up in a subtree with a ratio just as big, and capture at that many people at the end.

• People can distribute themselves 'evenly' among the leaves, ending up with less than $$$r+1$$$ on each at the end. Whenever we are on a vertex we give as many people as possible to each subtree without messing up its ratio (making it larger than $$$r$$$) and as we proved that is enough to fit all the people.

I think it is another name for pigeonhole principle.

If everyone is at root we can uniformly distribute each person to each leave. [] it is actually ceiling. Let us assume a1=13 and leaves 4 We can send 4 to the first and 3 to the remaining. So ans is [13/4]=4;

Yes the correct answer is :-

C(Bignum, cntBig)*(cntBig!)*C(Lessnum, cntLess)*(cntLess!)*(n - cntBig - cntLess -1)!

Where :- Bignum = (n - x) Lessnum = (x - 1)

And cntBig, cntLess is same as explained in the tutorial.

The correct answer is 36.

for input 6, 3, 2. The permutation pattern is:

"* a 3 B * *"

where B in {4, 5, 6}, a in {1, 2}

3 * 2 * (3!) = 36.

1 is not prime.

1 is not prime :) and its given in problem that sum should be prime

People be mourning to the rip case of C and random guy be like : 1 iS PrImE ..

Man come on revise your maths lessons

First of all simulate the given binary search.

For every mid position we know that whether our given element lies left or right of that mid position. If it lies in the left of the mid position then we need to place a element which is bigger than our given element otherwise we need to place a smaller element there.

We will count how many places there are where we can place smaller element and bigger element. Let's say we can place smaller element in S positions and bigger element is B positions and we have X smaller elements and Y bigger elements. So, how many ways can we arrange X elements in S positions and Y elements in B positions?

It is P(X,S) = C(X,S) * S! and P(Y,B) = C(Y,B) * B!

After placing all those elements let's say we have R elements remaining. Then R can be arranged in R! ways. So, the final answer is ans = P(X,S) * P(Y,B) * R!

what is exactly 'system test'?

In problem D- I first calculated the maximum population amongst all the leaf cities lets call it $$$maxele$$$ and then I filled up all the non-leaf cities' population in all the leaf city and made population of all leaf cities equal to 'maxele'

if after all this I've still population of non-leaf cities left then I'll distribute it equally amongst all leaf cities and my answer would be ->

but I'm getting wrong answer on test-5 now test-5 is quite big so I can't decode it, Can you please help?

Here's my Submission

I'm confused too. Can someone clarify please?

Yea the first middle would be one right ? Can someone help what makes this test to have answer zero ?

Exactly ! I also don't understand why the answer should be zero.

Edit:- Leave it I found where I was wrong.

I also got that wrong. But I guess the output for that test case is indeed 0 because they ask for the number of permutations for the given implementation of binary search, which indeed fails to find 3 for both permutations.

After asking for position 1, you're left with range [2,3]. Nevermind what number is on position 2 it is smaller than 3, thus left will be equal to 3 at the end if the process, not 2 as it should.

For 1 3 2 , No , Because mid=(3+0)/2=1 a[1]<=x left=2 now, mid=(2+3)/2=2; a[2]<x so left=mid+1=3 , so pos is found out to be left-1=2 , where as in question it should be 1 , notice that there is no break statement even if the element is found

You could notice that their dumb algorithm goes on even after finding the mid element..(suggested by smax) Even my code failed on test 10. Just change your smaller condition to make it a wrong BS like they desire.... like so :

//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const ll maxn=10000;
const ll mod=1e9+7;

vector<ll> fact(maxn,0);
ll bin(ll a, ll b) {
	a%=mod;
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % mod; //mod
        a = a * a % mod; //mod
        b >>= 1;
    }
    return res;
}

void fac()
{
	fact[0]=1;
	for(ll i=1;i<maxn;++i)
	{
		fact[i]=(fact[i-1]%mod*i%mod)%mod;
	}
}
ll bc(ll n,ll i)
{
	if(n<i)return 0LL;
	return (fact[n]%mod*bin(fact[n-i]*fact[i],mod-2)%mod)%mod;
}
ll mul(ll a,ll b){
	return (a%mod*b%mod)%mod;
}

int main(){
	fast;
	ll n,x,i,j,k,pos;
	fac();
	cin >> n >> x >> pos;
	ll l = 0;
	ll r = n;
	vector<ll> a(n,0);
	while(l<r){
		int m = (l+r)/2;
		if(pos>=m){
			a[m]=1; //<x
			l=m+1;
		}
		else if(pos<m){
			a[m]=2; //>x
			r=m;
		}
	
	}
	a[pos]=-1;
	ll low=0,high=0;
	for(i=0;i<n;i++){
		if(a[i]==1)++low;
		if(a[i]==2)++high;
	}
//	cout<<low<<" "<<high<<endl;
	ll ans1 = mul(bc(x-1,low),fact[low]);
	ll ans2 = mul(bc(n-x,high),fact[high]);
	ll fans = mul(mul(ans1,ans2),fact[n-low-high-1]);
	cout<<fans;



}

in case of 2 3 1 would

first iteration mid = 1 and 3<=x thus left = 2 and right = 3

second iteration mid = 2 and 1<=x thus left = 3 and right = 3

here you can clearly see left becomes 3 and a[3-1] != x thus it returns false

I'm also confused answer should be 0 only

Write the binary search program given in the question and try searching for element 3 at position 1 for the permutations (1,3,2) and (2,3,1). Both permutations give false as the answer. Then try looking why it happened, you'll get your answer.

For 3 3 1, for the function to return true. A[2] > x i.e A[2] > 3, which is not possible.

There are two steps in the dry run, 1) s = 0, e = 3 i.e a[1] <= x 2) s = 2, e = 3 i.e a[2] > x

lets execute step by step the code on first example "1 3 2":
a[3]={1,3,2}
l=0, r=3
iteration 1:
middle = (3+0)/2 = 1
a[middle]=a[1]=3 is less than or equal than 3 then l=middle+1=2
iteration 2:
middle = (2+3)/2 = 2
a[middle]=a[2]=2 is less than or equal than 3 then l=middle+1=3
we end the iterations
l=3
Then on line 11 of the code, left is greater than 0, but a[l]=a[3]=2 is not 3
hence we return false.
the same apply to the second case, good fortune!!!.

"in my other account" you dont deserve to have better pretests, as you are ruining the contest for actual div2 contestants.

The contest was extended for 10 minutes. So don't see a big problem there.