### lucyanna2018's blog

By lucyanna2018, history, 7 years ago,

SRM 717 will start in 4 hours,

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

• +111

 » 7 years ago, # |   +11 Starts in 15 minutes.
 » 7 years ago, # |   +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 years ago, # ^ |   +18 Medium: F(m) = n * F(m - 1) + (m - 1) * F(m - 2) + (m - 1) * F(m - 1). $p_1$ equals one of values [m + 1, n + m] p1 equals i and pi equals 1 (2 ≤ i ≤ m). p1 equals i and pi ≠ 1. Now we can say that pi also have forbidden value 1.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   -16 if you can use some more words that would be really helpfull to understand
•  » » » 7 years ago, # ^ |   -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 years ago, # ^ |   +10 I see the second part is too easy if have the formula.
 » 7 years ago, # |   +16 What happened in Div 1 Easy? Everyone's solution failed? and what is the intended solution for Div 1 Medium?
•  » » 7 years ago, # ^ | ← 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 hackLLE: 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 years ago, # ^ |   0 Using max flow ,how to guarantee that there are no cycles of length 2
•  » » » » 7 years ago, # ^ |   +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 years ago, # ^ |   0 Nice!!Any idea for a general case. Given in and out degrees ,find if graph exists with no cycles of length 2???
•  » » 7 years ago, # ^ | ← 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 years ago, # ^ | ← 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 years ago, # ^ |   +10 Yes, seems to me you are right
•  » » » 7 years ago, # ^ |   +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 years ago, # ^ |   +20 Cool, I have tested your sample in TC arena, it says this is an invalid input.
•  » » » » 7 years ago, # ^ |   +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 years ago, # ^ | ← 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 years ago, # ^ | ← 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 years ago, # ^ | ← 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 years ago, # ^ |   0 yeap I approve
 » 7 years ago, # | ← 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: Realize the above expression mod 2 reduces to P(1), which is 1 when m = 0 and 0 otherwise. 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. 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 years ago, # |   +5 How to solve Div2 Hard ???
•  » » 7 years ago, # ^ |   +5 Use inclusion-exclusion. The answer is:
•  » » » 7 years ago, # ^ |   +5 Sorry,But how did you arrive at it ??? I know it had some connections with derangements but could not come with formula during contest :(
•  » » » » 7 years ago, # ^ |   0 Its similar to how you use inclusion exclusion to find the formula when n = 0. Maybe this can help:https://math.stackexchange.com/questions/929005/derivation-of-derangement-with-inclusion-exclusion
 » 7 years ago, # |   +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 years ago, # ^ | ← 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 years ago, # ^ |   +5 Thank you, now I see.
•  » » 7 years ago, # ^ | ← 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 years ago, # ^ | ← 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 years ago, # |   +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 years ago, # ^ |   +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 years ago, # ^ |   +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 years ago, # ^ |   +18 Are tests in practice room correct?
•  » » » » » 7 years ago, # ^ |   +10 There are still some invalid tests. You can skip them by pasting this code to top of your "count" function.  if(s==vector{1, 1, 1, 2, 5, 6, 6, 6} || s==vector{5, 4, 4, 1, 1, 0}) return -1; 
 » 7 years ago, # |   +11
•  » » 7 years ago, # ^ |   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 years ago, # |   -8 can anyone explain div-1 easy??