Lyft Level 5 Challenge 2018 - Elimination Round

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.

Problems

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'...

Tutorials

The Lyft Level 5 Challenge 2018 Elimination Round (Div. 1 + Div. 2) Editorial

Submissions

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

remove filters

Back to search problems