Google Codejam 2015 contest overview - India perspective

About 25% of the contestant in Google Codejam 2015 were Indians. Below are few straight through stats,

Number of coders in qualification round: 5494 (Contest Dashboard)
Number of coder who qualified to round 1: 2044

Google Codejam 15 - Standing Ovation - simle problem explained simply

Event:
Google Codejam 2015 
Qualification Round 
Problem A : Standing Ovation
Link: https://code.google.com/codejam/contest/6224486/dashboard#s=p0

You advised to go through the problem in above link or read it at the bottom of this blog post.

Best technique to study any programming language or a related topic

I am taking java as example, you can substitute it with any programming language/buzz-word/topic/tool and read the post.

Best java studying technique go through to top users answers on StackOverflow (SO). First check which are the all time top users for a specific required tag, and just go through their top voted answers which will surely have 100s of votes.

Also, you can sort questions by all-time-votes and go through the answers. It's a open hidden treasure of knowledge which no one cares about until he/she realizes it.

NPTEL - C course completed successfully

IITs and IISC together have created a wonderful NPTEL program i.e. National Program on Technology Enhanced Learning. There are tons of recorded lectures for almost all the engineering streams. A very good resource for the 4 year engineering and also for many competitive exams like GATE.

(For the programmers) You need to pick your side

Let me state a fact, you spend time a lot of time on the internet reading about debate between design features of various programming languages, there pros and cons, why one language is better or should be preferred over the other. It's just not very relevant. You'll be lost for long and just won't get up and do something if you don't quit the above described behavior.

Java memory analysis using inbuilt tools

jhat(Heap Analysis Tool) is a tool that comes along with the jdk and is present under jdkxxx/bin/ .

There are two way to get the heap dump

1. Give it while starting the java program as
java -Xrunhprof:format=b,file=file.hprof class-name
2. Get the heap dump using jmap as

jmap -dump:file=file-name process_id

Here I am using the first method. The java code ran is the same as described in this post about Thread-Creation-Time.

Java analyzing thread creation time

In Java, the thread creation time increases with the number of thread that are already created, hence it is advisable to keep the thread count minimal and only create a Thread when actually needed.

The below gist is a minimal piece of java code that helps in proving this

Code Re-use or Build from scratch ?

You'll often here these terms in your programming life
- reuse is better
- code is made to be reused
- don't reuse other's code
- reuse of code breaks things

The above arguments each of them stand true in different scenarios. And this is the part most programmers miss. They hear one fact and applies it to all known problems in their life.

Whats the buzzword 'programming best-practices' all about?

This post is about what does the programming best practices buzz word means, and not a actual list of the best practices(which will surely differ language to language and scenario to scenario, but the core best-practices would be the same, few of which discussed here).

It's kind of hard to think the usefull-ness of this buzz-word when it is taught(ok not actually taught ;)) in collage. You need to work on some actual project, mission critical app, or any software that deals with money ;), to understand it in real sense. Until then it's just another `yea-i-know-it-well` kind of word in your head.

Project Euler #315

Problem: Digital Root Clocks

Solution: [Spoiler Ahead]

       One of the easy problems and one of the easy solutions.
       It's just straight forward,

the number of LED on-off by SAM's clock - the number of LED on-off by MAX's clock

       Globals I used, a noOfLEDsForDigit[] array holding the number of led's required to glow a particular digit.
A digits[] array holding hex values for the number that represent the ON-OFF LED. e.g.

Project Euler 5

Problem: What is the smallest number divisible by each of the numbers 1 to 20?

Solution: [Spoiler Ahead]

              I just checked for numbers that are divisible by all numbers between 11 and 20(inclusive), this algo is not much efficient but works well.

Toggle Code

Project Euler 4

Problem: Find the largest palindrome made from the product of two 3-digit numbers.

Solution: [Spoiler Ahead]

  The initial algorithm to the problem is : Check all products of two 3-digit number and store the required number.

Project Euler #3

Problem #3:Find the largest prime factor of a composite number.

Solution: 
As usual firstly the straight forward implementation. Run a loop and go on checking whether it divides the given number and check if it is prime, storing the largest one.

#include

#include"prime.h" //My own module,code not shown here

int main(){

long long num=600851475143L;

long largest_prime_factor=0,i;

for(i=10;i<num/2;i++)

if(num%i==0)

if(isPrime(i)) //return true if prime

largest_prime_factor=i;

printf("Answer to Euler #3 : %ld",largest_prime_factor);

return 0;

}

                    This can be optimized a little by defining a new upper bound for the loop counter  and that would be square root of the given number.

                     More over 2 is a factor which if checked separately will make our life easy. Then we can increase the factor by step of 2.

                    A little more optimized algorithm is:

n="a large number"



if n mod 2=0



then



    n=n / 2



    lastFactor=2



    while n % 2=0



        n=n / 2



else



    lastFactor=1





    factor=3



    while n>1



         if n % factor=0



         then



                n=n / factor



         lastFactor=factor



         while n % factor=0



                n=n / factor



         factor+=2





output lastFactor

This is not the fully optimized solution but can be modified further. That left to you ;-)

Enjoy coding :-)

Project Euler 2

Problem #2:Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

Solution: A straight forward implementation in C for this problem can be as shown

#include
#define LIMIT 4000000
int main()
{
 long a=1, b=2, c=0, sum=0;
 sum = b;
 while(c < LIMIT ){
  c = a+b;
  if(c < 1000000)
  if(c%2 == 0)
   sum += c;
  a = b;
  b = c;
 }
 printf("\nAnswer to euler #2 : %ld\n",sum);
}

        
                 This code works fine for our required need, but more optimizations can be done.How? Lets look at the fibo seq.

                                                    1 1 2 3 5 8 13 21 34 55 89 144 ...

                 As we can see,every 3rd term is a even number. Therefore we can change the code accordingly to just sum up every third number.
                 Another approach is we can find a recurrence funtion for this new series i.e. we can have :

F`(n)=4*F`(n-1) + F`(n-2)

It is easy to prove that for Fibonacci series we get:

 F(n)=4*F(n-3)+F(n-6) 

Thus we get a more faster running code, which we eventually need :-)

Enjoy coding :-)

Project Euler 1

Problem #1. Add all the natural numbers below one thousand that are multiples of 3 or 5.

Solution : This can be done in two ways ....

i. The normal method, i.e. run a for from 1 to 1000 and check for the given condition on each number.

This method does solves our problem but is crude.

upperlimit=999
total_sum=0
for i=1 to upperlimit do
if (i mod 3=0) or (i mod 5)=0 then
total_sum:=total_sum+i;
output total_sum

ii. The short-cut method : In this you need only one formula and just need to compute value of 3 expressions.

Just go through---->

The solution to given problem will be the answer of this expression :

ans = sumDivisibleBy(3) + sumDivisibleBy(5) - sumDivisibleBy(15)

Now for n=3 :

3,6,9,12,15,18,21,24,27,.....,999 = 3(1,2,3,4,5,6,7,8,9,....,333)

Now we know that :

1 + 2 + 3 + .... + q = 1/2*q*(q+1)

In our case : q = upperlimit / n

Therefore our solution says :

Function sumDivisibleBy(n):
q = upperlimit div n
return n*(q*(q+1)) div 2
EndFunction

print sumDivisibleBy(3)+sumDivisibleBy(5)-sumDivisibleBy(15)

Feel free to ask any kind of querry, I'll try my best to solve it.

Enjoy coding :-)