The handless (blindfolded ?) barman and his prankster intern

The problem

A handless barman has $$$n = 2^k$$$ glass placed in circle on a tray. Some of them are upside-down, some of them are right side up. He want every glass to be right side up, but he is handless. He needs the help of his intern. The barman can ask the intern to flip the glass in some set of positions. But the intern is a prankster ! He will rotate the tray (circularly shifting the positions of the glass) before performing the flips. The intern stops the game when every glass is right side up. Find a strategy for the barman to achieve this.

This problem can be instantiated in many ways, depending on the information the barman has (if he sees the glass / if he is totally blindfolded / if he knows the number of glass in right side up position).

You can see how it is linked with problem C of GCJ 2022 1B.

I want to add my polynomial point of view of this type of problem.

Solution when the barman isn't blindfolded

The barman sees the glass, how to solve the problem in $$$n$$$ rounds ?

Solution when the barman is blindfolded

The barman is blindfolded, how to solve the problem in $$$2^n - 1$$$ rounds ?

Solve(i) {
    if(i == n) return;
    Solve(i + 1)
    play (1 + X)^i
    Solve(i + 1);
}

I hope it's understandable. Of course, when we know more information, we can speed up this search by skipping sub-trees.

Generalizations

We can easily prove that when $$$n$$$ is not a power of $$$2$$$, the barman can't win. We can try to solve the problem with a group $$$G$$$ different than $$$\mathbb{Z} / n \mathbb{Z}$$$ (circular rotations) for the transformations performed by the intern : we want to study the nilpotent elements of the group algebra $$$F_2[G]$$$. For example, we can solve the problem on a giant tray, on which we have placed small trays in circle, on which we have placed the glass.

Fun story

Exactly three days before round 1B, I explained this polynomial approach to the Network and Optimization team in CWI. It's one of my favorite problems since it relates a combinatorics game with algebra and number theory. In fact, I have only presented the unblindfolded case to the N&O team, and only mentioned the blindfolded case. A member of the team did the GCJ 1B and was really frustrated of this :p He only told it to me today, it's why I come after the storm.

Hi everybody,

I started to implement very general functions to use in programming competitions, such as this general reader/writer for C++ tuple, containers, and basic types~:

#include <iostream>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
using namespace std;


template <typename T>
constexpr bool is_tuple = false;

template<typename ... types>
constexpr bool is_tuple<tuple<types...>> = true;

template<typename A, typename B>
constexpr bool is_tuple<pair<A, B>> = true;

	
template<typename T> struct IsContainer { 
	typedef typename remove_const<T>::type test_type;
	template<typename A> static constexpr bool test(A* pt, decltype(pt->begin())* = nullptr, decltype(pt->end())* = nullptr) 
	{ return is_same<decltype(pt->begin()),typename A::iterator>::value && is_same<decltype(pt->end()),typename A::iterator>::value; }
	template<typename A> static constexpr bool test(...) { return false; }
	static constexpr bool value = test<test_type>(nullptr);
};

template<typename T>
constexpr bool is_container = IsContainer<T>::value;


template <typename T>
constexpr bool is_string = is_same<T, string>::value;

template<typename>
struct to_mutable { };

template<typename... Ts>
struct to_mutable<tuple<Ts...>> {
    using type = tuple<typename remove_cv<Ts>::type...>;
};

template<typename... Ts>
struct to_mutable<pair<Ts...>> {
    using type = pair<typename remove_cv<Ts>::type...>;
};


string readline() { string value; getline(cin, value); return value; }

template<typename T, typename ...Args> typename enable_if<!is_tuple<T> && (!is_container<T> || is_string<T>), T>::type read() {
	T value;
	cin >> value;
	return value;
}

template<typename T, typename ...Args> typename enable_if<is_tuple<T>, T>::type read(Args ...args);
template<typename T, typename ...Args> typename enable_if<is_container<T>, T>::type read(size_t N, Args... args);

template<typename T> typename enable_if<is_container<T> && !is_string<T>, T>::type read() { 
	size_t N = read<size_t>();
	return read<T>(N);
}

template<typename X, size_t I = 0, typename ...Args, typename enable_if<is_tuple<X>, X>::type* = nullptr>
typename enable_if<I == tuple_size<X>::value, typename to_mutable<X>::type>::type read_tuple(Args... args) { return typename to_mutable<X>::type(); }

template<typename X, size_t I = 0, typename ...Args, typename enable_if<is_tuple<X>, X>::type* = nullptr>
typename enable_if<I < tuple_size<X>::value, typename to_mutable<X>::type>::type read_tuple(Args... args) {
	auto tmp = read<typename tuple_element<I, typename to_mutable<X>::type>::type>(args...);
	typename to_mutable<X>::type value = read_tuple<X, I + 1>(args...);
	get<I>(value) = tmp;
	return value;
}

template<typename T, typename ...Args> typename enable_if<is_tuple<T>, T>::type read(Args... args) { return read_tuple<T>(args...); }

template<typename T, typename ...Args> typename enable_if<is_container<T>, T>::type read(size_t N, Args... args) { 
	T container;
	for(size_t i = 0;i < N;i++) { 
		*inserter(container, container.end()) = read<typename T::value_type>(args...);
	}
	return container;
}


void flush() { cout << flush; }

void writesp() { cout << " "; }
void writeln() { cout << "\n"; }

template<typename T> void writesp(const T& value);
template<typename T> void writeln(const T& value);

template<typename T, typename enable_if<!is_container<T> && !is_tuple<T>, T>::type* = nullptr> 
void write(const T& value) { cout << value; }
void write(const string& value) { cout << value; }
void write(const char* value) { cout << value; }

template<typename T, typename enable_if<is_container<T>, T>::type* = nullptr> void writerow(const T& value) { 
	typedef typename T::const_iterator It; 
	for(It it = value.begin();it != value.end();it++) { writesp(*it); }
}

template<size_t I = 0, typename X, typename enable_if<is_tuple<X>, X>::type* = nullptr>
typename enable_if<I == tuple_size<X>::value, void>::type writerow(const X& t) {}
template<size_t I = 0, typename X, typename enable_if<is_tuple<X>, X>::type* = nullptr>
typename enable_if<I < tuple_size<X>::value, void>::type writerow(const X& t) { writesp(get<I>(t)); writerow<I + 1>(t); }

template<typename T, typename enable_if<is_container<T>, T>::type* = nullptr> void writecol(const T& value) { 
	typedef typename T::const_iterator It; 
	for(It it = value.begin();it != value.end();it++) { writeln(*it); }
}

template<size_t I = 0, typename X, typename enable_if<is_tuple<X>, X>::type* = nullptr>
typename enable_if<I == tuple_size<X>::value, void>::type writecol(const X& t) {}
template<size_t I = 0, typename X, typename enable_if<is_tuple<X>, X>::type* = nullptr>
typename enable_if<I < tuple_size<X>::value, void>::type writecol(const X& t) { writesp(get<I>(t)); writerow<I + 1>(t); }

template<typename T, typename enable_if<!is_container<typename T::value_type> && !is_tuple<typename T::value_type>, T>::type* = nullptr> void write(const T& value) { writerow(value); }
template<typename T, typename enable_if<is_tuple<T>, T>::type* = nullptr> void write(const T& value) { writerow(value); }

template<typename T> void write2d(const T& value) {
	typedef typename T::const_iterator It; 
	for(It it = value.begin();it != value.end();it++) { writeln(*it); }
}

template<typename T, typename enable_if<is_container<typename T::value_type>, T>::type* = nullptr> void write(const T& value) { write2d(value); }
template<typename T, typename enable_if<is_tuple<typename T::value_type>, T>::type* = nullptr> void write(const T& value) { write2d(value); }

template<typename T> void writesp(const T& value) { write(value); writesp(); }
template<typename T> void writeln(const T& value) { write(value); writeln(); }


void fast_io() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }


int main() {
	fast_io();

	int nbRows = read<int>(), nbCols = read<int>();
	auto grid = read<vector<vector<int>>>(nbRows, nbCols);

	write(grid);
	return 0;
}

The final goal is to write the minimum amount of code to describe an algorithm to the machine, by having a big library of algorithms I can use. I have a little tool that selects in the final code only the parts I need.

To use write, it is sufficient to call it with your variable. If you want to print a newline, or a space at the end, use writeln or writesp.

To use read, give the type you want to read between < and >. If you want to read a container (a STL-structure with begin() and end()), you can give sizes to the function, otherwise it'll read the size from the standard input.

This code works with many types, for examples, map<string, vector<pair<int, double>>>, but be aware that some structures (like priority_queue) aren't supported because they don't have begin() or end(). Keep also in mind that if you give sizes as arguments to your functions, they will be interpreted by order of depth in the template definition, but things like pair<vector<int>, vector<int>> will not work with given (different) sizes.

If enough people are interested in such implementations, I'll continue to publish them on my blog. If you find any bug, or if you think another structure should be able to be read/written, please leave a comment.

Thank you for reading.