Massive Algorithms: Hackerearth

Showing posts with label Hackerearth. Show all posts

Sauron Eye | Solve programming problems on HackerEarth

Sauron Eye | Solve programming problems on HackerEarth
Gandalf the Grey is in trouble as Saurons eye Rearrived in the middle world. Now he has to prepare for the war, But in order to defeat Sauron he has to know the power of saurons eye on the day in which he wants to attack.
According to the Elves(Good Friends of Gandalf),Gandalf came to know that saurons eye power on current day is equal to 3 time to its power on previous day minus the power on a day before previous day.
Now Gandalf ask Frodo to give him the power of the Saurons Eye on nth day, but poor Frodo is not good in mathematics so he ask for help from you.
Given the nth day you have to give Frodo power of Saurons eye on that day mod 10⁹ + 7.
Note You can assume the power of sauron eye is 1 on 1st day
and 3 on 2nd day.

As you have rightly identified given n solution is
f(n)= 3*f(n-1)-f(n-2);
This can be solved using matrix exponentiation as recurrance matrix
[3 -1 ]
[1 0 ]
you can read about matrix exponentiation here
http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html
https://www.hackerearth.com/submission/1950666/

static int mod = (int)(1E9 + 7);
static long fib(long n)
{
long F[][] = {{3,-1},{1,0}};
if (n == 0)
return 0;
else if(n==1)
return 1;
power(F, n-1);
return F[0][0];
}
/* Optimized version of power() in method 4 */
static void power(long F[][], long n)
{
if( n == 0 || n == 1)
return;
long M[][] = {{3,-1},{1,0}};
power(F, n/2);
multiply(F, F);
if (n%2 != 0)
multiply(F, M);
}
static void multiply(long F[][], long M[][])
{
long x = ((F[0][0]*M[0][0])%mod + (F[0][1]*M[1][0])%mod)%mod;
long y = ((F[0][0]*M[0][1])%mod + (F[0][1]*M[1][1])%mod)%mod;
long z = ((F[1][0]*M[0][0])%mod + (F[1][1]*M[1][0])%mod)%mod;
long w = ((F[1][0]*M[0][1])%mod + (F[1][1]*M[1][1])%mod)%mod;
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}

Read full article from Sauron Eye | Solve programming problems on HackerEarth

Once upon a time in Time-Land | Solve programming problems on HackerEarth

Once upon a time in Time-Land | Solve programming problems on HackerEarth
In a mystical TimeLand, a person's health and wealth is measured in terms of time(seconds) left. Suppose a person there has 24x60x60 = 86400 seconds left, then he would live for another 1 day. A person dies when his time left becomes 0. Some time-amount can be borrowed from other person, or time-banks. Some time-amount can also be lend to another person, or can be used to buy stuffs.
Our hero Mr X, is in critical condition, has very less time left.
Today's the inaugural day of a new time-bank. So they are giving away free time-amount worth 1000 years.
Bank released N slips, A[1], A[2], .... A[N]. Each slip has a time-amount(can be +ve as well as -ve).
A person can pick any number of slips(even none, or all of them, or some of them) out of the N slips. But bank introduced a restriction, they announced one more number K. Restriction is that, if a person picks a slip A[i], then the next slip that he can choose to pick will be A[i+K+1]. It means there should be a difference of atleast K between the indices of slips picked.
Now slip(s) should be picked in such a way that their sum results in maximum positive time-amount sum possible with the given restriction.
If you predict the maximum positive sum possible, then you win.
Mr X has asked for your help. Help him win the lottery, and make it quick!
Input Format:
First line of the test file contains single number T, the number of test cases to follow.
Each test case consists of two lines.
First line contains two numbers N and K , separated by a space. Second line contains the N numbers A[1], A[2] ..... A[N] separated by space.
Output Format:
For every test case, output in a single line the maximum positive sum possible, that is output for the case.

Solution :

maximum sum is to be found, so we ignore negative integers.
If we select ith index, next index to be selected will be (i+K+1) th index.

Lets take a DP approach. We are going to construct an array in which all the indexes represent maximum possible sum upto that index following the above rules.

Take an array of size N. SUM(0....N-1)
Initialize all elements of that array to zero.
For an array with just 1 element, maximum sum would be that element or zero, SUM[0] = max(0, first element)
Then we iterate from index 1 to N-1.
- If integer at current index is negative we take the sum upto previous index as the maximum sum.
- If current index is less than or equal to K, i.e. we are still trying to pick the first element optimally, we pick the maximum(integer at current index, sum upto previous index).
- If Current index is greater than K, we select the maximum(sum upto previous index , integer at current index + sum upto [current index - K - 1]).
SUM[N-1] will be our answer.

    for(;T--;)
    {
        int N,K;
        cin >> N >> K;

        vector<long long> A(N), SUM(N,0);

        for (int i = 0; i < N; ++i)
            cin >> A[i];

        SUM[0] = max(A[0],0ll);
        for (int i = 1; i < N; ++i)
        {
            if(A[i] < 0)
                SUM[i] = SUM[i-1];
            else if(i-K-1 < 0)
                SUM[i] = max(SUM[i-1],A[i]);
            else
                SUM[i] = max(SUM[i-1],A[i]+SUM[i-K-1]); 
        }
        cout << SUM[N-1] << "\n";
    }

Read full article from Once upon a time in Time-Land | Solve programming problems on HackerEarth

Easy IPhone | Solve programming problems on HackerEarth

Easy IPhone | Solve programming problems on HackerEarth
Ricky is crazy about IPhones, he want to use IPhones throughout his life.
Ricky has X number of IPhones, he can use only one IPhone for a year. After one year of use an IPhone becomes useless and he cannot use it any more. The company has an exchange offer for Ricky; he will get one new IPhone if he will return Y number of useless IPhones. This new IPhone can be used like any other new IPhones.
Now you have to tell for how many years can he use IPhones?

    int X, Y;
    scanf ("%d %d", &X, &Y);
    int ret = 0, useless = 0;
    while (X) {
        ret += X;
        useless += X;
        X = useless / Y;
        useless %= Y;
    }
    printf ("%d\n", ret);

Read full article from Easy IPhone | Solve programming problems on HackerEarth

The Magic HackerEarth Nirvana solutions Hiring Challenge - GoHired

The Magic HackerEarth Nirvana solutions Hiring Challenge - GoHired
Navi got a task at school to collect N stones. Each day he can collect only one stone. As N can be a very large number so it could take many days to complete the task,
but then he remembers that his mother gave him a magic that can double anything (i.e if he has 2 stones, the magic will make them to 4 stones). Navi can use this magic any number of time on the collected stone on a particular day and add this to the previously collected stones. Remember that he wants exactly N stones and he can't throw any stone. If he gets more than N stones then he gets 0 marks, of course he doesn't want 0 marks. Help him to collect exactly N stones in minimum number of days.

1. Navi gets 1 stone each day, on which she can apply the magic operation and raise it to any power of 2 (1->2->4->8 .... ) . (Note that there's no restriction on the number of times she can apply the magic operation).
2. We have to minimize the number of days in which we can collect N stones.

Now the problem is reduced to: Representing a number N as sum of powers of 2, such that the number of elements chosen are minimum.
e.g. 5 can be represented as 1+1+1+1+1, 1+2+2, 1+4, etc. The combination: 1+4 is the best answer(i.e. 2), since we need to minimize the number of elements chosen.

This problem is again reduced to finding number of set bits when the number N is represented in binary. This method is correct since in binary representation of number each power of 2 is represented by a particular bit which can be either 0 or 1(i.e. chosen or not-chosen).

int countSetBits(int n)
{
int count = 0;
while (n) {
n &= (n-1) ;
count++;
}
return count;
}

int T,N,stone,remaining,day;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
day=1;
remaining=N;
    while(1)
    {
        if(remaining==1) 
        break;
        if(remaining==0)
        {day--; break;}
        stone=1;
        while( (stone*2) <= remaining){
            stone = 2*stone;
        }
    remaining = remaining - stone;
    day++;
    }
printf("%dn",day);

Read full article from The Magic HackerEarth Nirvana solutions Hiring Challenge - GoHired

Problem solving with programming: Check if a number is the mirror image of itself

https://www.hackerearth.com/problem/algorithm/mirror-of-mahatma-gandhi/description/
Given an arbitrarily large number, how to check if it is same as it's mirror image.

Only need traverse once ==>


     string result = "YES";


     cin >> input;


     int i,j;


     for( i = 0; i < input.size(); i++ )


     {


      if( input[i] != '0' && input[i] != '1' && input[i] != '8' )


      {


       result = "NO";


       break;


      }


     }


     for( i = 0, j = input.size()-1; i <= j; i++, j--)


     {


      if( input[i] != input[j] )


      {


       result = "NO";


       break;


      }


     }


     cout << result << endl;


    }

Read full article from Problem solving with programming: Check if a number is the mirror image of itself

HackerRank ‘Max Min’ / ‘Angry Children’ Solution | MartinKysel.com

HackerRank 'Max Min' / 'Angry Children' Solution | MartinKysel.com

Given a list of

N integers, your task is to select

K integers from the list such that its unfairnessis minimized.

(x1,x2,x3,…,xk) are

K numbers selected from the list

N, the unfairness is defined as

m a x (x 1, x 2, \dots, x k) - m i n (x 1, x 2, \dots, x k)

where max denotes the largest integer among the elements of

K, and min denotes the smallest integer among the elements of

Pre-sort:
The unfairness is the distance between K elements in a sorted array.

if __name__ == '__main__':

    n = input()

    k = input()

    candies = [input() for _ in range(0,n)]

    candies.sort()

    min_diff = 1000000000

    ## Write code here to compute the answer using (n, k, candies)

    for i in xrange(n - k + 1):

        min_diff = min(min_diff, candies[i+k-1] - candies[i])

    print min_diff

Finding a sub list with least max-min difference - Codeforces puzzle
http://comproguide.blogspot.com/2015/02/finding-sub-list-with-least-max-min.html
The solution is to first sort the numbers in ascending order, and move a sliding window of sub-list size from begin to end while keeping track of the minimum difference between first and last numbers of the sub-list.


 sort(sizes.begin(), sizes.end());


 


 int start = 0, end = students-1;


 int minDiff = INT_MAX;


 while( end < list_len )


 {


  minDiff = min(minDiff, sizes[end]-sizes[start]);


  start++;


  end++;


 }


 cout << minDiff << endl;

Read full article from HackerRank 'Max Min' / 'Angry Children' Solution | MartinKysel.com