Day 7: M-LIS

4.7

3 votes
Dynamic Programming and Bit Masking, Dynamic programming, Algorithms, Medium-Hard, Dynamic Programming
Problem

This is a normal programming problem, a deterministic solution exists

You are given an array A of size N. Now, you may know of the LIS problem already. Today, you need to solve a modified version of this problem.

Given the array, you need to find the length of the longest increasing submask subsequence of this array, and also find any such subsequence. We call an increasing subsequence a submask subsequence, if :

Let the elements picked be A[k1],A[k2],A[k3]...A[kx],k1<k2<k3...<kx then A[ki]&A[ki1]=A[ki1] for all 2kx

Here , "&" denotes the BITWISE AND operation. You need to maximize x obeying the above constraints.

Input Format:

The first line contains a single integer T denoting the number of test cases. The description of each test case follows over 2 lines. The first line contains a single integer N denoting the size of the given array A , and the next line contains N space seprated integers denoting the elements of the given array.

Output Format:

For each test case, print the answer over 2 lines. On the first line, print a single integer k denoting the length of the subsequence. On the next line, print k space separated integers, where the ith integer denotes the index of the ith picked element of the subsequence. In the case of multiple answers, print any solution

Constraints:

1T2

1N100,000

0A[i]<216

Time Limit: 2.5
Memory Limit: 256
Source Limit:
Explanation

The elements 1,7 comprise of the required subsequence.

Editor Image

?