PAIRING - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

A greedy strategy works here. Consider the pairs in the reverse of the order they appear. When considering a given pair, we greedily take it if neither of the chefs were in a used pair earlier. To see why this is optimum, suppose an optimum solution had a higher total value than our greedy solution. Let i be the greatest index where our solution disagrees with the optimum. Based on our greedy selection strategy, it must be that we took the i’th pair whereas the optimum doesn’t include the i’th pair. But then we can improve the cost of the optimum solution by deleting all pairs j with j < i and adding pair i. This is an improvement because of the exponentially increasing values of the pairs: 2^1 + 2^2 + … + 2^{i-1} is strictly smaller than 2^i. This contradicts optimality of the considered solution.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2 Likes
2

note: it is already obivous that chef will start from the highest i’th pair to keep food at its best quality(quality of food=total pow(2, i)). so start from last (m-1’th) index, that index certainly will be on pairing list of chef(d[i]). go on till 1st(0’th) index of pairings, meanwhile on each check whether any of those potential pairs (u, v) have been used before, if not(if(c[a[i]]==0 && c[b[i]]==0)), then add those pairs on the chef’s list(d[i]++), and mark those pairs as used(c[a[i]]++, c[b[i]]++). at the end, starting from beginning to the end(for(int i=0; i<m; i++) check whether that index of pairs included on the chef’s list (if(d[i])), if yes, then print that index.