## More Reference Materials

If you’ve finished reading the training materials on the website, take a look at the following resources to further improve your programming prowess.

## Free Online Courses

Participants may use the following free online courses and resources:

## Recommended Books

Further books may be found at the IOI’s Recommended Reading List.

Trainers and students alike are invited to contact NOI.PH by emailing us at [email protected] for any questions regarding the training material and on how to train for the contest.

## Introduction to Programming Contests

NOI.PH is almost like a math competition in the sense that contestants are given a problem to solve. Contestants must then prove that they know how to solve the problem by usually giving a numerical answer to the judges. However, the problem setters need to stick with small numbers so that the contestants can work out the answer by only using pen and paper. Because of this, some problems might be guessable. Given enough time, contestants might be able to stumble upon the correct answer using the Trial And Error (TAE) method. This means that some might get points even if they have no idea how to completely solve the problem given. In programming competitions, this feat is almost impossible to pull off.

In programming contests such as NOI.PH, to prove that they know how to answer the question, they must submit to the judges a Fast, Efficient, Correct, Error-free Solution by coding a program. Not only will the judges know that you have the correct answer, there is some sort of evidence (through your submitted program) that you did not just guess it.

In the next posts, we discuss a sample problem Aguinaldo to help you with the transition from solving math problems to solving programming problems. In particular, we divide the discussion into the following parts:

This is a work in progress. So check back every now and then.

## The Problem Statement

We are discussing the Aguinaldo sample problem. This is Part 1 of a series of posts which started here.

Emilio has $N$ relatives. During Christmas, the first relative gives him $P$ pesos as a gift. For $2 \leq i \leq N$, the $i$th relative gives exactly the same amount as the $(i-1)$th relative. How much is the total money that Emilio receives from his relatives?

This is the problem statement. This is just like the problems you get in your math classes. The main difference is that instead of numbers, it usually involves variables.

The problem statement starts by talking about two variables $N$ and $P$. Upon reading it, we see that $N$ is the number of Emilio’s relatives and $P$ is the amount of money given to him by the first relative.

It then talks about how much the other relatives give. The $i$th relative is said to give exactly the same amount as the $i-1$th relative. This statement only applies when $2 \leq i \leq N$. And so, it means that the 2nd relative gives exactly the same amount as the 1st relative. And so, the 2nd relative also gives $P$. Similarly, the 3rd relative gives exactly the same as the 2nd relative. And so on.

Somewhere at the end of the problem statement, you will usually see a question. In our case, we want to know the total money Emilio receives from his relatives.

## Input Format and Sample Input

We are discussing the Aguinaldo sample problem. This is Part 2 of a series of posts which started here.

The first line of input will contain an integer $T$, the number of test cases.

The next $T$ lines will contain two space-separated integers, representing the values $N$ and $P$, in that order.

After the problem statement is the input format. This tells you how the data is arranged. Here, we see a new variable $T$, which is the number of test cases. This means that your program will need to answer the question $T$ times.

Of course, if we need to solve the problem $T$ times, we need to have $T$ pairs of $N$ and $P$. As expected, the second part of the input format tells us what $N$ and $P$ are for each test case.

Let’s look at the sample input for a more concrete example:

We see that $T = 2$. For the first case, $N = 3$ and $P = 500$. For the second case, $N = 5$ and $P = 2000$. This input format is equivalent to your math teacher giving you an exam with two questions.

The first question will be:

Emilio has 3 relatives. During Christmas, the first relative gives him 500 pesos as a gift. The second relative gives exactly the same amount as the first relative. The third relative gives exactly the same amount as the second relative. How much is the total money that Emilio receives from his relatives?

The second question will be:

Emilio has 2 relatives. During Christmas, the first relative gives him 200 pesos as a gift. The second relative gives exactly the same amount as the first relative.The third relative gives exactly the same amount as the second relative. The fourth relative gives exactly the same amount as the third relative. The fifth relative gives exactly the same amount as the fourth relative. How much is the total money that Emilio receives from his relatives?

Imagine having a teacher who gives you ten problems of this form! At first it will be fine, but then it gets boring since it’s essentially the same problem again and again. Usually, when you figure out how to solve it, then repeating it nine times becomes tedious.

But don’t worry! The good news it that you can write a program that answers this question correctly for any value of $N$ and $P$. In a way, writing a program that answers the question is proof that you know how to answer any question of that form. No matter what the numbers are.

## Constraints and Time Limits

We are discussing the Aguinaldo sample problem. This is Part 3 of a series of posts which started here.

$1 \le T \le 100$

$1 \le N, P \le 2000$

$1 \le N, P \le 3\cdot 10^9$

We look at the constraints section of the problem. There are two subtasks, each with different constraints for $N$ and $P$. For now, we say that the judges run your program once for each subtask. The first subtask asks that your program give the correct answer for all possible values of $N$ and $P$ that are most 2000. And the second asks that your program gives the correct answers for all values at most 3000000000.

## Time Limit

Competitions have time limits for the programs to ensure that not only is the submitted solution correct, but that it also finds the answer efficiently. Most programs will find the correct answer… eventually. To illustrate, we know that there are only a finite number of possible passwords. But guessing each possible password of length at most 20 characters will take millions of years. The program the hacker uses is correct in the sense that it will find the answer. However, our time in the universe is finite and so running a program like that is not worth it. This is why contestants are encouraged to find efficient and optimal algorithms to solve problems.

Here are the regular time limits we apply for each programming language:

• C / C++ : 2 seconds
• Java: 4 seconds
• Python: 10 seconds

This means that your program must finish processing the subtask within that amount of time. Note that since other programming languages run slower, they have more lax time limits. But the intended (optimal) solution for each subtask should be the ones which will pass.

For example, suppose your solution involves going inside a for loop $N$ times, and every time it adds two integers. Then, for each test case, it will enter the loop at most 2000 times. Thus, for each subtask, it will enter the loop at most 2000 · 100 times. This will reasonably pass the time limit. However, the same solution might not work for subtask 2 because we can see that the program is destined to enter the loop 3000000000 · 100 times. That’s probably not going to finish within the time limit.

We therefore conclude that you will need a more efficient solution than that.

## Navigating Around Your First NOI Problem

In this page, we discuss the different sections of the NOI problems.

## Problem Statement

In general, a relatable real-life problem is presented via the problem statement. It is always a good idea to read so that you can understand what is being asked.

## Input Format and Sample Input

The input format tells you how this real-life problem is represented in terms of only the variables involved in the problem statement. It contains a template on what types of input your program is expected to handle.

It is always a good idea to look at this section side-by-side with the sample input to make sure you understand how the problem is described.

## Output Format and Sample Output

The output format tells you how your program should print out the answer to show that it does indeed solve the required problem!

Take note that some problems might ask you for the answer modulo a certain integer, so it is always a good idea to look at it.

Make sure that your program only outputs what is required, nothing more and nothing less. Remove excess output used in debugging. Unnecessary lines printed by your program such as

are considered by the automatic judge to be part of the output and will consequently be marked wrong.

## Constraints

The constraints section imposes limits on the values of the integers, the length of strings, etc. Participants may safely assume that the judges’ input will always fall within these constraints. Thus, submitted programs need not verify that these constraints are met. This section may contain extra assumptions you may make depending on the problem.

Pay close attention to this section as sometimes it may ask you to give the answer in a different way than expected (i.e. modulo an integer, etc).

Still part of the constraints section is a description of each of the subtasks. This section imposes extra constraints to the problem. More details about these will be discussed in a separate post.

## Explanation

There is usually an explanation section about the sample test cases which give a quick solution on how to handle these (usually) small test cases. Some problems would have images in order to make the problem clearer.

## Code Editor

You can run and submit your code using the editor below the page. More on that later.

### Start Coding!

Now that you know how to navigate your way around a NOI problem, why not try it out?

1. Sign yourself up for a HackerRank account.
3. Register yourself to the NOI Practice Contest.
4. Try to solve In or Out or any of the problems below.

Here is a list of some easy problems you can start with. Upon finishing your registration to the practice contest, you will be able to access a bigger list of problems with varying difficulty.

• Sharing Chocolates
Can Alvin and Berto share their chocolates fairly?
• Family
Three sisters discover where to find the true treasure within.
• Body Mass Index
Help Payton find out whether he should go on a diet.
• Rectangle, Diagonal, Perimeter
Find the maximum perimeter of a rectangle whose diagonal length is given.
• Banana Queue
Everyone’s going bananas in this exciting work shift!
• Kawaii
How many ways can I help Senpai such that I do not produce a bakemono, avoid being itai and not be called that thing called taidana?

Let us know if you manage to solve something using the comment box below!

## Submitting Your First NOI Program

After reading the problem and taking note of the important details, you should start thinking how to solve a problem.

Once you think you have an answer, start coding! NOI allows the programming languages C, C++, Java and Python. You can choose your language by using the code editor.

For this post, we will solve the problem entitled Aguinaldo (pdf version) and use Java. If you can’t access the problem, you should try signing up for HackerRank first and following the instructions on this post.

## Attempt #1

Before we begin, read the problem first and try to think of a solution. Are you done? Let’s begin. Here is our first attempt at this problem.

Looking at the code, do you think this will print the correct answer? Let’s submit it and see what happens.

We can actually press the Run Code button first to see how our code fares with the sample input. Pressing the Run Code button gives us this:

## Attempt #2

Just like Jason Mraz, we wont give up! We can see from the disaster that is Attempt #1 that we forgot to take note of the output format. Now, rewriting line 22 as:

We submit again and obtain…

The reason why this is a wrong answer is not trivial. Where are we going wrong? Let’s look at the judges’ input to see what’s happening.

Attention! Normally, it wouldn’t be possible to look at the judges’ input. You’ll have to try your own test cases based on the constraints to see why you’re getting a wrong answer. You normally need to be creative enough to figure out which large cases your program fails at.

You get an error. Can you try fixing the code before reading the next section?

## Attempt #3

If you were keen enough, you would have figured out that to fix the error, we should have taken long as input, as opposed to int. This could have been avoided if we carefully looked at the constraints. A Java int would have a maximum value of 2147483647 before overflowing. This is less than 2149599350, the first value of N in the judges’ input. Sneaky judges! Let’s fix our code once again!

We need to get rid of an array since allocating space for more than 2147483647 ints will be too much! We should realize that all array elements assign the same value P. Let’s throw away the array and just add P again and again until we’ve done it N times. This should be correct now.

…and submit!

We have exceeded the time limit of 4 seconds (for Java)! That means our algorithm runs very slowly. Perhaps there is something we’re doing inefficiently? Maybe we’re making our program compute unnecessary operations? What could it be?

## Final Attempt

Now, after using pen and paper to figure out how to rewrite my program to make it more efficient, here’s my program to solve the problem correctly and quickly. Here’s the code!

If it doesn’t show up properly in your browser, don’t worry! You’re smart enough to figure it out for yourself!