Solution Notes (Mark Gordon): This problem was a not-so-thinly veiled bin packing problem which is one of the classic NP hard problems. This indicates that the expected solution is probably going to be exponential which is consistent with N being relatively small.

An initial approach to this problem would be a DP solution with the state given by the subset of cows that still need to ride the elevator. At each state we try each way of filling the elevator with some of the remaining cows. However a little math and we find this solution is O(N * 3^N) which we can reduce to O(3^N) with some pre-computation.

However a faster solution exists that is based on 'quick' computation of the 'Mobius transform', f(s) -> f'(s), of a function defined on subsets of a set in O(N * 2^N) time.

First we can precompute the sum of each subset of the cows, call it sum(s). Then let g_k(s) = sum(s) if s can be transported in k elevator rides and 0 otherwise. By changing the sum to max in the Mobius transform we can easily test if s can be transported in k+1 elevator rides by checking if sum(s) - g'_k(s) <= W. Using that we compute g_k+1 and continue on until all the cows can be transported.

To compute the Mobius function efficiently we'll use what we'll call the Mobius DP. Suppose our set has elements 1 through n. Then during the stages of Mobius DP we'll compute f'_k(s) to be like the Mobius transform except with the added constraint that the difference of s and t must only be elements no larger than k. From that definition we see that f'_0 = f and f' = f'_n. Finally f'_k+1 can be computed from f'_k as

The Mobius DP takes O(N * 2^N) time and so the overall computation takes O(N^2 * 2^N) and allows us to extract one elevator ride from an optimal solution. As our runtime is exponential and our problem size is shrinking the runtime remains O(N^2 * 2^N).

Below is my solution which produces the lexicographically least solution.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 18

int C[MAXN];
int D[MAXN];
int SUM[1 << MAXN];
int A[1 << MAXN];

void solve(int N, int W, bool top) {
  if(!N) return;

  memset(A, 0, sizeof(int) << N);
  for(int i = 0; i < 1 << N; i++) {
    for(int j = SUM[i] = 0; j < N; j++) {
      if(i & 1 << j) {
        SUM[i] += C[j];
      }
    }
  }

  int all = (1 << N) - 1;
  for(int res = 1; ; res++) {
    if(res > 1) for(int i = 0; i < N; i++) {
      int s = all ^ 1 << i;
      int* B = A + (1 << i);
      for(int j = s; j; j = j - 1 & s) {
        B[j] = max(B[j], A[j]);
      }
    }
    if(SUM[all] - A[all] <= W) {
      if(top) cout << res << endl;
      for(int i = 0; i < 1 << N; i++) {
        if(A[i] == SUM[i] && SUM[all] - SUM[i] <= W) {
          cout << N - __builtin_popcount(i);
          int p = 0;
          for(int j = N - 1; j >= 0; j--) {
            if(~i & 1 << j) {
              cout << ' ' << D[j];
            }
          }
          for(int j = 0; j < N; j++) {
            if(i & 1 << j) {
              C[p] = C[j];
              D[p++] = D[j];
            }
          }
          cout << endl;
          solve(p, W, false);
          break;
        }
      }
      break;
    }
    for(int i = 0; i < 1 << N; i++) {
      A[i] = SUM[i] - A[i] <= W ? SUM[i] : 0;
    }
  }
}

int main() {
  freopen("skyscraper.in", "r", stdin);
  freopen("skyscraper.out", "w", stdout);

  int N, W; cin >> N >> W;
  for(int i = 0; i < N; i++) {
    cin >> C[i];
    D[i] = 1 + i;
  }
  reverse(C, C + N);
  reverse(D, D + N);

  solve(N, W, true);
}