How should you or your students prepare for the NOI.PH? We’ve put together a list of resources so you’ll never run out of things to learn!
Read the Tutorial
Contestants use the HackerRank website to view the problems and submit their code. The problems are divided into several sections. Let’s dive straight in by looking at a (somewhat simple) programming problem suitable for first-timers.
Stumped in one of the problems? Perhaps there are some topics that you’re missing. The scientific committee has been writing a several training materials on various topics that might help you out! Not only will this help you prepare for the NOI, but the IOI as well. The website is in the process of being updated depending on the availability of the committee. If you would like to request for a topic to be written, feel free to give a gentle nudge by sending an email to [email protected].
Are the references not enough? Do you want to go beyond and learn more? Check out this curated list of reference materials!
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 Aguinaldoto help you with the transition from solving math problems to solving programming problems. In particular, we divide the discussion into the following parts:
We are discussing the Aguinaldo sample problem. This is Part 1 of a series of posts which started here.
Emilio has relatives. During Christmas, the first relative gives him pesos as a gift. For , the th relative gives exactly the same amount as the 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 and . Upon reading it, we see that is the number of Emilio’s relatives and is the amount of money given to him by the first relative.
It then talks about how much the other relatives give. The th relative is said to give exactly the same amount as the th relative. This statement only applies when . And so, it means that the 2nd relative gives exactly the same amount as the 1st relative. And so, the 2nd relative also gives . 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.
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 , the number of test cases.
The next lines will contain two space-separated integers, representing the values and , 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 , which is the number of test cases. This means that your program will need to answer the question times.
Of course, if we need to solve the problem times, we need to have pairs of and . As expected, the second part of the input format tells us what and are for each test case.
Let’s look at the sample input for a more concrete example:
We see that . For the first case, and . For the second case, and . 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 and . 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.
We are discussing the Aguinaldo sample problem. This is Part 3 of a series of posts which started here.
Subtask 1 (40 points each):
Subtask 2 (60 points each):
We look at the constraints section of the problem. There are two subtasks, each with different constraints for and . 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 and that are most 2000. And the second asks that your program gives the correct answers for all values at most 3000000000.
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 times, and every timeit 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.
In this page, we discuss the different sections of the NOI problems.
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
Please enter the integerT:_
are considered by the automatic judge to be part of the output and will consequently be marked wrong.
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.
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.
You can run and submit your code using the editor below the page. More on that later.
Now that you know how to navigate your way around a NOI problem, why not try it out?
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:
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?
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.
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?
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!