I'm sorry, looks like my internet provider blocks arena :(

What I did is as follows :

Made a recursive function with memorization (Dynamic Programming), which will return expected value given a subset of block (call it mask) and the face vector.

For each subset I calculated the result when a particular faces comes up with probability equal to 1/face.size() and for this face removed a subset, which sums to the number on this face, from mask, which will be most favorable (meaning which enable us create most of the numbers on the faces after removing the face).

I am NOT passing all testcases with this approach. Passing 6 out 7 given test cases.

Can anyone please explain where I am going wrong ?

Here is my code if you would like to have a look :

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

int test = 0;

class SubsetSumExtreme{
	public :
		int subset[4100];
		int perms[4100];
		double dp[4100];
		double getExpectation(vector <int> block, vector <int> face, int mask){
			if(dp[mask]!=-1.0) return dp[mask];
			double ans = 0.0;
			double n = (double)(face.size());
			int len_block = block.size();
			for(auto f : face){
				map < int, vector <int> > mp;
				for(int i = 0; i<(1<<len_block); i++){
					if((mask | i) == mask){
						if(subset[i]==f) mp[perms[mask-i]].push_back(i);
					}
				}
				if(mp.size()){
					for(auto p : mp.rbegin()->second){
						ans += getExpectation(block,face,mask-p)/n/mp.rbegin()->second.size();
					}
				}else{
					double z = 0.0;
					for(int i = 0; i<(len_block); i++){
						if(mask & (1<<i)) z+= block[i];
					}
					ans += z/n;
				}	
			}
			return dp[mask] = ans;
		}
		
		double getExpectation(vector <int> block, vector <int> face){
			sort(face.begin(),face.end());
			sort(block.begin(),block.end());
			int len_block = block.size();
			for(int i = 0; i<(1<<len_block); i++){
				int sum = 0;
				for(int j = 0; j<(len_block); j++){
					if(i & (1<<j)) sum += block[j];
				}
				subset[i] = sum;
				//cerr<<i<<" "<<sum<<endl;
			}
			for(int i = 0; i<(1<<len_block); i++){
				int count = 0;
				for(int j = 0; j<(1<<len_block); j++){
					if((i | j) == i){
						if(binary_search(face.begin(),face.end(),subset[j])) count++;
					}
				}
				perms[i] = count;
				//cerr<<i<<" "<<count<<endl;
			}
			for(int i = 0; i<(1<<len_block); i++) dp[i] = -1.0;
			return getExpectation(block,face,(1<<len_block)-1);
		}
};

I didn't understand the problem , didn't get the part about finding the minimum expected score . Can someone explain why the answer for {1,2,1} , {1,2} is 0.5 ?

The intended solution is like most submission.

Maybe it is too much like a brain teaser, but I think it is still legit to use it — at least it is kind of novel and the result (pass rate and score distribution) looks good.

First, let's binary search for answer. So problem reduces to finding if there exists a happy sublist with length at least m and value k.

For each number, we can compute the closest index on the left that has absolute value at most k, and the closest index on the right that has absolute value at most k.

For example, if the list is equal to [8,1,10,2,9,7], and k=2, then left = [-1,-1,0,1,2,4], and right = [2,3,4,6,5,6]. This is a pretty standard problem and can be solved using some binary indexed trees and takes O(n log n) time.

Now, consider the following pseudocode to check if all sublists are not happy:

def all_bad(s, e):
  if e-s <= m: # all subarrays are too short, so they are all bad
    return true
  find an index i such that left[i] < s and right[i] > e
  if no index exists: # all numbers are not lonely if we take the entire subarray
    return false
  # any subarray that contains index i will be bad, so we just need to check the two cases below.
  return all_bad(s, i-1) and all_bad(i+1, e)

This is correct, but it is too slow. In particular, the line for finding the index is too slow if we try the straightforward loop from s to e. Instead, let's just scan from both ends simultaneously. This now becomes O(n log n) (basic idea is the recurrence is now T(n) = T(a) + T(b) + min(a,b)).

Overall time complexity is O(n log^2 n).

You can sign up for the TopCoder Newsletter. You get all the information about upcoming contests (SRMs, Marathon etc) in advance, at least I do.