271C: Secret

for group ki, just assign 2(ki)-1, 2 * k to that group, and then the next k element to the group 1 to k, and remaining elements to group 1

444A: DZY Loves Physics(!!!)

Claim: that highest density subgraph can have only 2 nodes and 1 edge

Proof: suppose the target subgraph has more than 2 nodes, then for each (u, v) pair, in the graph , the density is sum(U) + sum(V) / sum(e(u, v)). However, we know that there exists u + v / e(u, v) >= that density. Otherwise, the equation is no longer possbile

140C: New Year Snowmen(!!!)

Solution 1: bsearch on the final answer with construction algorithm

Claim: we can form k snowmen, if and only if then there exists an arrangement takens from sorted number array, (1, k+1, 2k+1), (2, k+2, 2k+2), on condition that no number appears more than k times

Proof:

Construction => result : obvioius

result => construction

	1. at least 3 * k snowballs. 

        2. no number appears more than k times

	3. Therefore, if we sort all snowballs, this arrangement can still work, because of 2)

Solution 2: greedy

Claim: all quantities are < k and total >= 3 * k <=> we can form k snowmen with min number of snowballs

Proof:

Condition => result

	1. if there are >=3 numbers appearing more than k times, obviously

	2. if there are one or 2 numbers appearning more than k times, take these 2, and another random one, and do induction

	3. if there are no number appearing more than k times, we just take any 3 numbers, and do induction

Result => condition: obvious