McDic's blog

By McDic, history, 2 weeks ago, In English,

Hello, I hope all of you enjoyed my contest!

Tutorial is loading...

[Behind story of A]

Tutorial is loading...

[Behind story of B]

Tutorial is loading...

[Behind story of C]

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

[Behind story of D]

Tutorial is loading...

[Behind story of E]

Tutorial is loading...

[Behind story of F]

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

[Behind story of G (removed problem)]

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

Thanks in advance!

 
 
 
 
  • Vote: I like it
  • +338
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it +75 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +139 Vote: I do not like it

Fast editorial, Fast system testing, Balanced Problemset, Nice Problems.
This is really one of the finest round of Codeforces.

»
2 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

D can be easily solved by hashing

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    can you explain it pls

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 3   Vote: I like it +12 Vote: I do not like it

      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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        thx

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        @Bhatt21, Your solution 61496628 is giving wrong answer for the test case:
        3 1
        1 2
        which is given in the test set of the problem D as test case 48, I guess added after the contest but still, the status of the solution is shown accepted. Don't understand why.

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

61508959

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    how to solve G ? O_o

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        isn't it?

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        11 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you explain how you came up with this approach.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you define once again, what is incomplete column?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
          Rev. 2   Vote: I like it +6 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            13 days ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            I'm confused at the same point.

          • »
            »
            »
            »
            »
            »
            13 days ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              12 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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?

            • »
              »
              »
              »
              »
              »
              »
              12 days ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              Andimeo can you give an example ?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          @devACE Kindly redefine f(r,c) ?

          • »
            »
            »
            »
            »
            »
            13 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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!

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please explain how it works.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you can see my submission here 61498103

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -27 Vote: I do not like it

      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.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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.

»
2 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. I thought there is always a correct grid.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
2 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    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.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            13 days ago, # ^ |
            Rev. 6   Vote: I like it +6 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              13 days ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              I mean there are also ways to put three ones between

              • »
                »
                »
                »
                »
                »
                »
                »
                13 days ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                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?

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        12 days ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

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

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

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

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

        $$$1 | 2 | 2$$$

        $$$. | . | .$$$

        $$$. | . | .$$$

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

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

        $$$1 | 2 | 2$$$

        $$$1 | 2 | 2$$$

        $$$. | . | .$$$

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

        • »
          »
          »
          »
          »
          12 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

      • »
        »
        »
        »
        13 days ago, # ^ |
        Rev. 2   Vote: I like it +26 Vote: I do not like it

        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.

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

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Nice explanation. Thank you very much.

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            13 days ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like 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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 4   Vote: I like it +4 Vote: I do not like it

      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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

In the solution of E

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

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

      • »
        »
        »
        »
        2 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        My code
        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            I fixed, thank you.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

didn't understood explanation of B.please help

»
2 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I just forget it, total combination is = 2^n, What's a silly mistake I have done :|

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
2 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it
#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?

»
2 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it +39 Vote: I do not like it

    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)

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain problem B with code. Thanks.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Here is an editorial: 1228B — Filling the Grid — Editorial (Unofficial :: Explained), you may check out it for clear away confusion about your logic.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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^

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 .

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    Logical Explanation:
    Solution / Code:
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      lakshayv1

      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;
      }
      
»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like 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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

My submission : 61607967

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm trying to do pro C but i'm fail.

Can you help me ?

this is my code :https://ideone.com/JmKVN5

So sorry for my poor english , i can't explain my code by english ...

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone explain why is my code giving WA for D link

»
11 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 days ago, # ^ |
        Rev. 3   Vote: I like it +1 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you very much!

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How does one prove the solution in problem D is correct?

»
8 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like 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.