×

# Maximize OR of subset of array

 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

By Email:

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