Programming Geek
Rated 4.1/5 based on 446 reviews

Pebble Merchant : Problem #7 ( Aspirations 2020)





The problem is simple, It just needs a simple mathematics of calculating the area given the
coordinates of several vertices of a polygon:

The input file as given in the contest was:

package test.pebblemerchant;

public class PebbleMerchant {
 
 public int[ ] findCost(char[ ] direction,int[ ] length) 
 {
  //write code here
  int a[] = {0,0};
  return a;
 }
 
  public static void main(String args[]) 
  {
   PebbleMerchant pm = new PebbleMerchant();
   
   // example1
   {
    char[] direction = {'L','R','R','L','L','R','R','R','R','L','Z'};
       int[] length = {2,2,1,1,1,2,5,2,2,3,1};
   
       int res[] = pm.findCost(direction, length);
   
       for (int i = 0; i < res.length; i++)
       {
        System.out.println(res[i]);
       }
   }
   
   // example3
   {
    char[] direction = {'L','R','L','R','R','L','R','R','L','R','A','L','Z'};
     int[] length = {1,2,2,2,2,2,5,2,1,2,3,2,2};
 
     int res[] = pm.findCost(direction, length);
 
     for (int i = 0; i < res.length; i++)
     {
      System.out.println(res[i]);
     }
   }
  }
}


The solution is:
package test.pebblemerchant;

import java.awt.Point;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;

public class PebbleMerchant {

    public int[] findCost(char[] direction, int[] length) {
        int a[] = {0, 0};
        boolean flag = false;
        flag = isInvalid(direction, length);
        if (flag == false) {
            return a;
        } else {
            int area = getResult(direction, length);
            int cost = area * 15;
            a[0] = area;
            a[1] = cost;
            return a;
        }
    }

    public boolean isInvalid(char[] dir, int[] len) {
        boolean flag = false;

        if (dir == null || len == null) {

            return flag;
        } else if (dir.length != len.length) {

            return flag;
        } else if (!(dir[dir.length - 1] == 'Z')) {

            return flag;
        } else {

            for (int i = 0; i < len.length; i++) {
                if (len[i] <= 0) {
                    return flag;
                }

            }

            for (int i = 0; i < len.length - 1; i++) {
                if (dir[i] == 'L' || dir[i] == 'R') {
                    continue;
                } else {
                    return flag;
                }


            }
        }

        return true;


    }

    public int getResult(char[] direction, int[] length) {
       
        int x = 0;
        int y = 0;
        Vik vik = new Vik();
        ArrayList pArrayList = new ArrayList();
        for (int i = 0; i < direction.length; i++) {
            if (direction[i] == 'Z') {
                Point p = new Point(0, 0);
                pArrayList.add(p);
                break;
            }
            String next = vik.getNext(direction[i] + "");

            if (next.equals("X")) {
                x -= length[i];
                Point p = new Point(x, y);
                pArrayList.add(p);
                vik.curr = "W";
            }
            if (next.equals("XX")) {
                x += length[i];
                Point p = new Point(x, y);
                pArrayList.add(p);
                vik.curr = "E";
            }
            if (next.equals("Y")) {
                y += length[i];

                Point p = new Point(x, y);
                pArrayList.add(p);
                vik.curr = "N";
            }
            if (next.equals("YY")) {
                y -= length[i];
                Point p = new Point(x, y);
                pArrayList.add(p);
                vik.curr = "S";
            }

        }

        int area = 0;
        for (int i = 0; i < pArrayList.size(); i++) {
            if (i == pArrayList.size() - 1) {
                Point p = pArrayList.get(i);
                Point p1 = pArrayList.get(0);

                area += p.getX() * p1.getY() - p.getY() * p1.getX();


            } else {
                Point p = pArrayList.get(i);
                Point p1 = pArrayList.get(i + 1);
                area += p.getX() * p1.getY() - p.getY() * p1.getX();
            }



        }
        if (area < 0) {
            area *= -1;
        }
      //  System.out.println("area=" + area / 2);
        return area / 2;

    }

    private double area(Rectangle2D r) {
        return r.getWidth() * r.getHeight();
    }

    class Vik {

        String curr = "N";
        String next;

        String getNext(String str) {
            str.trim();
            if (curr.equals("N")) {
                if (str.equals("L")) {
                    next = "X";
                } else {
                    next = "XX";
                }

            }
            if (curr.equals("W")) {
                if (str.equals("L")) {
                    next = "YY";
                } else {
                    next = "Y";
                }
            }
            if (curr.equals("E")) {
                if (str.equals("L")) {
                    next = "Y";
                } else {
                    next = "YY";
                }


            }
            if (curr.equals("S")) {
                if (str.equals("L")) {
                    next = "XX";
                } else {
                    next = "X";
                }

            }
            return next;
        }
    }

    public static void main(String args[]) {
        PebbleMerchant pm = new PebbleMerchant();

        // example1
        {
            char[] direction = {'L', 'R', 'R', 'L', 'L', 'R', 'R', 'R', 'R', 'L', 'Z'};
            int[] length = {2, 2, 1, 1, 1, 2, 5, 2, 2, 3, 1};

            int res[] = pm.findCost(direction, length);


            for (int i = 0; i < res.length; i++) {
                System.out.println(res[i]);
            }

        }


        {
            char[] direction = {'L', 'L', 'R', 'R', 'L', 'R', 'R', 'L', 'R', 'L', 'R', 'R', 'L', 'R', 'L', 'R', 'R', 'L', 'Z'};
            int[] length = {1, 1, 1, 1, 2, 2, 2, 2, 1, 2, 1, 2, 2, 1, 1, 1, 1, 2, 2};
// char[] d={'L','R','R','R','Z'};
            // int[] l={1,1,2,1,1};
            //  pm.findCost(d, l);
            int res[] = pm.findCost(direction, length);

            for (int i = 0; i < res.length; i++) {
                System.out.println(res[i]);
            }

        }


        {
            char[] direction = {'L', 'R', 'L', 'R', 'R', 'L', 'R', 'R', 'L', 'R', 'A', 'L', 'Z'};
            int[] length = {1, 2, 2, 2, 2, 2, 5, 2, 1, 2, 3, 2, 2};

            int res[] = pm.findCost(direction, length);

            for (int i = 0; i < res.length; i++) {
                System.out.println(res[i]);
            }
        }

    }
}


Aspirations 2020 : A Programming Contest organized by Infosys




So here goes a great opportunity for you guys pursuing engineering or MCA and in second year or above. SO get ready to show your algorithmic and programming skill. This contest is organized by campus connect team of Infosys and sponsored by Infosys Limited. You will get a certificate also.This is a team event and there must be at least two members in the team. A team can comprise of at most three members. I suggest you to have three members in the team because each team members helps when need arises.I participated in Aspirations 2020 last year and won at college level. I visited Infosys Bhubaneswar Development Centre for DC round . It was a memorable moment for me. We could not qualify for final round but had a great experience. I will be posting problems and solutions of college round of last year Aspirations 2020 so keep visiting this site.



The schedule of this year Aspirations 2020 are as follows :

Briefing to colleges & college level campaigns1st & 2nd weeks of September, 2013 at your college
Registration Start Date Teasers1st & 2nd weeks of September, 2013
Registration End DateWednesday, 25th September, 2013
College Round1st Week of October, 2013 at your college
DC FinalsWednesday, 17th October, 2013 at Infosys Development Centre of your region (check at contest website)

The registration are open now. So what are you waiting for? Register your team and prepare yourself for a journey which will evaluate you what you know and what you can present when need of them arises because being only bookish worm can not get you a grand new gift sponsored by Infosys Limited. So register your self at http://campusconnect.infosys.com/aspirations and get ready to show your programming and algorithmic skill.

Have query ? Do leave a comment below... :)

CodeVita 2013 : Solution of Game of Primes

The problem statement is as given below :

Problem
In a global Mathematics contest, the contestants are told to invent some special numbers which can be built by adding the squares of its digits. Doing this perpetually, the numbers will end up to 1 or 4.
If a positive integer ends with 1, then it is called the Number of Game.
An example from above is:
13 = 1^2 + 3^2 = 1+9 = 10 (Step:1)
10 = 1^2 + 0^2 = 1+0 = 1 (Step:2), iteration ends in Step 2 since number ends with 1

Then in next round, the contestants are asked to combine their newly invented number, i.e. Number of Game with prime number.
Now, being a smart programmer, write a program to help the contestants to find out the Nth combined number within any given range, where N can be any integer.

Input Format:

Input consists of 3 integers X, Y, N, one on each line. X and Y are upper and lower limits of the range. The range is inclusive of both X and Y. Find Nth number in range [X,Y].

Line 1
X,where X is the upper limit of the range
Line 2
Y,where Y is the lower limit of the range
Line 3
N,where Nth element of the series is required

Constraints:

X <= Y
X > 0
N > 0

Output Format:

Output will show the Nth element of the combined series lying in the range between X and Y.

Line 1
For Valid Input,print

U,where U is the Nth element of the combined number series lying in the range between X and Y.

Or

No number is present at this index

For Invalid Input,print

Invalid Input


Sample Input and Output


SNo.InputOutput
1
1
30
3
19
2
12
33
5
No number is present at this index
3
-5
@
4
Invalid Input

Solution : 

import java.util.Scanner;


/**
 *
 * @author VIK
 */
public class GameOfPrimes {
    
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        try{
            
            int lower=0,upper=0,n=0;
            boolean flag=false;
            try {
                 lower=Integer.parseInt(sc.nextLine().trim());
        
            } catch (Exception e) {
                flag=true;
            }
            try {
                 upper =Integer.parseInt(sc.nextLine().trim());
        
            } catch (Exception e) {
                flag=true;
            }
            try {
                 n=Integer.parseInt(sc.nextLine().trim());
            } catch (Exception e) {
                flag=true;
            }
            if(flag)
                throw new Exception();
            if(lower>upper || lower<=0 || n<=0)
                throw new Exception();
        
        int count=0;
        int i=lower;
        for (i = lower; i <=upper; i++) {
            if(isPrime(i) && getJohn(i)==1)
            {
                count++;
               // System.out.println(count+" "+i+" "+getJohn(i));
                if(count==n)
                {    System.out.println(i);
                    break;
                }
                
            }
            
        }
        if(i>upper)
        {
            System.out.println("No number is present at this index");
        }
        }catch(Exception e)
        {
            System.out.println("Invalid Input");
        }
    }
    
    
    public static boolean isPrime(int num) {
        boolean flag = false;
        if (num < 2) {
            return flag;
        }
        if (num == 2) {
            return true;
        }
        if (num % 2 == 0) {
            return flag;
        }
        int i = 3;
        int rootn = (int) Math.sqrt(num);
        for (; i <= rootn; i += 2) {
            if (num % i == 0) {
                break;
            }

        }
        if (i > rootn) {
            flag = true;
        }
        return flag;
    }
     static int getJohn(int y)
    {
        if(y<=4)
        {
            return y;
        }
        if(y==10)
            return 1;
        String s=y+"";
        
        char[] c=s.trim().toCharArray();
        int sum=0;
        for (int i = 0; i < c.length; i++) {
            sum+=Math.pow(Integer.parseInt(c[i]+"".trim()),2);
        }
        
        
        sum= getJohn(sum);
        return sum;
        
    }
}

CodeVita 2013 : Solution of Jumble With Numbers

Problem
In NASA, two researchers, Mathew and John, started their work on a new planet, but while practicing research they faced a mathematical difficulty. In order to save the time they divided their work.
So scientist Mathew worked on a piece and invented a number computed with the following formula:
A Mathew number is computed as follows using the formula:
H(n) = n(2n-1)
And scientist John invented another number which is built by the following formula which is called John number.
T(n) = n(n+1)/2
Now Mathew and John are jumbled while combining their work. Now help them combine their research work by finding out number in a given range that satisfies both properties. Using the above formula, the first few Mathew-John numbers are:
1 6 15 28 …

Input Format:

Input consists of 3 integers T1,T2,M separated by space . T1 and T2 are upper and lower limits of the range. The range is inclusive of both T1 and T2. Find Mth number in range [T1,T2] which is actually a Mathew-John number.


Line 1
T1 T2 M,where T1 is upper limit of the range, T2 is lower limit of the range and M ,where Mth element of the series is required

Constraints:

0 < T1 < T2 < 1000000

Output Format:

Print Mth number from formed sequence between T1 and T2(inclusive).

Line 1
For Valid Input,print

Print Mth number from formed sequence between T1 and T2
Or
No number is present at this index

For Invalid Input,print

Invalid Input


Sample Input and Output


SNo.InputOutput
1               
90 150 2             
120
2
20 80 6
No number is present at this index
3
-5 3 a
Invalid Input

Solution :
import java.util.Scanner;

/**
 *
 * @author VIK
 */
public class JumbleWithNumbers {

    public static void main(String[] args) {
        int lower = 0;
        int upper = 0;
        int n = 0;
        Scanner sc = new Scanner(System.in);
        String[] s=sc.nextLine().trim().split(" ");
        try {
            boolean flag = false;
            try {
                lower = Integer.parseInt(s[0].trim());

            } catch (Exception e) {
                flag = true;
            }
            try {
                upper = Integer.parseInt(s[1].trim());

            } catch (Exception e) {
                flag = true;
            }
            try {
                n = Integer.parseInt(s[2].trim());
            } catch (Exception e) {
                flag = true;
            }
            if (flag) {
                throw new Exception();
            }
            if (lower > upper) {
                throw new Exception();
            }

            int i = 1;
            flag = false;
            int count = 0;
            while (true) {
                int nu = i * (2 * i - 1);

                if (nu < lower) {
                    i++;
                    continue;
                }
                if (getMathew(lower,upper,nu)) {
                    count++;
                    if (count == n) {
                        System.out.println(nu);
                        break;
                    }

                }

                if (nu > upper) {
                    flag = true;
                    break;
                }



                i++;
            }
            if (flag) {
                System.out.println("No number is present at this index");
            }
        } catch (Exception e) {
            System.out.println("Invalid Input");
        }
    }

    static boolean getMathew(int lower,int upper,int num) {


        int i = 1;
        while (true) {
            int nu = i * (i + 1);
            nu /= 2;
            if (nu < lower) {
                i++;
                continue;
            }

            if (nu == num) {
                return true;
            }
            if (nu > upper) {

                break;
            }



            i++;

        }
        return false;
    }
}

CodeVita 2013 : Solution of Zombie World

The problem statement is as follows :

Problem

One day Bob is playing Zombie World video game. In Zombie World game each round will contain N zombie's and each zombie's energy is Zi (where 1<=i<=N). Bob will start the round with B energy. In order to move to the next level Bob need to kill all the N zombie's but Bob can select any one among N Zombie's. If energy of Bob (B) is less than Zombie energy (Zi) then Bob will die and lose the round else Bob will won, during the fighting with zombie, Bob will lose his energy by (Zi%2)+(Zi/2). At any point of game Bob will play optimally. Now your task is to find out whether Bob can reach to the next level or not.

Input Format:

First line will contains B and N, separated by space, where B is the energy of Bob and N is the number of Zombie. Next line will contain N spaced integers each will represent the energy of zombie.

Line 1

B N, where B is the energy of Bob and N is the number of Zombie
Line 2

Zi, where Zi is a list containing energy of zombies separated by space

Constraints:

1<=N<=10^4
1<=B<=10^9
1<=Zi<=10^5

Note:
for this problem all the divisions are integer divisions.
Output Format:
Print "YES" or "NO" depending upon whether Bob can reach the next level or not.

Line 1         
For Valid Input,print

YES

Or
                                                     
NO

For Invalid Input,print

Invalid Input


Sample Input and Output

SNo.InputOutput
1           
35 3

5 9 6                 
YES                 
2
456 68

a
Invalid Input
3
4 4

1 3 2 4
NO


Solution : 


import java.util.Scanner;
public class ZombieWorld {
 
 public static void main(String[] args) {
  int B=0, N;    
  Scanner sc = new Scanner(System.in);
  try{ B = Integer.parseInt(sc.next().trim());
   N = Integer.parseInt(sc.next().trim());
   int a;
   for (int i = 0; i < N; ++i) {
    a = Integer.parseInt(sc.next().trim());
    B = B - ((a % 2) + (a / 2));
   }}
  catch(Exception e){
   System.out.println("Invalid Input");
   System.exit(0);
  }
  if(B>0)
  System.out.println("YES");
  else
  System.out.println("NO");
 }
}


CodeVita 2013 : Sequence (Longest Progressive Sequence)

Given a sequence, the objective is to find the longest progressive sequence arranged in ascending order. Detailed descriptions are as:

Problem
A sequence is said to be progressive if it doesn’t decrease at any point in time.
For example 1 1 2 2 is a progressive sequence but 1 2 1 is not a progressive sequence. Let S be the sequence and be represented by L spaced integers Ki, now your task is to find out the first longest progressive sequence present in the given sequence (S).

Input Format:

First line will contain T, the length of the sequence and next line will contain T spaced integers Ki (where i = 0,1, …,L).
Line 1 T,where T is the length of the sequence
Line 2 Ki,where Ki is integer in sequence separated by space

Constraints:

1<=T<=10^6(one million)
1<=Ki<=10^9(one billion)

Output Format:

Line 1 longest progressive sequence present in the given sequence

Sample Test Cases:


SNo.InputOutput
1                  
4                                    
1 1 2 1
1 1 2                                       
2
5
1 2 1 2 2
1 2 2


I have not followed coding standards while solving the problems.




/**
 *
 * @author VIK VIKASH VIKKU 
 * Business Logic class
 */
import java.util.ArrayList;
import java.util.Scanner;

public class LongestProgressiveSequence {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        ArrayList<Integer> ls = new ArrayList<Integer>();
        Integer[] temp = new Integer[0];
        for (int i = 0; i < t; i++) {
            int num = sc.nextInt();
            if (!(ls.isEmpty())) {
                if (num >=ls.get(ls.size()-1 )) {
                    
                    ls.add(num);
                } else {
                   
                    if(ls.size()>temp.length)
                    temp=ls.toArray(temp);
                    ls.clear();
                    ls.add(num);
                }
                
            } else {
                ls.add(num);
            }
        }
      
        if(ls.size()>temp.length)
        {
            temp=ls.toArray(temp);
        ls.clear();
        }
            for (int i = 0; i < temp.length; i++) {
            if(i<temp.length-1)
            System.out.print(temp[i]+" ");
            else
                System.out.println(temp[i]);

        }
        
    }
}



Review : CodeVita 2013

So now the contest is about to end. I think there is no problem in talking about round 1 of CodeVita 2013. The overall problems were good but there were several typing mistakes which caused a lot of confusion to participants. The test cases must be awesome. First two problems were easy and then started tougher problems. In the last two problem, it was difficult for me to manage memory as the problems were to read data from file and to reach out to solution. There were different sets of question depending upon the time of login but the difficulty level were almost same for each set as my friend told me. Sometimes my solution was uploaded but there was no submission detail for that. Yeah, I know there was a lot of traffic but each of the submitted solution should be judged.  I tried my best to reach out to solutions. The mystery will be clear after a while.   I will start posting my solutions soon. Stay tuned... :D


Median Maintenance

The problem statement is taken from Coursera programming assignment #6 .

Download the text file here.

The goal of this problem is to implement the "Median Maintenance" algorithm . The text file contains a list of the integers from 1 to 10000 in unsorted order; you should treat this as a stream of numbers, arriving one by one. Letting xi denote the ith number of the file, the kth median mk is defined as the median of the numbers x1,,xk. (So, if k is odd, then mk is ((k+1)/2)th smallest number among x1,,xk; if k is even, then mk is the (k/2)th smallest number among x1,,xk.)

In the box below you should type the sum of these 10000 medians, modulo 10000 (i.e., only the last 4 digits). That is, you should compute (m1+m2+m3++m10000)mod10000.

Algorithm ( naive ):
   
  1. sum=0, input a[n]
  2. for each input a[i]
    1. Sort a[0..i]
    2. sum+=a[i/2]
  3. print sum%10000
JAVA implementation : 

/**
 *
 * @author VIK VIKASH VIKKU
 */
import java.util.Arrays;
import java.util.Scanner;

public class MedianMaintenance {

    public static void main(String[] args) {
        int[] list = new int[10000];
        Scanner sc = new Scanner(System.in);
        long sum = 0;

        for (int i = 0; i < list.length; i++) {

            list[i] = sc.nextInt();
            Arrays.sort(list, 0, i+1);
            sum+=list[i/2];
        }
        System.out.println(sum%10000);

    }
}