Topcoder SRM 717 - Codeforces

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

Topcoder SRM 717

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

SRM 717 will start in 4 hours,

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

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

+111

lucyanna2018
7 лет назад
40

Комментарии (40)

Написать комментарий?

rhezo

7 лет назад, # |

+11

Starts in 15 minutes.

→ Ответить

rng_58

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!

→ Ответить

RomaWhite

7 лет назад, # ^ |

+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]
p₁ equals i and p_i equals 1 (2 ≤ i ≤ m).
p₁ equals i and p_i ≠ 1. Now we can say that p_i also have forbidden value 1.

→ Ответить

joker_in

7 лет назад, # ^ |

← Rev. 2 →

-16

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

→ Ответить

joker_in

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

→ Ответить

chemthan

7 лет назад, # ^ |

+10

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

→ Ответить

code_kika

7 лет назад, # |

+16

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

→ Ответить

geniucos

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

→ Ответить

teja349

7 лет назад, # ^ |

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

→ Ответить

geniucos

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

→ Ответить

teja349

7 лет назад, # ^ |

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

→ Ответить

spiderbatman

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

→ Ответить

Reyna

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

→ Ответить

spiderbatman

7 лет назад, # ^ |

+10

Yes, seems to me you are right

→ Ответить

geniucos

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

→ Ответить

sd0061

7 лет назад, # ^ |

+20

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

→ Ответить

Andrei1998

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.

→ Ответить

rng_58

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.

→ Ответить

Andrei1998

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.

→ Ответить

xyz.abc

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

→ Ответить

spiderbatman

7 лет назад, # ^ |

yeap I approve

→ Ответить

Andrei1998

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:

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

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.

→ Ответить

Petr

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.

→ Ответить

AshishYadav

7 лет назад, # |

How to solve Div2 Hard ???

→ Ответить

kazuma_desu

7 лет назад, # ^ |

Use inclusion-exclusion. The answer is:

$\text{[math]}$

→ Ответить

AshishYadav

7 лет назад, # ^ |

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

→ Ответить

kazuma_desu

7 лет назад, # ^ |

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

→ Ответить

Baklazan

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?

→ Ответить

Andrei1998

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.

→ Ответить

Baklazan

7 лет назад, # ^ |

Thank you, now I see.

→ Ответить

geniucos

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

→ Ответить

rng_58

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.

→ Ответить

Arterm

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.

→ Ответить

geniucos

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

→ Ответить

Arterm

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.

→ Ответить

HE_MATEMATIK

7 лет назад, # ^ |

+18

Are tests in practice room correct?

→ Ответить

nuip

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;

→ Ответить

dush1729

7 лет назад, # |

+11

_IsItRated_?

→ Ответить

P___

7 лет назад, # ^ |

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

→ Ответить