Hello, I hope all of you enjoyed my contest!

Tutorial is loading...

**[Behind story of A]**

- There is a successful hack for A. I am really surprised.
- My code: https://codeforces.com/contest/1228/submission/61578842

Tutorial is loading...

**[Behind story of B]**

- There is no behind story.
- My code: https://codeforces.com/contest/1228/submission/61578841

Tutorial is loading...

**[Behind story of C]**

- Initial version of C statement consists of tons of mathematical formula. CF team and testers requested me to reduce amount of mathematical formula.
- This problem was added before a week to the round. If there was no such C, the balance would be bad.
- Thanks for dorijanlendvaj , he improved test data for C a lot!
- My code: https://codeforces.com/contest/1228/submission/61578856

Tutorial is loading...

**[Behind story of D]**

- Same as C, I wrote tons of mathematical formula in D. After CF team's request, I reduced the amount of formula.
- This is my personal favorite problem among ABCDEF.
- My code: https://codeforces.com/contest/1228/submission/61578861

Tutorial is loading...

**[Behind story of E]**

- MikeMirzayanov changed the name of problem before 10~20 minutes to the contest. It was "Minimum One" before.
- This problem was the easiest to prepare data. Just pure random and $$$k=1$$$ is strong enough.
- I managed to create $$$O(n^3)$$$ pypy3 solution for E in 1 second lol.
- Thanks tfg for providing $$$O(n \log n)$$$ solution.
- My code: https://codeforces.com/contest/1228/submission/61578868

Tutorial is loading...

**[Behind story of F]**

- This problem was the hardest to prepare data. We considered more than 10 types of trees to block various kind of WA solutions.
- I intended top-down error-toleration based case handling approach for this contest, but seems other approaches are also ok.
- Also thanks for dorijanlendvaj here, he is real MVP tester.
- My code: https://codeforces.com/contest/1228/submission/61578884

**[Behind story of G (removed problem)]**

- Nobody(including red testers) solved this problem for a week. This problem is saved as spare problem for another Div.1 contest.
- I love this beautiful problem than any other problems I ever made.

Thanks in advance!

The behind story to each problem (except B) is really interesting and new. Great round btw O_o

Fast editorial, Fast system testing, Balanced Problemset, Nice Problems.

This is really one of the finest round of Codeforces.

.

D can be easily solved by hashing

can you explain it pls

all the members of a particular set will have similar neigbours for ex in the first example 2,3 -> 1,4 5 6 , 4,5,6 -> 1,2,3 and 1 -> 2 3 4 5 6 so u can has these no.s([1,4,5,6],[1,2,3],[2,3,4,5,6]) and just check if u have total hash == 3

thx

in your code, for(ll i=1;i<=n;i++) pw[i] = 29*pw[i-1]; won't this part lead to overflow And can you please explain a bit your code

@Bhatt21

Here's my explanation: he uses hash so this step is to map all the points to numbers randomly, which makes it easier to judge if two points have the same set of neighbours. It doesn't matter if it overflows or not as long as all numbers are distrubuted randomly.

Thanks

@Bhatt21, Your solution 61496628 is giving wrong answer for the test case:3 1

1 2

which is given in the test set of the problem D as test case 48, I guess added after the contest but still, the status of the solution is shown

accepted. Don't understand why.When you iterate all the vertexes, if one vertex doesn't have any connect vertex(hash[i]==0) the answer is -1. The auther missed this point.

You can refer to my submission 61524180

is it not possible that a vertex is connected with two vertexes and pow of one is -x and pow of second is +x.

Alternatively a deterministic bitset solution, which I used during the contest.

Very fast editorial, really appreciate it! But is there a proof for the solution of D?

There isn't really a proof needed; it's just a constructive algorithm with lots of constraint checks. Step #4 is just a sanity check to make sure that step #5 won't take $$$O(n^2)$$$ time.

edit: Oh... you mean a proof that if the algorithm fails the answer is definitely impossible. That's a bit beyond my abilities at the moment

nvm thats to ensure its complete

61508959

I'm failing test case 13 in problem C. Can anyone tell me why? I'm unable to figure out

may be your find prime set algo don't recognize cases as 2 * 397

Problem G is the best problem I've ever seen !

how to solve G ? O_o

Considering the fact that the problem G is too complicated for most people, the solution below is only visble for the people who is clever enough .

My solution on problem G in O(n!):

Please delete your comment with solution. This problem will be used in round 599.

A really well-conducted contest. The system testing got over instantaneously and the editorial was posted without delay. We appreciate your effort.

I'm quite curious to wait for the ratings of the problem to see if C has a higher rating than B since I personally found B much harder than B for this contest.

During the contest, I thought D was a variation of the problem of finding a triangle in a graph. But, that problem is known to take at least $$$O(n^2)$$$ time. It's quite nice to see the solutions.

Here are all my solutions to this contest, in case anybody wants to refer them.

I found your C's solution quite neat & elegant. Can you explain. I didn't get why we multiplying p^E in the ans, where p is prime factor of x and E is it's max power in n.

In nutshell, I didn't get the solution yet. :|

We are not exactly multiplying the maximum power of $$$p$$$ in $$$n$$$.

Firstly, we want to find the contribution of each

prime factorin the productindependentlyandmultiplythem.What is the contribution of $$$p$$$ ?$$$p$$$ occurs in the product as many times as p has a multiple from $$$[1, n]$$$

$$$p^2$$$ occurs in the product as many times as p^2 has a multiple from $$$[1, n]$$$

And so on.

Basically, we are trying to find the number of $$$0$$$ in $$$n!$$$ in base $$$p$$$

Please refer my explanation in GitHub and let me know if you have any doubts.

Thanks.

So, for finding the count from [1,n] for p, we have n/p — n/(p^2)...

isn't it?

We are not counting the number of multiples of $$$p$$$. We want the exponent of $$$p$$$.

Each multiple of $$$p$$$ adds $$$1$$$ to the exponent

Each multiple of $$$p^2$$$ adds $$$2$$$ to the exponent

However, each multiple of $$$p^2$$$ is also a multiple of $$$p$$$. That is why, we only add $$$n/p^2$$$ once and not twice. Because it is already added while considering $$$n/p$$$

Similarly $$$n/p^3$$$ adds $$$3$$$ to the exponent. But, we have already added it once in $$$n/p$$$ and another time in $$$n/p^2$$$ so we just add $$$n/p^3$$$ once

EDIT: Got it nowin ur code in github u used power_mod() is it predefined b/c i didn't find its implementation on github

It's written just above the main() function

Can you explain how you came up with this approach.

Questions which are about evaluating a large sum or product generally become easier when we notice the number of terms is not that large and count the contribution of each term, rather than iterating over the whole sum/product.

In this particular question, I thought of checking the contribution of each prime factor to the product rather than evaluating the product as it is.

Once, I found an easy way to get the contribution of each prime factor, all the was left to do was find out all the prime factors and calculate all their contributions

Can someone explain the intuition/proof for solution of D by the approach mentioned in the editorial or the hashing approach? Thanks in advance.

every node from the same set has 2 properties, 1/ not connected to any node from same set, 2/ connected directly to all other nodes, so if we take adjacent list of each node from the same set it will be the same, so we hash the adjacent list after sort, same hash equals same set.

Is the definition of f(r, 0) for problem E incorrect? Or it's my problem with understanding English?

It's correct actually.

$$$f(r,0)$$$ are the ways to fill $$$r$$$ rows and $$$0$$$ incomplete columns (i.e. every column has already at least one $$$1$$$).

Now, the idea behind the formula to calculate the ways to fill each row is: there are $$$n$$$ squares in which in every one of them you can put every number from $$$1$$$ to $$$k$$$ ($$$k^n$$$). However, you are also counting ways in which there is no $$$1$$$, which violates the condition of the problem. Therefore, just remove the number of ways which doesn't include any $$$1$$$. It's the same idea, you have $$$n$$$ squares and in each one of them you put every number from $$$2$$$ to $$$k$$$ ($$$(k-1)^n$$$).

So, the ways to fill each row is $$$k^n - (k-1)^n$$$ and to fill $$$r$$$ rows is $$$(k^n - (k-1)^n)^r$$$.

Can you define once again, what is incomplete column?

An incomplete column is a column that so far it doesn’t have any $$$1$$$.

At the beggining you start with $$$n$$$ incomplete columns as the grid is empty and in each step (filling one row) you can decrease the number of incomplete columns by placing $$$1’s$$$ on them or you can keep it the same.

So consider a 2x3 matrix (n=3) [[1,2,2], [1,2,2]] The above permutation is included in the formula (k^(n)-k^(n-1))^(r). But does not contain 0 incomplete columns.

I'm confused at the same point.

Actually, f(r, c) doesn't mean in how many ways we can reach the state of c incomplete columns. However, it means if we are facing a state with c incomplete columns, in how many ways we can make it a valid matrix.

Sorry, it's not clear at least for me... I think [[1,2,2], [1,2,2]] is not valid matirx even though it is taken into account in (k^(n)-k^(n-1))^(r). Is there still something I missed?

Andimeo can you give an example ?

Thank you very much on the explanation.

But I still can't understand the third formula, especially the first half of the addition. I assume the first half corresponds to c_0 = 0. If so, does it lack a multiplier of (k-1)^c? How to fill the c cells (for the c incomplete columns) in row r?

I explained it here

f(r,0) are the ways to fill r rows and 0 incomplete columns (i.e. every column has already at least one 1).

so why the answer is f(n,n)?

i think it should be f(n,0).

I think I get your idea now.

I think you can see the formula as $$$f(r,c)$$$ are the ways to fill the grid when there are $$$r$$$ rows remaining to fill and you have $$$c$$$ columns which still lack at least one $$$1$$$.

$$$f(n,n)$$$ is the answer and $$$f(n,0)$$$ would calculate the ways to fill $$$n$$$ rows and all of a sudden you have $$$0$$$ columns that lack at least one $$$1$$$ (i.e. every column has at least one $$$1$$$). This is equivalent to just ignore the fact that you have to place at least one $$$1$$$ on every column.

It's because we have n incomplete rows and n incomplete columns, to begin with.

I am still not able to get how the formula for f(r,0) holds because f(1,0) should be number of ways to fill 1 row with all n complete columns (i.e the only possibility is filling all n cells in row by 1) which is just 1 way and not k^n-(k-1)^n. Please tell where I am going wrong. Thank you in advance.

I think you're mistaking n complete columns with all 1s which isn't the case. For example consider a 3 x 3 matrix where you have all three columns satisfied in the first row only, but still, you gotta fill at least one 1 in each of the next two rows. So, for the second row, we will have k^n(no of ways filling all n columns with any number from 1 to k) — (k-1)^n(no of ways of filling all n columns from 2 to k i.e. any number except 1).

@devACE Kindly redefine f(r,c) ?

No of ways to fill r incomplete rows and c incomplete columns.

If anyone is still having this problem. You are thinking bottom up but the editorial approach is top down. f(r, c) means the remaining r rows and c incomplete columns. The n — r rows are already done

D can be solved with some vector sorting (sort and sort). what a very strong vector! :D

Of course, Thanks McDic for the best CF round I have ever participate in!

Please explain how it works.

you can see my submission here 61498103

Saw it already but couldn't understand what's actually happening, what those variables denote.

First, I make an Edge List for each vertex in the graph. Then I sort every vertex's list , check if a list is equal to another one, but I sort the whole Edge List first to make it easier.

Note that keeping the order is needed (for the output) so I make a pair to save it.

I usually do not like a problem if I do not understand the tutorial, like C and E.

B is a problem where one can miss several things, resulting in late errors. With such problems it is nice to have strong pre-tests. Unfortunatly we do not have them here.

It's almost impossible to make 0 solutions fail on systest, you're being biased and not seeing the big picture here, there were really few FST.

Of course I am biased, because my B failed on test 21, which is annoying.

There is that 1x1 example (the second one). That could have been at least a 2x2 example without spoiling the problem in any way, but having a meaningful "negative" example.

However, if you are not willing to give such example, then at least make it a pre-test. I do not think that was because of "we cant test everything", I think it was intentionally.

and again you are salty

If you get a WA in pretest,then you would try to debug it,and there is a good chance of getting AC later,but if it passes the pretest,we seldom(read never)think about it,and we just move on to the next problem. Now you would be LUCKY if you get WA in pretest itself,or be at least hacked.Now your performance in a contest boils down to LUCK.

Just my opinion

Not we, speak for yourself. I've resubmitted my solutions more than once even after getting AC and not getting hacked because I revisited problems and figured out my solution was incorrect.

Anyway, this is a part of contests with systest, your solution is always at risk not getting AC, just practice so you get them right more often.

what if you provide all systest as pretest. I wonder if its still impossible to make 0 solutions fail on systest ?. you're always seeing the same big picture multiple times

That doesn't make a difference unless you disallow hacks. Tests aren't perfect, there'll always be a chance for wrong solutions to AC and correct but slightly too slow solutions to TLE.

How actually the grid looks for this test of B?

I can't understand at all

After applying r_i's I've got

I can't understand how to apply c4 because according to the problem statement in third row I have 1 1 1 0

And why right answer is 0 if we have 2 unreserved cells, its M[2][3] and M[4][3]?

The row descriptions says cell 4,3 must be white, the col description says it must be black. So, there is no solution, hence the answer is 0.

Can someone please explain problem E tutorial — can't understand what's f(r, c) is here. Thanks.

I explained a few comments above $$$f(r,0)$$$. I think it would be nice to read it if it isn't completely clear because I will refer to that.

The first term, which I think it's really $$$(k-1)^c \cdot (k^{n-c}-(k-1)^{n-c}) \cdot f(r-1,c)$$$ means:

You have $$$c$$$ incomplete columns and in this step, you won't decrease this number. It means that in the $$$c$$$ incomplete columns you can put every number from $$$2$$$ to $$$k$$$ ($$$(k-1)^c$$$), the $$$1$$$ is forbidden because this way you would decrease the number of incomplete columns.

Now, you can fill the remaning $$$n-c$$$ squares as you want as long as there is at least one $$$1$$$ in the row, that is $$$k^{n-c} - (k-1)^{n-c}$$$ (I explained this in my previous comment) and now you have $$$1$$$ row less but still $$$c$$$ incomplete columns $$$f(r-1,c)$$$.

The second term

is when you are reducing the number of incomplete columns by $$$c_o$$$ which goes from $$$1$$$ to $$$c$$$.

As you will place at least one $$$1$$$ in this row to reduce the number of incomplete columns, the $$$n-c$$$ already completed columns are free to choose every number from $$$1$$$ to $$$k$$$ ($$$k^{n-c}$$$). Now, you can place the $$$c_o$$$ ones in the $$$c$$$ incomplete columns in $$$\binom{c}{c_o}$$$ ways. Among the $$$c - c_o$$$incompleted columns which will remain incomplete, you can choose every number from $$$2$$$ to $$$k$$$ only ($$$(k-1)^{c-c_o}$$$). And finally, you have $$$1$$$ row less and $$$c - c_o$$$ incomplete columns $$$f(r-1,c-c_o)$$$.

Notice that the first factor is constant in the summatory so it can be placed outside.

Please, explain to stupid guy. Why column order is not important? For example f(1,c)=k^(n−c), like why do not we mult it by C(n)(c) ?

I was wondering the same thing. PoIar_ can you explain?

pepelats The column order "isn't important" because the formula already considers that.

Taking you example, $$$f(1,3)$$$ with $$$n = 5$$$ and $$$k = 2$$$ would mean you have $$$2$$$ squares to put every number you want (the remaining $$$3$$$ must be filled with ones) and it's not the same to fill $$$[1|2]$$$ and fill $$$[2|1]$$$ in those squares. However, you count $$$k^{n-c} = 2^2$$$, which means that in every square you are placing every number from $$$1$$$ to $$$k$$$, which will consider every possible combination already. So, in this particular case this $$$4$$$ ways are $$$[1|1], [1|2], [2|1] $$$ and $$$ [2|2]$$$ and the counting is correct.

Hope it helped.

Not exactly,

f(1,3)

1,1,2,2,2

1,2,1,2,2

1,2,2,1,2

1,2,2,2,1

2,1,1,2,2

...

2,2,2,1,1

It is clearly much more than 4.

I mean there are also ways to put three ones between

It seems I got it. To f(r, c) we come from some outer step (from f(r+1, x) for example). Like we call f(r-1,c-c0) with already set order (some of C(c)(c0) combinations). These c columns are also ordered with another outer step (f(r+1,x)) and so on. Am I right?

Correct

OMG, how to come up with this state representation during contest time?

I have a doubt for $$$f(r, c)$$$, if we fill the $$$c$$$ incomplete columns in the first $$$r - 1$$$ rows, then the whole $$$r$$$ th row will be free and the only constriant is to have a 1 in $$$r$$$th row. Then we would have $$$f(r - 1, c) \times (k^n - (k - 1)^n)$$$, which is different. You mentioned about not to decrease the number of incomplete columns, which does not really make sense to me. e.g. say column 3 is completed in $$$f(r - 1, c)$$$, that does not mean we cannot fill column 3 in the $$$r$$$ th row with a 1. That's why the term $$$(k - 1)^c$$$ does not make sense to me. And idea on that?

There's a misunderstanding in what $$$f(r,c)$$$ counts.

$$$f(r,c)$$$ counts the ways to fill $$$r$$$ rows and there are $$$c$$$ columns which you have to complete, not that we have completed $$$c$$$ columns.

So, when you are filling a current row and you have $$$c$$$ columns to complete, you have to place at least one $$$1$$$ in this row, but there's the possibility that we won't decrease at this step the number of incomplete columns.

For example let $$$n = 3$$$ and $$$k = 2$$$. Imagine that we have filled the first row this way

$$$1 | 2 | 2$$$

$$$. | . | .$$$

$$$. | . | .$$$

At this step we arrive at the state $$$f(2,2)$$$ as we have to complete $$$2$$$ more rows and $$$2$$$ more columns.

Now, imagine I fill the second row so that the grid would look so far this way

$$$1 | 2 | 2$$$

$$$1 | 2 | 2$$$

$$$. | . | .$$$

Note that now we arrive at the state $$$f(1,2)$$$ and that the number of columns that we have to complete are still $$$2$$$. This is what I mean when I say that there's the possibility to keep the incomplete columns the same.

Thanks for the detailed answer and example, it makes sense to me now! Seems I need to work on DP more.

Actually I think the $$$O(n^2)$$$ and $$$O(n\log n)$$$ solution are more straightforward.

Can you explain O(n^2) and O(nlogn) solution ?

First enumerate how many rows and columns have the minimum larger than 1, then fill the other blocks randomly. If there are $$$i$$$ such rows and $$$j$$$ such columns, then the answer is

Where $$$g(i,j)$$$ equals to the number of ways to let $$$i$$$ rows and $$$j$$$ columns have the minimum larger than 1 and fill the rest blocks arbitrarily. We use the inclusion-exclusion theorem here because when we fill the other blocks randomly, more rows' minimum may be larger than 1. $$$C_n^i,C_n^j$$$ means to choose $$$i$$$ rows from $$$n$$$ rows,$$$j$$$ columns from $$$n$$$ columns.

Then calculate $$$g(i,j)$$$. $$$i$$$ such rows and $$$j$$$ such columns includes $$$ni+nj-ij$$$ blocks. The value of those blocks must >1, so the number of ways is $$$ {(k-1)}^{ni+nj-ij} $$$. The rest $$$n^2-ni-nj+ij$$$ blocks can be filled randomly, $$$k^{n^2-ni-nj+ij}$$$. Therefore,the answer is:

Enumerate $$$i,j$$$ use fast exponentiation, the complexity is $$$O(n^2 \log n)$$$ .My code: 61549764

Noted that

It looks like $x^k y^{n-k}$ in the Binomial Theorem. Therefore, it equals to

If you can read Chinese, here is my tutorial in Chinese. Sorry about my bad English.

https://www.cnblogs.com/birchtree/p/11614243.html

Nice explanation. Thank you very much.

Can you elaborate more on the $$$(-1)^{i+j}$$$ ?

When $$$i=0,j=0, (-1)^{i+j}=1$$$ means the universal set.

When $$$i=1,j=0, (-1)^{i+j}=-1$$$, we need to subtract the situation that 1 row's minimum is larger than 1 from the universal set. So $$$(-1)^1=-1$$$

When $$$i=0,j=1, (-1)^{i+j}=-1$$$, we need to subtract the situation that 1 column's minimum is larger than 1. It's the same as above.

However, because we filled other blocks randomly, $$$i=1,j=0$$$ situation may include $$$i=1,j=1$$$ situation.We subtract $$$i=1,j=1$$$ situation twice, so we need to add it back to the answer. $$$(-1)^{1+1}=+1$$$

thanks, got it

awesome explanation! loved it, thanks a lot

D: Check if the complement of the Graph (connect nodes i,j if they are not connected in the original graph) has exactly 3 completely connected components. This is the only check needed acc to me, sadly couldn't do it efficiently in time.

Can you explain why does it works and how did you get the intuition to this approach?

Sorry for the late reply. If you pick any node from one of the 3 groups, it is clear that this node needs to be connected to every node in the other 2 groups. This directly implies that it only not connected to the nodes in the same group, aka in the complement graph it will be connected to all the nodes of the same group and nothing else. Do the same thing for all the nodes and we end up with 3 completely connected components.

Great approach. But making a complement graph, by checking for each pair, i&j, will give you TLE — O(n^2) approach.

I did the same, by building compliment graph, assuming there are three components. Instead of taking all the N & iterating over N we can find any 3 vertices which are not in one component and make graph from them, reducing it to 3*N.

Then, you can check for each edge if both vertices connected to the edge are in different components. If not print -1 . Also, check if the number of edges is correct by assuming sizes of those 3 components.

Code:61517792

Similar problem : https://www.codechef.com/SEPT19A/problems/DOOFST

Where is the solution code for the One Node is Gone problem?

I am sorry. I will add it later.

In the solution of E

`Now you can see that the formula can be described as below;`

I think in the third formula the first term should be multiplied with (k-1) ^ c https://codeforces.com/contest/1228/submission/61516757

I didn't get you. What I understand is we are filling all the 'c' incomplete columns here and so all of them have '1' and in remaining we can choose anything but there must be atleast one '1' in this row and so we have the first term as written there. So, where from that $$$(k-1)^c$$$ comes?

And also I have a doubt. If I understood the approach correctly, so whenever $$$c > 0$$$ we are sure that there are atleast $$$1$$$ column which is incomplete and we are going to fill it here. So, isn't the first term should be K^(n-c) only?

The first term is for the case when we keep the same number of incomplete columns, so we can place anything but 1 in those c columns (k-1)^c and among the ones that are complete, we must have atleast one 1. (k^ (n-c) — (k-1)^(n-c)) and then make a recursive call to (r-1,c)

McDic, Can you please verify this!

My code`f[r][c] = clean(kpower[n-c] - k1power[n-c]) * k1power[c] % mod * f[r-1][c] % mod;`

Yup you have multiplied it with k1power[c] :)

I fixed, thank you.

The formula in the $$$O(n^2)$$$ solution for E should be $$$-1^{i+j}$$$?

Yes, sorry.

I fixed. It will be reflected soon.

In 1228B - Filling the Grid, I'm trying to count all combinations (nCr) of unreserved cell. I'm not sure why combination is not the right way?? and why 2^unreserved_cell should be the output??

You can make any of these cells black or white. So two possibilities per cell. Each one cell independent of all other cells. So if you got one more cell, the number of possibilities doubles.

Why step 4 is necessary for D? I thought it was sufficient to put vertices without a direct edge in the same set and checking if there is an edge between two vertices in the same set.

I didn't do that check in my solution but from what I guess, it's meant to check that there should be no edges between nodes in the same set. (Note that you can't iterate through every pair because the number of pair can be very large)

Why this code gives me the incorrect output for test 2 in problem E? I just implemented the function the tutorial told me to. Can someone please help?

Man you are very active on cf(your graph says it) and you don't know how to use SPOILER or LINK in comments for your code. It is really annoying to see such huge codes in comments.

Sorry. but I don't know how to do that.

Just go to https://paste.ofcode.org or https://ideone.com (usually I use paste.ofcode.org 'cause it more easy to use) and paste your code, then you can just send to someone the link.

Like this -> https://paste.ofcode.org/329jEhW7par3TKGBpYxpsNK or just link the word ->

click.Hope it helps u.

How to share your submission:Example:Check out my submission 61479457:You can share your code here:

CODEThanks. Can you demonstrate how to attach a picture ?

In problem D I missed 1 line and related it to 3-coloring problem. How stupid of me!

Can anyone explain what a "restriction" (in E tutorial) is? If we can intersect these "restrictions", then I guess it's a set. What are elements of these sets?

Ok, I think that I got it. I understand it in the following way. We are considering only grids of elements from $$$[1, k]$$$. $$$R_i$$$ is the set of all grids where all elements in the $$$i$$$-th row are greater than $$$1$$$ and $$$C_j$$$ is the set of all grids, where all elements in the $$$j$$$-th column are greater than $$$1$$$. So, $$$R_1 \cup R_2 \cup \ldots \cup R_n \cup C_1 \cup C_2 \cup \ldots \cup C_n$$$ is set of all bad grids (grids that have at least one row or column without $$$1$$$), let's denote it as $$$B$$$. Let $$$U$$$ be the set of all grids. In this problem we need to find the number of grids that have at least one $$$1$$$ in each row and at least one $$$1$$$ in each column. Therefore, we just take the set of all grids and subtract the set of all bad grids: $$$U \setminus B$$$.

Am I right? (I know that it differs a bit from what is written above. However, it still seems to be something equivalent)

Correct!

In

A, simply check which numbers do not have same digit pair. In Perl:`print +( grep !/(.).*\1/, -1, $l .. $r )[ -1 ]`

Can anyone please explain problem B with code. Thanks.

Just fix the matrix, according the constraints, take the matrix, as 3 state value —

Now apply the constraints on all rows one by one. Then for each column, check if its possible to apply the constraints given for those columns. Once applied, the remaining -1 ' count, (say cnt) each can be filled with either 1 or 0. Thus 2^cnt will be the answer.

Refer my submission: https://codeforces.com/contest/1228/submission/61514443

Possible solution of

B.(Perl example)Here:

X: not visited

0: visited, and must be white/empty

1: visited, and must be black/filled

Make an array of strings containing 'X'-es.

`@strings = ( 'X' x w ) x h;`

Write a subroutine (function) which searches and replaces (

`s///`

) from beginning of a string.SEARCH for exact number (depending on $$$h_i$$$ or $$$w_i$$$) of consecutive 'X' or '1', and '1' must not follow (

`(?!1)`

as negative look-ahead), but any other symbol may follow (`(.)?`

, saved as capture`$1`

):`^[X1]{$fill->[$i]}(?!1)(.)?`

.REPLACE this with consecutive '1' followed by '0' (if

`$1`

defined):`1 x $fill->[$i] . ( defined $1 ? 0 : '' )`

.1. Apply subroutine for an array of strings, using values from array

`h`

.2. Transpose strings.

3. Apply subroutine for an array of strings, using values from array

`w`

.Count 'X'-es, and answer is 2^X with mod. If matching fails at any point, that means it is impossible to fill correctly, answer zero.

In problem C, what i am doing is calculating the maximum number of divisible elements from

1 to nfor each power offactorwhere factor is the prime factor ofx. However it is resulting in WA, here's my submission 61509357Very nice round, problems was really good to solve and there was no bugs!

One of the interesting rounds I've ever solved.

Thank youMcDic ^3^I'm sorry that the Tutorial for problem E in $$$ O(n^3) $$$ must be wrong. How can the answer be $$$f(n)(n)$$$ in your define? I'm look forward to reading the correct Tutorial .

I fixed. Thank you.

I guess, it'd be better if you had rather written $$$R[i]$$$ to be the set of matrices which have at least one $$$1$$$ in its $$$i$$$-th row. It took me couple of minutes to realize what you actually meant.

Also, I think the difficulty of problems didn't increase as it is supposed to. Maybe nlgn version of E could be moved to F and F to E. But, having both D and F in a single round is kind of not-so-interesting for the contestants. Like, you can figure out what the solution is at first sight but have to spend some boring time figuring out every bits and pieces and also the $$$\Delta$$$ difficulty of D and F is actually not that mush :(.

problem D https://codeforces.com/contest/1228/submission/61536068 i am geting wrong on testcase 6...help me to know which cases i am missing..

maybe you forget that three sets must not be empty? The reason I am wrong answer on testcase 6 is that.

No..that was checked..please go through my code once!

You can do D in

O(n+m)and without hashing because instead of step"5. For all vertices

u_1andu_2from different vertex sets, if there is no direct connection betweenu_1andu_2, then answer is impossible."we can just check if every edge is between vertexes from different vertex sets.

Here is such a submission written by me: 61543333.

Thanks for the detailed and descriptive editorial. All the editorials should be like this one.

Could someone help me getting the logic behind Div2 C problem.I am not able to understand the editorial.Thank you!

How do we "look at your code" in problem F McDic?

I will post soon, sorry.

I posted my solution codes. Thank you.

I think it can also be a good way to solve C by using fastpower. 61555003 Anyway,it's a really tricky problem.I only need another five minutes to solve it because of my poor B. :(

LittleBear1224 Can you please explain your logic for problem C. I cannot understand the editorial.

Errorist

In the num array, store the prime factors of x. Next, iterate on all these prime factors and check the total power of each that the answer should have. The answer should have a total power of (k1+k2...+kn) for a prime p, where ki is the max power of p in i. That is equivalent to calculating the total power of p in factorial(n). This code calculates the same.

Story behind PROBLEM B, nowhere mentioned that if the blocks are conflicted, you have to cout 0, how the hell, m i supposed to know that,,, still if feel like it is smiliar to the problem on At CODER named, "01 Matrix",...

Can somebody explain E deeper? Particularly what is incomplete column? Why "Incomplete columns means which doesn't contain 1 in already filled part", but they do contain?

f(r,c) -> take an incomplete column i. In i'th column the rows from 1..r do not contain '1'.

What I understood: f(r, c) — number of ways to fill r last rows, where c columns do not have 1 yet. Why does not the order of these columns play role?

Can anyone please explain what is map of vectors ?? Because most of the solutions of Problem D were done with it..

Problem B What kind of problem is this? For input: 3 6 0 0 0 0 0 0 0 0 0

For the same code output in my system: 1048 CF say participant's output: 0 My submission link

I'm failing test case 13 in problem D.Can anyone help me why? I'm unable to figure out :

My submission : 61607967

Could someone give me an O(n^3) code with explanatory notes of Problem E? I think I am not able to understand the O(n^3)solution by my poor English while the O(n^2)solution is much more clear.

Problem D can be solved in O(n+m) time complexity using BFS.

I first do 2 coloring using BFS where the first set has no edges in it, while the second may or may not have edges in it. After this I do 2 coloring on the second set created earlier in this the two sets need to have no edges in them otherwise it is impossible. To check whether it is complete or not we can see if total edges given is equal |s1|*|s2| + |s1|*|s3| + |s3|*|s2|, where si is the ith partition. Also, none of the partitions should be of 0 size.

Submission

In problem E，I don’t figure out how to pre-solve the combination in $$$O(nlogn)$$$，though the later calculation can be solved in $$$O(nlogn)$$$. So I doubt the existence of $$$O(nlogn)$$$'s solution a little.

Sorry！Now I know how to get it. I <==> stupid .

In problem C, why $$$h(n!, p) = \sum_{k=1}^{\infty} \Bigl \lfloor \frac{n}{p^k} \Bigr \rfloor$$$?

Dose we just distribute number p in range $$$[1:n]$$$ by the way the position $$$i$$$ in range $$$[1:n]$$$ still larger than pow(p, number of p located at i)?

Try to describe $$$n!$$$ in products of $$$p$$$-ary digit numbers.

Sorry, what does $$$p$$$-ary mean?

Let me explain in another way.

$$$n! = p \cdot 2p \cdot 3p \cdot \ldots \cdot kp \cdot C$$$ where $$$k = floor(\frac{n}{p})$$$ and $$$C$$$ is some positive integer number.

There are at least $$$k$$$ terms which has $$$p$$$. Divide both side by $$$p^k$$$, then you get $$$\frac{n!}{p^k} = k! \cdot C$$$. Now, do previous step again for $$$k!$$$.

Thank you very much!

"If you choose any u as first vertex of specific vertex set, then you can simply add all vertices which are not directly connected to u in that vertex set". McDic, What would be the most optimal way to do this for all vertices and how is the complexity O((n+m)log n) ?

You choose vertices(without thinking invalid edges) at first, vertex sets validation is the seond step.

I used

`std::vector<std::set<int>>`

to store graph info so that's why my complexity is $$$O((n+m) \log n)$$$ (It's possible to do this in $$$O(n+m)$$$)Yes, I understand that validation is the second step. Creation of vertex sets using the method you mentioned above, wouldn't that exceed time limit, since for each vertex you have to find the vertices that are not directly connected to it.

No, it will use $$$O(n)$$$ or $$$O(n \log n)$$$, because you will scan vertices only $$$3$$$ times. Check my code for details.

got it, thanks

McDic in your code when u check if m edges are present or not, you iterate over two groups at a time

the complexity of that part is ab + ac + bc where a, b, c are the sizes of the vertex sets

why is this complexity not O(n^2) and not giving TLE?

Because the program will terminate if you find when there is no connection between $$$v_1$$$ and $$$v_2$$$ when there should one exist. Since there are at most $$$m$$$ edges, time complexity is $$$O(m)$$$ for this part.

Wow, E literally appeared (with a higher N) in the Asia Nanjing Regional ICPC.

Do they intended $$$O(n \log n)$$$ ?

can someone plz explain the solution of C briefly?? tnx in advance. cant get the solution for many hours.

I think key observation is that we need to build answer for every prime factor independent.

So, given one primefactor $$$pr$$$, we want to find the number of numbers in interval $$$(1,n)$$$ which are devisable by $$$pr^k$$$ but not by $$$pr^{k+1}$$$, for all possible $$$k$$$.

This number of times $$$pr^k$$$ contributes to ans.

For implementation we should observe that it is same if $$$pr^k$$$ contributes $$$m$$$ times, or $$$pr^{k-1}$$$ contributes $$$m\cdot pr$$$ times.

So we end up with a fairly simple loop as shown in example code, where we count how much times $$$pr$$$ contributes, and calculate that contribution with a single $$$pow(pr, times, mod)$$$ operation.

77173595

spookywooky why we will calculate the frequency of each prime divisor in n!.I actually understood mathematical expression written in the editorial until the line before the last.Line before the last says that we have to calculate the sum of all h(i, p), means maximum power of p which divides i as h(x, p) is defined as the maximum power of p which divides x, isn't it? So using the formula

`h(x,p)+h(y,p)=h(xy,p)`

we reached to the next line as h(n!, p). My main confusion is in this point. Doesn't h(n!, p) mean that maximum power of p which divides factorial n? If that then shouldn't we calculate how many numbers between [1, n] which`only`

contains p^0, then p^1 then p^2........so on upto the maximum power.Why we are calculating the frequency of prime p in n!, shouldn't we go part by part? As the number which contains p ^ 2 (say) then it only contain p ^ 2, that is the maximum power of p that can divide it is 2 (p ^ 2). But we have already calculated the frequency of p ^ 1 and some of the numbers which contain p ^ 2 or p ^ 3 will also be considered as the numbers contains p ^ 1 when we are calculating p ^ 1.I want to say that if p ^ 1 comes than it should comes from those numbers which only contain p ^ 1, not from p ^ 2 or p ^ 3 or any other and those particular number will be divisible by maximum power of p is 1.I'm totally messed up, please help.Sorry, I did not understand how that construct h(x,p) in the tutorial works, and all the formula.

my AC code

my solution for D

i just tried coloring the graph

let parent color = 1, cur node color = 2

if there is an edge between [parent of cur node] and [child of cur node] => color child of cur node 3

if there isnt an edge between [parent of cur node] and [child of cur node] => color child of cur node 1

just like bipartite graph + ensuring all the edges exist

https://codeforces.com/contest/1228/submission/88625214 this is my AC solution for D

https://codeforces.com/contest/1228/submission/88625178 this is my WA solution for D

These codes differ only at 1 position and logic is almost same can anyone plz check why 1 work and 2 doesn't (spookywooky if time permits plz have a look)

Also, both the solution are very elegant even more than the tutorials and other's submissions I have seen so far.

Sorry, I do not get this one. I find it hard to understand why it works at all. There are so much cases in which order the assignment of group 2 or 3 can happen to a vertex.

Graph in Problem D Should not be Bipartite Graph. Hence it should have one or more odd cycle. If removing one vertex make the graph bipartite then we could form Tripartite ? does anybody care to explain whats wrong in my thought process or any extension to above idea ? I guess we can keep on removing vertex from graph G which is responsible for not becoming bipartite and keep on removing until it becomes bipartite and the removed vertices can be kept in set v3 ?

Alternative solution to problem D: Create a graph G, where an edge exists between vertices u and v if and only if there is no existing edge between them in the graph given in the input. The three independent sets of vertices will be separate connected components of this graph, where each connected component is a complete graph. We can find the number of connected components and what vertices are in them using a BFS. AC Code: 217774204