Educational Codeforces Round 33 (Rated for Div. 2) E. Counting Arrays
2926. Maximum Balanced Subsequence Sum
You are given a 0-indexed integer array
nums.A subsequence of
numshaving lengthkand consisting of indicesi0 < i1 < ... < ik-1is balanced if the following holds:
nums[ij] - nums[ij-1] >= ij - ij-1, for everyjin the range[1, k - 1].A subsequence of
numshaving length1is considered balanced.Return an integer denoting the maximum possible sum of elements in a balanced subsequence of
nums.A subsequence of an array is a new non-empty array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.
2925. Maximum Score After Applying Operations on a Tree
There is an undirected tree with
nnodes labeled from0ton - 1, and rooted at node0. You are given a 2D integer arrayedgesof lengthn - 1, whereedges[i] = [ai, bi]indicates that there is an edge between nodesaiandbiin the tree.You are also given a 0-indexed integer array
valuesof lengthn, wherevalues[i]is the value associated with theithnode.You start with a score of
0. In one operation, you can:
- Pick any node
i.- Add
values[i]to your score.- Set
values[i]to0.A tree is healthy if the sum of values on the path from the root to any leaf node is different than zero.
Return the maximum score you can obtain after performing these operations on the tree any number of times so that it remains healthy.
There are
nteams numbered from0ton - 1in a tournament; each team is also a node in a DAG.You are given the integer
nand a 0-indexed 2D integer arrayedgesof lengthmrepresenting the DAG, whereedges[i] = [ui, vi]indicates that there is a directed edge from teamuito teamviin the graph.A directed edge from
atobin the graph means that teamais stronger than teamband teambis weaker than teama.Team
awill be the champion of the tournament if there is no teambthat is stronger than teama.Return the team that will be the champion of the tournament if there is a unique champion, otherwise, return
-1.Notes
- A cycle is a series of nodes
a1, a2, ..., an, an+1such that nodea1is the same node as nodean+1, the nodesa1, a2, ..., anare distinct, and there is a directed edge from the nodeaito nodeai+1for everyiin the range[1, n].- A DAG is a directed graph that does not have any cycle.
There are
nteams numbered from0ton - 1in a tournament.Given a 0-indexed 2D boolean matrix
gridof sizen * n. For alli, jthat0 <= i, j <= n - 1andi != jteamiis stronger than teamjifgrid[i][j] == 1, otherwise, teamjis stronger than teami.Team
awill be the champion of the tournament if there is no teambthat is stronger than teama.Return the team that will be the champion of the tournament.