Codeforces Round #277.5 Div. 2

Problem A:
A. SwapSort

Solution:
You simply need to implement a Selection Sort since it will require at most N number of swaps. Why? Imagine placing N items to N correct positions in increasing order, then for each i in N there is only 2 possibility: item on i is already at its correct position, or we can find the item that should actually be there. So worst case scenario is you have to do the swapping N times.

Problem B:
B. BerSU Ball

Solution:
Greedy approach: Sort each stacks, and going from the top of each stack we pair what we can pair. If we find that the two elements on the top cannot be paired, eliminate the one which is bigger.



Problem C:
C. Given Length and Sum of Digits...

Solution:
To find the biggest possible:
From left to right: Greedily try to fill in 9. If can't be done, then fill in the biggest possible, and fill the rest with 0.
To find the smallest:
From left to right: Try to fill in i = 0, 1, 2, ..., 9. If remaining sum - i <= 9*(remaining length), then we can fill i. Otherwise increase i. Caution: the leftmost digit cannot be 0.

Problem D:
D. Unbearable Controversy of Being

Solution:
Very interesting problem. Notice that to find the number of damn rhombus between vertex u and v, we need to find M[u][v], the number of vertices i such that edge u-i and edge i-v exists, and then the number of damn rhombus between u and v is just the number of ways to choose those vertices i. Now the problem reduces to finding an efficient way to get that information for all pairs u-v. This can be done by going through all edges i-j that is provided, and for each k such that j-k is connected, then we increase M[i][k] by 1. Hence we have an \(O(VE + V^2)\) running time overall.

Problem E:
Discussion on Problem E

Problem F:
Discussion on Problem F