Ok, with some help from ngfam_kongu I finally found solution to B. I think it is very beautiful.

• First, to avoid confusion of variable naming, let's restate the problem statement: We have N people, M machines. Person i comes at time Ai and leaves at time Bi. If a machine has set of people S, then its value is min(Bi for i in S) — max(Ai for i in S).
• Consider the machine with the person with largest value of Ai (maxAi). If we also fix the value of minBi for this machine, then we can know who can be assigned to this machine (everyone with Bi >= minBi). Also note that the more people we can assign to a machine, the better, so we can greedily take all of them.
• So now we can attempt the following DP:
  • Sort by increasing A
  • f(i, j) = maximum value if we assign people 1..i to j machines.
  • f(i, j) = max( f(i', j-1) + minBi — A(i) )

• There is something wrong with the formula: B is not increasing, so we could not take everyone with Bi >= minBi (if we sort by B, then we could not select person with maxAi). To fix this, observe that if we ignore all people i such that there exists j where Ai <= Aj < Bj <= Bi (lets call them bad people), then when we sort in increasing order of A, it is already sorted in increasing order of B. And the bad people can always be assigned to the some group without affecting the answer. (there is some corner case here, but I left it as an exercise :))

There's actually Youtube videos with misof and Per describing the solutions for said problems. :)

(I watched the ones for B and F. Quite nice. ^^)

Problem J is an easy version of Задача 9. Хэш-функция

Clearly none of the jury members had seen that problem before, otherwise we wouldn't have used it. It seems that two people came up with the same idea independently, I guess that great minds think alike :-)

Also, G and this kattis problem are the same, and I guess we were lucky one of our team members (TimonKnigge) remembered the solution, using order statistics trees in the nodes of a segmenttree.