Codeforces Round #589 (Div. 2) Editorial

5 years ago, # |

← Rev. 2 →

+21

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

→ Reply

Spheniscine

5 years ago, # ^ |

← Rev. 4 →

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

→ Reply

Shameek

4 years ago, # ^ |

← Rev. 2 →

nvm thats to ensure its complete

→ Reply

i_used_to_love_samiksha

5 years ago, # |

61508959

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

→ Reply

sthfaceless

5 years ago, # ^ |

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

→ Reply

fried-chicken

5 years ago, # |

← Rev. 2 →

+24

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

→ Reply

qmk

5 years ago, # ^ |

+20

how to solve G ? O_o

→ Reply

fried-chicken

5 years ago, # ^ |

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

→ Reply

antontrygubO_o

5 years ago, # ^ |

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

→ Reply

5 years ago, # |

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.

→ Reply

nilesh8757

5 years ago, # ^ |

← Rev. 2 →

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

→ Reply

5 years ago, # ^ |

← Rev. 2 →

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

Firstly, we want to find the contribution of each prime factor in the product independently and multiply them.

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.

→ Reply

nilesh8757

5 years ago, # ^ |

Thanks.

→ Reply

msdcoder7

5 years ago, # ^ |

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

isn't it?

→ Reply

5 years ago, # ^ |

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

→ Reply

mehulcoder

4 years ago, # ^ |

← Rev. 3 →

EDIT: Got it now

/*
* Basically we need to prime factorize x. And iterate on them.
* For each prime pi we need the contribution of pi, pi**2, pi**3...
* to numbers in [1, n] . Number of multiple of pi will give how many times pi has contributed.
* Eg: 1-30 p = 2:
* 2^1 contributes: (2^1)^(30/2)
* 2^2 contributes: (2^2)^(30/2^2): But they are already once counted with 2^1
* So the total contribution of above two is: (2^1)^(30/2)*(2^1)^(30/20^2)
* similary for 3rd power. Therefore, net contri = (2^1)^(30/2)*(2^1)^(30/20^2)*(2^1)^(30/2^3)
* similarly for 4th, therefore net: (2^1)^(30/2)*(2^1)^(30/20^2)*(2^1)^(30/2^3)*(2^1)^(30/2^4)
*/
 
/*
* Proof: Say contri of p^(i-1) = (n/p^(i-1)) ---->c1
* contri of p^(i) = n/(p^i). But that has contri of
* p^(i-1) too. Net contri of p^(i-1) = (n/p^(i-1))-(n/p^(i))---->c2
* Therefore the result for them both can be written as
* (p^(i-1))^(c1))*(p^i)^c2 == p^((i-1)*(n/p^(i-1)) * p^((i-1)*n/p^(i))
* This is valid for all i
*/

→ Reply

shubham95

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

It's written just above the main() function

→ Reply

Yatharth1

5 years ago, # ^ |

Can you explain how you came up with this approach.

→ Reply

5 years ago, # ^ |

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

→ Reply

NewRules

5 years ago, # |

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

→ Reply

pleb

5 years ago, # ^ |

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.

→ Reply

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

+21

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

→ Reply

siisback

5 years ago, # ^ |

Can you define once again, what is incomplete column?

→ Reply

5 years ago, # ^ |

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.

→ Reply

shreyasbalakrishna19

5 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

k_k_hiroki

5 years ago, # ^ |

I'm confused at the same point.

→ Reply

5 years ago, # ^ |

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.

→ Reply

k_k_hiroki

5 years ago, # ^ |

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?

→ Reply

shreyasbalakrishna19

5 years ago, # ^ |

Andimeo can you give an example ?

→ Reply

5 years ago, # ^ |

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?

→ Reply

5 years ago, # ^ |

I explained it here

→ Reply

cocktail

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

devACE

5 years ago, # ^ |

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

→ Reply

stillfaking

5 years ago, # ^ |

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.

→ Reply

devACE

5 years ago, # ^ |

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

→ Reply

tanya_sapra

5 years ago, # ^ |

@devACE Kindly redefine f(r,c) ?

→ Reply

devACE

5 years ago, # ^ |

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

→ Reply

Atill83

5 years ago, # ^ |

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

→ Reply

PvDzxc

5 years ago, # |

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!

→ Reply

t1war1

5 years ago, # ^ |

Please explain how it works.

→ Reply

PvDzxc

5 years ago, # ^ |

you can see my submission here 61498103

→ Reply

t1war1

5 years ago, # ^ |

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

→ Reply

PvDzxc

5 years ago, # ^ |

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.

→ Reply

5 years ago, # |

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.

→ Reply

5 years ago, # ^ |

+25

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.

→ Reply

5 years ago, # ^ |

-27

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.

→ Reply

qmk

5 years ago, # ^ |

and again you are salty

→ Reply

AjaySabarish

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

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.

→ Reply

B_Consistent

18 months ago, # ^ |

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

→ Reply

18 months ago, # ^ |

+12

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.

→ Reply

ValeriyG

5 years ago, # |

← Rev. 4 →

How actually the grid looks for this test of B?

4 4
2 0 3 1
1 3 0 3

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

→ Reply

5 years ago, # ^ |

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.

→ Reply

rupav

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

+51

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

$$$ \sum_{c_o = 1}^{c} k^{n-c} \cdot \binom{c}{c_o} \cdot (k-1)^{c-c_o} \cdot f(r-1,c-c_o) $$$

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.

→ Reply

5 years ago, # ^ |

+11

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

→ Reply

lrvideckis

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

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.

→ Reply

P___

5 years ago, # ^ |

← Rev. 6 →

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.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

I mean there are also ways to put three ones between

→ Reply

5 years ago, # ^ |

← Rev. 2 →

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?

→ Reply

5 years ago, # ^ |

Correct

→ Reply

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

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?

→ Reply

5 years ago, # ^ |

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

$$$. | . | .$$$

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.

→ Reply

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

5 years ago, # ^ |

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

→ Reply

birchtree

5 years ago, # ^ |

← Rev. 2 →

+23

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

→ Reply

deepsavani

5 years ago, # ^ |

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

→ Reply

birchtree

5 years ago, # ^ |

← Rev. 2 →

+26

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

$$$\sum_{i=0}^n \sum_{j=0}^n (-1)^{i+j} C_n^i C_n^j g(i,j)$$$

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:

$$$\sum_{i=0}^n \sum_{j=0}^n (-1)^{i+j} C_n^i C_n^j {(k-1)}^{ni+nj-ij} k^{n^2-ni-nj+ij}$$$

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

Noted that

$$${(k-1)}^{ni+nj-ij} k^{n^2-ni-nj+ij}=k^{(n-j)(n-i)}(k-1)^{(n-j)i}(k-1)^{j \times n}=[k^{n-i}(k-1)^i]^{n-j}(k-1)^j$$$

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

$$$\sum_{i=0}^{n} (-1)^i \cdot C_n^i \cdot (k^{n-i} \cdot (k-1)^{i} - (k-1)^{n})^n$$$

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

→ Reply

deepsavani

5 years ago, # ^ |

Nice explanation. Thank you very much.

→ Reply

5 years ago, # ^ |

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

→ Reply

birchtree

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

thanks, got it

→ Reply

grapo_Oranges

3 years ago, # ^ |

awesome explanation! loved it, thanks a lot

→ Reply

namansinghal198

5 years ago, # |

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.

→ Reply

yonkoamit

5 years ago, # ^ |

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

→ Reply

namansinghal198

5 years ago, # ^ |

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.

→ Reply

rupav

5 years ago, # ^ |

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

→ Reply

siisback

5 years ago, # ^ |

← Rev. 4 →

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

→ Reply

siisback

5 years ago, # ^ |

→ Reply

nytemusik

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

← Rev. 2 →

I am sorry. I will add it later.

→ Reply

harshhx17

5 years ago, # |

+11

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.net/contest/1228/submission/61516757

→ Reply

pk842

5 years ago, # ^ |

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?

→ Reply

harshhx17

5 years ago, # ^ |

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!

→ Reply

5 years ago, # ^ |

← Rev. 2 →

My code

    std::vector<lld> kpower = {1}, k1power = {1};
    for(int i=1; i<=n; i++){
        kpower.push_back(kpower.back() * k % mod);
        k1power.push_back(k1power.back() * (k-1) % mod);
    }

    // f(r, 0) = (k^n - (k-1)^n)^r
    for(int r=1; r<=n; r++) f[r][0] = clean(power(power(k, n) - power(k-1, n), r));
    // f(1, c) = k^(n-c) (c>=1)
    for(int c=1; c<=n; c++) f[1][c] = power(k, n-c);

    // f(r, c) = (k^(n-c) - (k-1)^(n-c)) f(r-1, c) + for_{c0} k^(n-c) [c]C[c0] f(r-1, c-c0)
    for(int r=2; r<=n; r++) for(int c=1; c<=n; c++){
        //if(c==n) f[r][c] = 0;
        //else f[r][c] = clean(power(k, n-c) - power(k-1, n-c)) * power(k-1, c) % mod * f[r-1][c] % mod;
        f[r][c] = clean(kpower[n-c] - k1power[n-c]) * k1power[c] % mod * f[r-1][c] % mod;
        for(int c0=1; c0<=c; c0++){
            //f[r][c] += power(k-1, c-c0) * power(k, n-c) % mod * nCr[c][c0] % mod * f[r-1][c-c0] % mod;
            f[r][c] += k1power[c-c0] * kpower[n-c] % mod * nCr[c][c0] % mod * f[r-1][c-c0] % mod;
            f[r][c] %= mod;
        }
    }

→ Reply

harshhx17

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

I fixed, thank you.

→ Reply

flashmt

5 years ago, # |

+14

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

→ Reply

5 years ago, # ^ |

Yes, sorry.

→ Reply

5 years ago, # ^ |

I fixed. It will be reflected soon.

→ Reply

ismail

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

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.

→ Reply

Nson

5 years ago, # |

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.

→ Reply

flashmt

5 years ago, # ^ |

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)

→ Reply

joker70

5 years ago, # |

-30

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

const int MAX = 250 + 5;
const int MOD = 1e9 + 7;

#define dbg(a) cout << "-> " << #a << " = " << a << endl

int add (int a, int b) {
    return (a + b < MOD) ? (a + b) : (a + b - MOD);
}

int sub (int a, int b) {
    return (a >= b) ? (a - b) : (a - b + MOD);
}

int mul (int a, int b) {
    return (a * 1LL * b) % MOD;
}

int expo (int a, int b) {
    int ret = 1;
    while (b != 0) {
        if (b & 1) {
            ret = mul(ret, a);
        }
        a = mul(a, a);
        b >>= 1;
    }
    return ret;
}

int main() {
	vector<vector<int>> C(MAX, vector<int> (MAX));
    for (int n = 0; n < MAX; n++) {
        for (int r = 0; r <= n; r++) {
            if (n == r or r == 0) {
                C[n][r] = 1;
            }
            else {
                C[n][r] = add(C[n - 1][r], C[n - 1][r - 1]);
            }
        }
    }

    int n, k;
    scanf("%d %d", &n, &k);

    vector<int> x(MAX), y(MAX);
    x[0] = y[0] = 1;
    for (int i = 1; i < MAX; i++) {
        x[i] = mul(k, x[i - 1]);
        y[i] = mul(k - 1, y[i - 1]);
    }
    
    vector<vector<int>> dp(n + 1, vector<int> (n + 1));
    int val = sub(x[n], y[n]);
    for (int r = 1; r <= n; r++) {
        dp[r][0] = expo(val, r);
    }
    for (int c = 1; c <= n; c++) {
        dp[1][c] = x[n - c];
    }
    for (int r = 2; r <= n; r++) {
        for (int c = 1; c <= n; c++) {
            int ret = mul(dp[r - 1][c], sub(x[n - c], y[n - c]));
            for (int c0 = 1; c0 <= c; c0++) {
                int now = mul(C[c][c0], y[c - c0]);
                now = mul(now, dp[r - 1][c - c0]);
                ret = add(ret, mul(now, x[n - c]));
            }
            dp[r][c] = ret;
        }
    }
    printf("%d\n", dp[n][n]);
    return 0;
}

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?

→ Reply

techgig0

5 years ago, # ^ |

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.

→ Reply

joker70

5 years ago, # ^ |

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

→ Reply

moonpie24

5 years ago, # ^ |

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.

→ Reply

ismail

5 years ago, # ^ |

+29

How to share your submission:

Example: Check out my submission 61479457:

→ Reply

ismail

5 years ago, # ^ |

← Rev. 2 →

+23

You can share your code here:

CODE

import sys
 
def main():
  l, r = sys.stdin.readline().split()
  for i in range(int(l), int(r) + 1):
    s = str(i)
    a = set(s)
    if len(a) == len(s):
      print(i)
      exit()
  print(-1)
 
if __name__ == "__main__":
  main()

→ Reply

Nieb_Hasan_077

5 years ago, # ^ |

Thanks. Can you demonstrate how to attach a picture ?

→ Reply

techgig0

5 years ago, # |

← Rev. 2 →

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

→ Reply

j2v

5 years ago, # |

← Rev. 2 →

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?

→ Reply

j2v

5 years ago, # ^ |

← Rev. 3 →

+39

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)

→ Reply

5 years ago, # ^ |

Correct!

→ Reply

rsFalse

5 years ago, # |

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

→ Reply

not_found99

5 years ago, # |

Can anyone please explain problem B with code. Thanks.

→ Reply

rupav

5 years ago, # ^ |

← Rev. 2 →

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

-1: not visited
0: visited, and must be white/empty
1: visited, and must be black/filled.

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.net/contest/1228/submission/61514443

→ Reply

rsFalse

5 years ago, # ^ |

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.

→ Reply

DLN

5 years ago, # |

In problem C, what i am doing is calculating the maximum number of divisible elements from 1 to n for each power of factor where factor is the prime factor of x. However it is resulting in WA, here's my submission 61509357

→ Reply

moonpie24

5 years ago, # |

+13

Very nice round, problems was really good to solve and there was no bugs!

One of the interesting rounds I've ever solved.

Thank you McDic ^3^

→ Reply

timing

5 years ago, # |

← Rev. 2 →

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 .

→ Reply

5 years ago, # ^ |

I fixed. Thank you.

→ Reply

memento

5 years ago, # |

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 :(.

→ Reply

chowdhuryan1999

5 years ago, # |

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

→ Reply

kimoyami

5 years ago, # ^ |

← Rev. 3 →

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

→ Reply

chowdhuryan1999

5 years ago, # ^ |

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

→ Reply

Nizil

5 years ago, # |

You can do D in O(n+m) and without hashing because instead of step

"5. For all vertices u_1 and u_2 from different vertex sets, if there is no direct connection between u_1 and u_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.

→ Reply

Nieb_Hasan_077

5 years ago, # |

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

→ Reply

kush_76

5 years ago, # |

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

→ Reply

yeeeet

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

I will post soon, sorry.

→ Reply

5 years ago, # ^ |

I posted my solution codes. Thank you.

→ Reply

LittleBear1224

5 years ago, # |

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. :(

→ Reply

Errorist

5 years ago, # ^ |

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

→ Reply

Shrey97

5 years ago, # ^ |

← Rev. 2 →

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.

long long tmp=n;
ans=0;
while(tmp>=num[i])
{
    tmp/=num[i];
    ans+=tmp;
}

→ Reply

gautam_verma

5 years ago, # |

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",...

→ Reply

5 years ago, # |

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?

→ Reply

P___

5 years ago, # ^ |

← Rev. 2 →

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

→ Reply

5 years ago, # ^ |

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?

→ Reply

pedastrian57

5 years ago, # |

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

→ Reply

Nieb_Hasan_077

5 years ago, # |

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

→ Reply

phanlong2811

5 years ago, # |

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

My submission : 61607967

→ Reply

chenyanbo

5 years ago, # |

← Rev. 4 →

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.

→ Reply

apurva9

5 years ago, # |

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

→ Reply

universeofHk

5 years ago, # |

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.

→ Reply

universeofHk

5 years ago, # ^ |

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

→ Reply

Hd7

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

← Rev. 3 →

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

→ Reply

Hd7

5 years ago, # ^ |

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

→ Reply

5 years ago, # ^ |

← Rev. 3 →

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

→ Reply

Hd7

5 years ago, # ^ |

Thank you very much!

→ Reply

_greymatter

5 years ago, # |

← Rev. 3 →

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

→ Reply

5 years ago, # ^ |

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

→ Reply

_greymatter

5 years ago, # ^ |

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.

→ Reply

5 years ago, # ^ |

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

→ Reply

_greymatter

5 years ago, # ^ |

got it, thanks

→ Reply

Shameek

4 years ago, # ^ |

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?

→ Reply

4 years ago, # ^ |

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.

→ Reply

box

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

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

→ Reply

_NoobMaster__

5 years ago, # |

← Rev. 2 →

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

→ Reply

5 years ago, # ^ |

← Rev. 2 →

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

→ Reply

LegendaryNewbie_

5 years ago, # ^ |

← Rev. 3 →

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.

→ Reply

5 years ago, # ^ |

Sorry, I did not understand how that construct h(x,p) in the tutorial works, and all the formula.

→ Reply

Shameek

4 years ago, # |

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

→ Reply

_pastor_

4 years ago, # |

← Rev. 3 →

https://codeforces.net/contest/1228/submission/88625214 this is my AC solution for D
https://codeforces.net/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.

→ Reply