SPLIT - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

CHALLENGE

EXPLANATION

The problem is more commonly known as the necklace splitting problem that is often told with thieves trying to split a necklace with an even number of each jewel type so the two thieves get the same number of each jewel. Currently, no polynomial-time algorithm is known but is also not known to be NP-hard. There is one very interesting result concerning this problem. If d is the number of istinct ingredients/jewel types, then there is a way to cut the sandwich/necklace using at most d cuts [1]. However, the proof is non-constructive and does not provide a polynomial-time algorithm for finding these cuts. To get an idea what flavor these non-constructive are, it follows from the Borsuk-Ulam theorem which is like a very powerful generalization of Brouwer’s fixed-point theorem to higher dimensions.

The problem is known to be in PPAD [2] which roughly means that there is an algorithm that will find a solution using at most d cuts that
is, in some sense, similar in spirit to the Simplex algorithm for solving linear programs. The Wikipedia page on PPAD is a decent
starting point to learn more about problems in PPAD [3] if you are curious. It is an interesting complexity class between P and NP. There
is a notion of a problem being PPAD-complete and an interesting open problem is to determine if the necklace splitting problem is PPAD-complete or not.

  1. Alon, Noga; West, D. B. (December 1986). “The Borsuk-Ulam theorem and bisection of necklaces”. Proceedings of the American Mathematical
    Society 98 (4 pages=623-628).
  2. Christos Papadimitriou (1994). “On the complexity of the parity argument and other inefficient proofs of existence”. Journal of Computer and System Sciences 48 (3): 498-532. doi:10.1016/S0022-0000(05)80063-7
  3. http://en.wikipedia.org/wiki/PPAD

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

//