Hackerrank option

If I do not persist in expressing some dissatisfaction, bitterness, or despair about reality, life becomes so hypocritical that it has no sincerity at all.

Create at: 2017-10-06 14:35:49

Kingdom Division

Given a tree, colour every vertex 0 or 1. A vertex’s adjacent vertices cannot all have the opposite colour, because that arrangement causes a war. Count the valid colourings.

dp[x][0/1][0/1] represents whether, when vertex x has colour 0 or 1, all its neighbours have the other colour. 0 means isolated; 1 means it has a neighbour of the same colour.

During transitions, maintain validity at all times. The count for the state with an adjacent same-colour vertex is the total minus the isolated state.

int n;
vector<int>edge[maxn];
ll dp[maxn][2][2];
// col 0 1
// 0: out of limb
// 1: has neighbor

void hmod(ll & x)
{
	x = (x%mod+mod)%mod;
}

void dfs(int x,int fa)
{
	int cnt = 0;
	for(int i=0;i<edge[x].size();i++)
	{
		int nxt = edge[x][i];
		if(nxt == fa)continue;
		dfs(nxt,x);
		cnt++;
	}
	if(cnt==0)
	{
		dp[x][0][0]=1;
		dp[x][1][0]=1;
		return;
	}
	ll sum1 = 1,sum2 = 1;
	dp[x][0][0] = dp[x][1][0] = 1;
	for(int i=0;i<edge[x].size();i++)
	{
		int nxt = edge[x][i];
		if(nxt == fa)continue;
		dp[x][0][0] = dp[x][0][0]*dp[nxt][1][1];
		hmod(dp[x][0][0]);

		dp[x][1][0] = dp[x][1][0]*dp[nxt][0][1];
		hmod(dp[x][1][0]);

		sum1 = sum1*(dp[nxt][1][1]+dp[nxt][0][0]+dp[nxt][0][1]);
		hmod(sum1);

		sum2 = sum2*(dp[nxt][1][1]+dp[nxt][1][0]+dp[nxt][0][1]);
		hmod(sum2);
	}
	dp[x][0][1] = sum1 - dp[x][0][0];
	hmod(dp[x][0][1]);

	dp[x][1][1] = sum2 - dp[x][1][0];
	hmod(dp[x][1][1]);
}

void solve()
{
	sa(n);

	repp(i, 1, n - 1)
	{
		int x, y;
		sa(x), sa(y);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	dfs(1, -1);
	ll ans = (dp[1][0][1] + dp[1][1][1]) % mod;
	printf("%lld\n", ans);
}

Prime XOR

There are 100,000 numbers, each in [3500,4500]. Count the subsets whose XOR is prime.

Because every value lies in [3500,4500], record only their counts and use 0/1 knapsack transitions over those counts.

int vis[maxn];

void init()
{
	int up = 1e4;
	for(int i=2;i<=up;i++)
	{
		if(vis[i])continue;
		//if(i>=2048&&i<=8192)cout<<i<<endl;
		for(int j=i+i;j<=up;j+=i)
		{
			vis[j]=1;
		}
	}
}

int n;
int val[maxn];
int dp[1005][8200];
void solve()
{
	sa(n);
	memset(val,0,sizeof(val));
	repp(i,1,n)
	{
		int x;
		sa(x);
		val[x]++;
	}
	dp[0][0]=1;
	repp(k,3500,4500)
	{
		int i = k-3500+1;
		for(int pre=0;pre<=8192;pre++)
		{
			dp[i][pre] = 1LL*(val[k]/2+1)*dp[i-1][pre]%mod;
		}
		for(int pre=0;pre<=8192;pre++)
		{
			dp[i][pre^k] += 1LL*(val[k]+1)/2*dp[i-1][pre]%mod;
			while(dp[i][pre^k]>=mod)dp[i][pre^k]-=mod;
		}
	}
	int ans=0;
	for(int i=2;i<=8192;i++)
	{
		if(vis[i]==0)
		{
			ans+=dp[1001][i];
			ans%=mod;
		}
	}
	cout<<ans<<endl;
}

Fair Cut

Choose $k$ of $n$ numbers as one set and leave the rest as another, minimising the value between the two sets.
$$
f(I)=\sum_{i\in{I}}\sum_{j\in{J}}|a_i-a_j|
$$

I initially considered DP too, but did not know how to handle the absolute value.

I should have seen it: sort first, then each number’s contribution becomes known.

ll n,k;
ll dp[3005][3005];
ll val[3005]; 

void solve()
{
	scanf("%lld%lld",&n,&k);
	repp(i,1,n)
	{
		scanf("%lld",&val[i]);
	}
	sort(val+1,val+n+1);
	memset(dp,0x3f,sizeof(dp));

	dp[0][0]=0;
	repp(i,1,n)
	{
		repp(j,0,i-1)
		{
			ll t1 = dp[i-1][j] + val[i]*(i-1 -j-(n-k-(i-1 -j)));
			dp[i][j+1]=min(dp[i][j+1],t1);

			ll t2 = dp[i-1][j] + (val[i]*(j-(k-j)));
			dp[i][j]=min(dp[i][j],t2);
		}
	}
	printf("%lld\n", dp[n][k]);
}

Find the Running Median

set defeated me; multiset solved it.

The solution actually uses priority_queue.

vector<double> runningMedian(vector<int> a) {
  vector<double>ans;
  multiset<double>small;
  multiset<double>big;
  double med = 0;
  for(int i=0;i<a.size();i++) {
    if(i==0) {
        big.insert(a[i]);
    } else {
        if(a[i]>=med){
            big.insert(a[i]);
        } else {
            small.insert(a[i]);
        }
    }

    while(big.size() > small.size() + 1) {
      int x = *big.begin();
      big.erase(big.begin());
      small.insert(x);
    }
    while(small.size() > big.size() + 1) {
      auto g = small.end();
      g--;
      big.insert(*g);
      small.erase(g);
    }
    int sz1 = small.size();
    int sz2 = big.size();
    if((sz1 + sz2) % 2) {
      if(big.size() > small.size())
       {
           med = (*big.begin());
        ans.push_back(1.0*(*big.begin()));
       }
      else {
        auto g = small.end();
        g--;
        med = (*g);
        ans.push_back(1.0*(*g));
      }
    } else {
      auto g = small.end();
      g--;
      med = 1.0*(*g + 1.0*(*big.begin()))/2.0;
      ans.push_back(med);
    }

  }
  return ans;
}

Other Solution:

priority_queue<int, vector<int>, greater <int> > min_heap;
priority_queue<int> max_heap;
void add(int a)
{
    if( max_heap.size() && a >= max_heap.top())
        min_heap.push(a);
    else
        max_heap.push(a);

    if(abs(max_heap.size() - min_heap.size()) > 1)
    {
        if(max_heap.size() > min_heap.size())
        {
            int temp = max_heap.top();
            max_heap.pop();
            min_heap.push(temp);
        }
        else
        {
            int temp = min_heap.top();
            min_heap.pop();
            max_heap.push(temp);
        }
    }
}