Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + 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
1553 Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2) FINISHED False 9000 110388311 July 22, 2021, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 1069 ) G Common Divisor Graph PROGRAMMING binary search ds graphs math number theory

B"Consider a sequence of distinct integers a_1, ldots, a_n , each representing one node of a graph. There is an edge between two nodes if the two values are not coprime, i. e. they have a common divisor greater than 1 . There are q queries, in each query, you want to get from one given node a_s to another a_t . In order to achieve that, you can choose an existing value a_i and create new value a_{n+1} = a_i cdot (1 + a_i) , with edges to all values that are not coprime with a_{n+1} . Also, n gets increased by 1 . You can repeat that operation multiple times, possibly making the sequence much longer and getting huge or repeated values. What's the minimum possible number of newly created nodes so that a_t is reachable from a_s ? Queries are independent. In each query, you start with the initial sequence a given in the input. The first line contains two integers n and q ( 2 <= q n <= q 150 ,000 , 1 <= q q <= q 300 ,000 ) -- the size of the sequence and the number of queries. The second line contains n distinct integers a_1, a_2, ldots, a_n ( 2 <= q a_i <= q 10^6 , a_i neq a_j if i ne j ). The j -th of the following q lines contains two distinct integers s_j and t_j ( 1 <= q s_j, t_j <= q n , s_j neq t_j ) -- indices of nodes for j -th query. Print q lines. The j -th line should contain one integer: the minimum number of new nodes you create in order to move from a_{s_j} to a_{t_j} . In the first example, you can first create new value 2 cdot 3 = 6 or 10 cdot 11 = 110 or 3 cdot 4 = 12 . None of that is needed in the first query because you can already get from a_1 = 2 to a_2 = 10 . In the second query, it's optimal to first create 6 or 12 . For example, creating 6 makes it possible to get from a_1 = 2 to a_3 = 3 with "...

Tutorials

Harbour.Space Scholarship Contest 2021-2022 (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
123356522 rainboy G July 22, 2021, 6:40 p.m. OK GNU C11 TESTS 34 1497 205107200
123368533 q-w-q-w-q G July 22, 2021, 9:25 p.m. OK GNU C++11 TESTS 34 373 37785600
123367345 q-w-q-w-q G July 22, 2021, 8:59 p.m. OK GNU C++11 TESTS 34 639 254668800
123374839 fallleaves01 G July 23, 2021, 12:40 a.m. OK GNU C++11 TESTS 34 670 70860800
123350175 Salley-Garden G July 22, 2021, 5 p.m. OK GNU C++11 TESTS 34 685 254668800
123374618 iqx37f G July 23, 2021, 12:33 a.m. OK GNU C++11 TESTS 34 701 239616000
123390299 uuku G July 23, 2021, 4:47 a.m. OK GNU C++11 TESTS 34 717 62976000
123379548 Copsdorg G July 23, 2021, 2:12 a.m. OK GNU C++11 TESTS 34 763 74854400
123379567 RPChe_ dottle G July 23, 2021, 2:12 a.m. OK GNU C++11 TESTS 34 763 74854400
123381916 nantf G July 23, 2021, 2:47 a.m. OK GNU C++11 TESTS 34 842 58572800
123381641 zhylj G July 23, 2021, 2:43 a.m. OK GNU C++11 TESTS 34 873 42803200
123383915 beginend G July 23, 2021, 3:16 a.m. OK GNU C++14 TESTS 34 343 45056000
123383079 AhoCorasick G July 23, 2021, 3:04 a.m. OK GNU C++14 TESTS 34 373 162099200
123348324 DeadPillow G July 22, 2021, 4:54 p.m. OK GNU C++14 TESTS 34 389 68300800
123360987 Daredemo_Daisuki G July 22, 2021, 7:19 p.m. OK GNU C++14 TESTS 34 467 44544000
123388331 Kerim.K G July 23, 2021, 4:19 a.m. OK GNU C++14 TESTS 34 592 82841600
123361023 mraron G July 22, 2021, 7:19 p.m. OK GNU C++14 TESTS 34 639 74956800
123381947 tzc_wk G July 23, 2021, 2:48 a.m. OK GNU C++14 TESTS 34 733 106803200
123365474 awoo G July 22, 2021, 8:24 p.m. OK GNU C++14 TESTS 34 857 92160000
123351236 scli_weapon G July 22, 2021, 5:03 p.m. OK GNU C++14 TESTS 34 920 54067200
123384534 superguymj G July 23, 2021, 3:24 a.m. OK GNU C++14 TESTS 34 1060 150937600
123346914 Tima G July 22, 2021, 4:49 p.m. OK GNU C++17 TESTS 34 374 52531200
123376944 kizen G July 23, 2021, 1:27 a.m. OK GNU C++17 TESTS 34 405 55398400
123369843 flashmt G July 22, 2021, 9:55 p.m. OK GNU C++17 TESTS 34 420 36352000
123381039 cs142857 G July 23, 2021, 2:34 a.m. OK GNU C++17 TESTS 34 436 18124800
123381320 cs142857 G July 23, 2021, 2:38 a.m. OK GNU C++17 TESTS 34 467 18124800
123346807 sam.rei G July 22, 2021, 4:49 p.m. OK GNU C++17 TESTS 34 498 51814400
123360521 islingr G July 22, 2021, 7:14 p.m. OK GNU C++17 TESTS 34 514 38912000
123360581 islingr G July 22, 2021, 7:14 p.m. OK GNU C++17 TESTS 34 545 38912000
123394465 Ant_Man G July 23, 2021, 5:40 a.m. OK GNU C++17 TESTS 34 577 31334400
123355714 re_eVVorld G July 22, 2021, 6:36 p.m. OK GNU C++17 TESTS 34 592 27852800
123365203 12tqian G July 22, 2021, 8:19 p.m. OK GNU C++17 (64) TESTS 34 420 30003200
123387304 wmRdIXOc G July 23, 2021, 4:03 a.m. OK GNU C++17 (64) TESTS 34 436 69529600
123365138 12tqian G July 22, 2021, 8:18 p.m. OK GNU C++17 (64) TESTS 34 467 66867200
123390700 Fysty G July 23, 2021, 4:52 a.m. OK GNU C++17 (64) TESTS 34 483 71987200
123356932 rainboy G July 22, 2021, 6:43 p.m. OK GNU C++17 (64) TESTS 34 483 205619200
123370877 LiChenKoh G July 22, 2021, 10:26 p.m. OK GNU C++17 (64) TESTS 34 498 35840000
123346137 orzdevinwang G July 22, 2021, 4:47 p.m. OK GNU C++17 (64) TESTS 34 514 76492800
123383331 Quang G July 23, 2021, 3:08 a.m. OK GNU C++17 (64) TESTS 34 529 140902400
123376189 OIerwanhong G July 23, 2021, 1:12 a.m. OK GNU C++17 (64) TESTS 34 530 36761600
123349276 _tryhard G July 22, 2021, 4:57 p.m. OK GNU C++17 (64) TESTS 34 545 89702400
123347971 clyring G July 22, 2021, 4:53 p.m. OK Haskell TESTS 34 1075 63180800
123377299 dalt G July 23, 2021, 1:33 a.m. OK Java 11 TESTS 34 701 268390400
123372632 YahiaSherif G July 22, 2021, 11:23 p.m. OK Java 8 TESTS 34 1622 66764800
123355913 sansen G July 22, 2021, 6:37 p.m. OK Rust TESTS 34 234 36659200

remove filters

Back to search problems