Really fast editorial!

Is this just me or did everyone else feel that this round should be renamed to Pinely Round 1 (Div.1 + Div.1)

it's a gud contest but does this have rated?

i was able to solve C but not B :LOL

Could anyone please explain the solution of D to me?

I do understand the following DP approach:

dp[n][k][0] = 3 * dp[n - 1][k][0] + dp[n - 1][k][1];
dp[n][k][1] = dp[n - 1][k - 1][0] + 3 * dp[n - 1][k - 1][1]`)

However, I couldn't figure out how to straighten this access pattern.

Did anyone solve problem D by using generating functions?

Nice contest ..For me C is easier than B..B took me 1 hour and I did not solv it..but C took me 5 minutes..

Can you guys check the solution for q1, I was getting wrong answer despite getting it correct in test case. And the solution mentioned here is exactly same as my solution ~~~~~

include<bits/stdc++.h>

using namespace std;

define long long int

signed main() { int t; cin>>t; while(t--) { int n,a,b; cin>>n>>a>>b;

/*if(n%2==0 && (a+b<=n-1))
    {
        cout<<"YES"<<endl;
    }*/
    if(a+b<=n-2)
    {
      cout<<"YES"<<endl;
    }
    else if(a==b==n)
    {
      cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
}
return 0;

} ~~~~~

How many tests you have made for G? Problemsetters: Yes

Why the hell did I use topological sort in C ?

In problem D I thought of a n^2 solution which involved some combinatorics and figured that if this problem is solvable there must exist a fast way to compute the sum of all terms, I was stuck trying to achieve this the entire contest.

I want to know how do other contestants decide when to stop trying to reduce the combinatorics elements and think of a different approach altogether in these kind of problems?

The summation I came up with: $$$\sum_{x=1}^{k} \sum_{y=0}^{n-k} {k-1 \choose x-1} {x+y \choose x} {n-k \choose y} {2^{n-(x+y)}}$$$

My O(n) for D, quite similar to the editorial, did not pass. Perhaps 1000 ms was too strict.

B was really hard :(

when the solution for G will be published

Did anyone try solving Problem B using Doubly Linked-List?
I don't know why my solution fails for pretest 3.
Can anyone please help?

#include<bits/stdc++.h>
using namespace std;

class node {
public:
	int val = 0;
	node* left = NULL;
	node* right = NULL;
};

void solve(){
	int n; cin>>n;
	vector<int> arr(n);
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	node* head = new node;
	head->val = arr[0];
	node* temp = head;
	for(int i=1;i<n;i++){
		node* new_node = new node;
		new_node->val = arr[i];
		new_node->left = temp;
		temp->right = new_node;
		temp = new_node;
	}
	
	temp->right = head;
	head-> left = temp;
	int count = 0;
	int len = n;
	node* itr = head;
	while(len>3){
		int start_len = len;
		for(int i=0;i<len;i++){
			int l1 = (itr->left)->val;
			int r1 = (itr->right)->val;
			if(l1 != r1){
				// remove cur_val
				itr = itr->left;
				node* temp_itr = (itr->right)->right;
				itr->right = temp_itr;
				temp_itr-> left = itr;
				len--;
				break;
			}
			itr = itr->right;
		}
	
		if(start_len == len){
			// remove two adjacent elenments
			len-=2;
			node* temp_itr = ((itr->right)->right)->right;
			itr->right = temp_itr;
			temp_itr->left = itr;
		}
		count++;
	}
	if(len == 3){
		count+=3;
	}
	else if(len == 2){
		count+=2;
	}
	else if(len == 1){
		count++;
	}
	
	cout<<count<<endl;
}

int main(){
	int t; cin>>t;
	while(t--)
	solve();
	return 0;
}

The pain of missing out on a problem by 2 mins in 2 consecutive rounds

Can someone explain proof of B? Didn't understand from editorial.

Can any one tell me.How to master combinatorics and probabality problem. ! any suggestion Blog Tutorial.. What rating problem should i solve . I have tried till 1500 but still not able to get it.

I don't understand B's proof. In particular, why is the following claim true?

"When the length of the sequence is greater than 3, there will always be a pair of positions (i, j), such that a[i] = a[j] and a[i] has two different neighboring elements."

(I'm assuming that this is for the case "there are > 2 types of elements".)

Can someone explain it?

UPDATE: now I understand.

My first ever contest in CF , very good learning experience , looking forward for div4 contest tomorrow.

If constraints for problem B was 1 <= n <= 100000, instead of 1 <= n <= 100, would have solved B lot quicker XD

In editorial of D, what does c[i] means?

From what I understood, c[i] should not be this: "Notice that c[i]=a[i]∨b[i]∨c[i−1]". It should be (a[i]∧b[i])∨((a[i]∨b[i])∧c[i-1]))

Time limit for D was so tight. Is there a reason for such tight bounds?

My solution passed after precomputing powers of 3 instead of using fast exponentiation. I think it's not fair the problem was fairly hard and such a time-expensive test case should've been in the pretests.

orz

Let me expand B's proof: why for >= 3 types of elements can we always do n operations?

(1) If there is a type of element occurring only once, let's say it is x. then we repeatedly remove the element before x and finally remove x itself. The entire process doesn't have auto-erasing since x is different from anything before it.

(2) If every type of element occurs more than once, then first the length of the ring is at least 6. Also, there must exist a position j such that a[j - 1] != a[j + 1] (otherwise for all j, a[j - 1] = a[j + 1]. Then if a[1] = x and a[2] = y, then a[3] has to be x, a[4] has to be y, etc. This contradicts the assumption that there are >= 3 types of elements). So we remove a[j] and the problem is reduced. We can eventually reduce the problem to case (1) and use (1)'s process to remove the entire ring.

If anyone finds this helpful, here's my written solutions (video):

A. Two Permutations

B. Elimination of a Ring

C. Set Construction

D. Carry Bit

Problem E is very good. I learned a new concept called Clique and how problems can be framed around that. However, the time limit is bit tight.

$$$2$$$ corrections for $$$D$$$'s editorial:

1. $$$c_i$$$ should be $$$(a_i\&b_i)|(a_i\&c_{i-1})|(b_i\&c_{i-1})$$$.
2. Number of segments of consecutive $$$1s$$$ should be $$$\lceil \dfrac{q}{2}\rceil$$$ and number of segments of consecutive $$$0s$$$ should be $$$\lfloor \dfrac{q}{2}\rfloor +1$$$.

Problem E is a trash problem.

• So many details?
• use cin or scanf("%1d",&x) will get TLE.

The E has so many border cases

Here's the solution for the Problem D from the tester myee, which can give out the answer of query pairs $$$(k,k),(k+1,k),\dots,(n,k)$$$ in the time complexity of $$$O(n)$$$.

Let's define a function $$$L(v)=\log_2\operatorname{lowbit}(v+1)$$$; that means, $$$L(v)$$$ is the number of last bits $$$1$$$ of $$$v$$$ in the binary system.

For example, $$$L((1011)_2)=2,L((11100100111)_2)=3$$$.

Then, let's define

and the answer would be

Let's think about making recursion(or Dynamic Programming?) on it.

With classification discussion on the last bit of $i,j$, it's easy for us to prove that

and it immediately give out

That is, we need just to get some infomation of $C(n,k,0)$!

Let's define a Bivariate Generating Function

Then we can find that

And our answer would be

Let's think about how to calculate $Ans_{t,k}$, for all $$$t\in[k,n]$$$.

The two parts are similar, so let's just look at the first part. Let's just call it $A_t$.

If we just want to get single $A_n$, we can find that

So we can get it in the time complexity of $O(n+\log\mathbf{Mod})$, which is the Problem D.

As for the bonus, how can we get the answers in $$$O(n)$$$ time?

Let's think of the method of ODE, which is well-known in China.

Let's call

and then

So

That is

So

And we can find that

So it's just the way how the sequence of $G$ can be calculated in $$$O(n)$$$ time.

Moreover, in fact we can get the single answer in $$$O(\sqrt n\log n)$$$ time, if $$$\mathbf{Mod}=998244353$$$.

Code 1 for D itself.

Code 2 for the bonus.

I tried to solve problem C using topological sort but it gave me WA .
But when I just initialize the sets with one value for each ans[s][cur] = 1 before the topological sort it get accepted ,here is my accepted code.

Why this little modification make this difference ? can any one find a counter example .

I hope I wasn't the only one going on OEIS for D. Felt really close to the answer there

Can somebody explain why this test in problems E my solution judged as unvalid output:

Can we say that Number of carries in (a+b) = Number of ones in the binary representation of (a&b) ? where & is the bitwise AND.

I love C! Although I did not make it during the race.

Can anybody help me in debugging my solution for Problem C. Not able to debug why its failing on test 2.

Link of submission: https://mirror.codeforces.com/contest/1761/submission/181847962

I am going with idea of topological sorting.If i is a subset of j then I have added an edge from j to i in the graph and I have also constructed a transposed graph.Later for the nodes having no out edges I have assigned single elements to them and proceeding in a similar way with their ancestors.If any ancestor's set is equal to its child's set then I added one more element.

I'm solved it)

Can anyone point out the name of a well-known problem from F2? Thank you in advance ;)

I solved C in the contest and its similar to editorial approach (I write it if anyone did not understand editorial:

we have N sets and each set is non-empty and no two set are the same Ai!=Aj for all pairs of i and j

so try to look at the matrix (called it B) (N*N) as you make it from beginning like this:

N=4;
0000
0000
0000
0000

our matrix tell us that no set is a proper subset of any other set...
and he said in the statement of problem that each set must be non-empty and no two sets are equal... 

so our sets will be:

A1={1}
A2={2}
A3={3}
A4={4}

so if we try to make B[1][3] equal (1)... so we should make (A1) a proper subset  of (A3) ..so will insert every element in (A1) in (A3) 
so A3 will be{1, 3}, 
(we will use (set data structure) to prevent equal elements) ..and so on try it with example in problems and you will understand 
sorry for my bad english 

My submission

Why Problem D has fft tag? I am new to it. Any solutions around that?

Alternate solution to G:

As in the editorial, we reduce the problem to finding vertices $$$a$$$ and $$$b$$$ such that the centroid lies on the path between them. Picking $$$a$$$ and $$$b$$$ at random will succeed with probability at least $$$1/2$$$. We would like to repeat this to boost our success rate, but we can only afford to test one pair. Instead, we will repeat a cheaper process that finds $$$a'$$$ and $$$b'$$$ such that the path $$$a'$$$-$$$b'$$$ will contain the centroid with constant probability if $$$a$$$-$$$b$$$ does not contain the centroid, and with near certainty if $$$a$$$-$$$b$$$ does contain the centroid.

To do this, we sample $$$s$$$ vertices at random. Let $$$A_1,\ldots,A_k$$$ be the components of the graph with the edges of the path $$$a$$$-$$$b$$$ deleted, such that $$$a\in A_1,\ldots,b\in A_k$$$ (i.e. same $$$A_i$$$ as in editorial). For each sampled vertex $$$v$$$, we compute $$$dist(a,b)+dist(v,a)-dist(v,b)$$$ using two queries to determine which $$$A_i$$$ it belongs to. If the centroid does not lie on $$$a$$$-$$$b$$$, with probability at least $$$1/2$$$, at least half the vertices will be on the opposite side of the centroid as the path $$$a$$$-$$$b$$$, so some $$$A_i$$$ will contain half our sampled vertices. We can then replace an endpoint of our path $$$a$$$-$$$b$$$ with a sampled vertex from $$$A_i$$$ to have at least a $$$1/4$$$ chance of our new path containing the centroid.

To ensure that we do not lose the centroid if it is already on $$$a$$$-$$$b$$$, we use our freedom to choose which of $$$a$$$ or $$$b$$$ to replace. Suppose our new endpoint is selected from $$$A_i$$$. Let $$$w(A_j)$$$ denote the number of sampled vertices in $$$A_j$$$. We replace $$$a$$$ if $$$w(A_1)+w(A_2)+\ldots+w(A_{i-1})\le w(A_{i+1})+w(A_{i+2})+\ldots+w(A_k)$$$ and $$$b$$$ otherwise. Since we only replace if $$$w(A_i)\ge s/2$$$, we can only lose the centroid if $$$3/4$$$ of the sampled vertices lie on one side of the centroid. For $$$s=100$$$, the probability of this happening is already less than $$$10^{-6}$$$.

Code: 181852626

Oh B is interesting indeed. I submitted something that doesn't explicitly compute the frequency of elements (182076103)

In summary, "once removable implies twice removable". Here we say an element is "removable" if its adjacent neighbours are different.

Suppose our sequence contained exactly one removable element $$$R$$$. Then by uniqueness of removability, it would look like:

... (x R) x R y (R y) ...

But our circular sequence is finite, so the ends must meet:

... (R x) R (y R) ...
... (R x) (y R) ...

contradicting the uniqueness of removability in both cases.

Therefore, if there exists some removable element, we can remove it without affecting removability of the other one. Apply the same argument to this element in the new sequence.

In the editorial of problem E, to prove that there always exists a non-cut vertex in a non-clique component, so that it is not adjacent to all other vertices in this component, it reads:

Firstly, if there exist vertices that are adjacent to all other vertices in the component, we erase all of them.

Apparently, the remaining component would still be a non-clique component. Otherwise, the component could only be a clique from the beginning, which contradicts the premise.

However, the proof above is wrong, since after erasing vertices, the component may be divided into several components, and these components may be all cliques.

Instead, the proof can be something like this: Find any non-cut vertex $$$u$$$. If $$$u$$$ is not adjacent to all other vertices in this component, we are done. Otherwise, all other vertices should be non-cut vertices, since after removing any one of them, the component will be still connected due to the existence of $$$u$$$. According to the premise that the component is not a clique, we can always find a vertex (differing from $$$u$$$) that is not adjacent to all other vertices in this component, which must be a non-cut vertex as mentioned above. Q.E.D

By the way, here is the proof that a vertex with the least degree in a non-clique connected component is a feasible vertex: Let's name the vertex $$$u$$$. If $$$u$$$ is a non-cut vertex, since $$$u$$$ is not adjacent to all other vertices in this component, we are done. Otherwise, consider any one of the connected components $$$V$$$ after removing $$$u$$$, and let its size be $$$s$$$. Since the degree of any vertex in $$$V$$$ is not greater than $$$s$$$ (or $$$|V|$$$ will be greater than $$$s$$$), the degree of vertex $$$u$$$ should be not greater than $$$s$$$. And because there are other connected components besides $$$V$$$, the number of edges between $$$u$$$ and $$$V$$$ should be less than $$$s$$$, which means after operating on $$$u$$$, $$$u$$$ and $$$V$$$ will be still connected. Q.E.D

If you view the page saved in the Wayback Machine(Internet Archive), you'll get Chinese editorial without an*me pictures. (Maybe that's because he used a Chinese website to save his pictures, and it was not accessible to the Internet Archive.)

For problem E, the editorial said "Actually, the vertex with the least degree in a connected component always satisfy the condition", I don't understand why the least degree node in a connected component must NOT be a cut vertex. Imagine you have a connected component where node A connects to two different connected component with one edge each. So, A has degree 2, and in those two connected component, each node connects to each other. So A has the least degree, but apparently A is a cut vertex. Would anyone please help me? Thanks a lot.

In problem C, won't the time complexity be O($$$n^{3}$$$) or O($$$n^{3}logn$$$)? Looking at tourist's solution, for sure, it doesn't seem to be O(n^2). 181757137 (tourist's solution) 189290765 (my solution)

code https://mirror.codeforces.com/contest/1761/submission/181776511

problem C Set Construction [Validation check]
the above code got accepted for below test case but the code is generating incorrect output.
Test case:
1
4
0100
0010
0001
0000
This code generates output:
1 1 
2 1 2 
2 2 3 
2 3 4 

but the output must be 
1 1
2 1 2
3 1 2 3
4 1 2 3 4

I think you should include this test case too for the validation. 

Can someone tell me is it possible to solve D using fft? If so please explain

For 3rd question an alternative solution

https://mirror.codeforces.com/contest/1761/submission/250187225

My solution to G that happens to pass the tests that I am not sure if it is completely sound: 292548741

Given a path a-b on a tree, the "projection" of another vertex $$$v$$$ is the vertex on the path nearest to v. Special hanlde the case of small $$$n$$$ (we need n to be somewhat large for the concentration inequality estimate below to hold).

Following the editorial, we reserve 1.5e5 queries to confirm one specific path. At the beginning, we start with a random path between two points. We then attempt to improve the odds that this path contains the centroid as follows:

We spend 2500 queries by picking out 1250 random points, and using two queries each, we can calculate their projection (represented by distances to a,b). We now obtain 1250 samples for random point along our path. Let $$$s=1250$$$ be the number of samples, we call a position bad if there is at least $$$s/2 - 4 sqrt(s)$$$ points located in this position. (Note that, if the centroid is indeed in this position, this position would be bad with very high probability, using general concentration inequalities about binomial distribution). Now:

• If there are no bad positions, we don't change the path
• If there is one bad position, let x be a randomly chosen in this position. Let y be the further endpiont of (a,b) to x. Change our path to x-y
• If there are two bad positions, let x be a randomly chosen point from first position, let y be a randomly chosen point from second bad position. Change our path to x-y.

It is clear that if the centroid did not belong to the path a-b, then with at least 50% chance, the centroid now belong to the path. What seems to be true, but I am unable to prove, is that if the centroid is already on the path, it will keep being on the path. However, this seems to be true enough to get an AC.