Codeforces Round 657 (Div. 2)

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
1379 Codeforces Round 657 (Div. 2) FINISHED False 7200 142030763 July 19, 2020, 9 a.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 434 ) E Inverse Genealogy PROGRAMMING constructive algorithms divide and conquer dp math trees 2400

B'Ivan is fond of genealogy. Currently he is studying a particular genealogical structure, which consists of some people. In this structure every person has either both parents specified, or none. Additionally, each person has exactly one child, except for one special person, who does not have any children. The people in this structure are conveniently numbered from 1 to n , and s_i denotes the child of the person i (and s_i = 0 for exactly one person who does not have any children). We say that a is an ancestor of b if either a = b , or a has a child, who is an ancestor of b . That is a is an ancestor for a , s_a , s_{s_a} , etc. We say that person i is imbalanced in case this person has both parents specified, and the total number of ancestors of one of the parents is at least double the other. Ivan counted the number of imbalanced people in the structure, and got k people in total. However, he is not sure whether he computed it correctly, and would like to check if there is at least one construction with n people that have k imbalanced people in total. Please help him to find one such construction, or determine if it does not exist. The input contains two integers n and k ( 1 <= q n <= q 100 ,000 , 0 <= q k <= q n ), the total number of people and the number of imbalanced people. If there are no constructions with n people and k imbalanced people, output NO. Otherwise output YES on the first line, and then n integers s_1, s_2, ldots, s_n ( 0 <= q s_i <= q n ), which describes the construction and specify the child of each node (or 0, if the person does not have any children). In the first example case one can have a construction with 3 people, where 1 person has 2 parents. In the second example case one can use the following construction: Only person 1 is imbalanced, because one of their parents has 1 an'...

Tutorials

Codeforces Round #657 Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
87390401 xryjr233 E July 20, 2020, 12:56 a.m. OK GNU C++11 TESTS 118 46 3891200 2400
87365812 s_h_y E July 19, 2020, 3:09 p.m. OK GNU C++11 TESTS 118 46 3891200 2400
87351475 Frame233 E July 19, 2020, 12:34 p.m. OK GNU C++11 TESTS 118 46 5836800 2400
87394704 autoint E July 20, 2020, 3:10 a.m. OK GNU C++11 TESTS 118 46 7065600 2400
87394440 JJLeo E July 20, 2020, 3:03 a.m. OK GNU C++11 TESTS 118 46 7065600 2400
87372206 lavenderwithbluish E July 19, 2020, 4:33 p.m. OK GNU C++11 TESTS 118 46 7680000 2400
87310093 3.141592653 E July 19, 2020, 9:50 a.m. OK GNU C++11 TESTS 118 46 12595200 2400
87349081 Tohsaka_Sakura E July 19, 2020, 12:11 p.m. OK GNU C++11 TESTS 118 61 34304000 2400
87362088 atoiz E July 19, 2020, 2:28 p.m. OK GNU C++11 TESTS 118 62 8192000 2400
87367751 OMG_link E July 19, 2020, 3:32 p.m. OK GNU C++11 TESTS 118 62 9932800 2400
87392136 Ziyi_Wang1 E July 20, 2020, 2:02 a.m. OK GNU C++14 TESTS 118 46 4096000 2400
87377332 steam_giant E July 19, 2020, 6:01 p.m. OK GNU C++14 TESTS 118 46 4096000 2400
87340460 RedStar_13 E July 19, 2020, 10:56 a.m. OK GNU C++14 TESTS 118 46 4403200 2400
87331017 Hyperbolic E July 19, 2020, 10:36 a.m. OK GNU C++14 TESTS 118 46 4505600 2400
87327455 Potassium E July 19, 2020, 10:27 a.m. OK GNU C++14 TESTS 118 46 4505600 2400
87360875 upobir E July 19, 2020, 2:15 p.m. OK GNU C++14 TESTS 118 46 5222400 2400
87328995 tmwilliamlin168 E July 19, 2020, 10:31 a.m. OK GNU C++14 TESTS 118 46 6963200 2400
87389862 SoiMae E July 20, 2020, 12:30 a.m. OK GNU C++14 TESTS 118 46 8089600 2400
87348856 Will_Dearborn E July 19, 2020, 12:09 p.m. OK GNU C++14 TESTS 118 46 8396800 2400
87383894 krijgertje E July 19, 2020, 8:21 p.m. OK GNU C++14 TESTS 118 46 8908800 2400
87347536 wasa855 E July 19, 2020, 11:57 a.m. OK GNU C++17 TESTS 118 31 4096000 2400
87375193 vipjml E July 19, 2020, 5:23 p.m. OK GNU C++17 TESTS 118 46 4198400 2400
87334225 antontrygubO_o E July 19, 2020, 10:43 a.m. OK GNU C++17 TESTS 118 46 4198400 2400
87374237 I_Love_Tourist_ E July 19, 2020, 5:06 p.m. OK GNU C++17 TESTS 118 46 4403200 2400
87347060 meaningful E July 19, 2020, 11:53 a.m. OK GNU C++17 TESTS 118 46 4403200 2400
87374350 solaimanope E July 19, 2020, 5:08 p.m. OK GNU C++17 TESTS 118 46 4812800 2400
87390753 xiahongyu E July 20, 2020, 1:14 a.m. OK GNU C++17 TESTS 118 46 6963200 2400
87390615 xiahongyu E July 20, 2020, 1:08 a.m. OK GNU C++17 TESTS 118 46 6963200 2400
87370145 timf1089 E July 19, 2020, 4:02 p.m. OK GNU C++17 TESTS 118 46 6963200 2400
87363865 icecuber E July 19, 2020, 2:47 p.m. OK GNU C++17 TESTS 118 46 7987200 2400
87397647 neal E July 20, 2020, 4:33 a.m. OK GNU C++17 (64) TESTS 118 31 4710400 2400
87383816 EmilConst E July 19, 2020, 8:19 p.m. OK GNU C++17 (64) TESTS 118 46 4710400 2400
87371076 Geothermal E July 19, 2020, 4:15 p.m. OK GNU C++17 (64) TESTS 118 46 4710400 2400
87347153 Roundgod E July 19, 2020, 11:53 a.m. OK GNU C++17 (64) TESTS 118 46 4710400 2400
87358741 Qwerty1232 E July 19, 2020, 1:51 p.m. OK GNU C++17 (64) TESTS 118 46 5120000 2400
87388293 _oscar_S21 E July 19, 2020, 10:58 p.m. OK GNU C++17 (64) TESTS 118 46 5324800 2400
87377339 12tqian E July 19, 2020, 6:01 p.m. OK GNU C++17 (64) TESTS 118 46 13107200 2400
87392283 WZYYN E July 20, 2020, 2:07 a.m. OK GNU C++17 (64) TESTS 118 62 5427200 2400
87351638 suncongbo E July 19, 2020, 12:36 p.m. OK GNU C++17 (64) TESTS 118 77 48435200 2400
87331203 jiangly E July 19, 2020, 10:36 a.m. OK GNU C++17 (64) TESTS 118 78 17920000 2400
87386086 Tlatoani E July 19, 2020, 9:28 p.m. OK Kotlin TESTS 118 171 23449600 2400

remove filters

Back to search problems