admin

[Solution] Tree Coloring solution codeforces

Tree Coloring solution codeforces You are given a rooted tree consisting of 𝑛n vertices numbered from 11 to 𝑛n. The root of the tree is the vertex 11. You have to color all vertices of the tree into 𝑛n colors (also numbered from 11 to 𝑛n) so that there is exactly one vertex for each color. Let 𝑐𝑖ci be the color of vertex 𝑖i, and 𝑝𝑖pi be the parent of vertex 𝑖i in …

[Solution] Tree Coloring solution codeforces Read More »

[Solution] MEX Sequences solution codeforces

MEX Sequences solution codeforces Let’s call a sequence of integers 𝑥1,𝑥2,…,𝑥𝑘x1,x2,…,xk MEX-correct if for all 𝑖i (1≤𝑖≤𝑘1≤i≤k) |𝑥𝑖−MEX(𝑥1,𝑥2,…,𝑥𝑖)|≤1|xi−MEX⁡(x1,x2,…,xi)|≤1 holds. Where MEX(𝑥1,…,𝑥𝑘)MEX⁡(x1,…,xk) is the minimum non-negative integer that doesn’t belong to the set 𝑥1,…,𝑥𝑘x1,…,xk. For example, MEX(1,0,1,3)=2MEX⁡(1,0,1,3)=2 and MEX(2,1,5)=0MEX⁡(2,1,5)=0. You are given an array 𝑎a consisting of 𝑛n non-negative integers. Calculate the number of non-empty MEX-correct subsequences of a given array. The number of subsequences can be very large, so print it modulo 998244353998244353. Note: a …

[Solution] MEX Sequences solution codeforces Read More »

[Solution] Poisoned Dagger solution codeforces

Poisoned Dagger solution codeforces Monocarp is playing yet another computer game. In this game, his character has to kill a dragon. The battle with the dragon lasts 100500100500 seconds, during which Monocarp attacks the dragon with a poisoned dagger. The 𝑖i-th attack is performed at the beginning of the 𝑎𝑖ai-th second from the battle start. The dagger itself does …

[Solution] Poisoned Dagger solution codeforces Read More »

[Solution] Absent Remainder solution codeforces

Absent Remainder solution codeforces You are given a sequence 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an consisting of 𝑛n pairwise distinct positive integers. Find ⌊𝑛2⌋⌊n2⌋ different pairs of integers 𝑥x and 𝑦y such that: 𝑥≠𝑦x≠y; 𝑥x and 𝑦y appear in 𝑎a; 𝑥 𝑚𝑜𝑑 𝑦x mod y doesn’t appear in 𝑎a. Note that some 𝑥x or 𝑦y can belong to multiple pairs. ⌊𝑥⌋⌊x⌋ denotes the floor function — the largest integer less than or equal to 𝑥x. 𝑥 𝑚𝑜𝑑 𝑦x mod y denotes the remainder from dividing 𝑥x by 𝑦y. If there are multiple solutions, print any of …

[Solution] Absent Remainder solution codeforces Read More »