PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
CAKEWALK
PREREQUISITES:
GREEDY
PROBLEM:
Given a matrix b_{i, j}, find an array of integers a_{i} such that a_{i} or a_{j} is equal to b_{i, j} if b_{i, j} \neq -1.
EXPLANATION:
First, let’s look at what happens when b_{i, j} \le 1. Now, the following greedy solution works : Initialize a_{i} as 1 for all i. For each entry b_{i, j} = 0, mark a_{i} = 0 and a_{j} = 0. Leave the rest of the numbers as it is.
This works because we’re guaranteed that a solution exists, and thus we can just satisfy all the conditions b_{i, j} = 0 and since the remaining conditions are b_{i, j} = 1 (or -1 which we don’t care about), we can just greedily assign the remaining a_{i} as 1.
Now, how to solve the general version. It’s exactly the same as the easy version. We note that we can solve for each bit of the number separately, and each bit can be solved using the solution above. Thus, we can solve for each bit separately and combine the answers together in the end in O(n^{2}\log b_{i, j}).
In fact, with this observation, you can easily obtain an O(n^{2}) solution. (see the tester’s solution)
Time Complexity : O(n^2) or O(n^{2}\log b_{i, j})
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.