During the latest USACO plat I managed to reduce the 2nd problem to the following:

You are given N restrictions and M truth/false variables. Restrictions are : given a1, a2... ak, at least one of them must be true for the restriction to be met ( so a1 or a2 or ... or ak == true). Each variable appears in at most 2 restrictions. What is the minimum number of variables which have to be true so that all restrictions are met?

Is there any (polynomial) solution to this problem ?

Hello.

I have recently encountered a problem where I need to binary search on a segment tree starting at any position( there are no updates, but there isn't enough memory for a sparse table). The problem is that the time limit does not allow a O(logn ^2) binary search , so I'm wondering if there is a different approach. The segment tree is for maximums, so transforming the binary search by including the prefix then removing it is ( I think) not possible.

Thanks for your help !