Educational Codeforces Round 145 (Rated for 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
1809 Educational Codeforces Round 145 (Rated for Div. 2) FINISHED False 7200 57684263 March 23, 2023, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 460 ) G Prediction PROGRAMMING combinatorics data structures dp

B'Consider a tournament with n participants. The rating of the i -th participant is a_i . The tournament will be organized as follows. First of all, organizers will assign each participant an index from 1 to n . All indices will be unique. Let p_i be the participant who gets the index i . Then, n-1 games will be held. In the first game, participants p_1 and p_2 will play. In the second game, the winner of the first game will play against p_3 . In the third game, the winner of the second game will play against p_4 , and so on -- in the last game, the winner of the (n-2) -th game will play against p_n . Monocarp wants to predict the results of all n-1 games (of course, he will do the prediction only after the indices of the participants are assigned). He knows for sure that, when two participants with ratings x and y play, and |x - y| > k , the participant with the higher rating wins. But if |x - y| <= k , any of the two participants may win. Among all n! ways to assign the indices to participants, calculate the number of ways to do this so that Monocarp can predict the results of all n-1 games. Since the answer can be large, print it modulo 998244353 . The first line contains two integers n and k ( 2 <= n <= 10^6 ; 0 <= k <= 10^9 ). The second line contains n integers a_1, a_2, ... , a_n ( 0 <= a_1 <= a_2 <= ... <= a_n <= 10^9 ). Print one integer -- the number of ways to assign the indices to the participants so that Monocarp can predict the results of all n-1 games. In the first example, a match with any pair of players can be predicted by Monocarp, so all 24 ways to assign indices should be counted. In the second example, suitable ways are [1, 3, 2] , [2, 3, 1] , [3, 1, 2 ] and [3, 2, 1] . '...

Tutorials

114300

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
198880173 LXH-cat G March 24, 2023, 1:12 a.m. OK GNU C++14 TESTS 53 358 24371200
198829692 stkwill G March 23, 2023, 4:38 p.m. OK GNU C++14 TESTS 53 374 24064000
198893667 donghanwen G March 24, 2023, 5:16 a.m. OK GNU C++14 TESTS 53 1747 40038400
198885423 zft_4995 G March 24, 2023, 3:06 a.m. OK GNU C++17 TESTS 53 327 12083200
198859922 2023_365_streak G March 23, 2023, 8:27 p.m. OK GNU C++17 TESTS 53 343 12083200
198840833 gautamankoji G March 23, 2023, 5:36 p.m. OK GNU C++17 (64) TESTS 53 202 12083200
198828608 tute7627 G March 23, 2023, 4:34 p.m. OK GNU C++17 (64) TESTS 53 233 28057600
198832652 potato167 G March 23, 2023, 4:50 p.m. OK GNU C++17 (64) TESTS 53 234 40140800
198837763 pawan1712 G March 23, 2023, 5:17 p.m. OK GNU C++17 (64) TESTS 53 1170 16076800
198831844 Rubikun G March 23, 2023, 4:46 p.m. OK GNU C++17 (64) TESTS 53 1216 33075200
198829525 Rubikun G March 23, 2023, 4:37 p.m. OK GNU C++17 (64) TESTS 53 2386 37273600

remove filters

Back to search problems