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

The Coaches 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

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

Note by Agnishom Chattopadhyay
3 years, 4 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. 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"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Great! (:clapping)

Sandeep Bhardwaj - 3 years, 4 months ago

Log in to reply

Thanks, Sandeep.

Agnishom Chattopadhyay Staff - 3 years, 4 months ago

Log in to reply

Are ypu sonewhere in that photo?

Ashish Siva - 3 years, 4 months ago

Log in to reply

@Ashish Siva Haha, I am flattered.

No, I was a student. Those are the coaches

Agnishom Chattopadhyay Staff - 3 years, 4 months ago

Log in to reply

@Agnishom Chattopadhyay You deserve to be a coach.

Ashish Siva - 3 years, 4 months ago

Log in to reply

@Ashish Siva Actually, my performance was so bad in the camp, that I am truly humbled with the experience.

Agnishom Chattopadhyay Staff - 3 years, 4 months ago

Log in to reply

@Agnishom Chattopadhyay Aww, anyway I am sure that your computer science skills rock.

Ashish Siva - 3 years, 4 months ago

Log in to reply

Interesting

Ayanlaja Adebola - 3 years, 4 months ago

Log in to reply

better

md mainu - 2 years, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...