Dasha Code Championship - SPb Finals Round (only for onsite-finalists)

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
1210 Dasha Code Championship - SPb Finals Round (only for onsite-finalists) FINISHED False 9000 168296087 Sept. 22, 2019, 9:05 a.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 217 ) F1 Marek and Matching (easy version) PROGRAMMING brute force probabilities 2900

B"This is an easier version of the problem. In this version, n <= 6 . Marek is working hard on creating strong testcases to his new algorithmic problem. You want to know what it is? Nah, we're not telling you. However, we can tell you how he generates the testcases. Marek chooses an integer n and n^2 integers p_{ij} ( 1 <= i <= n , 1 <= j <= n ). He then generates a random bipartite graph with 2n vertices. There are n vertices on the left side: ell_1, ell_2, ... , ell_n , and n vertices on the right side: r_1, r_2, ... , r_n . For each i and j , he puts an edge between vertices ell_i and r_j with probability p_{ij} percent. It turns out that the tests will be strong only if a perfect matching exists in the generated graph. What is the probability that this will occur? It can be shown that this value can be represented as frac{P}{Q} where P and Q are coprime integers and Q not equiv 0 pmod{10^9+7} . Let Q^{-1} be an integer for which Q cdot Q^{-1} equiv 1 pmod{10^9+7} . Print the value of P cdot Q^{-1} modulo 10^9+7 . The first line of the input contains a single integer n ( mathbf{1 <= n <= 6} ). The following n lines describe the probabilities of each edge appearing in the graph. The i -th of the lines contains n integers p_{i1}, p_{i2}, ... , p_{in} ( 0 <= p_{ij} <= 100 ); p_{ij} denotes the probability, in percent, of an edge appearing between ell_i and r_j . Print a single integer -- the probability that the perfect matching exists in the bipartite graph, written as P cdot Q^{-1} pmod{10^9+7} for P , Q defined above. In the first sample test, each of the 16 graphs below is equally probable. Out of these, 7 have a perfect matching: Therefore, the probability is equal to frac{7}{16} . As 16 cdot 562 ,500 ,"...

Tutorials

Dasha Code Championship Finals and Mirror Round 588 Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
62622315 LODB---D F1 Oct. 15, 2019, 1:10 p.m. OK GNU C++14 TESTS 28 156 29593600 2900
62622169 LODB---D F1 Oct. 15, 2019, 1:08 p.m. OK GNU C++14 TESTS 28 296 29593600 2900
61065657 vintage_Vlad_Makeev F1 Sept. 22, 2019, 10:59 a.m. OK GNU C++17 TESTS 28 139 614400 2900
61065705 aid F1 Sept. 22, 2019, 11 a.m. OK GNU C++17 TESTS 28 295 8396800 2900
62063671 Super_M. F1 Oct. 7, 2019, 2:28 p.m. OK GNU C++17 TESTS 28 608 30003200 2900
65700000 I_love_chickpea F1 Nov. 25, 2019, 10:18 a.m. OK GNU C++17 TESTS 28 6177 14336000 2900
61065648 VArtem F1 Sept. 22, 2019, 10:59 a.m. OK Java 8 TESTS 28 265 0 2900

remove filters

Back to search problems