SPOJ 450. Enormous Input Test Problem Code: INTEST

---Link to the problem---

This problem also appears in CodeChef ---here---

This problem is to test how fast you are able to read the input. Faster input output methods are required for some problems in UVa, SPOJ, CodeChef and other sites (Usually the problem statements have a warning that the IO is huge).

What I found out about faster IO:

Never use cin or cout. Always use scanf and printf (they are about twice faster). But there are methods much much faster than scanf and printf!!

My first solution to the above problem: was using scanf and printf. -->Execution time: 5.44 s

Then I googled to find out this function to read integers using getchar:

inline void fastRead(int *a)

{
register char c=0;
while (c<33) c=getchar();
*a=0;
while (c>33)
{
    *a=*a*10+c-'0';
    c=getchar();
}
}

I used it and my execution time became reduced by 2 seconds  to 3.40 s 

I then stumbled upon UVa forum where someone suggested that getchar_unlocked is faster than getchar. So I modified the function to use getchar_unlocked:

inline void fastRead(int *a)

{
 register char c=0;
 while (c<33) c=getchar_unlocked();
 *a=0;
 while (c>33)
 {
     *a=*a*10+c-'0';
     c=getchar_unlocked();
 }
}

I submitted the program again with the getchar_unlocked modification and my execution time is now believe it or not: 0.76 s

Check this out:

---Link to my submissions page for the problem---

SPOJ 24. Small factorials. Problem code: FCTRL2

---Link to the problem---

Bottom line:

The 100! does not fit into an integer. You need to store the number as an array or list of integers. You also need to write the code for multiplication (like how it is done with pen and paper).

SPOJ 5. The Next Palindrome Problem code: PALIN

This problem has several traps.

The solution to the problem is to understand the answer to the question :

“If I am allowed to change a digit in a number (to make it a palindrome) which digit should I change in order to change the given number as little as possible?”

The idea:

Let the given number be 123321. Let’s try to get the next palindrome.

First, we try changing the rightmost digit (1) to 2, then we need to change also the leftmost digit (1) to 2 in order to make it a palindrome. But the leftmost digit of any number is the most significant digit. Changing it will change the number by the highest possible amount. So, we don’t want that.

So, we can see that we need to change the middle digits so that we get the “smallest palindrome larger than the given number” as asked in the problem statement. Therefore the idea is to start in the middle and change digits in both directions outwards to make the palindrome.

This is how we get the next palindrome:

123321 --> 124421

For the sample inputs given in the problem statement:

808 --> 818

2133 --> 2223 --> 2222

Some special inputs:

0 --> 1

9 --> 11

99 --> 101

Points to note:

1. Each number given as input can be as long as 1000000 digits. This means that you cannot use any available data types like int or double. You need to store the number in an array of chars. Note: Remember to give the size of the array as 1000001 or more. Because a 1000000 digit number occupies 1000000 chars + 1 char for the null (string termination).

2. Try inputs of both even and odd length numbers.

SPOJ 1688. A Very Easy Problem! Problem code: EASYPROB

The problem asks you to output some form of these numbers: 137, 1315, 73, 136, 255, 1384, 16385, one per line in the listed order.

Let’s see the first line of the correct output:

137=2(2(2)+2+2(0))+2(2+2(0))+2(0)

Hmmm… I don’t want to take the fun out the problem by giving the answer directly to you. So, I will give you a clue.

The clue:

If you have been thinking in this direction :

“How can I make the left hand side (in this case 137) to become the right hand side?”

Stop thinking!

The right direction to think for this problem is:

“How can I make the RIGHT HAND SIDE of the equation to become the left hand side?”

Got it?

Let's Get It Started!

For those who interested in solving the problems in SPOJ, UVA and the like…

I have found that there are not many resources available on the net when I get stuck with a problem. There are very few tutorials available out there that explain how to solve a problem. I usually end up browsing through forums looking for clues…

Well… I am going to write in this blog, tutorials for some of the problems that I have and am going to solve…

However, note that I am going to write here how I solved the problem and not the BEST way to solve the problem… (hey! I am just an average coder…)

Hope this would be helpful to someone.

Happy coding!!