Wednesday, 24 December 2014

Hackerrank Bot saves princess Solution

Problem Statement
Princess Peach is trapped in one of the four corners of a square grid. You are in the center of the grid and can move one step at a time in any of the four directions. Can you rescue the princess?
Input format
The first line contains an odd integer N (3 <= N < 100) denoting the size of the grid. This is followed by an NxN grid. Each cell is denoted by '-' (ascii value: 45). The bot position is denoted by 'm' and the princess position is denoted by 'p'.
Grid is indexed using Matrix Convention
Output format
Print out the moves you will take to rescue the princess in one go. The moves must be separated by '\n', a newline. The valid moves are LEFT or RIGHT or UP or DOWN.
Sample input
3
---
-m-
p--
Sample output
DOWN
LEFT
Task
Complete the function displayPathtoPrincess which takes in two parameters - the integer N and the character array grid. The grid will be formatted exactly as you see it in the input, so for the sample input the princess is at grid[2][0]. The function shall output moves (LEFT, RIGHT, UP or DOWN) on consecutive lines to rescue/reach the princess. The goal is to reach the princess in as few moves as possible.
The above sample input is just to help you understand the format. The princess ('p') can be in any one of the four corners.
Scoring
Your score is calculated as follows : (NxN - number of moves made to rescue the princess)/10, where N is the size of the grid (3x3 in the sample testcase).
Source Code:
 #include <stdio.h>  
 #include <string.h>  
 #include <math.h>  
 void displayPathtoPrincess(int n, char grid[101][101]){  
   //logic here  
   int i =0,j=0,posi=0,posj=0;  
   for(i=0;i<n;i++)  
     {  
     for(j=0;j<n;j++){  
       if(grid[i][j]=='m')  
         {  
         posi = i;  
         posj = j;  
       }  
     }  
   }  
   if(grid[0][0]=='p')  
     {  
     while(posj>0)  
       {  
       posj--;  
       printf("UP\n");  
     }  
     while(posi>0)  
       {  
       posi--;  
       printf("LEFT\n");  
     }  
   }  
   else if(grid[0][n-1]=='p')  
     {  
         while(posj>0)  
       {  
       posj--;  
       printf("UP\n");  
     }  
     while(posi<n-1)  
       {  
       posi++;  
       printf("RIGHT\n");  
     }  
   }  
   else if(grid[n-1][0]=='p')  
     {  
         while(posj<n-1)  
       {  
       posj++;  
       printf("DOWN\n");  
     }  
     while(posi>0)  
       {  
       posi--;  
       printf("LEFT\n");  
     }  
   }  
   else  
     {  
     while(posj<n-1)  
       {  
       posj++;  
       printf("DOWN\n");  
     }  
     while(posi<n-1)  
       {  
       posi++;  
       printf("RIGHT\n");  
     }  
   }  
 }  
 int main()  
 {  
   int m,i;  
   scanf("%d", &m);  
   char grid[101][101];  
   char line[101];  
   for( i=0; i<m; i++) {  
     scanf("%s", line);  
     strcpy(grid[i], line);  
   }  
   displayPathtoPrincess(m,grid);  
   return 0;  
 }  
** The above solution is my own code and it may not be the optimal solution or optimal way to approach the problem but it passes all the testcases in Hackerrank. So if you have any optimal approaches feel free to paste the code as the comment below..... :) :) :)




Hackerrank ACM ICPC Team Solution

Problem Statement
You are given a list of N people who are attending ACM-ICPC World Finals. Each of them are either well versed in a topic or they are not. Find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics.
Input Format
The first line contains two integers N and M separated by a single space, where N represents the number of people, and M represents the number of topics. N lines follow.
Each line contains a binary string of length M. If the ith line's jth character is 1, then the ithperson knows the jth topic and doesn't know the topic otherwise.
Output Format
On the first line, print the maximum number of topics a 2-person team can know.
On the second line, print the number of 2-person teams that can know the maximum number of topics. 
Constraints
2 ≤ N ≤ 500
1 ≤ M ≤ 500
Sample Input
4 5
10101
11100
11010
00101
Sample Output
5
2
Explanation
(1, 3) and (3, 4) know all the 5 topics. So the maximal topics a 2-person team knows is 5, and only 2 teams can achieve this.
Source Code:
 #include <cmath>  
 #include <cstdio>  
 #include <vector>  
 #include <iostream>  
 #include <algorithm>  
 using namespace std;  
 int main() {  
   /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
   int arr[500][500],n,m,i,j,k,problem=0,team=0;  
   char val[600][600];  
   cin>>n>>m;  
   for(i=0;i<n;i++){  
     cin>>val[i];      
   }  
   int tproblem = 0,tteam = 0,flag =0;  
   for(i=0;i<n;i++){  
     for(j=i+1;j<n;j++)  
       {  
       flag = 0;  
       tproblem = 0;  
       for(k=0;k<m;k++){  
         int x,y;  
         x = val[i][k]-48;  
         y = val[j][k]-48;  
         //cout<<x<<"x";  
         if(x|y){  
           tproblem ++;  
         }  
       }  
       if(tproblem == problem){  
         tteam++;  
       }  
       if(tproblem > problem){  
         problem = tproblem;  
         tteam= 1;  
       }  
     }  
   }  
   cout<<problem<<endl<<tteam<<endl;  
   return 0;  
 }  

** The above solution is my own code and it may not be the optimal solution or optimal way to approach the problem but it passes all the testcases in Hackerrank. So if you have any optimal approaches feel free to paste the code as the comment below..... :) :) :)

Tuesday, 23 December 2014

Hackerrank Angry Children Solution

Problem Statement
Bill Gates is on one of his philanthropic journeys to a village in Utopia. He has N packets of candies and would like to distribute one packet to each of the K children in the village (each packet may contain different number of candies). To avoid any fighting among the children, he would like to pick K out of N packets, such that unfairness is minimized.
Suppose the K packets have (x1, x2, x3,....xk) candies in them, where xi denotes the number of candies in the ith packet, then we define unfairness as
max(x1,x2,...xk) - min(x1,x2,...xk)
where max denotes the highest value amongst the elements, and min denotes the least value amongst the elements. Can you figure out the minimum unfairness and print it?
Input Format
The first line contains an integer N.
The second line contains an integer KN lines follow. Each line contains an integer that denotes the candy in the nth (1nN) packet.
Output Format
An integer that denotes the minimum possible value of unfairness.
Constraints
1<=N<=105
1<=K<=N
0<= number of candies in any packet <=109
Sample Input #00
7
3
10
100
300
200
1000
20
30
Sample Output #00
20
Explanation #00
Here K = 3. We can choose packets that contain 10,20,30 candies. The unfairness is
max(10,20,30) - min(10,20,30) = 30 - 10 = 20
Sample Input #01
10
4
1
2
3
4
10
20
30
40
100
200
Sample Output #01
3
Explanation #01
Here K = 4. We can choose the packets that contain 1,2,3,4 candies. The unfairness is
max(1,2,3,4) - min(1,2,3,4) = 4 - 1 = 3

Source Code:

 #include <stdio.h>  
 #include <string.h>  
 #include <math.h>  
 #include <stdlib.h>  
 #include <algorithm>  
 using namespace std;  
 #define MAX 100000  
 #define MAX_VAL 1000000001  
 int candies[MAX];  
 int cmpfunc (const void * a, const void * b)  
 {  
   return ( *(int*)a - *(int*)b );  
 }  
 /** The code to read from STDIN and output to STDOUT has been provided by us, for convenience. You may or may not use this. **/  
 int main() {  
   int N,K;  
   int i,upper,lower[MAX];  
   scanf("%d %d",&N,&K);  
   for(i = 0;i < N;i++){  
     scanf("%d",candies + i);  
   }  
   sort(candies,candies+N);  
   int unfairness =  candies[K-1]-candies[0];  
 for(i = 0;i < N-K-1;i++){  
   if(unfairness>candies[i+K-1]-candies[i])  
     unfairness = candies[i+K-1]-candies[i];  
 }  
   // Compute the min unfairness over here, using N,K,candies  
   printf("%d\n",unfairness);  
   return 0;  
 }  



** The above solution is my own code and it may not be the optimal solution or optimal way to approach the problem but it passes all the testcases in Hackerrank. So if you have any optimal approaches feel free to paste the code as the comment below..... :) :) :)


Hackerrank Counting Sort 3 Solution

Problem Statement
In the previous challenge, it was easy to print all the integers in order, since you did not have to access the original list. Once you had obtained the frequencies of all the integers, you could simply print each integer in order the correct number of times. However, if there is other data associated with an element, you will have to access the original element itself.
In the final counting sort challenge, you are required to print the data associated with each integer. This means, you will go through the original array to get the data, and then use some "helper arrays" to determine where to place everything in a sorted array.
If you know the frequencies of each element, you know how many times to place it, but which index will you start placing it from? It will be helpful to create a helper array for the "starting values" of each element.
Challenge
You will be given a list that contains both integers and strings. In this challenge you just care about the integers. For every value i from 0 to 99, can you output L, the number of elements that are less than or equal to i?
Input Format
n - the size of the list ar.
n lines follow, each containing an integer x, and a string, s.
Output Format
Output L for all numbers from 0 to 99 (inclusive).
Constraints
1 <= n <= 1000000
0 <= x < 100 , x ∈ ar
Sample Input
10
4 that
3 be
0 to
1 be
5 question
1 or
2 not
4 is
2 to
4 the
Sample Output
1 3 5 6 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 
Explanation
0 appears 1 time, so the 0th number is 1.
0 and 1 combined appear 3 times, so the next number is 3.
This continues for the rest of the list, until no more new numbers appear.
Source Code:
 #include <cmath>  
 #include <cstdio>  
 #include <vector>  
 #include <iostream>  
 #include <string>  
 #include <algorithm>  
 using namespace std;  
 int main() {  
   /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
   unsigned long long t;  
   unsigned long long arr[150]={0},i,j,k,sum =0,x;  
     string a;  
   cin>>t;  
   k = t;  
   while(t--){  
     cin>>x>>a;  
     arr[x]++;  
   }i=0;  
   while(i<100){  
     sum += arr[i];  
     cout<<sum<<" ";  
     i++;  
   }  
   return 0;  
 }  
** The above solution is my own code and it may not be the optimal solution or optimal way to approach the problem but it passes all the testcases in Hackerrank. So if you have any optimal approaches feel free to paste the code as the comment below..... :) :) :)


Hackerrank Counting Sort 2 Solution


Problem Statement
Often, when a list is sorted, the elements being sorted are just keys to other values. For example, if you are sorting files by their size, the sizes need to stay connected to their respective files. You cannot just take the size numbers and output them in order, you need to output all the required file information.
However, if you are not concerned about any other information, then you can simply sort those numbers alone. This makes counting sort very simple. If you already counted the values in the list, you don't need to access the original list again. This challenge involves a simple counting sort where the elements being sorted are all that matter.
Challenge
Given an unsorted list of integers, output the integers in order.
Hint: You can use your previous code that counted the items to print out the actual values in-order.
Input Format
There will be two lines of input:
  • n - the size of the list
  • ar - n space separated numbers that belong to the list
Output Format
Output all the numbers of the list in-order.
Constraints
1 <= n <= 1000000
0 <= x < 100 , x ∈ ar
Sample Input
100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33 
Sample Output
1 1 3 3 6 8 9 9 10 12 13 16 16 18 20 21 21 22 23 24 25 25 25 27 27 30 30 32 32 32 33 33 33 34 39 39 40 40 41 42 43 44 44 46 46 48 50 53 56 56 57 59 60 61 63 65 67 67 68 69 69 69 70 70 73 73 74 75 75 76 78 78 79 79 80 81 81 82 83 83 84 85 86 86 87 87 89 89 89 90 90 91 92 94 95 96 98 98 99 99 
Explanation
In the output you can see the numbers sorted in ascending order. You can also see that numbers appearing multiple times are printed accordingly.
Source Code:

 #include <cmath>  
 #include <cstdio>  
 #include <vector>  
 #include <iostream>  
 #include <algorithm>  
 using namespace std;  
 int main() {  
   /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
   long long arr[1000000] ={0},i,j,k,x,n;  
   cin>>n;  
   for(i=0;i<n;i++){  
     cin>>x;  
     arr[x]++;  
   }  
   i=0;  
   while(n>0){  
     while(arr[i]>0){  
       cout<<i<<" ";  
       n--;  
       arr[i]--;  
     }  
     i++;  
   }  
   cout<<endl;  
   return 0;  
 }  

** The above solution is my own code and it may not be the optimal solution or optimal way to approach the problem but it passes all the testcases in Hackerrank. So if you have any optimal approaches feel free to paste the code as the comment below..... :) :) :)

Hackerrank Counting Sort 1 Solution

Problem Statement
Comparison Sorting
Quicksort usually has a running time of n*log(n), but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e., they sort a list just by comparing the elements with one another. A comparison sort algorithm cannot beat n log(n) (worst-case) running time, since n log(n) represents the minimum number of comparisons needed to know where to place each element. For more details, you can see these notes (PDF).
Alternative Sorting
However, for certain types of input, it is more efficient to use a non-comparison sorting algorithm. This will make it possible to sort lists even in linear time. These challenges will cover Counting Sort, a fast way to sort lists where the elements have a small number of possible values, such as integers within a certain range. We will start with an easy task - counting.

Challenge
Given a list of integers, can you count and output the number of times each value appears?
Hint: There is no need to sort the data, you just need to count it.
Input Format
There will be two lines of input:
  • n - the size of the list
  • ar - n space separated numbers that makes up the list
Output Format
Output the number of times every number from 0 to 99 (inclusive) appears in the list.
Constraints
100 <= n <= 106
0 <= x < 100 , x ∈ ar
Sample Input
100
63 25 73 1 98 73 56 84 86 57 16 83 8 25 81 56 9 53 98 67 99 12 83 89 80 91 39 86 76 85 74 39 25 90 59 10 94 32 44 3 89 30 27 79 46 96 27 32 18 21 92 69 81 40 40 34 68 78 24 87 42 69 23 41 78 22 6 90 99 89 50 30 20 1 43 3 70 95 33 46 44 9 69 48 33 60 65 16 82 67 61 32 21 79 75 75 13 87 70 33 
Sample Output
0 2 0 2 0 0 1 0 1 2 1 0 1 1 0 0 2 0 1 0 1 2 1 1 1 3 0 2 0 0 2 0 3 3 1 0 0 0 0 2 2 1 1 1 2 0 2 0 1 0 1 0 0 1 0 0 2 1 0 1 1 1 0 1 0 1 0 2 1 3 2 0 0 2 1 2 1 0 2 2 1 2 1 2 1 1 2 2 0 3 2 1 1 0 1 1 1 0 2 2 
Explanation
the output states that 0 appears 0 times.
1 appears 2 times.
2 appears 0 times.
and so on in the given input array.

Source Code:
 #include <cmath>  
 #include <cstdio>  
 #include <vector>  
 #include <iostream>  
 #include <algorithm>  
 using namespace std;  
 int main() {  
   /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
   long long arr[1000000]={0},n,i,j,k,x;  
   cin>>n;  
   for(i=0;i<n;i++){  
     cin>>x;  
     arr[x]++;  
   }  
   for(i=0;i<100;i++)  
     {  
     cout<<arr[i]<<" ";  
   }  
   cout<<endl;  
   return 0;  
 }  

** The above solution is my own code and it may not be the optimal solution or optimal way to approach the problem but it passes all the testcases in Hackerrank. So if you have any optimal approaches feel free to paste the code as the comment below..... :) :) :)


Hackerrank Connecting Towns Solution

Problem Statement
Gandalf is travelling from Rohan to Rivendell to meet Frodo but there is no direct route fromRohan (T1) to Rivendell (Tn).
But there are towns T2,T3,T4...Tn-1 such that there are N1 routes from Town T1 to T2, and in general, Ni routes from Ti to Ti+1 for i=1 to n-1 and 0 routes for any other Ti to Tj for j ≠ i+1
Find the total number of routes Gandalf can take to reach Rivendell from Rohan.
Note
Gandalf has to pass all the towns Ti for i=1 to n-1 in numerical order to reach Tn.
For each Ti , Ti+1 there are only Ni distinct routes Gandalf can take.
Input Format
The first line contains an integer T, T test-cases follow.
Each test-case has 2 lines. The first line contains an integer N (the number of towns).
The second line contains N - 1 space separated integers where the ith integer denotes the number of routes, Ni, from the town Ti to Ti+1
Output Format
Total number of routes from T1 to Tn modulo 1234567
Constraints
1 <= T<=1000
2< N <=100
1 <= Ni <=1000
Sample Input
2
3
1 3
4
2 2 2
Sample Output
3
8
Explanation
Case 1: 1 route from T1 to T2, 3 routes from T2 to T3, hence only 3 routes.
Case 2: There are 2 routes from each city to the next, at each city, Gandalf has 2 choices to make, hence 2 * 2 * 2 = 8.

Source Code:


 import java.io.*;  
 import java.util.*;  
 import java.text.*;  
 import java.math.*;  
 import java.util.regex.*;  
 public class Solution {  
   public static void main(String[] args) throws Exception{  
     /*  
   {  
   } */  
     int t;  
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
     String nn = br.readLine();  
     t = Integer.parseInt(nn);  
     while((t--)>0){  
       int num,sum,i;  
     BigInteger array = new BigInteger("1");  
       String n = br.readLine();  
       num = Integer.parseInt(n);  
       String nns[] = br.readLine().split(" ");  
     for(i=0;i<num-1;i++)  
     {  
       sum = Integer.parseInt(nns[i]);  
       array = array.multiply(new BigInteger(sum+""));  
     }  
       array = array.modPow(new BigInteger(1+""),new BigInteger(1234567+""));  
     System.out.println(array)  ;  
     }  
   }  
 }  

** The above solution is my own code and it may not be the optimal solution or optimal way to approach the problem but it passes all the testcases in Hackerrank. So if you have any optimal approaches feel free to paste the code as the comment below..... :) :) :)