SRM 717 will start in 4 hours,

By Shayan

Before stream
03:08:39

# | User | Rating |
---|---|---|

1 | tourist | 3690 |

2 | jiangly | 3647 |

3 | Benq | 3581 |

4 | orzdevinwang | 3570 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | Radewoosh | 3509 |

8 | ecnerwala | 3486 |

9 | jqdai0815 | 3474 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | awoo | 164 |

3 | adamant | 163 |

4 | TheScrasse | 159 |

5 | nor | 157 |

6 | maroonrk | 155 |

7 | -is-this-fft- | 152 |

8 | Petr | 146 |

8 | orz | 146 |

10 | BledDest | 145 |

SRM 717 will start in 4 hours,

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/18/2024 15:51:21 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Starts in 15 minutes.

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!

Medium:

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

m+ 1,n+m]p_{1}equalsiandp_{i}equals 1 (2 ≤i≤m).p_{1}equalsiandp_{i}≠ 1. Now we can say thatp_{i}also have forbidden value 1.if you can use some

morewords that would be really helpfull to understandcan 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

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

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

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

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

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

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

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

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

Yes, seems to me you are right

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

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

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.

~~In general we can apply this theorem for the checker.~~No, it may add two edges a->b and b->a.Landau's Theorem gives a very simple characterization of valid score sequences. It is stated on the Wikipedia article about tournament graphs.

When you start typing

`petr generated invalid test case`

it should auto correct to`I dont understand petr's test case`

yeap I approve

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), wherePis 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 whenm= 0 and 0 otherwise.Realize the above expression mod 3 reduces to 2

^{N}·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 2^{N}·2^{C}for bipartite graphs, where C is the number of connected components.Combine the 2 answers with the Chinese Remainder Theorem, or, even simpler:

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.

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.

How to solve Div2 Hard ???

Use inclusion-exclusion. The answer is:

Sorry,But how did you arrive at it ??? I know it had some connections with derangements but could not come with formula during contest :(

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

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?

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.

Thank you, now I see.

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

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.

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.

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

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.

Are tests in practice room correct?

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

_IsItRated_?

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

can anyone explain div-1 easy??