Approach for HIRING and SAVJEW of COOK110B

Can someone share their approach for HIRING and SAVJEW.

In HIRING what I have done is for each element iterate over each of it’s submask and calculate the sum of all it’s value and thus we get "number of subsequence ending at i". But it gives WA. Can someone please point out my mistake in this solution?

Here is my submission.

Thanks.

The solution to HIRING is dp[i] += dp[j] if a[i] & a[j] = 0
Divide a mask into 2 parts, the first 8 bits and the last 8 bits. Then to calculate sum of submasks of a mask m, only care about submasks of the first 8 bits. And when adding to the preprocess array, only care about submasks of the last 8 bits. N * 2^8 should pass.

SAVEJEW: An obvious observation is we only prevent a theft if the item that was prevented from being stolen will never be stolen again. So for each item i, we want to know: If it exist at all times, what is the last heist it will be stolen? This can be easily done by binary search, and the complexity is O(N * log^2)

For HIRING I am also doing same thing. Can you suggest where my approach fails?

Submask don’t run through 0

1 Like

I don’t get the 2 masks thing. I did the dp, but I got TL because testing all a[i] & a[j] == 0 for i < j is too slow.

cnt(i, j) stores the sum of all dp[k] that a[k]'s first 8 bits is exactly i, while its last 8 bits is a submask of j.