You are not logged in. Please login at www.codechef.com to post your questions!

×

# Maximize OR of subset of array

 0 We are given an array of length N. We have to find the minimum length subset( not subarray) of array with maximum OR value. N bound till 10^5. Ai<=10^6 Only one example was given: Array elements are 1,2,3,4,5 possible max OR is 7. Minimum length subset are (5,2) and (3,4) asked 21 Jun '18, 18:06 4★vbt_95 440●6 accept rate: 27% Can u please post the link of the question? (21 Jun '18, 19:16) link is not active now. It was a hiring question (21 Jun '18, 19:17) vbt_954★ @vivek_1998299 I think we can solve it using Dynamic Programming, though I am not sure as I can not verify it because I did not find this problem posted any online judge/ interview site where I can submit solution. Would like to know your insight. (22 Jun '18, 01:09) sorb19974★ I think I saw such a question in a past contest :/ . It involved dp. (22 Jun '18, 01:29) I tried a dp. Recursive with memoization. First i found out OR of all elements which is actually maximum. Then made a boolean array req which tells whether ith bit is required or not. Initally count=0(number of elements taken) and index=0. I call dp(req,0,0). For element at index i find out whether it can satisfy any required bit. If yes then there can be two cases- take it or not.So i return minimum of( dp(newreq,cnt+1, ind+1) and dp(req,cnt,ind+1). If not then there is no need to include that element so simply return dp(req,cnt,ind+1). (22 Jun '18, 02:07) vbt_954★ The terminating condition is if( index>= array length), check if req array has a true value or not. If yes that means we failed to obtain max OR so return Integer.MAX_VALUE( as we are taking min above). If there is no true value that means that the number is obtained so return count. (22 Jun '18, 02:09) vbt_954★ So you did not get a right answer? Where were you stuck? I am yet to appear for any interview but from what I have heard, interviewee is looking more for your approach to solve the question rather than question itself. And even with the Brute Force approach(O(2^N)) you must have got some partial acceptance from the interviewee? (22 Jun '18, 02:29) sorb19974★ 1 I faced the same problem in a hiring contest of a company I cracked and managed to get all the test-cases accepted with a simple hack in the O(n^2) algorithm by using a break whenever an element was useless (i.e did not increase the overall current value of OR of the subset in consideration). I am unable to find the code and think of the exact solution right now but it's surely not the optimal solution. I got lucky with the trick and all the test-cases barely passing. (22 Jun '18, 03:21) dwij285★ I really have no idea on how to solve this.Initially i thought ,that since this problem is reducible to set covering ,it must be np-hard,but since the set size is no more than 20,i think i could have an optimal solution,but i cant find it :( Like 1,2,3,4,5 can be represented as sets {1},{2},{1,2},{4},{1,4} and basically u want to get the set {1,2,4} taking union of as minimum sets as possible (22 Jun '18, 10:22) 2 and @vbt_95 the time complexity of your approach is 2^20 * 20 * n which will time out (22 Jun '18, 10:28) Yeah i know. That's why i said i tried a dp :( @dwij28 i think i could have optimized the solution a little bit more but then also it wouldn't be a optimal solution (22 Jun '18, 12:16) vbt_954★ Can anyone help please? (23 Jun '18, 14:37) vbt_954★ @vivek_1998299 @vijju123 can minimum bipartite vertex cover work in this problem? (26 Jun '18, 02:02) vbt_954★ Not sure dear :( (26 Jun '18, 13:46) Is the question link active now? (27 Jun '18, 15:10) @vivek_1998299 not yet (27 Jun '18, 16:30) vbt_954★ showing 5 of 16 show all

 1 The best I could think of is $3^{log(max(a_i))}$. finding the max or is easy. consider binary representation of a number to be it's mask. now for a mask m let dp[m] be minimum no. of elements required such that their or is a supermask of m. so if m=6=110. then both 2,4 and 2,5 are valid choice. notice that 2,5 produces 111 but is still valid as we need a super mask. now calculating the dp. First remove all duplicates in a. it's easy to see this won't change the answer. Initialize dp to infinity. Now for each element in a initialize dp[a$*i$] to 1 and also each of it's submasks. Now lets say a$_i$ has k bits set in it. then it has 2$^k$ submasks. so the entire initialization process costs $\Sigma*{k=0}^{k=20}$ C(20,k)2$^k$. this by binomial expansion is (1+2)$^{20}$ which is 3$^{20}$. Now start calculating each dp[m] in incresing order of no. of bits set in m. for each mask m consider every submask p. dp[m]=min(dp[m],dp[p]+dp[m^p]). this relation means if p can be obtained in n1 items and m^p(which is completment of p wrt m) can be obtained from n2 items. then since their or is m, m can be obtained in n1+n2 elements. again total no. of submasks if 2^k and therefore takes total time of 3^{20}. final answer is dp[OR]. If any part is not clear you can ask me. Or if I'm wrong point it out. This would work easily for a$_i$<=1e5 but will tl for 1e6. maybe someone can think of some optimization. answered 26 Jun '18, 04:15 298●1●9 accept rate: 8% Max ai is 10^6. So 3^20 will get TLE. (26 Jun '18, 11:41) vbt_954★ @praveenkumar12 Can u tell your idea,maybe we could optimize it to fit in TL. (26 Jun '18, 12:17)
 0 I guess it can be modelled as a vertex cover problem. We can easily find what is the maximum OR possible. Now keep only those bits and draw edges with the elements for which those bits are set. Now problem is finding minimum vertex cover. Correct me if I am wrong. answered 26 Jun '18, 13:38 1.8k●6●14 accept rate: 22% Could u please explain what are your vertices and edges? I thought this : vertices: each set bit i,and then n array elements edges: set bit i:to all array elements whose ith bit is set but for the example given above, we have edges: 0 th bit set:1,3,5 1 st bit set:2,3 2 nd bit set:4,5 but here the minimum vertex cover is {0th bit set,1st bit set,2nd bit set} I know i am missing something,could u please correct me? (26 Jun '18, 15:15) Yes you are right sadly it doesnt work. I have an alternate solution though. Let me think on it a bit before posting here because it might also be wrong xD (26 Jun '18, 16:08)
 0 Okay minimum vertex cover actually works. Model the problem as i told above. Now I am explaining why it gives correct answer. Focus on the defination of vertex cover. "Each edge must have an end point in the selected subset". Now assume after selecting a subset of vertices my ith bit doesnt get set(Note it must be set in actual ans i.e max OR). Now this in turn means no edge having end points in ith bit has a end point in the selected subset. WHY? Because if the edge had an end point and it was not ith bit then it must be a[j] where ith bit is set in a[j]. So ith bit gets set which is contradiction. Hence all the bits get set after considering the minimum vertex cover. Also it passes in time as E=nlogn here. answered 26 Jun '18, 14:30 1.8k●6●14 accept rate: 22% Is there any tutorial for learning minimum vertex cover properly? (26 Jun '18, 14:51) vbt_954★ sorry this doesnt work. Trying to think of some alternate approach :( (26 Jun '18, 16:08) @soham1234 is this a matching problem? (29 Jun '18, 16:05) vbt_954★
 0 Sorry, I'm was wrong. answered 27 Jun '18, 13:21 5★filyan 21●3 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×77

question asked: 21 Jun '18, 18:06

question was seen: 493 times

last updated: 29 Jun '18, 16:05