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

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

61508959

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

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

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.

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

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

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!

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.

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

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[2][3] and M[4][3]?

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

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.

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

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://mirror.codeforces.com/contest/1228/submission/61516757

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

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

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.

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

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?

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.

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^

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 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://mirror.codeforces.com/contest/1228/submission/61536068 i am geting wrong on testcase 6...help me to know which cases i am missing..

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

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?

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.

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