First-Timer Primer

In this post, we answer some questions that participants have asked us.

Q: Is there any way to bypass the 264-1 limit in Java or C++?

A: Java has an arbitrary-precision library called java.math.BigInteger (and java.math.BigDecimal). Keep in mind though that problems used in official NOI contests usually won’t require the use of arbitrary-precision libraries. But we’re not preventing you from using them!

For C++, there is no built-in arbitrary-precision library, so it depends on the amount of “bypassing” you want. For example, you can simulate 128-bit integers by creating a class with two 64-bit integers, the first one representing the higher-order bits and the second the lower-order bits. If you want to use larger numbers, I suggest implementing your own arbitrary-precision arithmetic library.

Q: What is the big O notation and why do I see it in editorials all the time?

A: Roughly speaking, the big O notation expresses the speed of your program relative to the input size. In other words, it describes how quickly your program’s running increases as the input size increases. O(f(n)) roughly means that if the input size is n, then the running time grows approximately as f(n).

For another explanation, we recommend reading this. Also, don’t hesitate to ask us if you’re still having trouble understanding it!

Q: What do you suggest for inputs where n is near the billions?

A: For such problems, an O(n) solution would most likely not be accepted, due to the time limits. (Even a loop from 1 to n might not finish in time!) Try finding faster (sublinear) solutions, such as those that run in O(√n), O(log3 n), O(log n) or O(1) time (to name a few). Also, for n ≤ 1018, some slower solutions, such as those that run in O(√n) time, become too slow for these time limits.

However, time complexities such as O(n) can be a bit misleading, because there is a hidden constant behind the O() notation. Also, using pure operation count as your basis for program speed isn’t necessarily more accurate either, because some operations are slower than others. For example, one division is much slower than one bit shift. It’s up to you to judge, and it takes some experience to get the hang of it.

Q: What is “modulo”, and why do a lot of problems ask for the answer “modulo” some number?

A: The result of the operation a mod b” (read “a modulo b”) is simply the remainder when a is divided by b (here b is called the modulus). For example, 100 mod 3 = 1, 5 mod 100 = 5, 100 mod 5 = 0, and 0 mod 11 = 0.

Usually, a problem asks for the answer modulo some number so that the output size isn’t very large, and that computation can all be done without resorting to arbitrary-precision arithmetic. This is because of the following properties of the modulo operation (among others):

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a × b) mod m = ((a mod m) × (b mod m)) mod m
(ab) mod m = ((a mod m) – (b mod m) + m) mod m

This means that intermediate values can be reduced modulo m safely as long as the operations involved are addition, subtraction, and multiplication (and possibly some other operations).

In C, C++, Java and Python, a mod b is written as a % b.

Q: Why do a lot of problems use the modulus 109+7 if we could just use something else, for example 109?

A: 109+7 is prime, and a prime modulus is desirable in some cases:

1. Sometimes, if the modulus is 109, some important values become 0 for large inputs (or something trivial), making the problem a bit easier for those inputs. But usually when the modulus is prime, it doesn’t. For example, n! mod 109 quickly becomes 0 as early as n = 40, but n! mod (109+7) is nonzero until n = 109+6.

2. You can “divide” modulo a prime by using modular inverses. Keep in mind though that modular inverses usually aren’t required in official NOI contests.

In some problems, the modulus plays a key role, and a problem can be very difficult with one modulus and easier with another. For example, if we ask you, given n ≤ 106, to compute n! mod m for some modulus m, then the problem is easy if m = 109 but a bit harder if m = 109+7. So we recommend paying attention to the modulus.

Q: How do I prepare for the NOI if I have limited knowledge on problem solving, algorithms and implementation?

A: The best way to improve is to join online contests regularly. For example, HackerRank, Codeforces, CodeChef, etc. host programming contests regularly (for example, in weekly / monthly intervals). Check this link for a schedule of upcoming contests. Joining these contests is free!

If you have limited time, I suggest going through all past NOI problems (which are all hosted in our HackerRank NOI practice page) and solving as much as you can, preferably those you feel are standard stuff but you’re not familiar with. Remember that, being past NOI problems, these problems usually have their editorials available somewhere.

For standard stuff like graphs, data structures, standard algorithms, etc., we suggest you to learn them as soon as possible. You can’t rely on pure instinct all the time.

Finally, I suggest learning problem-solving and implementation skills simultaneously. As you encounter new algorithms/data structures, implement them immediately. Usually when you find tutorials, there are sample problems you can try them out with.

Q: What resources would you recommend for learning?

A: Aside from all the links given in the editorials of past NOI problems (of which there are a lot!), you may check this link for a list of tutorials and sample problems. You can find a lot of things to learn there. Be warned though that they aren’t listed in increasing order of difficulty, so I don’t suggest learning them in that order!

In general, you can try searching the web for any topic you hear about, and you might find a tutorial for that. Sometimes, especially in CodeChef long contests, we even look at research papers for solution (and problem) ideas!

But be sure you’re usually able to code brute-force solutions first! Don’t underestimate experience. You could be the most talented guy and yet fail at contests if you can’t code well enough.

Also, try setting a goal for yourself. For example, solve all NOI practice problems, or get some number of points in UVa Online Judge, or get to a certain rating in Codeforces/HackerRank/CodeChef, etc. During college I tried to get as many points in UVa as possible, and it helped me solve and train regularly.

You may also want to check out our previous posts to prepare for the NOI.

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.

Programming language switcher. On the upper-right hand side of the code editor, you can choose the programming language you wish to use.
Programming language switcher. On the upper-right hand side of the code editor, you can choose the programming language you wish to use.

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.

Oh no! We got a wrong answer, even for the sample test file! We were very careless.
Oh no! We got a wrong answer, even for the sample test file! We were very careless.

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:

Sample input. Running our code with the sample input, we can clearly see where we went wrong in that specific case.
Sample input. Running our code with the sample input, we can clearly see where we went wrong in that specific case.

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…

Attempt #2. We have the first test file down, but the second test file is stubborn! Let's investigate.
Attempt #2. We have the first test file down, but the second subtask is stubborn! Let’s investigate.

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.

Custom input. Let's try to run our program to the judges' first test case.
Custom input. Let’s try to run our program to the judges’ first test case.

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!

Terminated due to timeout. Our program runs too slowly!
Terminated due to timeout. Our program runs too slowly!

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!

How to Access the NOI Practice Problems

Here’s how to access the NOI Practice Problems.

  1. Sign yourself up for a HackerRank account.
  2. Login with your credentials.
  3. Register yourself to the NOI Practice Contest.

IOI 2016 will be held in Kazan, Russia. Join NOI.PH 2016 to qualify!

The beautiful city of Kazan in Russia is host to the 2016 International Olympiad in Informatics. To have the chance to represent the Philippines at the 2016 IOI, register and join the NOI.PH 2016!