Technocup 2021 - Elimination Round 3

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
1411 Technocup 2021 - Elimination Round 3 FINISHED False 7200 128876111 Dec. 20, 2020, 3:05 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 682 ) G No Game No Life PROGRAMMING games math matrices

B"Let's consider the following game of Alice and Bob on a directed acyclic graph. Each vertex may contain an arbitrary number of chips. Alice and Bob make turns alternating. Alice goes first. In one turn player can move exactly one chip along any edge outgoing from the vertex that contains this chip to the end of this edge. The one who cannot make a turn loses. Both players play optimally. Consider the following process that takes place every second on a given graph with n vertices: Find the probability that Alice will win the game. It can be shown that the answer can be represented as frac{P}{Q} , where P and Q are coprime integers and Q not equiv 0 pmod{998 ,244 ,353} . Print the value of P cdot Q^{-1} bmod 998 ,244 ,353 . The first line contains two integers n and m -- the number of vertices and edges of the graph ( 1 <= q n <= q 10^5 , 0 <= q m <= q 10^5 ). The following m lines contain edges description. The i -th of them contains two integers u_i and v_i -- the beginning and the end vertices of the i -th edge ( 1 <= q u_i, v_i <= q n ). It's guaranteed that the graph is acyclic. Output a single integer -- the probability of Alice victory modulo 998 ,244 ,353 . "...

Tutorials

Technocup 2021 Elimination Round 3 and Round #692 (Div. 1 + Div. 2) Editorial

Submissions

No solutions yet.