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

Автор lucyanna2018, история, 7 лет назад, По-английски
  • Проголосовать: нравится
  • +111
  • Проголосовать: не нравится

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

Starts in 15 minutes.

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

Easy somehow reminded me an old problem from Distributed Code Jam.

Sorry for writing a stupid solution for Medium. I completely had no idea. It seems the intended solution is very nice and short.

There are two parts in Hard. I don't like the first part very much because it's actually "google the number of acyclic orientations". Still the second part is very nice!

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

    Medium:

    F(m) = n * F(m - 1) + (m - 1) * F(m - 2) + (m - 1) * F(m - 1)

    .

    1. $p_1$ equals one of values [m + 1, n + m]
    2. p1 equals i and pi equals 1 (2 ≤ i ≤ m).
    3. p1 equals i and pi ≠ 1. Now we can say that pi also have forbidden value 1.
    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

      if you can use some more words that would be really helpfull to understand

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

      can some one explain why so many downvotes on my comment of asking for some more explanation, may be you have understood it, but i didn't so i asked . this is really shameful to downvote someone's questions for clearnace

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

    I see the second part is too easy if have the formula.

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

What happened in Div 1 Easy? Everyone's solution failed? and what is the intended solution for Div 1 Medium?

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

    I'm wondering the same thing. I believe that only special tests have the property that any graph with those numbers of out edges has the same, invariant, answer. So, even though the tests were built accordingly, in hack phase, this property might not have been checked? I'm not sure, just trying to guess what happened. My solution, for example, at least in terms of concept, is 100% correct (it just finds a graph using max flow and then compute the answer through brute force), so it's the only explanation I could find...

    LE: I see that my source failed just one test with expected answer -1. The task assures us, however, that there is always a solution. Also, the test is among the last, so I guess it was added after being used as a hack

    LLE: Even though it appeared that the solution failed on test 172/171, I'm displayed on the practice room's rankings as one who solved it. Something really is strange, that's for sure

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

      Using max flow ,how to guarantee that there are no cycles of length 2

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

        I used the following network: a source, a destination, N(N-1)/2 nodes on the left side and N nodes on the right side. For each edge (i, j) we have a node in the left side that has two edges of capacity 1 to the i and j on the right side, and one edge of capacity 1 from the source. Also, from each node k with 1<=k<=N on the right side, we add an edge to the destination of capacity out[i]. Applying max flow on this network should generate a flow of N(N-1)/2 and for each edge (i, j) you basically chose which orientation it has (they are counted either for out[i] or for out[j]). The complexity is N^4 though (the flow is N^2 and one iteration is N^2 in worst case), but, as usually, it's much faster in practice

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

          Nice!!Any idea for a general case. Given in and out degrees ,find if graph exists with no cycles of length 2???

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

    UPD you are about to read some stupid comment :)

    Petr challenged my submission with 4,4,4,1,1,1 and I don't think it is the valid tournament graph, so that might be the problem

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

      why isn't this correct?
      it's just 2 cycles of length 3, the first one is connected to the second one (vertex by vertex K3,3), the first cycle would have 4 outgoing edges, and the second triangle would have 1
      Correct me if i'm wrong

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

      That test is ok. {5, 4, 4, 1, 1, 0}, however, is not. I checked it with my program and there is no graph generating those numbers of out edges

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

        Cool, I have tested your sample in TC arena, it says this is an invalid input.

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

        And intuitively, too, look at the nodes with out degree {0, 1, 1}. They should have exactly 3 edges between each other, but you only have 0 + 1 + 1 = 2.

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

      In general we can apply this theorem for the checker. No, it may add two edges a->b and b->a.

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

        Landau's Theorem gives a very simple characterization of valid score sequences. It is stated on the Wikipedia article about tournament graphs.

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

      When you start typing petr generated invalid test case it should auto correct to I dont understand petr's test case

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

Solution for Hard:

Google "Counting Acyclic Orientations" and find the theorem:

The number of Acyclic Orientations of an undirected graph is given by ( - 1)N·P( - 1), where P is the chromatic polynomial of the given graph.

Computing chromatic polynomials is hard in general, but mod 2 and 3 are especially easy:

  1. Realize the above expression mod 2 reduces to P(1), which is 1 when m = 0 and 0 otherwise.

  2. Realize the above expression mod 3 reduces to 2N·P(2), which is the number of 2-colorings of the graph. This is easy to compute, being 0 when the graph has at least one odd cycle and 2N·2C for bipartite graphs, where C is the number of connected components.

  3. Combine the 2 answers with the Chinese Remainder Theorem, or, even simpler:

for (int i = 0; i < 6; ++ i)
    if (i % 2 == ansMod2 && i % 3 == ansMod3)
        return i;

Petr mentioned he proceeded by induction in the TopCoder chat. I guess it would be extremely useful in the long run if he wouldn't mind sharing his solution here.

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

    Your solution is much better :) I've googled a paper with the theorem (https://www.math.ku.edu/~jmartin/courses/math796-S08/notes0222.pdf), but I didn't notice the beautiful trick of P(-1)=P(2) mod 3, so I've proceeded with using the proof of the theorem instead, more specifically statements A1-A3 in the proof of Theorem 2 there.

    First, let's assume we know that for non-bipartite graphs the answer is 0 mod 3, then let's learn to find the answer for bipartite graphs. Consider a bipartite graph. In case it has an (even) cycle, let's apply statement A3 to any edge in this cycle. Contracting this edge leads to a non-bipartite graph, so there we get 0 mod 3. So the answer mod 3 for the graph is the same as the answer mod 3 for the graph without this edge. Repeating this, we'll ultimately get a spanning forest of the original graph, and for it the answer is 2**num_edges mod 3=2**(n-num_components) mod 3.

    Now let's prove by induction that the answer for non-bipartite graphs is 0 mod 3. Suppose it's not true, consider the smallest counterexample. Since it's non-bipartite, it has an odd cycle. If it doesn't have anything else, then the answer for it is 2**n-2 which 0 mod 3 for odd n. If it does have some other edge, let's apply statement A3 to that edge. Both after removing this edge and after contracting this edge, the graph is still non-bipartite since it still has the odd cycle, so the answer is 0 mod 3 by induction hypothesis.

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

How to solve Div2 Hard ???

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

I can see how Div1 250 can be solved using maxflow (you might need to use one of faster maxflow algorithms though), but I can't see any easy solution. What am I missing? Does anyone know a simple solution?

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

    Take the node with the highest out-degree and link it with the smallest possible degrees. Also, link all other nodes to itself. Then, remove the node and repeat while necessary.

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

    There are easier ways to reconstruct a graph, using this lemma mentioned by Andrei1998. However, I've seen really interesting sources by good competitiors (so they have high probability of being correct) that simply played with the given array and did not actually reconstruct the answer. Also, another reason for which such solutions must exist is that the answer is the same regardless of the chosen graph, so it should be directly determined by the given array

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

    See the editorial of "johnny" (https://code.google.com/codejam/contest/8254486/dashboard#s=p3&a=3 ). You can compute strongly connected components only from the degree sequence.

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

Hello, I was writer of this round. In div-1 easy I made a bug in a validator; I wrote smth like if (s < i * (i - 1) / 2 instead of if (s < i * (i + 1) / 2), sorry for inconvenience.

I want to thank cgy4ever for his great help with this round, without him it would have much more bugs and weaker tests in div1-easy.

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

    Soo, what's going to happen? Will you just ignore the wrong hacks and rejudge all the submissions? Could you assess how much it'll take for you to do that? I just want to see my final position:))

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

      Admins are probably sleeping right now because round started at 4am in their time zone. So, it's better not to expect results in short notice.

      I see only few hacks in div-1 easy. I believe even fewer of them used exploit I made in the validator (this mistake allowed some invalid tests, but all valid tests are still valid). So, I hope round will be ranked, but decision is up to admins. A year ago in similar situation it was ranked.

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

        Are tests in practice room correct?

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

          There are still some invalid tests. You can skip them by pasting this code to top of your "count" function.

              if(s==vector<int>{1, 1, 1, 2, 5, 6, 6, 6} ||
                 s==vector<int>{5, 4, 4, 1, 1, 0}) return -1;
          
»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I wrote max-flow for div1 250, which obviously failed because of a->b->a cycles. I wanted that round to be unrated and thought that there would be some justice after unrated cf 421.

    However the round is rated and I'm such an idiot that despite getting 0 pts, my rating increased by 1 point to 1392...

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

can anyone explain div-1 easy??