The Coaches

The IOITC is an informatics training camp in which qualifying candidates from the Indian Computing Olympiad participate. In this note, I will discuss the problems encountered by the participants.

The problems may not be all original, although the TST problems and the APIO problems, definitely are. Please do not be discouraged to interpret and solve the problems in your own way; my description of them may not be accurate and only serves an illustrative purpose.

Problems Discussed Only

Given a graph, check if there exists a pair of vertices connected by three vertex disjoint simple paths
Given a graph, and two vertices on it, check if there exists a simple path connecting them consisting of an odd number of edges

Warmup Problems

Homogeneous Maintain a multiset supporting fast checking if it contains multiple kinds of items or an item twice
Password Dynamic Programming - Generating strings satisfying constraints

Practice Problems

Circles Computational Geometry - Projecting overlapping circles into a discretized grid
Hill Numbers Dynamic Programming - Enumerating numeric strings satisfying a certain constraint on their digits
Caves and Miners Trees - Finding and adjusting the weight of a node to make sure all its children satisfy a certain constraint
Electronic Pollution Determining if a set of simultaneous equations allow solving a given equation
Nice Inversions Minimizing inversions on ordered pairs
Racing Gems Maximum Increasing Subsequence - Finding a path that allows maximum accumulation of points along a grid
Mind Craft Modified Dijkstra - Minimum Cost reaching a vertex based on a dependency list
Lexicographic Toposort Add edges to a Directed Acyclic Graph to maximize an objective function regarding its topological sort
Tree Orientation Centroid Decomposition - Direct a given tree to maximize the number of pairs of vertices which can be reached from one to the other

Asian Pacific Informatics Olympiad Problems

Boats Dynamic Programming - Enumerating sequences satisfying constraints
Fireworks Trees - Minimal Cost modification of edges of a tree to ensure that all paths from the root to the leaves are equal
Gap Designing a function to find the maximum gap between consecutive elements of an array not directly accessible

Team Selection Test Problems

I am not supposed to be discussing these here right now. Will be uploading these later

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Problems from International Olympiad in Informatics Training Camp (India) 2016

Problems Discussed Only

Warmup Problems

Practice Problems

Asian Pacific Informatics Olympiad Problems

Team Selection Test Problems

Comments