Codechef-Hints to some easy problems

This is a post for beginners facing problem on the coding practice problems of easy level on Codechef.
(haven't heard of codechef?It is an online judge like SPOJ, UVa, Topcoder etc. It uses the Sphere Resesrch Labs and thus most of its practice problems can be found on the SPOJ problem set as well.It introduces some really good problems during its monthly problems which also have some really good prizes to be won.Though I haven't been able to solve too many of those problems :(     (I am a newbie myself.)

Easy practice problems on Codechef that i have already hinted about in this and this post are:

• Life,the Universe and Everything (TEST)
• Poker(POKER)
• Small Factorials(FCTRL2)

A couple of the medium level problems have also been already covered:

• Bytelandian Gold Coins(COINS)
• Prime Generator(PRIME1)

Now some other problems:

• Factorial-(FCTRL)

This is a pretty simple problem.Forget the long explanation,you just have to calculate the number of trailing zeros in N!. Don't try to calculate N! for it just remember this line from the problem statement:

"we can never "lose" any trailing zero by multiplying by any positive number. We can only get new and new zeros".

• ATM(HS08TEST)

This is just too easy a problem.You just have to use a conditional statement and basic arithmetics.

• Enormous Input Test (INTEST)

This problem is like a tutorial for the problems ahead.It forces you to leave behind the inefficient ways of i/o.

E.g you should use scanf/printf if you are using c++ instead of cin/cout.

• Sums In a Triangle (SUMTRIAN)

Its a basic problem of recursion.A very nice tutorial for the problem has been put up here.

• Turbo Sort (TSORT)

It is a straight forward sorting problem but with a little strict time limit.As long as you use an O(nlogn) algorithm,you should be easily accepted.

I used Merge Sort.This is what wiki says about it.

• Ambiguous Permutation (PERMUT2)

You have to determine whether the given permutation of numbers and their inverse permutation are same or not.

I'll explain the first test case in detail if there's is any confusion about the problem statement:

The given permutation is 1 4 3 2.If it is inverse,then:

1should be at position given by first number i.e 1 itself.

2 should be at position given by second number i.e 4

Similarly for 3 and 4.

Thus the given permutation is inverse.

Also keep one thing in mind declare the array on the heap not on the stack i.e out of all function definition or you might get a SIGSEGV runtime error.

• Paying Up (MARCHA1)

Again a very good tutorial is given for this problem here.

• The Way to a Friends House Is Never Too Long (POINTS)

All you have to do is sort the list with respect to X and consider Y to sort two points for which X  are equal.Merge sort will can be used here too.

•  A Very Easy Problem (EASYPROB)

Just notice the number being used again and again and you will be able to find the pattern.(Did you know :2^2=4)

• The Lead Game (TLG)

Just keep record of the total points of each player after every round and the lead after every round.You have to output the lead when it was largest.

• Odd (DCE05)

I think I'll just take a couple of test cases here:

input

4

5

12

18

39

output

4

8

16

32

• Johnny and the Beanstalk (MARCHA2)

Nice tutorial available here

Though the above mentioned problems are easy enough but still if you are stuck,just leave a comment.If you want to share any hints for any problems,you are most welcome.

Read more

Some medium level problems on SPOJ

Here are some of the medium level problems on SPOJ:

1. Prime Generater – This question can be solved by applying sieve’s algorithm. What we do is make an array of prime numbers in the range of 1 to 32000 ( square root of 1000000000 ) .. now we have our initial setup ready .. for generating primes i used sieve’s algorithm which states that you make an boolean array of 32000 values and initialize it as true that means declare all of them as prime .. now start from 2 and if the current number is prime .. make all itz multiple in the apropriate range as composite ( i.e. set their index in the array as false .. ) .. this is the fastest method for generating prime numbers .. now we start taking the input from the user .. lets say he gives the numbers m and n as input ( m> n) now we apply sieve again .. first make an array of booleans of size m-n ….. now for all the prime numbers from 2 to the prime number next to the square root of m we make their multiples in the range n to m as composite ( i.e. set their array as false ) .. now after this procedure is over .. just a linear traversal in the second array .. and print whatever is prime .. ( i.e. flag is true .. ) .


2. Small Factorial .. – This is fairly simple problem .. you just have to make a programme to multiply arbitrary large numbers . ( stored as strings .. ) and then run a loop from 1 to n to calculate the answer .. thats it ..


3. Bytlandian cryptographer .. act 2nd .. – This is again a very easy problem .. add 1 to a number isnt it easy !!!! .. but the problem is you have to write the code in Brainf*** yeah that language does not have even a multiplication and addition operators .. just 8 instructions and the language is over .. !!!  .. but you can try the official documention of brainf*** language .. go through may be first page and thats it for this problem ....so easy points once you go through this page ..


4.Bytelandian gold coins -This problem can be solved by recursion using the relation:
                                  f(n)=max(n,f(n/2)+f(n/3)+f(n/4))
but it times out.The solution to that is memoization.It is a technique in which we store the already calculated results in a sort of cache and use it whenever needed instead of calculating it again.
here's a sample  for the same in C++:


map reference;


long long f(n)
{
   if(n==0)return 0;
   if(reference[n]==0)
   {
         reference[n]=max(n,f(n/2)+f(n/3)+f(n/4));
   }
   return reference[n];
}


5.POKER:Though its a very easy problem if you know the rules of POKER but i put it in medium because i think its very easy to miss any condition in this and  get it wrong.


Best Of Luck

Read more

EASY PROBLEMS ON SPOJ

Its sometimes pretty difficult to find the easy problems among the thousands on SPOJ.
Here are some of the problems on SPOJ that i found easy and that pretty must guarantees that they are easy.  :)

TEST- This is the first problem I solved in SPOJ. I recommend the same for you as it will introduce with the way of accepting input and printing output that SPOJ wants. 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..!! ;)


FASHION-The explanation is quite big but it all comes down to sorting the two lists of degree of hotness and then multiplying the corresponding numbers and adding them.pretty simple huh ;).


ADDREV-Take two numbers as input. Reverse both. Add the reversed number. Reverse again.


MIRRORED- Print "Mirrored pair" wherever you confront "bd" or "db" or "pq" or "qp", otherwise print "Ordinary pair"


OFORTUNE- The explanation is frightening and large.But the problem is really simple.It just needs six inputs and a simple interest and compound interest formula implementation .Due to the large explanation not many people have solved this ...so you'll get a lot of points too.


FEYNMAN-If you observe for a while ,you will find that the answer is just the sum of the squares of the numbers 1 to N.


Some more easy problems are SIZECON ,NSTEPS,TABLES,JULKA,CANDY,CANDY 3


Best of Luck !            




Please post your complaints(if any) and suggestions here

Read more

Getting Started with SPOJ...

SPOJ is the perfect place to practice coding in any language you prefer.no matter how good or bad you are at coding..you will find problems for your level.

This is a quick how to begin on SPOJ:

The first thing you need to do is to register (it's free and spamless). Then find problem from one of the extensive problemsets, write a solution in your favorite language and submit it. Next switch to status page and watch progress of judging of your solution. After few moments you will see the result:

1. AC - accepted - your program ran successfully and gave a correct answer (this you will like most :) )

2. WA - wrong answer - your program ran successfully, but gave an incorrect answer

3. TLE - time limit exceeded - your program was compiled successfully, but it didn't stop before time limit

These are status codes you will see most often. To know all of them, see FAQ or this tutorial.

Once you get up and running,you get points for the problems you solve on the following basis:

• for solving classical problem p: 80/(40+number_of_people_who_have_solved p) points
• for a top score in any challenge: 3 points,
• for any lower score in a challenge: (user's_score relative_to_the top_score) points.

Numbers given in brackets beside the scores correspond to the number of solved classical problems and the number of challenges for which the user's best score is also the top score, respectively.

Now check out your programming skills.For a start look at these for hints:
Easy SPOJ problems
Medium Level SPOJ problems

Please post your complaints(if any) and suggestions here

Read more