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:

• The Problem Statement
• Input Format and Sample Input
• Constraints and Time Limits
• Output Format and Sample Output
• Subtasks

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

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

Emilio has $latex N$ relatives. During Christmas, the first relative gives him $latex P$ pesos as a gift. For $latex 2 \leq i \leq N$, the $latex i$th relative gives exactly the same amount as the $latex (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 $latex N$ and $latex P$. Upon reading it, we see that $latex N$ is the number of Emilio’s relatives and $latex P$ is the amount of money given to him by the first relative.

It then talks about how much the other relatives give. The $latex i$th relative is said to give exactly the same amount as the $latex i-1$th relative. This statement only applies when $latex 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 $latex 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.

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 $latex T$, the number of test cases.

The next $latex T$ lines will contain two space-separated integers, representing the values $latex N$ and $latex 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 $latex T$, which is the number of test cases. This means that your program will need to answer the question $latex T$ times.

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

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

We see that $latex T = 2$. For the first case, $latex N = 3$ and $latex P = 500$. For the second case, $latex N = 5$ and $latex 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 $latex N$ and $latex 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.

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

$latex 1 \le T \le 100$

 

Subtask 1 (40 points each):
$latex 1 \le N, P \le 2000$

Subtask 2 (60 points each):
$latex 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 $latex N$ and $latex 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 $latex N$ and $latex 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 $latex 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.