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.

Access the Past Problems

Although the composition of the problems are similar to that of the IOI, our problems have a local twist. In no other high school programming contest would you find problems about Tinikling, Heneral Luna, and Pabebe Girls! View the rest of the problems here and following these instructions to enable yourself to submit.

Visit the Training Site

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].

External Sources

Are the references not enough? Do you want to go beyond and learn more? Check out this curated list of reference materials!

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.

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:

Sample Input

1

2

3

2

3 500

5 2000

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.

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 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.

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

1

Please enter the integerT:_

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?

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.

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.

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.

Attempt #1

Java

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

importjava.io.*;

importjava.util.*;

importjava.text.*;

importjava.math.*;

importjava.util.regex.*;

publicclassSolution{

publicstaticvoidmain(String[]args){

Scanner sc=newScanner(System.in);

intT=sc.nextInt();

for(intkeis=1;keis<=T;keis++){

intN=sc.nextInt();

intP=sc.nextInt();

int[]arr=newint[N];

arr[0]=P;

for(inti=1;i<arr.length;i++){

arr[i]=arr[i-1];

}

intANS=0;

for(inti=0;i<arr.length;i++){

ANS+=arr[i];

}

System.out.println(ANS);

}

}

}

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:

Attempt #2

Java

22

System.out.println("Php "+ANS);

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.

Judges' Input

Java

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

100

2149599350507998472

486675710255186788

26073129451197348814

1204142729620751190

9411913732569041728

12873255162052893020

1523141987385124468

7502341692834659788

24162145331475354239

17758902292413632196

12215352072107202348

2379963155560375889

20197029562490563604

12753675411797762070

25653221142265556196

5135094692027310655

29451782981189598371

21883000982468591817

1574804947575296376

17372110271011514760

37461169853752274

521939010484403605

17300038792234029273

1112478100975189695

1918724042700193810

22660666671049565530

29154865511264144540

239273375417637084

24363822542367886554

481420834271378083

254644297558367108

1740178541431859644

880920901265895630

1907899781380011834

11886194951642679744

19251340572283687165

19730156221748658555

14847614271127434130

2544863731784916287

6780196251283269495

21915525521712515110

174810651396714781

5984156192447735437

5805592921435454777

2785331264314480211

29485773452747306490

16226105981779351758

27639033471324331529

21879650451205758060

19890919751458145420

21283823102184064204

1993310331381183136

9252555662946653207

20085687162264247

2520777175858816087

2788214701456044704

1677078229946502052

5379534682238907172

1990292881982665064

736802005165845852

5965252701663405367

3466960752573763267

8781297941550851618

19294550831613795088

2510577406442449030

16661894901242855994

2255045752312312304

23559195552969441839

6403339862370871371

28335771112543696564

28927884092777883149

17440490751285453588

790329449388405548

942439644307105487

27791975521255888011

21970645132704236251

1484820861934698559

1319156727122341872

2137652007585416622

7031104992880437369

24786537091480060599

21085754432468976134

2130355818552100462

26160142261946733248

606706162815119891

10730287121045812347

1602281921789223452

28198627861580303966

436264953375265798

22751298352315143528

7285008262142560571

14925531281062715927

16951442261134043474

837699491704817060

7970949381203983562

14252408881341645201

3765751882840710928

23882975801446517922

805432949155624349

17874744772178863903

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.

Attempt #3

Java

8

9

10

11

12

13

14

15

16

17

18

19

longT=sc.nextLong();

for(intkeis=1;keis<=T;keis++){

intN=sc.nextInt();

longP=sc.nextLong();

longANS=0;

for(inti=0;i<N;i++){

ANS+=P;

}

System.out.println("Php "+ANS);

}

}

}

…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!