Semifinal 1 is live at https://go.twitch.tv/topcoder_official.

Good luck to all. Special good luck for scott_wu, who just won $10,000 from another contest 9 hours before (for reference it is OpenBracket, but that's off topic for now)

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

1 | Um_nik | 3538 |

2 | tourist | 3509 |

3 | Benq | 3473 |

4 | ecnerwala | 3446 |

5 | ksun48 | 3432 |

6 | maroonrk | 3404 |

7 | Radewoosh | 3383 |

8 | yosupo | 3324 |

9 | boboniu | 3300 |

10 | apiadu | 3238 |

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

1 | Errichto | 207 |

2 | Monogon | 199 |

3 | SecondThread | 194 |

4 | vovuh | 189 |

5 | Um_nik | 186 |

5 | antontrygubO_o | 186 |

7 | pikmike | 184 |

8 | Ashishgup | 182 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

Semifinal 1 is live at https://go.twitch.tv/topcoder_official.

Good luck to all. Special good luck for scott_wu, who just won $10,000 from another contest 9 hours before (for reference it is OpenBracket, but that's off topic for now)

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/25/2020 16:26:54 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

How to solve 500?

We'll count the number of ways to choose directions so that the resulting graph would NOT be strong-connected. Main idea: graph is not strong-connected if and only if it has at least one strong-connected subcomponent such that it is a leaf in DAG of components.

Let's call dp[mask] number of ways to choose directions of edges with both ends in mask so that it is not strong-connected.

The answer is 2^m — dp[2^n — 1].

How to count: Let's look at the first vertex in mask. Let's choose it's strong-subcomponent (now it's O(3^n)). Call this subcomponent M1; M2 := mask ^ M1. We suggest that M2 != 0. M1 is either leaf or not. 1) M1 is a leaf. Then we now the direction of all edges between M1 and M2. We need to add 2^{number of edges strictly inside M2} * (2^{number of edges strictly inside M1} — dp[M1]). 2) M1 is not a leaf but M2 is a component and it is a leaf. Add (2^{number of edges strictly inside M2} — dp[M2]) * (2^{number of edges strictly inside M1} — dp[M1]). 3) M1 is not a leaf and so M2 has subcomponent that is a leaf (or the same: M2 is not strong-connected). Add (2^{number of edges between M1 and M2} — 2) * dp[M2] * (2^{number of edges strictly inside M1} — dp[M1]).

In 3), how to make sure that M1 is a strong-subcomponent?

For example, consider the case where M1 = {0, 1}, M2 = {2, 3}, and the edges are 0 - > 1, 1 - > 0, 2 - > 3, 0 - > 2, 3 - > 1.

Here's my solution.

Let dp[mask] be the number of ways to orient the edges to make each connected component in mask strongly connected. Then answer is dp[2^n-1] (if there is more than one connected component, the answer is zero).

Let's do this by complimentary counting. First, dp[mask] = 2^(edges in mask). We subtract any bad arrangement. For each bad arrangement, we can identify it with the subset of nodes that are in some source strongly connected component (i.e. strongly connected component with indegree 0).

Ideally, we would like to do something like dp[mask] -= dp[submask] * 2^(edges in submask^mask), and then we are done.

What's the problem with this? Well, some bad arrangements are subtracted multiple times. In particular, let's say submask has C connected components. Then, it's actually subtracted 2^C-1 different times right now.

We can fix this by adding a (-1)^(C) term in our subtraction. You can check that -(C choose 1) + (C choose 2) — (C choose 3) + ... (C choose C) = -1, so each bad arrangment is only subtracted exactly once.

The implementation of this is pretty short. After setting everything up, the main dp can be computed in just a couple of lines. Here's an example implementation:

solutionany where we can find the contest scoreboard?

Found it here.

Me and Petr are planning to do kind of live stream here

Anyone who knows how to solve 1000?

I solved it in the practice room in the following way.