Where is fyy Memorial Valley School

All hail our emperor anton

All hail our emperor anton

broke another chain

orzdevinwang orz

If my rating dropped,I will downvote you!!!

pigstd orz

my mommy

I can't wait to see that!

This year Technocup will be held not on Codeforces, but on the Allcups platform made by VK so unfortunately it seems to me there will be no mirror.

Maybe hard I think.

I apologize if it bothers you. The picture is a representation of our team spirit. She is not from an anime. We designed the picture and spend a lot of time and money to make her alive. I appreciate your honesty and hope you like her

If you take a look at her profile, you will know that she is Chisato Nishikigi, obviously a girl. She even has a picture of herself uploaded as proof.

Yes!I'm her classmate,she is so cute! :d

Dude, this is not important, the important thing is that pigstd is really cute.

It depends on your imagination :).

Rated for everyone

The statements were made as briefly and clearly as we could.

Don't worry :)

Is China in the world cup?

Grade 10

Of course a cute girl~

Don't be cheated by his anime girl profile. sure.

What is your definition of girl?

average newbie

me too... -120+ yay

How are you a specialist?

Me too but i wasted like 25 min something

Why not try the next div4 Codeforces Round 835 (Div. 4) to gain your confidence and rating?

is there a nice way to cover this case? i ended up directly checking the validity of my candidate answers in $$$O(n^2)$$$ with bitset.

put $$$a$$$ and $$$b$$$ on top of each other, and lets build a string $$$c$$$ of length $$$n$$$ on the alphabet $$$(0,0)$$$, $$$(0,1)$$$, $$$(1,0)$$$, and $$$(1,1)$$$ (i can't get the column vectors to play nice with the inline latex, but the first one goes to $$$a$$$ and the second goes to $$$b$$$). we will count by starting off with the empty string, and sequentially inserting characters into valid positions.

carries are started by a $$$(1,1)$$$, are continued leftwards by either $$$(0,1)$$$ or $$$(1,0)$$$, and are terminated by $$$(0,0)$$$ or another $$$(1,1)$$$.

suppose we will place $$$x$$$ chains of carries, where $$$1 \leq x \leq k$$$. we will place $$$x$$$ of $$$(1,1)$$$ and $$$k - x$$$ of $$$(0,1)$$$ or $$$(1,0)$$$ that will continue these chains. we have $$$2$$$ characters to choose for each of the continuations, and we must place these $$$k-x$$$ items into one of $$$x$$$ groups, so there are $$$2^{k-x}\binom{k - 1}{x - 1}$$$ to make this assignment.

now, for each of these $$$x$$$ chains, either it will be terminated by a $$$(0,0)$$$ or by the $$$(1,1)$$$ that starts the next chain. let's manually terminate $$$y \leq \min(x, n-k)$$$ chains with $$$(0,0)$$$. there are $$$\binom{x}{y}$$$ ways to place these.

we have $$$n-k-y$$$ non-carry positions left to place. each of them can go in one of $$$y+1$$$ groups: either to the left of one of the $$$(0,0)$$$'s, or on the very right before any of the chains have begun. there are $$$3$$$ legal characters for these: $$$(0,0)$$$, $$$(0,1)$$$, and $$$(1,0)$$$. thus, we have $$$3^{n-k-y} \binom{n-k}{y}$$$ to fill in these last positions.

our answer comes out to

from here, i brute forced my way though to the end using a convolution, so there is likely a more clever solution. nevertheless, i manipulated the equation with

note that the inner summation is a convolution of two sequences $$$p$$$ and $$$q$$$, where

precompute the inner summation with your convolution tool of choice in $$$O(n \log n)$$$, which allows us to compute the outer summation in $$$O(k)$$$.

I got to the following formula:

where $$$i$$$ is the number of blocks of consecutive carries (11 followed by 11,10 or 01 any number of times, ended by 00). The binomial coefficients count the placement of these blocks within the n bits. The second sum accounts for the case when the last block is not ended by 00.

It doesn’t. The checker guarantees that the answer exists for all testcases.

The answer does NOT always exist. The problem specifically implies this. However, the problem guarantees that an answer must exist for each test case, so you don't have to worry about these no-answer scenarios.

A simple counterexample is when every row has at least one 1. Since there is no all-zero row, this means every set is a proper subset of another set, which must lead to a cycle of proper subset chains, so each set in this cycle is a proper subset of itself, which is impossible.

Anyway, my answer was to enforce a rule that the number $$$i$$$ will only appear exactly in set $$$i$$$ and its proper subsets. I'll refer to $$$i$$$ as the ID of set $$$i$$$. This fulfills the three conditions:

1. Sets are non-empty (must contain its ID) and values are from $$$1$$$ to $$$n$$$ (all IDs are from $$$1$$$ to $$$n$$$, and no other values are considered).

2. All sets are distinct, because if we consider any pair of sets, they cannot both be proper subsets of each other (this leads to a contradiction as I mentioned above), so the one that isn't a proper subset will lack the ID of the other.

3. Binary Matrix representing proper subsets is proven by how we construct the sets: for row $$$i$$$ of the matrix, we add the ID $$$i$$$ to each column $$$j$$$ for which $$$b_{i, j} = 1$$$. This fulfills the third condition, while also following the ID rule.

My submission: 181766895

My code returns this:

1 1 
1 2 
2 2 3 
4 1 2 3 4 

I have thought of this solution:

1. Let's think the graph is not connected.

2. Let's think there is no single vertex, else we could invert its edges.

3. If there is a connected component that is not complete, let's invert the edges of one its vertex that is not a joint and is not connected to all vertices of the component. Then it will be connected to at least one of the other vertices and the other vertices themselves will be connected together. Note that if there is a vertex of the component that is connected to every other vertex, the other vertices are all not joints, and if there is none, the leaves of the DFS tree still are all not joints.

4. If all the components are complete, there are either two components or more.

5. One possible answer is to invert all the vertices of any component.

6. There is another way to do it if there are >= 3 components. We can see that if we invert a vertex in each of some two components, the graph will be connected. (Note that after we invert some vertices, the not inverted vertices of each component will be connected together and the inverted vertices of each component will also be connected together and also with the not inverted vertices of other components.)

First N choose t for the places, then for the sizes, we have t integers summing up to K, each must be greater than 1, it's a case of bars and stars.

In fact we can solve the bonus of D with DP, but need some hard knowledge. :(

You will see it in the tutorial soon.

I don't know your approach, but here is a counterexample: graph with two components A-B-C and D-E-F, both paths. The answer should be 1, because if you apply the operation on any vertex other than B or E, the graph becomes connected. The test-case format is:

6
010000
101000
010000
000010
000101
000010

More generally, if there is a connected component with at least 3 vertices and at least one vertex has degree-1 (which is always true for a tree btw), then choosing this vertex would always be sufficient. It will connect to all other components, and although it loses an edge with its neighbor, it will gain edges to the other neighbors of this neighbor, so connectivity within its own component is preserved.

(I didn't solve E btw, but this particular subcase I was able to establish)