Codeforces 8E Beads

This is a difficult one.

First. If we have a method “solve”, given some fixed digits and given some undetermined digits in the array, we know how many distinct beads combinations there are, we can have this skeleton algorithm:

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <string>
#include <memory>  
#include <cstring>
using namespace std;

#include <stdio.h>
#include <stdlib.h>


int n, k;
int a[55];
long long c[55][55][2][2];
bool visited[55][55][2][2];



int main() {
	cin >> n >> k;
	k++; // because 0000000..000 doesn't count
	memset(a, -1, sizeof(a));
	a[0] = 0; //first one must 0.
	if (solve(0, n - 1, 0, 0) < k) {
		cout << -1 << endl;
		return 0;
	}
	for (int i = 1; i < n; ++i) {
		memset(visited, 0, sizeof(visited));
		a[i] = 0; 
		if (k > solve(0, n - 1, 0, 0)) {
			k -= solve(0, n - 1, 0, 0); //remove all a[i] == 0 possibilities.
			a[i] = 1; //so it has to be 1.
		}
	}
	for (int i = 0; i<n; i++)
	{
		cout << a[i];
	}
	cout << endl;
	return 0;
}

 

The way to implement solve() is based on following critical observations:

  1. We want to know how many groups there are, i.e. how many smallest numbers – i.e. how many numbers will not become smaller if transformed by 3 operations: revert, invert or revert+invert.
  2. Reduce and conquer: each time we enumerate the left-end and right-end of current range of array. Then reduce the size of the problem by 2.
  3. 0….1 can always be used when enumerating. Because it cannot be made smaller by any of the 3 operations.
  4. 0….0 can always be used.
  5. If there is an outer 0…1, then 1…0 can be used in following enumerations. i.e. 0…1….0…1 because any operation cannot make the number smaller. (yes i know it’s related to 0…0 and 1…1 placements but you will understand if you are patient. also this is not a complete proof. you will need to do induction if you want one.)
  6. If there is an outer 0…0, then 1…1 can be used. i.e. 0…1…1…0
  7. If we make sure 1…1 is always enclosed by some 0…0, and 1…0 is always enclosed by some 0…1, then the result number is a smaller number in some group. (and all such numbers meet this condition.)
  8. So we have the following implementation of solve() function
long long solve(int l, int r, int can10, int can11) { 
	//if there has been 0---0, we can start to put 1---1 because rev-inv will make a larger number. (0---1 and 1---0 keep same)
	//if there has been 0---1, we can start to put 1---0 because rev will make a larger number. (0---0 and 1---1 keep same)
	if (l > r) {
		return 1;
	}
	if (visited[l][r][can10][can11]) {
		return c[l][r][can10][can11];
	}
	visited[l][r][can10][can11] = true;
	long long& ans = c[l][r][can10][can11];
	ans = 0;
	for (int nl = 0; nl < 2; ++nl) {
		if (a[l] != -1 && a[l] != nl) { //already fixed.
			continue;
		}
		for (int nr = 0; nr < 2; ++nr) {
			if (a[r] != -1 && a[r] != nr) { //already fixed.
				continue;
			}
			if (!can10 && nl > nr) {
				continue;
			}
			if (!can11 && nl && nr) {
				continue;
			}
			if (l == r && nl != nr) {
				continue;
			}
			ans += solve(l + 1, r - 1, can10 || nl < nr, can11 || (!nl && !nr));
		}
	}
	return ans;
}

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s