Imthiyash786's blog

By Imthiyash786, 5 weeks ago, In English

Given an array of n integers $$$a_1,a_2,...a_n$$$ output the minimum size of the subsequence $$$b = {b_1,b_2,..b_k}$$$ of array a such that the following condition holds

$$$b_1$$$ & $$$b_2$$$ & $$$b_3$$$ &.....& $$$b_k = 0$$$

constraints : 1 <= n <= 1e5, 1 <= $$$a_i$$$ <= 1e4

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

is there a link for the problem?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No I reduced some other problem to this and couldn't find solution to this task.

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

This problem is the OV problem with $$$\log$$$ bits, it cannot be solved better than $$$\mathcal O(nv)$$$.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I get it that the time complexity should $$$O(nv)$$$, but I need the solution can you please post if you get one!

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I am not sure this solution is right, so do not blame me if I wrong(XD.
Due to I do not know link to test, I can only give you this $$$O(v^2)$$$ solution of DP

//Retired?
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
signed main(){
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n; cin >> n;

    vector<int> a(n + 1);
    vector<int> dp((1 << 14) | 1, 1e9);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        dp[a[i]] = 1;
    }

    sort(a.begin() + 1, a.end());
    a.erase(unique(a.begin() + 1, a.end()), a.end());
    n = a.size() - 1;

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= (1 << 14); j++){
            dp[j & a[i]] = min(dp[j & a[i]], dp[j] + 1); 
        }
    }

    cout << (dp[0] == 1e9 ? -1 : dp[0]) << '\n';

    return 0;
}
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, it is right, I have a friend created this problem before, I test it and get ac.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      share the link of this problem

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is a Chinese problem,here is link:https://ac.nowcoder.com/acm/problem/270788