1001
1002
1003
1004
1005
1006
1007
1008
In this problem, we must remove edges as many as possible and assign each of the K monkeys to the vertices so that all the monkeys are directly connected to at least one another monkey by the remaining edges. So, we must work out the maximum bipartite matching of all the vertices first. Let’s denote the size of maximum bipartite matching S. Then, we can choose T= min(K / 2, S) pairs of matched vertices and assign 2 * T monkeys to that vertices and assign all the other monkeys to the remaining vertices which are directly connected to already occupied vertices. Hence, the optimal answer is T + (K – 2 * T) = K - T.
1009
The number of points in the left side of the line is not changed. (we assume this number is p.) We call the points are P1, P2, … Pn and the line is L and one line vertical with L is L1. If we project the points P1, P2, … Pn to the line L1, then we can get n points Q1, Q2, … Qn on the line L1. (some points can be same.) We can sort Q1, Q2, … Qn from left to right and we can get n points R1, R2, … Rn. The point from P1, P2, … Pn corresponding with Rp is the rotating centre. So you must find this points array R1, R2, … Rn every time. Initially you can get this array sorting all points by x coordinate, then every time some pairs of points can be swapped, so you must find and swap these pairs. After the line rotates 2π, then the rotating centres array will be repeated, so you may find the rotating centres array until the line rotates 2π. Every pair of points will swap exactly two times so the time complexity is O(n*n).
1010
In this problem, we must assign each task in optimal way so that minimize the number of working machines first and when we use minimum number of machines, also minimize the total working time of all machines. So, we can use greedy method to solve this problem. First, we must sort all the tasks in increasing order of their starting time. Then, selecting the tasks in that order, we must choose the machine which is available to assign current task and most recently finished its working, and assign current task to that machine. When there isn’t such machine, we must assign current task to a new machine. By doing so, we can minimize both the number of working machine and total working time.
1011
