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 |
---|---|---|---|---|---|---|
1033 | Lyft Level 5 Challenge 2018 - Elimination Round | FINISHED | False | 7200 | 198593724 | Oct. 7, 2018, 5:05 p.m. |
Solved$ |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
---|---|---|---|---|---|---|
( 666 ) | E | Hidden Bipartite Graph | PROGRAMMING | binary search constructive algorithms dfs and similar graphs interactive | 2700 |
B'Bob has a simple undirected connected graph (without self-loops and multiple edges). He wants to learn whether his graph is bipartite (that is, you can paint all vertices of the graph into two colors so that there is no edge connecting two vertices of the same color) or not. As he is not very good at programming, he asked Alice for help. He does not want to disclose his graph to Alice, but he agreed that Alice can ask him some questions about the graph. The only question that Alice can ask is the following: she sends s -- a subset of vertices of the original graph. Bob answers with the number of edges that have both endpoints in s . Since he doesn 't want Alice to learn too much about the graph, he allows her to ask no more than 20000 questions. Furthermore, he suspects that Alice might introduce false messages to their communication channel, so when Alice finally tells him whether the graph is bipartite or not, she also needs to provide a proof -- either the partitions themselves or a cycle of odd length. Your task is to help Alice to construct the queries, find whether the graph is bipartite. The first line contains a single integer n ( 1 <= q n <= q 600 ) -- the number of vertices in Bob 's graph. First, read an integer n ( 1 <= q n <= q 600 ) -- the number of vertices in Bob 's graph. To make a query, print two lines. First of which should be in the format "? k" ( 1 <= q k <= q n ), where k is the size of the set to be queried. The second line should contain k space separated distinct integers s_1, s_2, ... , s_k ( 1 <= q s_i <= q n ) -- the vertices of the queried set. After each query read a single integer m ( 0 <= q m <= q frac{n(n-1)}{2} ) -- the number of edges between the vertices of the set {s_i } . You are not allowed to ask more than 20000 queries. If m = -1 , it means that you asked more queries than allowed, or asked an invalid query. Your pro'... |
The Lyft Level 5 Challenge 2018 Elimination Round (Div. 1 + Div. 2) Editorial |
Submission Id |
Author(s) |
Index |
Submitted |
Verdict |
Language |
Test Set |
Tests Passed |
Time taken (ms) |
Memory Consumed (bytes) |
Tags |
Rating |
---|---|---|---|---|---|---|---|---|---|---|---|
43988391 | emoairx | E | Oct. 8, 2018, 8:44 a.m. | OK | GNU C++11 | TESTS | 48 | 140 | 307200 | 2700 | |
44751715 | ReaLNero1 | E | Oct. 23, 2018, 8:19 p.m. | OK | GNU C++11 | TESTS | 48 | 155 | 102400 | 2700 | |
47437801 | alex_Harry | E | Dec. 23, 2018, 8:25 p.m. | OK | GNU C++11 | TESTS | 48 | 156 | 0 | 2700 | |
43989295 | emoairx | E | Oct. 8, 2018, 9:14 a.m. | OK | GNU C++11 | TESTS | 48 | 187 | 2355200 | 2700 | |
54367832 | mmmod_lqs | E | May 19, 2019, 4:34 a.m. | OK | GNU C++11 | TESTS | 48 | 233 | 102400 | 2700 | |
44255392 | S.A.O_3 | E | Oct. 13, 2018, 12:09 p.m. | OK | GNU C++11 | TESTS | 48 | 233 | 1331200 | 2700 | |
57868717 | lopare | E | July 27, 2019, 11:35 p.m. | OK | GNU C++11 | TESTS | 48 | 234 | 1331200 | 2700 | |
44017969 | ditoly | E | Oct. 9, 2018, 12:04 a.m. | OK | GNU C++11 | TESTS | 48 | 248 | 1331200 | 2700 | |
46452683 | Um_nik | E | Dec. 1, 2018, 4:19 p.m. | OK | GNU C++11 | TESTS | 48 | 248 | 1536000 | 2700 | |
58909360 | _twilight | E | Aug. 16, 2019, 12:27 p.m. | OK | GNU C++11 | TESTS | 48 | 249 | 409600 | 2700 | |
43993620 | Motarack | E | Oct. 8, 2018, 10:22 a.m. | OK | GNU C++14 | TESTS | 48 | 124 | 307200 | 2700 | |
43971485 | Atreus | E | Oct. 7, 2018, 7:03 p.m. | OK | GNU C++14 | TESTS | 48 | 171 | 204800 | 2700 | |
43969316 | mjhun | E | Oct. 7, 2018, 6:45 p.m. | OK | GNU C++14 | TESTS | 48 | 186 | 1228800 | 2700 | |
43973063 | zeliboba | E | Oct. 7, 2018, 8:02 p.m. | OK | GNU C++14 | TESTS | 48 | 186 | 1740800 | 2700 | |
44094129 | mgoncharov | E | Oct. 10, 2018, 9:44 p.m. | OK | GNU C++14 | TESTS | 48 | 217 | 204800 | 2700 | |
59541804 | little_misfortune | E | Aug. 26, 2019, 7:17 p.m. | OK | GNU C++14 | TESTS | 48 | 218 | 204800 | 2700 | |
43976931 | xiaowuc1 | E | Oct. 7, 2018, 9:48 p.m. | OK | GNU C++14 | TESTS | 48 | 218 | 204800 | 2700 | |
43967501 | xiaowuc1 | E | Oct. 7, 2018, 6:29 p.m. | OK | GNU C++14 | TESTS | 48 | 218 | 204800 | 2700 | |
43980198 | iloveUtaha | E | Oct. 8, 2018, 2 a.m. | OK | GNU C++14 | TESTS | 48 | 218 | 1433600 | 2700 | |
43989856 | consecutivelimit | E | Oct. 8, 2018, 9:31 a.m. | OK | GNU C++14 | TESTS | 48 | 218 | 1536000 | 2700 | |
44653929 | aki167yuuki | E | Oct. 21, 2018, 12:21 p.m. | OK | GNU C++17 | TESTS | 48 | 171 | 716800 | 2700 | |
43967779 | Benq | E | Oct. 7, 2018, 6:31 p.m. | OK | GNU C++17 | TESTS | 48 | 186 | 1126400 | 2700 | |
43969431 | Farhod_Farmon | E | Oct. 7, 2018, 6:46 p.m. | OK | GNU C++17 | TESTS | 48 | 218 | 307200 | 2700 | |
43965407 | isaf27 | E | Oct. 7, 2018, 6:11 p.m. | OK | GNU C++17 | TESTS | 48 | 218 | 2252800 | 2700 | |
48099034 | mareksom | E | Jan. 8, 2019, 6:57 p.m. | OK | GNU C++17 | TESTS | 48 | 233 | 307200 | 2700 | |
43978205 | LiChenKoh | E | Oct. 7, 2018, 11:11 p.m. | OK | GNU C++17 | TESTS | 48 | 233 | 3481600 | 2700 | |
44184683 | helThazar | E | Oct. 12, 2018, 12:44 p.m. | OK | GNU C++17 | TESTS | 48 | 234 | 409600 | 2700 | |
43971559 | V--o_o--V | E | Oct. 7, 2018, 7:03 p.m. | OK | GNU C++17 | TESTS | 48 | 234 | 409600 | 2700 | |
61393691 | tfg | E | Sept. 28, 2019, 12:09 a.m. | OK | GNU C++17 | TESTS | 48 | 234 | 512000 | 2700 | |
61342504 | Kuroni | E | Sept. 26, 2019, 11:59 p.m. | OK | GNU C++17 | TESTS | 48 | 234 | 512000 | 2700 | |
44995653 | Martynas | E | Oct. 28, 2018, 3:26 p.m. | OK | Go | TESTS | 48 | 904 | 9830400 | 2700 | |
43968555 | ilyakor | E | Oct. 7, 2018, 6:38 p.m. | OK | Java 8 | TESTS | 48 | 560 | 0 | 2700 | |
43983408 | t.yoshihara.ae | E | Oct. 8, 2018, 5:12 a.m. | OK | Java 8 | TESTS | 48 | 717 | 0 | 2700 | |
43966198 | qwerty787788 | E | Oct. 7, 2018, 6:18 p.m. | OK | Java 8 | TESTS | 48 | 748 | 0 | 2700 | |
43987552 | amnesiac_dusk | E | Oct. 8, 2018, 8:15 a.m. | OK | Java 8 | TESTS | 48 | 951 | 0 | 2700 | |
44067604 | PrakharJain | E | Oct. 10, 2018, 10:16 a.m. | OK | Java 8 | TESTS | 48 | 3182 | 0 | 2700 | |
44069610 | PrakharJain | E | Oct. 10, 2018, 11:11 a.m. | OK | Java 8 | TESTS | 48 | 3306 | 0 | 2700 | |
44037950 | PavelChadnov | E | Oct. 9, 2018, 1:37 p.m. | OK | Mono C# | TESTS | 48 | 935 | 22630400 | 2700 | |
44037740 | PavelChadnov | E | Oct. 9, 2018, 1:33 p.m. | OK | Mono C# | TESTS | 48 | 967 | 24166400 | 2700 | |
44038029 | PavelChadnov | E | Oct. 9, 2018, 1:39 p.m. | OK | Mono C# | TESTS | 48 | 998 | 22630400 | 2700 | |
44037880 | PavelChadnov | E | Oct. 9, 2018, 1:36 p.m. | OK | Mono C# | TESTS | 48 | 1060 | 24166400 | 2700 | |
43975519 | LoneFox | E | Oct. 7, 2018, 8:50 p.m. | OK | MS C++ | TESTS | 48 | 343 | 409600 | 2700 | |
43980189 | EbTech | E | Oct. 8, 2018, 1:59 a.m. | OK | Rust | TESTS | 48 | 795 | 57241600 | 2700 | |
43980476 | EbTech | E | Oct. 8, 2018, 2:20 a.m. | OK | Rust | TESTS | 48 | 810 | 57241600 | 2700 |
Back to search problems