Блог пользователя McDic

Автор McDic, история, 4 года назад, По-английски

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!

Разбор задач Codeforces Round 589 (Div. 2)
  • Проголосовать: нравится
  • +338
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +75 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +139 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

D can be easily solved by hashing

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    can you explain it pls

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        thx

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          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.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    nvm thats to ensure its complete

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

61508959

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    how to solve G ? O_o

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Thanks.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        isn't it?

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            EDIT: Got it now

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

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Can you explain how you came up with this approach.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    It's correct actually.

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

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

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you define once again, what is incomplete column?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            I'm confused at the same point.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        I think I get your idea now.

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

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Please explain how it works.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      you can see my submission here 61498103

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -27 Проголосовать: не нравится

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

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

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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.

    • »
      »
      »
      11 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        11 месяцев назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +51 Проголосовать: не нравится

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

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

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

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

    The second term

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

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

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

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

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

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

          Hope it helped.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 6   Проголосовать: нравится +6 Проголосовать: не нравится

            Not exactly,

            f(1,3)

            1,1,2,2,2

            1,2,1,2,2

            1,2,2,1,2

            1,2,2,2,1

            2,1,1,2,2

            ...

            2,2,2,1,1

            It is clearly much more than 4.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              I mean there are also ways to put three ones between

              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                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?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

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

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

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

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

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

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

        Noted that

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

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

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

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

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Nice explanation. Thank you very much.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          awesome explanation! loved it, thanks a lot

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 4   Проголосовать: нравится +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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

In the solution of E

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

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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!

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        My code
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In 1228B - Заполнение таблицы, 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??

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
4 года назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится
#include <bits/stdc++.h>
using namespace std;

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

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

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

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

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

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

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

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

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

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +39 Проголосовать: не нравится

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

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

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please explain problem B with code. Thanks.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

One of the interesting rounds I've ever solved.

Thank you McDic ^3^

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 .

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Errorist

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

      long long tmp=n;
      ans=0;
      while(tmp>=num[i])
      {
          tmp/=num[i];
          ans+=tmp;
      }
      
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

My submission : 61607967

»
4 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

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

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

    77173595

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      spookywooky why we will calculate the frequency of each prime divisor in n!.I actually understood mathematical expression written in the editorial until the line before the last.Line before the last says that we have to calculate the sum of all h(i, p), means maximum power of p which divides i as h(x, p) is defined as the maximum power of p which divides x, isn't it? So using the formula h(x,p)+h(y,p)=h(xy,p) we reached to the next line as h(n!, p). My main confusion is in this point. Doesn't h(n!, p) mean that maximum power of p which divides factorial n? If that then shouldn't we calculate how many numbers between [1, n] which only contains p^0, then p^1 then p^2........so on upto the maximum power.Why we are calculating the frequency of prime p in n!, shouldn't we go part by part? As the number which contains p ^ 2 (say) then it only contain p ^ 2, that is the maximum power of p that can divide it is 2 (p ^ 2). But we have already calculated the frequency of p ^ 1 and some of the numbers which contain p ^ 2 or p ^ 3 will also be considered as the numbers contains p ^ 1 when we are calculating p ^ 1.I want to say that if p ^ 1 comes than it should comes from those numbers which only contain p ^ 1, not from p ^ 2 or p ^ 3 or any other and those particular number will be divisible by maximum power of p is 1.I'm totally messed up, please help.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

my AC code

my solution for D

i just tried coloring the graph

let parent color = 1, cur node color = 2

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

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

just like bipartite graph + ensuring all the edges exist

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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