Codeforces Round 773 (Div. 1)

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
1641 Codeforces Round 773 (Div. 1) FINISHED False 7200 86212199 Feb. 23, 2022, 10:10 a.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 210 ) E Special Positions PROGRAMMING combinatorics fft

B'You are given an array a of length n . Also you are given m distinct positions p_1, p_2, ldots, p_m ( 1 <= q p_i <= q n ). A non-empty subset of these positions T is randomly selected with equal probability and the following value is calculated: sum_{i=1}^{n} (a_i cdot min_{j in T} <= ft|i - j right|). In other word, for each index of the array, a_i and the distance to the closest chosen position are multiplied, and then these values are summed up. Find the expected value of this sum. This value must be found modulo 998 ,244 ,353 . More formally, let M = 998 ,244 ,353 . It can be shown that the answer can be represented as an irreducible fraction frac{p}{q} , where p and q are integers and q neq 0 (mod M ). Output the integer equal to p cdot q^{-1} (mod M ). In other words, output such integer x that 0 <= q x < M and x cdot q = p (mod M ). The first line contains two integers n and m ( 1 <= q m <= q n <= q 10^5 ). The second line contains n integers a_1, a_2, ldots, a_n ( 0 <= q a_i < 998 ,244 ,353 ). The third line contains m distinct integers p_1, p_2, ldots, p_m ( 1 <= q p_i <= n ). For every 1 <= q i < m it is guaranteed that p_i < p_{i+1} . Print a single integer -- the answer to the problem. In the first test: The answer to the problem is frac{20 + 10 + 5}{3} = frac{35}{3} = 665 ,496 ,247 (modulo 998 ,244 ,353 ). '...

Tutorials

Codeforces Round #773 editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
147450489 djq_cpp E Feb. 23, 2022, 11:23 a.m. OK GNU C++14 TESTS 74 420 16896000
147524530 Mackerel_Pike E Feb. 24, 2022, 1:36 a.m. OK GNU C++14 TESTS 74 967 24166400
147461389 nantf E Feb. 23, 2022, 11:58 a.m. OK GNU C++14 TESTS 74 2433 53452800
147456831 CQXYM E Feb. 23, 2022, 11:43 a.m. OK GNU C++14 TESTS 74 3337 38912000
147485044 ugly2333 E Feb. 23, 2022, 2:55 p.m. OK GNU C++14 TESTS 74 4742 10547200
147528826 Achtoria E Feb. 24, 2022, 3:26 a.m. OK GNU C++14 TESTS 74 4882 1638400
147528491 Achtoria E Feb. 24, 2022, 3:19 a.m. OK GNU C++14 TESTS 74 4960 1638400
147470648 Marcin_smu E Feb. 23, 2022, 12:59 p.m. OK GNU C++17 TESTS 74 545 9216000
147526701 world_top_1_AD_uzi E Feb. 24, 2022, 2:36 a.m. OK GNU C++17 TESTS 74 1356 165273600
147473927 cnnfls_csy E Feb. 23, 2022, 1:21 p.m. OK GNU C++17 TESTS 74 1637 41676800
147462090 zh0ukangyang E Feb. 23, 2022, 12:01 p.m. OK GNU C++17 TESTS 74 1699 94617600
147468382 SpyCheese E Feb. 23, 2022, 12:47 p.m. OK GNU C++17 TESTS 74 1730 57753600
147523370 huzhaoyang E Feb. 24, 2022, 1:04 a.m. OK GNU C++17 TESTS 74 1872 11980800
147526419 sunzh E Feb. 24, 2022, 2:30 a.m. OK GNU C++17 TESTS 74 2246 26214400
147441536 zhouziheng E Feb. 23, 2022, 11:01 a.m. OK GNU C++17 TESTS 74 2714 71884800
147514167 ilyakrasnovv E Feb. 23, 2022, 8:41 p.m. OK GNU C++17 TESTS 74 3275 5734400
147456452 Rebelz E Feb. 23, 2022, 11:42 a.m. OK GNU C++17 TESTS 74 4368 2048000
147523700 qazswedx2 E Feb. 24, 2022, 1:13 a.m. OK GNU C++17 (64) TESTS 74 218 58060800
147509128 Benq E Feb. 23, 2022, 7:19 p.m. OK GNU C++17 (64) TESTS 74 233 5734400
147525963 Alfalfa_w E Feb. 24, 2022, 2:18 a.m. OK GNU C++17 (64) TESTS 74 249 11161600
147441075 5002ryx E Feb. 23, 2022, 11 a.m. OK GNU C++17 (64) TESTS 74 249 15155200
147512385 aryanc403 E Feb. 23, 2022, 8:08 p.m. OK GNU C++17 (64) TESTS 74 327 11571200
147497862 aryanc403 E Feb. 23, 2022, 5:03 p.m. OK GNU C++17 (64) TESTS 74 374 15872000
147454919 maroonrk E Feb. 23, 2022, 11:37 a.m. OK GNU C++17 (64) TESTS 74 452 49254400
147468737 golikovnik E Feb. 23, 2022, 12:48 p.m. OK GNU C++17 (64) TESTS 74 483 19865600
147524014 xay5421 E Feb. 24, 2022, 1:22 a.m. OK GNU C++17 (64) TESTS 74 608 18534400
147446189 ecnerwala E Feb. 23, 2022, 11:11 a.m. OK GNU C++17 (64) TESTS 74 623 15769600
147469209 frame233 E Feb. 23, 2022, 12:50 p.m. OK GNU C++20 (64) TESTS 74 155 18432000
147445838 tourist E Feb. 23, 2022, 11:11 a.m. OK GNU C++20 (64) TESTS 74 202 6246400
147482345 ZongDeChuangSiYiGeBa E Feb. 23, 2022, 2:30 p.m. OK GNU C++20 (64) TESTS 74 421 17203200
147475647 golikovnik E Feb. 23, 2022, 1:33 p.m. OK GNU C++20 (64) TESTS 74 467 19558400
147475711 golikovnik E Feb. 23, 2022, 1:33 p.m. OK GNU C++20 (64) TESTS 74 483 19558400
147475624 golikovnik E Feb. 23, 2022, 1:33 p.m. OK GNU C++20 (64) TESTS 74 483 19558400
147455497 ksun48 E Feb. 23, 2022, 11:38 a.m. OK GNU C++20 (64) TESTS 74 592 18944000
147468585 ynsm E Feb. 23, 2022, 12:47 p.m. OK GNU C++20 (64) TESTS 74 655 2969600
147523624 gary88 E Feb. 24, 2022, 1:10 a.m. OK GNU C++20 (64) TESTS 74 670 21504000
147530535 Y25t E Feb. 24, 2022, 4:02 a.m. OK GNU C++20 (64) TESTS 74 686 21708800

remove filters

Back to search problems