Codeforces Round 728 (Div. 1)

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
1540 Codeforces Round 728 (Div. 1) FINISHED False 8100 107187899 June 25, 2021, 3:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 2653 ) B Tree Array PROGRAMMING brute force combinatorics dp math probabilities trees

B"You are given a tree consisting of n nodes. You generate an array from the tree by marking nodes one by one. Initially, when no nodes are marked, a node is equiprobably chosen and marked from the entire tree. After that, until all nodes are marked, a node is equiprobably chosen and marked from the set of unmarked nodes with at least one edge to a marked node. It can be shown that the process marks all nodes in the tree. The final array a is the list of the nodes' labels in order of the time each node was marked. Find the expected number of inversions in the array that is generated by the tree and the aforementioned process. The number of inversions in an array a is the number of pairs of indices (i, j) such that i < j and a_i > a_j . For example, the array [4, 1, 3, 2] contains 4 inversions: (1, 2) , (1, 3) , (1, 4) , (3, 4) . The first line contains a single integer n ( 2 <= n <= 200 ) -- the number of nodes in the tree. The next n - 1 lines each contains two integers x and y ( 1 <= x, y <= n ; x neq y ), denoting an edge between node x and y . It's guaranteed that the given edges form a tree. Output the expected number of inversions in the generated array modulo 10^9+7 . Formally, let M = 10^9+7 . It can be shown that the answer can be expressed as an irreducible fraction frac{p}{q} , where p and q are integers and q not equiv 0 pmod{M} . Output the integer equal to p cdot q^{-1} bmod M . In other words, output such an integer x that 0 <= x < M and x cdot q equiv p pmod{M} . This is the tree from the first sample: For the first sample, the arrays are almost fixed. If node 2 is chosen initially, then the only possible array is [2, 1, 3] ( 1 inversion). If node 3 is chosen initially, then the only possible array is [3, 1, 2] ( 2 inversio"...

Tutorials

Tutorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
120586224 Gassa B June 25, 2021, 4:45 p.m. OK D TESTS 14 405 0
120582018 gisp_zjz B June 25, 2021, 4:36 p.m. OK GNU C++11 TESTS 14 15 204800
120554880 Alice_foo_foo B June 25, 2021, 3:53 p.m. OK GNU C++11 TESTS 14 15 204800
120556140 Argentina B June 25, 2021, 3:54 p.m. OK GNU C++11 TESTS 14 31 204800
120594999 sunzihao B June 25, 2021, 5:06 p.m. OK GNU C++11 TESTS 14 31 204800
120568157 AC-Evil B June 25, 2021, 4:11 p.m. OK GNU C++11 TESTS 14 31 204800
120636487 dcmfqw B June 26, 2021, 5:13 a.m. OK GNU C++11 TESTS 15 31 204800
120627265 flyFeather B June 26, 2021, 1:46 a.m. OK GNU C++11 TESTS 15 31 307200
120583719 Violet_Evergarden B June 25, 2021, 4:40 p.m. OK GNU C++11 TESTS 14 31 716800
120557665 Isonan B June 25, 2021, 3:56 p.m. OK GNU C++11 TESTS 14 46 102400
120582291 BilyHurington B June 25, 2021, 4:37 p.m. OK GNU C++11 TESTS 14 46 204800
120573332 SlowDecay B June 25, 2021, 4:20 p.m. OK GNU C++14 TESTS 14 15 1024000
120578686 AlternatingCurrent B June 25, 2021, 4:30 p.m. OK GNU C++14 TESTS 14 31 512000
120564672 Marckess B June 25, 2021, 4:06 p.m. OK GNU C++14 TESTS 14 31 512000
120572809 Sohsoh84 B June 25, 2021, 4:19 p.m. OK GNU C++14 TESTS 14 31 512000
120594551 ComradePetr B June 25, 2021, 5:05 p.m. OK GNU C++14 TESTS 14 61 716800
120551958 T1duS B June 25, 2021, 3:49 p.m. OK GNU C++14 TESTS 14 61 716800
120578567 peehs_moorhsum B June 25, 2021, 4:29 p.m. OK GNU C++14 TESTS 14 62 512000
120574217 cscsc B June 25, 2021, 4:21 p.m. OK GNU C++14 TESTS 14 62 1536000
120552393 Radewoosh B June 25, 2021, 3:50 p.m. OK GNU C++14 TESTS 14 62 8499200
120550370 DmitryGrigorev B June 25, 2021, 3:48 p.m. OK GNU C++14 TESTS 14 77 307200
120569026 mshcherba B June 25, 2021, 4:13 p.m. OK GNU C++17 TESTS 14 15 307200
120567406 _Karuna B June 25, 2021, 4:10 p.m. OK GNU C++17 TESTS 14 15 1536000
120567856 egor_bb B June 25, 2021, 4:11 p.m. OK GNU C++17 TESTS 14 30 307200
120550352 xtqqwq B June 25, 2021, 3:48 p.m. OK GNU C++17 TESTS 14 31 307200
120571936 sd0061 B June 25, 2021, 4:18 p.m. OK GNU C++17 TESTS 14 31 307200
120562039 frokaikan B June 25, 2021, 4:02 p.m. OK GNU C++17 TESTS 14 31 307200
120562214 BigBag B June 25, 2021, 4:02 p.m. OK GNU C++17 TESTS 14 31 409600
120574203 TeaPot B June 25, 2021, 4:21 p.m. OK GNU C++17 TESTS 14 31 409600
120576341 sam.rei B June 25, 2021, 4:25 p.m. OK GNU C++17 TESTS 14 31 512000
120571274 wifiiii B June 25, 2021, 4:17 p.m. OK GNU C++17 TESTS 14 31 512000
120561118 jz_597 B June 25, 2021, 4:01 p.m. OK GNU C++17 (64) TESTS 14 15 409600
120558121 alya_wow B June 25, 2021, 3:57 p.m. OK GNU C++17 (64) TESTS 14 15 1126400
120564928 natsugiri B June 25, 2021, 4:06 p.m. OK GNU C++17 (64) TESTS 14 30 204800
120559106 aid B June 25, 2021, 3:58 p.m. OK GNU C++17 (64) TESTS 14 30 204800
120542169 tourist B June 25, 2021, 3:42 p.m. OK GNU C++17 (64) TESTS 14 30 409600
120624355 basic_string B June 25, 2021, 11:25 p.m. OK GNU C++17 (64) TESTS 15 30 409600
120559129 Xellos B June 25, 2021, 3:58 p.m. OK GNU C++17 (64) TESTS 14 30 819200
120587344 ecnerwala B June 25, 2021, 4:47 p.m. OK GNU C++17 (64) TESTS 14 31 204800
120618193 surgutti B June 25, 2021, 7:55 p.m. OK GNU C++17 (64) TESTS 15 31 204800
120611608 geckods B June 25, 2021, 6:22 p.m. OK GNU C++17 (64) TESTS 14 31 307200
120586994 Haskell_for_a_pint B June 25, 2021, 4:47 p.m. OK Haskell TESTS 14 124 1126400
120568783 cirno3153 B June 25, 2021, 4:12 p.m. OK Java 11 TESTS 14 218 0
120579320 Discombobulated B June 25, 2021, 4:31 p.m. OK Java 11 TESTS 14 327 512000
120613892 martins B June 25, 2021, 6:46 p.m. OK Java 11 TESTS 14 389 0
120613987 martins B June 25, 2021, 6:47 p.m. OK Java 11 TESTS 14 529 0
120565342 SecondThread B June 25, 2021, 4:07 p.m. OK Java 11 TESTS 14 670 0
120593550 ElragolEl3enab B June 25, 2021, 5:02 p.m. OK Java 8 TESTS 14 233 0
120575807 dalt B June 25, 2021, 4:24 p.m. OK Java 8 TESTS 14 234 0
120595100 pulkit1411 B June 25, 2021, 5:06 p.m. OK Java 8 TESTS 14 296 15769600
120611052 hu_tao B June 25, 2021, 6:17 p.m. OK Java 8 TESTS 14 608 0
120620078 2020akadaver B June 25, 2021, 8:38 p.m. OK Java 8 TESTS 15 1029 0
120611527 Tlatoani B June 25, 2021, 6:21 p.m. OK Kotlin TESTS 14 202 0
120595989 Hakiobo B June 25, 2021, 5:08 p.m. OK Kotlin TESTS 14 312 0
120614115 r57shell B June 25, 2021, 6:48 p.m. OK MS C++ TESTS 14 155 512000
120582808 Catmoonlight B June 25, 2021, 4:38 p.m. OK MS C++ 2017 TESTS 14 468 716800
120596454 azukun B June 25, 2021, 5:10 p.m. OK .NET Core C# TESTS 14 233 4505600
120605594 mban259 B June 25, 2021, 5:38 p.m. OK .NET Core C# TESTS 14 343 4403200
120597108 codicon B June 25, 2021, 5:11 p.m. OK PyPy 3 TESTS 14 280 5529600
120569657 Kiri8128 B June 25, 2021, 4:14 p.m. OK PyPy 3 TESTS 14 311 6656000
120580994 chinerist B June 25, 2021, 4:34 p.m. OK PyPy 3 TESTS 14 483 12288000
120588538 asdsasd B June 25, 2021, 4:50 p.m. OK PyPy 3 TESTS 14 670 9318400
120591549 SPD_9X2 B June 25, 2021, 4:57 p.m. OK PyPy 3 TESTS 14 795 19251200
120618533 titia B June 25, 2021, 8:02 p.m. OK PyPy 3 TESTS 15 1559 35430400
120561292 qwerty787788 B June 25, 2021, 4:01 p.m. OK Rust TESTS 14 46 1024000
120575493 nebocco B June 25, 2021, 4:24 p.m. OK Rust TESTS 14 109 819200
120600109 cottoncotton B June 25, 2021, 5:20 p.m. OK Rust TESTS 14 218 512000
120564271 sansen B June 25, 2021, 4:05 p.m. OK Rust TESTS 14 249 819200
120593761 toomer B June 25, 2021, 5:03 p.m. OK Rust TESTS 14 529 307200

remove filters

Back to search problems