lucyanna2018's blog

Topcoder SRM 717
By lucyanna2018, history, 7 years ago, In English

SRM 717 will start in 4 hours,

Time: 7:00 am EDT Friday, June 30, 2017

Calendar: https://www.topcoder.com/community/events/

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

»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Starts in 15 minutes.

→ Reply
»
7 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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!

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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.
    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it -16 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +20 Vote: I do not like it

    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

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

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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        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

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

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

          → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +25 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +20 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 3   Vote: I like it +10 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +27 Vote: I do not like it

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

      → Reply
»
7 years ago, # |
← Rev. 7   Vote: I like it +84 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +15 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve Div2 Hard ???

→ Reply
»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    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

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +15 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +59 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        Are tests in practice room correct?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          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;
          → Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

_IsItRated_?

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

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

    → Reply
»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

can anyone explain div-1 easy??

→ Reply