SPOJ: Some very easy problems

Its been a month since I have started coding in SPOJ. There are over 5000 problems present there. Its really gets very tough when one tries to get some easy problems from that lot. So, I dedicate this post to beginners. Go for the below mentioned problems.

Some very easy classical problems:

TEST- This is the first problem I solved in SPOJ. I recommend the same for you. It gives a brief introduction of the whole environment. What you need to do is to accept and print the input by the user until you come across 42. The easiest problem at SPOJ and a confidence booster to begin with..!! ;)

ADDREV- Take two numbers as input. Reverse both. Add the reversed number. Reverse again. Simple..!! The thing you need to keep in mind is that you have to provide the number of test cases first. While taking the inputs you can print the result too. You need not store them and print later.

FASHION- Quite big explanation of the problem (a bit interesting too ;) ). The only thing you need to keep in mind is that you have to sort the degree of hotness of men and women and then multiply and add them up. If you do not sort them, it will give a WA.

MIRRORED- Print "Mirrored pair" wherever you confront "bd" or "db" or "pq" or "qp", otherwise print "Ordinary pair". Don't forget to print "Ready" in the beginning. You do not have to take the test cases as input here. Just end the input when you confront two spaces. I got an AC at very first attempt..!! Hope the same for you.. :)

NSTEPS- Analize the graph properly. Whenever x and y co-ordinates are even the corresponding output is (x+y) for input (x=y) and (x=y-2). When they are odd the corresponding ouput is (x+y-1) for input (x=y) and (y=x-2). You can also do the problem with a different approach too. You can form a series for the numbers, and hence, generate the output.

OFORTUNE- Common.. don't get astonished by the enormous length of the question. Try tackling the problem. It just needs six inputs and a simple interest and compound interest formula implementation thats it.. Try it.. You will gain a hell lot of points..!!

Some very easy challenge problems:

SIZECON- The difficulty does'nt lies in the problem statement. The difficulty lies in the choice of programming language. I managed to do it in 96 characters. Best solution in c++ has 70 characters in it. Perl language wins with just 6 characters..!!

BFWRITE- I have already written a post about this problem. Try learning Brainf_ck language and solve this problem too. Here's the link to my post.

More easy problems are being searched. Kindly mention some in comments if you confront one.. Here's my SPOJ handle.. vaibhav_pandey.

* * * * *

Getting started with Project Euler

Hello folks.. After getting started with SPOJ and TOPCODER, lets get started with another fine programming competition which is Project Euler.

The first question which originates is.. why Project Euler??

My answer.. why not?? If you are interested in programming.. make yourselves interested in mathematical shortcuts and logics for solving problems too. Project Euler is a site that provides you problems that bind you to explore some unexplored areas of mathematics. Now, lets get started..

Steps:

• Get registered.
• See the problems from problems tag. There are more than 260 problems at present.
• Solving problems requires you either to build a source code that computes the asked value or to pick up pen and paper and start solving. My advice.. prefer the earlier one..!! :)
  

Your profile consists of the number of problems you have solved. Your ranking is based on levels. If you have successfully solved 25 questions you qualify to the level 1 and so on and so forth. On solving a problem its thread gets unlocked and you can check solutions of others in the languages they preferred. Thus, you can compare your code with others.

Your profile gets dissolved if no activity happens in 90 days of time. This happens if you are 0, 1 or 2 level programmer. Level 3 and level 4 programmers are granted immortality, thus, here lies the advantage of being superior.. 8)
So, get started with Project Euler and hone your programming skills..

To see my profile, first register to the site and then type the URL: http://projecteuler.net/index.php?section=profile&profile=vaibhav_pandey

* * * * *

My experience with BrainF_ck Programming Language

Hi folks.. Last few days I worked a bit on BrainF_ck language. A nice language that may be used for encoding sort of stuff. What we code in it.. it might happen that we ourselves forget about it, such is the level of complexity of the language!!
The brilliant factor about the language is that it is just made of eight symbols in total..!! Surprised.. so was I..!! :D

Whole of the language depends on just an array. Every manipulation has to be done in the array using a memory pointer, which moves through the memory blocks of the array. Now, getting over to the practical implementation of the language. The eight symbols are:

> = increases memory pointer, or moves the pointer to the right 1 block.
< = decreases memory pointer, or moves the pointer to the left 1 block.
+ = increases value stored at the block pointed to by the memory pointer
- = decreases value stored at the block pointed to by the memory pointer
[ = like c while(currentBlockValue != 0) loop.
] = if block currently pointed to's value is not zero, jump back to [
, = like c getchar(). input 1 character.
. = like c putchar(). print 1 character to the console.
I made my first program for SPOJ challenge problem BFWRITE. Before going through the code I would give you the link of an online compiler for BrainF_ck language. I prefer BrainF interpreter. So now, here's my code:

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

Looks quite difficult to understand but I'll make it simpler for you.

• First line assigns value 10 to a[0]
• Second line begins a loop checking value of current block a[0].
• Third line moves pointer ahead once(>) and assigns value 7 to a[1](++++++). The same line then again pushes pointer to a[2] and assigns value 10. 3 value is given to a[3]. The pointer returns back to a[0](<<<) and decrements the value to 9.
• In the fourth line.. loop goes on until the value of a[0] exhausts.
• Finally the values are.. a[0]=0, a[1]=70, a[2]=100, a[3]=30.
• The sixth line decreases a[1] by 3 and makes its value equal to 67. '.' prints the value 'S', ASCII code of 67.
• Likewise the further lines print the text:- 'P','O','J',' ','i','s',' ','i','n','d','e','e','d',' ','a','w','e','s','o','m','e'. Hence on our output comes as:- SPOJ is indeed awesome.
  

I further improved my code to 153 characters. Instead of making the array 70, 100, 30 in the beginning I made the array as 64, 32, 104, 112. Try it out yourself to optimize the code.

* * * * *

How to handle very large test cases in c++

Most of us come across some c++ problems where we are asked to get some simple calculations done. For example: we can get a problem of subtracting 1 from a 100 digit number. Now, subtracting one is not a big problem for us but the problem is '100 digit number'.

None of the datatype has capacity to store such a large number. Stop thinking about unsigned long long.. even it cant..!! So, here's a short solution to this cute problemo..

We can take the input as a string and process each of its elements as in elementary mathematics i.e. if last digit is'nt 0 then reduce it by 1(dont forget it to convert to int and then back to string).. if last digit is zero then make it nine and move back to the adjacent digit following the same procedure. Simple :)

Here's the source code..

#include
using namespace std;
int main()
{
int i,t=40;
string z;
cin>>z;
i=z.size()-1;
do
{
if(z[i]!='0')
{
z[i]=int(z[i])-1;
break;
}
z[i--]=57;

}while(i>=0);

Then print the string a.

The only problem comes when we give input as 10, 100, 1000, 10000 ... the answer comes out as 09, 099, 0999, 09999... instead of normal numbers such as.. 9, 99, 999, 9999... I have resolved this problem for myself.. I'll not upload the source.. try it out yourself..!! ;)

* * * * *

Getting started with TopCoder..

After successfully coding the first time in Topcoder, I really feel greatful in sharing my experience with all. Simply, it was great. Got to learn a lot of new things. I have started it too late but being in UPTU and that too in a college where seniors are not that into coding, it was still very early.. ;)

So, m writing this post to acquaint my mates with the TopCoder Competitions. What I m goin to discuss is all about the algorithm competitions.
Top Coder is a programming arena where you are given a set of problems and you have to solve them (in your preferred language) in a given amount of time. There are some simple steps to follow before starting with the coding competition:

• Goto Topcoder site and get yourself registered.
• Now when you are registered, download the Topcoder arena. You will need Java to be installed in your system for making the applet run.
• Get yourself an editor(I use KawigiEdit). The editor helps in generating the code required for the competition. If you need help to install it.. read this.
• Start the contest application and start navigating. There are practice rooms where you can practice the earlier SRM's(single round matches).
  

SRM are the single round matches which are organized twice every month. You are given three problems to solve. What you need to do is to generate the code using KawigiEdit and simply put your logic in the function provided.
The important point about TopCoder is that you don't use the main() method in your code. All your logic is dumped inside a function and you have to return your answer instead of printing it.
The several phases of the competition are:

• Coding Phase: During this phase you are given 75mins of time to solve as many problems as you can. What you need to do is to write your code, compile it and after rigourous testing on test cases provided and some of your own test cases, "submit" it.
• Intermission: 5mins intermission.. I hear a song usually.. :)
• Challenge Phase: During this phase in 20mins time any of the room members can see your code or you can see theirs. If anyone finds anything wrong with anyone's code, he can simply challenge it. If he succeeds the submitted problem will be discarded and points will fall back to 0.00
• System Testing Phase: After the challenge phase comes System Testing Phase. This takes a fare bit of time. After near about 20mins you can goto tools and room summary for checking whether your code passed the System Testing or not.
  

After about 2 hrs of play the result is out..!! If you see your name coloured (Green,Blue,Yellow,Red), feel like a champ. If you are Grey, you need to practice more and more. The colors listed above are in hierarchial order.. i mean Red is the highest pointer(2200+) whereas grey is the lowest(001-899).

Being associated with IEEE, TopCoder is a good platform for being recruited. Moreover, it hons your programming skills, giving your career a boost.

You can watch your entire TopCoder profile by just entering your username in the handle.
I m listing some of the TopCoder handles that will inspire you a lot..
Some foreigners:
ACRUSH
petr

Some Indians:
konqueror
innocentboy
vijay03
shalinmangar (from JSS.. a thing to feel proud of..)

Here's my hanlde.. its not that good.. I'll improve it further.. m sure..
vaibhavpandey

* * * * *

SIGSEGV error in c++ programs

While solving a question TOANDFRO in spoj I was introduced to the SIGSEGV (segmentation fault) error. The very first thing, as I often do, I googled the error. The forums I visited and info I got simply did'nt tell me what exactly went wrong with my code. So, after a "deep-deep" analysis I m here to provide my readers with the solution to such an error.

There are various causes of segmentation faults, but fundamentally, you are accessing memory incorrectly. This could be caused by dereferencing a null pointer, or by trying to modify read only memory, or by using a pointer to somewhere that is not mapped into the memory space of your process.
A segfault basically means you did something bad with pointers. This is probably a segfault:

char *c = NULL;
...
*c; // dereferencing a NULL pointer

Or this:

char *c = "Hello";
...
c[10] = 'z'; // out of bounds, or in this case, writing into read-only memory

Or maybe this:

char *c = new char[10];
...
delete [] c;
...
c[2] = 'z'; // accessing freed memory

* * * * *

Getting started with SPOJ (Sphere Online Judge)

After successfully getting involved in SPOJ I think I must give a little idea of it to others too. SPOJ is an online coding website for practicing ACM-ICPC style problems.
You need to join this website if you are interested in coding and have a thirst to solve new problems otherwise you can sit back and relax hearing your music stuff.. :p

To start with you can register for SPOJ here.
After getting registered you can see number of problems. Right now there are around 4K+ problems at SPOJ. For submitting a problem in whichever language you desire you can click submit and submit your file or directly the source code. One of the best things about online judges is their instant feedback. You dont have to wait for your program to get judged! The judge results are:

• Accepted – The output from your program perfectly matched the required output. This problem is then added to your list of accepted problems.
• Time Limit Exceeded – It means your program took too long to execute. Try optimizing your program and check for accidental infinite loops.
• Wrong Answer – Your program ran on time, but it did not produce the required output.
• Compile Error -Your program had some syntax error. For these errors, click on the text “Compile Error” in the judge result. It`ll take you a page which will list the compile errors and their line numbers in your program. The compilation error can also be sent to you as mail.
• Runtime Error – This is usually accompanied by a code like SIGSEV. It can happen due to a lot of reasons, but the two most common are using too much memory ( you can use around 6000*6000*4 bytes of memory ) and not remembering to use int main() and return 0 in your programs. (NZEC error).

Your ranking in SPOJ arena is dynamic. More the number of users who solve the problem you'v solved lesser will be points gained. The points you gain in SPOJ come with the formula:

points= 80/(40+users successfully solved the problem)

So, more the difficult question you solve more points you get and higher is your rank. Even your institute gets ranked on your points. Check your institute's rank here.

Here is my SPOJ handle.. vaibhav_pandey

Start coding now!!!

* * * * *