TroJan

This was a easy problem as I solved by a naive approach. The link to solution is link

A very easy problem with complexity :O(13*len)

A normal infinite loop to check whether a number is prime and maintain the count.

Factorial of a long number and then sum of the digits.

This was a easy problem where the sum of square and sum of n terms can be applied to calculate the answer.

In this problem, largest palindrome number that can be made by the product of two 3 digit number is to be obtained.

The complexity of the code is O(n2).

One optimization which I did is I ran the loop of j from i because when loop for i will run for say 999 then 999*999,999*998 and so on will be computed. If j runs from 999 instead of i then 998*999 will be recomputed which is useless. 

The other trick was a good one. To check for palindrome I used sprintf to output the number in to a character array as it is sure that number will be a 6 digit number

In this problem, a number was given and the task was to determine the largest prime number that divides it.

So I ran a loop from the square root of the number down to 0 and kept on checking for each divisor whether it is prime or not.

The code can be fount at:

This topic pata nai q is one of favourite topic of one of my friend named Ankur Rana.

So the September Challenge made me learn about this.

So lets see what it is.

Suppose you need to calculate the following 

(n*(n-1)/5!)%10000

so as u can see the mod can easily be distributed over the numerator part but when it comes to denominar part, you have to write denominator in inverse form.

like (n*(n-1) * 5! ^-1)%10000

so now how to calculate modular inverse. It is very simple.

power(5!,10000-2,10000)

yes this much of simple. Now simple multiply this term and then take mod.

This was a learning problem for me. I  knew that I have to calculate gcd in this problem. but i didn't knew that the answer will the least prime factor of gcd.

One approach to find that can be to iterate till the square root of that number and check for divisibility. the time limits were so that this solution would obviously be passed but since I am learning new things so I decide to go for precomputing that array using Sieve method

The function was:

int prime[100000];

void sieve(){

int i,j;

prime[0]=0;

for(i=1;i<=100000;i++)prime[i]=i;

for(i=2;<=sqrt(100000)+1;i++)

if(prime[i]==i){

for(j=2*i;j<=100000;j+=i)prime[j]=min(prime[j],i);}

This was a problem where string matching was required.

For the time being I used strstr() function in C++ to check for matching string.

This was a easy problem but I faced some difficulty in understanding it. The problem was to calculate the minimum number of steps required for a string. First the string is taken as input,then the first character is loaded,printed and increment operations are done till we dont reach the second character.

The main point was that if the difference is positive then the difference can be just 

a[i]-a[i-1]                     provided i>0

whereas if this difference is negative then you will have to subtract its absolute value from 26 i.e.

Wow pahle toh ye question dek k lag rha tha yaar fir iska editorial dekhan padega but fir maine apni 3 golden rule for codechef follow kiye

dhyan se padha toh pata chala ki sorting toh karni padegi hi

Jo dikhta woh toh kabhi b nai hota h.. 

This problem made this fact more bold and fixed in my mind. What a problem it was. Seeing this problem I was thinking of segment trees because 10 test cases with N=10^5 array size and then 10^4 queries, a sure shot time out. 

But since this problem was tagged as adhoc, it means that there was something unusual in it. When I read its editorial, I was really impressed that the sum of L and R values can create a difference.

The answer was so simple

if( l<=c<=r)

This problem made me learn a simple fact about Codechef and life that things are not the way they seem to be. Now my point of view about Codechef is :

* Read the problem statement very carefully.

* Implement test cases yourself.

* Jo dikhta h woh kabhi b nai hota