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. |
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 "... |
Harbour.Space Scholarship Contest 2021-2022 (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 |
---|---|---|---|---|---|---|---|---|---|---|---|
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 |
Back to search problems