QUESTION 1. 
Construction: 12pts
Proof of correctness: 3pts

Many students got this question wrong. First we should focus on the problem of deciding 
if such an assignment exists. This in fact makes the problem simpler. 

Next we observe that there exists an assignment, in which we hire at least d candidates 
from each  group, if and only if there exists an assignment, in which we hire *exactly* d
candidates from each group. Thus, it suffices to construct a flow network to decide the 
relax problem where we need to hire *exactly* d candidates from each group. It should be
easier to construct a flow network for the relax problem.

==========================
A possible solution is the following flow network:
- Source s, sink t, vertices G_1,...,G_k to represent k groups, vertices c_1,...,c_n to 
represent n candidates, and vertices p_1,...,p_m to represent m positions.
- Edges from s to each g_i with capacity d; edges from each G_i to every candidate
c_j who belongs to G_i with capacity 1; edges from each candidate c_j to every position
p_l in the set C_j with capacity 1; edges from each position p_l to t with capacity 1.

Using this network, we can use the network flow to decide the problem as follows. 
We find a max-flow f of this network, and if for all i in {1,...,k}, f(s,g_i)=d, then 
we output YES (i.e. such an assignment exists). Otherwise, we output NO.

==========================
In the proof of correctness, we need to show two statements:
- If we have an assignment to the original problem (where "at least" d candidates
in each group are hired), then we can construct a flow f for the network such that for 
all i in {1,...,k}, f(s,g_i)=d.
- Conversely, if a flow f for the network such that for all i in {1,...,k}, f(s,g_i)=d, 
then we can construct an assignment to the original problem where "at least" d candidates
from each group are hired (we actually hire exactly d candidates from each group, but this 
is sufficient). 

It is very important to note that an assignment produced by a maximum flow might be 
*smaller* than a maximum assignment, since we force that f(s,g_i)<=d for all i. This is 
different from A3, where the assignment produced by a maximum flow is always a maximum
assignment for the original problem.

If your proof missed one of these two statements or if it's not clear what you're trying
to prove, I took away 1-3pts.

==========================
Another valid solution is to use a network flow with maximum and minimum flow constraints 
(as discussed in Tutorial #5) to require that all edges (s,g_i) in the above flow network 
have capacity at least d. Only 3 students tried this approach even though it seems more 
natural.


==========================
Unfortunately, other approaches that students tried didn't work. If this is the case,
you give up to 6/15 marks for a good attempt.



QUESTION 2.
Construction: 12pts
Proof of correctness: 3pts

Most students did well on this question. A possible LP solution is:

Objective: minimize d_1+d_2+...+d_n
Subject to:
b_i<=b_{i+1} 		for i=1,...,n-1
a_i-b_i<=d_i		for i=1,...,n
b_i-a_i<=d_i		for i=1,...,n

==========================
Notes: 
* We always have a_i-b_i>=0 or b_i-a_i>=0, so constraints d_i>=0 are redundant.
* The function d_1+d_2+...+d_n is already linear, so there's no need to add a variable d, 
a constraint d_1+d_2+...+d_n <= d, and then minimize d.

I didn't take away any mark for these redundancies. 
	
==========================
I took away 1pt, if you use the constraint b_1<=b_2<=...<=b_n (which is not yet in the 
proper form for a linear constraint) instead of
b_i<=b_{i+1} 		for i=1,...,n-1.


Another common mistake is to forget arguing that each solution b_1,...,b_n to the problem
corresponds to an LP solution with objective value exactly deviation(b_1,...,b_n). This
is very similar to the mistake that students made in Q2 of A3; unfortunately many students 
repeated the same mistake again. For this, I only took away 1pt. But this is a very 
serious mistake.

If your solution looks nothing like an LP, you get 0/15.