Codeforces Global Round 7

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
1326 Codeforces Global Round 7 FINISHED False 9000 152724311 March 19, 2020, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 86 ) G Spiderweb Trees PROGRAMMING dp geometry trees 3600

B"Let's call a graph with n vertices, each of which has it's own point A_i = (x_i, y_i) with integer coordinates, a planar tree if: Imagine a planar tree with n vertices. Consider the convex hull of points A_1, A_2, ldots, A_n . Let's call this tree a spiderweb tree if for all 1 <= q i <= q n the following statements are true: An example of a spiderweb tree: The points A_3, A_6, A_7, A_4 lie on the convex hull and the leaf vertices of the tree are 3, 6, 7, 4 . Refer to the notes for more examples. Let's call the subset S subset {1, 2, ldots, n } of vertices a subtree of the tree if for all pairs of vertices in S , there exists a path that contains only vertices from S . Note that any subtree of the planar tree is a planar tree. You are given a planar tree with n vertexes. Let's call a partition of the set {1, 2, ldots, n } into non-empty subsets A_1, A_2, ldots, A_k (i.e. A_i cap A_j = emptyset for all 1 <= q i < j <= q k and A_1 cup A_2 cup ldots cup A_k = {1, 2, ldots, n } ) good if for all 1 <= q i <= q k , the subtree A_i is a spiderweb tree. Two partitions are different if there exists some set that lies in one parition, but not the other. Find the number of good partitions. Since this number can be very large, find it modulo 998 ,244 ,353 . The first line contains an integer n ( 1 <= q n <= q 100 ) -- the number of vertices in the tree. The next n lines each contain two integers x_i, y_i ( -10^9 <= q x_i, y_i <= q 10^9 ) -- the coordinates of i -th vertex, A_i . The next n-1 lines contain two integers s, f ( 1 <= q s, f <= q n ) -- the edges (s, f) of the tree. It is guaranteed that all given points are different and that no three of them lie at the same line. Additionally, it is guaranteed that the given edges and coordinates of the points describe a planar tree. Pri"...

Tutorials

74961

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
73771365 TakeMe2Letovo G March 20, 2020, 7:46 a.m. OK GNU C++17 TESTS 115 46 2560000 3600
73746414 WrongAnswerOnTest1 G March 19, 2020, 10:31 p.m. OK GNU C++17 TESTS 115 46 2560000 3600
73746367 dontorzme G March 19, 2020, 10:30 p.m. OK GNU C++17 TESTS 115 46 2560000 3600
73746475 Benq G March 19, 2020, 10:33 p.m. OK GNU C++17 TESTS 115 748 921600 3600

remove filters

Back to search problems