### bus_u_he's blog

By bus_u_he, history, 2 weeks ago,

I recently took an OA with a question involving n arrays of size m. The task was to create an array A of size n by choosing one element from each array. Then, we had to find the minimum value of A0 | A1 | A2 | ... | An-1 (bitwise OR of all elements in A) and n<1000,m<1000 and each element in those n arrays is less than 100000.

I used recursive DP, considering two options: either go forward in the same array or pick the current element and move to the start of the next array. However, this approach gave incorrect results for 3 out of 10 test cases. Can anyone help me identify what I missed or if I made an unforced error?

• +9

 » 2 weeks ago, # |   0 Auto comment: topic has been updated by bus_u_he (previous revision, new revision, compare).
 » 2 weeks ago, # |   0 Share your code
•  » » 2 weeks ago, # ^ |   0
 » 2 weeks ago, # |   +11 If you managed to take some minimum value from the first array, that does not mean that it is the best idea to use that value. Ex: first array: [1, 2], second array: [2, 2]. If you take 1 from the first array because it is smaller, then you get the answer of 3, but the minimum value is 2.One corect solution is as follows:For each bit from most signifficant to least signifficant check if there is some element in each array that has that bit off. If so, then there is some way to pick the numbers so you don't have this bit set in the answer. Then you need to reduce each array. Remove the numbers that have that bit set since if you take them, you break the minimality.If however there is some array where no element has the bit off then there is no way to get this bit off in the final solution. No array reduction is required, as you can take either on or off numbers without influencing this bit.This way you build both the minimum value, and (can then build) all the posibilities (each array only has "useful" values at the end so picking any one of them from each array constitutes a good solution)The time complexity is $O(N\cdot M\cdot \log A)$ where $A$ is the biggest value in the input.
•  » » 2 weeks ago, # ^ |   +1 thanks a lot mate, now I know why I was wrong
•  » » 2 weeks ago, # ^ |   -8 But where is his solution wrong? He is checking all possible cases, his test case may be failing because of max limit of integer.
•  » » » 2 weeks ago, # ^ |   +1 No, he is not. He is doing a greedy and masking it as a dp.
•  » » » » 13 days ago, # ^ |   +1 I am trying to code up your logic but couldn't come up with a solution can you please send the code or give a little more detailed answer please
•  » » » » » 13 days ago, # ^ |   +1 The breaking logic can also be made with some booleans but I personally prefer this way. Tell me if you still don't understand something int minOr(std::vector >& v) { int bit, ans = 0, i, j, N = (int)v.size(); for(bit = 16/*16 is the biggest bit one value can have set in your problem*/;bit > -1;--bit) { for(i = 0;i < N;++i) { for(j = 0;j < (int)v[i].size();++j) { if(!((v[i][j] >> bit) & 1)) // the i'th array has at least one element with that bit off { j = (int)v[i].size(); // break } } if(j == (int)v[i].size()) // did not break { i = N; // break } } if(i == N) // did not break { // All arrays have some element with that bit off for(i = 0;i < N;++i) { for(j = 0;j < (int)v[i].size();++j) { if((v[i][j] >> bit) & 1) // Bad element. Remove { std::swap(v[i][j], v[i].back()); v[i].pop_back(); --j; } } } } else { // This bit is unavoidable ans |= 1 << bit; } } return ans; } 
•  » » » » » » 12 days ago, # ^ |   0 Thanks a lot ! Now I understand the code and its intuition as well, all thanks to you. You are truly "The-Winner." By the way, was this logic part of some theoretical stuff or ad-hoc? Again, orz
•  » » » » » » » 12 days ago, # ^ |   +1 The logic/intuition comes from a data structure called a trie (I think it is also known as a prefix tree). Here is a wikipedia article. It is very useful
 » 2 weeks ago, # |   0 what were the constraints? I have an O(32 * n * m * log(m)) algorithm. Idea is similar to above comment but I use sets, so additional log(m) factor.
 » 2 weeks ago, # |   0 for the 2nd if statement return INT_MAX instead of 1e7. Input : 1 4 4 434581591 366413825 351340371 81099756 443064262 783025542 980413631 511982969 956581993 979244577 507833677 890948799 808418018 212545955 683065029 351233430 Expected Output : 520093695 Your Output : 10000000 
•  » » 13 days ago, # ^ |   +1 i have edited the blog to clarify the constraints
•  » » 12 days ago, # ^ |   0 Your expected output is wrong, I don't know how you got there. Stress test it or find my implementation below, both produces 520093663.
 » 2 weeks ago, # |   0 Auto comment: topic has been updated by bus_u_he (previous revision, new revision, compare).
 » 12 days ago, # |   0 Implementing The-Winner's solution cuz I liked it. Other than that, maybe it can be useful for some people: Code#include using namespace std; using i64 = long long; void solve() { int n, m; cin >> n >> m; vector> g (n, vector (m)); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { cin >> g[i][j]; } } //checks if each array has atleast one element where the bth bit is off or not auto check = [&] (int b) -> bool { vector> v (n); for (int i = 0; i < n; ++i) { for (int x: g[i]) { if ((x & (1 << b)) == 0) { v[i].push_back(x); } } if (v[i].size() == 0) return false; } g = v; return true; }; int ans = 0; for (int b = 16; b >= 0; --b) { if (!check(b)) ans |= (1 << b); } cout << ans << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; } 
 » 12 days ago, # |   0 If you want to solve another problem that uses an idea similar to the one suggested by The-Winner you can try this.
 » 12 days ago, # |   0 I think we can use a greedy idea.