Wednesday, January 6, 2010

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:

A couple of the medium level problems have also been already covered:
Now some other problems:
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".
This is just too easy a problem.You just have to use a conditional statement and basic arithmetics.
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.
Its a basic problem of recursion.A very nice tutorial for the problem has been put up here.
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.
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.
Again a very good tutorial is given for this problem here.
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.
Just notice the number being used again and again and you will be able to find the pattern.(Did you know :2^2=4)
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.
I think I'll just take a couple of test cases here:
input
4
5
12
18
39
output
4
8
16
32
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.

1 comment:

Monica said...

Thhanks for sharing