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!