### McDic's blog

By McDic, history, 6 months ago, , Hello, I hope all of you enjoyed my contest!

[Behind story of A]

[Behind story of B]

[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

[Behind story of D]

[Behind story of E]

[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. Tutorial of Codeforces Round #589 (Div. 2)  Comments (177)
 » 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.
•  » » 6 months ago, # ^ | ← Rev. 2 →   .
 » D can be easily solved by hashing
•  » » can you explain it pls
•  » » » 6 months ago, # ^ | ← Rev. 3 →   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
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   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
•  » » » » »
•  » » » » » » can u explain how B works?
•  » » » » » 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
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   @Bhatt21, Your solution 61496628 is giving wrong answer for the test case:3 11 2which 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
•  » » Alternatively a deterministic bitset solution, which I used during the contest.
 » 6 months ago, # | ← Rev. 2 →   Very fast editorial, really appreciate it! But is there a proof for the solution of D?
•  » » 6 months 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
 » 61508959I'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
 » 6 months ago, # | ← Rev. 2 →   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.
•  » » 6 months 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. :|
•  » » » 6 months 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 pPlease 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 exponentEach multiple of p^2 adds 2 to the exponentHowever, 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/pSimilarly 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 •  » » » » in 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. •  » » » » » 6 months 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. •  » » » » » » 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). •  » » » » 6 months 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. •  » » » » 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! :DOf 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.  » 6 months 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 allAfter applying r_i's I've got 1 1 0 x 0 x x x 1 1 1 0 1 0 x x I can't understand how to apply c4 because according to the problem statement in third row I have 1 1 1 0 1 1 0 1 0 1 x 1 1 1 1 ? 1 0 x 0 And why right answer is 0 if we have 2 unreserved cells, its M and M? •  » » 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. •  » » » Thanks. I thought there is always a correct grid. •  » » » you're right the problem setter didn't mentioned it I was confused so I assumed it to be always correct and was getting WA at pre 4 then finally figured it out really interesting problem btw it should be grid (3, 4) which is conflicting.  » 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 \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_oincompleted 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. elManco can you explain? •  » » » » » polyakoff 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. •  » » » » » » 6 months ago, # ^ | ← Rev. 6 → Not exactly,f(1,3)1,1,2,2,21,2,1,2,21,2,2,1,21,2,2,2,12,1,1,2,2...2,2,2,1,1It is clearly much more than 4. •  » » » » » » » 6 months ago, # ^ | ← Rev. 2 → I mean there are also ways to put three ones between •  » » » » » » » » 6 months 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? •  » » » » » » » » » 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 rth 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 way1 | 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 way1 | 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.
•  » » 6 months ago, # ^ | ← Rev. 2 →   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 ?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   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: 61549764Noted 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.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
 » 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.
•  » » » 6 months 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
•  » » » » Similar problem : https://www.codechef.com/SEPT19A/problems/DOOFST
 » Where is the solution code for the One Node is Gone problem?
•  » » 6 months ago, # ^ | ← Rev. 2 →   I am sorry. I will add it later.
 » In the solution of ENow 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!
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   My code std::vector 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] = 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[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; } } 
•  » » » » » 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.
•  » » » Thanks for clarification.
•  » » I just forget it, total combination is = 2^n, What's a silly mistake I have done :|
 » 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)
 » #include 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> C(MAX, vector (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 x(MAX), y(MAX); x = y = 1; for (int i = 1; i < MAX; i++) { x[i] = mul(k, x[i - 1]); y[i] = mul(k - 1, y[i - 1]); } vector> dp(n + 1, vector (n + 1)); int val = sub(x[n], y[n]); for (int r = 1; r <= n; r++) { dp[r] = expo(val, r); } for (int c = 1; c <= n; c++) { dp[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?
•  » » 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: •  » » » » 6 months ago, # ^ | ← Rev. 2 →   You can share your code here: CODEimport 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() •  » » » » » Thanks. Can you demonstrate how to attach a picture ?
•  » » » » » » Sure, I'll try.
 » 6 months ago, # | ← Rev. 2 →   In problem D I missed 1 line and related it to 3-coloring problem. How stupid of me!
 » 6 months 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?
•  » » 6 months ago, # ^ | ← Rev. 3 →   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.
•  » » 6 months 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.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/filledMake 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.
•  » » Here is an editorial: 1228B — Filling the Grid — Editorial (Unofficial :: Explained), you may check out it for clear away confusion about your logic.
 » 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
 » 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^
 » 6 months 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 .
•  » » 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..
•  » » 6 months ago, # ^ | ← Rev. 3 →   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_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.
 » 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.
 » Anyone help me solution B pls.I solved 3 first test of problems.Wrong test 4. I have no idea what i was wrong?Here is my code: https://ideone.com/jotIxv (so long).
• »
»

Reference: 1228B — Filling the Grid — Editorial (Unofficial :: Explained), you may check out it: .

Logical Explanation:
Solution / Code:
 » 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.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   lakshayv1In 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; } 
 » 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",...
•  » » That is common sense bro. The number of ways can be 0 obviously and we were supposed to find when. Your "how the hell, m i supposed to know that" doesn't make sense.
 » 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?
•  » » 6 months ago, # ^ | ← Rev. 2 →   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 0For 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
 » I'm trying to do pro C but i'm fail.Can you help me ?this is my code :https://ideone.com/JmKVN5So sorry for my poor english , i can't explain my code by english ...
 » In the name of me, Hope you my children had a good contest, Top 10 winners get free lmg, Like always dont forget to recruit rush, See you later, Peace
 » 6 months ago, # | ← Rev. 2 →   can anyone explain why is my code giving WA for D link
 » 6 months 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.
 » 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)?
•  » » 6 months ago, # ^ | ← Rev. 3 →   Try to describe $n!$ in products of $p$-ary digit numbers.
•  » » » Sorry, what does $p$-ary mean?
•  » » » » 6 months 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!$.
•  » » » » » Thank you very much!
 » How does one prove the solution in problem D is correct?
 » 6 months 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) ?
•  » » You choose vertices(without thinking invalid edges) at first, vertex sets validation is the seond step.I used std::vector> 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
 » Wow, E literally appeared (with a higher N) in the Asia Nanjing Regional ICPC.
•  » » Do they intended $O(n \log n)$ ?