Codeforces functionality may be limited from June 18, 19:00 (UTC) to June 19, 3:00 AM (UTC) due to technical maintenance. Polygon will work as usual. ×

aknov711's blog

By aknov711, history, 20 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • +9
  • Vote: I do not like it

By aknov711, history, 22 months ago, In English

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 ?

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it