GOOGLE CODE JAM ( QUALIFICATION ROUND ) 2015

CLEARED THE QUALIFICATION ROUND WITH 34 POINTS :)

Code:

Problem 1 :  http://ideone.com/AeXJ1H   (17 points )

Problem 4 : http://ideone.com/tIIaw3 ( 8 points )

Problem 2 :http://ideone.com/ONjN4L ( 9 points )  Could not solve !!!

Interesting Problem : To Find nth NON-FIBONACCI NUMBER

First Few Non-Fibonacci nos. are : 4,6,7,9,10,11,12..........................

This is very similar to generating fibonacci numbers.Initialize your loop with the 3 initial fibonacci numbers a=1,b=1,c=2.Now , whenever this loop iterates, this tuple moves on to the next tuple of fibonacci numbers.(a=1,b=2,c=3).At every iteration, the number of non-fibonacci numbers jumped over is c-b+1.Keep adding this count as long as it is less than N. When this count exceeds N, it means that we just crossed the Nth Non-Fibonacci number on the numberLine. So if we move back the required numbers (the number by which count exceeds N), we will get the answer.

Complexity: O(log n)

              a=1 b=2 c=3

              while(n>0)

              {

               a=b;

               b=c;

               c=a+b;

               n-=(c-b-1);

              }

              n+=(c-b-1);

              ans=b+n;

CODEFORCES ROUND 297 Div. 2 ( Pasha and String )

Problem Link

Go Greedy!!!

Main Idea is that you go in any order , the swaps will not change.
Swap and Unswap totally depends on the total swap at that position

So , First just mark the swaps at each positon.

Then , sum them to get the total swaps at each position

Now if swap sum count is odd then swap otherwise not

This is one of the finest problem i had seen on greedy basic !!