### aknov711's blog

By aknov711, history, 14 months ago, Given N tasks in a game which need to be performed in any order. Initially, we have a power of 1 unit and speed of 1 unit. The $i^{th}$ task requires a minimum of $A_{i}$ power or $B_{i}$ speed. On completing the ith task we get $C_{i}$ points which can be used to increase speed or power. 1 point can be used to increase 1 power or 1 speed. Find the maximum number of tasks that can be completed.

1<=N<=100

1<=A[i],B[i],C[i]<=1000

Example:

Input:

A=[1,1,2,7]

B=[1,3,4,4]

C=[2,3,1,1]

Output: 4

By aknov711, history, 15 months ago, Recently, I got stuck in this line of thoughts.. Given a graph with n nodes and m edges with no cycles and multiple edges. Consider the summation of minimum degrees of the two endpoints of every edge of the graph.

More formally, wann'a know bound for

S= $\Sigma$ min( $deg_u,deg_v$ ) $\forall (u,v) \in E$

What would it be assympotically equal to ? Definitely, one upperbound can be O(n*m) since the largest degree for any node can ne n-1.

Suppose if n and m both are of order $10^5$ , then what it would be equal to? Can you share your thoughts on this ?