OLYMPIADS IN INFORMATICS, 2016, Vol. 10, pp. 87 - 98
© IOI, Vilnius University

ISSN 1822-7732

DOI: 10.15388/ioi.2016.06

Understanding Unsolvable Problem

Jonathan Irvin GUNAWAN

Undergraduate Student
School of Computing, National University of Singapore
Computing 1, 13 Computing Drive, Singapore 117417
e-mail: jonathan.irvin@yahoo.com

Abstract

In recent IOIs, there are several problems that seem unsolvable, until we realise that there is a special case to the problem that makes it tractable. In IOI 2014, the problem ‘Friend’ appears to be a standard NP-hard Maximum Independent Set problem. However, the graph is generated in a very special way, hence there is a way to solve the problem in polynomial time. There were several contestants who didn’t identify the special case in this problem, and hence were stuck at the problem. In this paper, we will study a well-known technique called reduction to show that a problem we are currently tackling is intractable. In addition, we introduce techniques to identify special cases such that contestants will be prepared to tackle these problems.

Keywords:

special case, unsolvable, NP-hard.


PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe


Copyright © International Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2016