Rasta and Kheshtak

Rasta is a big fan of Kheshtaks. A Kheshtak is a rectangle that in each of it cells there is an integer.
Today rasta came up with an interesting problem, Biggest Common Subsquare (BCS). A Kheshtak is called a Square if the number of its columns is equal to the number of its rows. A Square S is called a subsqaue of a Kheshtak A if and only if we can turn A to S by deleting some of its rows and some of its columns (maybe none).
He gives you two Kheshtaks, A and B (A one is n × m and B is x × y).

Input format

The first line of input contains n and m.
Then you are given A (n lines, in each line there are m space separated integers).
After that you are given x and y.
Then you are given B (x lines, in each line there are y space separated integers).
1 ≤ n, m, x, y ≤ 700 and all numbers in A and B are integers in the interval [1, 1000].

Output format

Print the size of BCS of A and B in a single line (size of a Square is number of its rows).

---

Sample Input

3 3
1 2 0
1 2 1
1 2 3
3 3
0 1 2
1 1 2
3 1 2

Sample Output

2

---

Time Limit: 2 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

 

First observation we should make to be able to solve this problem: if two matrices have common subsquare of size X, they also have common subsquares of sizes X-1, X-2, X-3,... ,1 (you may simply take part of large subsquare).
This observation should make idea of using binary search here quite obvious. Now we need to learn how to check that given matrices have common subsquare of size X.
Quite a few of tests are small&random enough to give you points even for some naive checking - running over all squares in first matrix, comparing them with all squares in second matrix (you may add some smart breaks here etc.). However, this isn't supposed to give you a full score.
First improvement is to learn how to compare two squares faster than with naive checking. Here hashing can help us.

Hashing will allow us to represent whole square as a single number, and compare two squares by comparing corresponding numbers.
Type "Rabin-Karp 2d" in Google and at the first page you'll have several different guides/implementations for 2d version of Rabin-Karp algorithm. If you are completely new to all these things - start with 1d version of algorithm (where we are comparing substrings instead of subsquares). After understanding 1d version - 2d version should be also pretty clear, because it is a simple generalization of 1d.

Now we have O(N^4) checker for particular value of X, which is still too slow (but much better than before). How to improve it even more? Instead of comparing our subsquare with every single subsquare from other matrix, we may compare it with all subsquares from that matrix at the same time. We are interested to know if there is a pair of equal subsquares; let's put all subsquares of first matrix in a set. Now for every subsquare from second matrix we can check if it has a pair in first matrix, by simply looking at our set. It gives us logN instead of N^2 here.
Now we have some sort of proper solution. Time limit isn't very strict; however, if you are actually going to use sets, it may be too slow. Instead you may store all values in sorted vector and use std::lower_bound() to check that some value is presented there. Also you may get rid of any % operations by doing all calculations modulo 2^64 (yes, there were no anti-hash tests in data set :) ) Such solution should get full score without any problems.
 

 

 Code : 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class problem3 {

    /**
     * @param args
     */
    static int[][] matrix1;
    static int[][] matrix2;
    static int comparison = 0;

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        String[] parts = input.split(" ");
        int n = Integer.parseInt(parts[0]);
        int m = Integer.parseInt(parts[1]);
        matrix1 = new int[n][m];
        for (int i = 0; i < n; i++) {
            input = br.readLine();
            parts = input.split(" ");
            for (int j = 0; j < m; j++) {
                matrix1[i][j] = Integer.parseInt(parts[j]);
            }
        }
        input = br.readLine();
        parts = input.split(" ");
        int x = Integer.parseInt(parts[0]);
        int y = Integer.parseInt(parts[1]);
        matrix2 = new int[x][y];
        for (int i = 0; i < x; i++) {
            input = br.readLine();
            parts = input.split(" ");
            for (int j = 0; j < y; j++) {
                matrix2[i][j] = Integer.parseInt(parts[j]);
            }
        }
        int min = m;
        if (n < m) {
            min = n;
        }
        if (x < min) {
            min = x;
        }
        if (y < min) {
            min = y;
        }
//        boolean ansSet = false;
//        for (int i = min; i > 0; i--) {
//            if (CompareAllSquaresOfGivenSize(i, n, m, x, y)) {
//                System.out.println(i);
//                ansSet = true;
//                break;
//            }
//        }
//        if (!ansSet)
//            System.out.println(0);
       
        System.out.println(Calc(0,min,n,m,x,y,min));
    }

    public static int Calc(int start,int end,int n,int m, int x, int y,int maxSquareSide)
    {
        if(start==0 && end==0)
        {
            return 0;
        }
            int mid=(start+end)/2;
            if(CompareAllSquaresOfGivenSize(mid, n,m,x,y))
            {
                if(!CompareAllSquaresOfGivenSize(mid+1, n,m,x,y))
                {
                    return mid;
                }
                if(mid+1<=maxSquareSide)
                    return Calc(mid+1,end,n,m,x,y,maxSquareSide);
                else
                    return mid;
            }
            else
            {
                return Calc(start,mid-1,n,m,x,y,maxSquareSide);
            }
   
    }

    public static boolean CompareAllSquaresOfGivenSize(int size, int n, int m,
            int x, int y) {
        for (int startingPointRow1 = 0; startingPointRow1 + size - 1 < n; startingPointRow1++) {
            for (int startingPointColum1 = 0; startingPointColum1 + size - 1 < m; startingPointColum1++) {
                for (int startingPointRow2 = 0; startingPointRow2 + size - 1 < x; startingPointRow2++) {
                    for (int startingPointColum2 = 0; startingPointColum2
                            + size - 1 < y; startingPointColum2++) {
                        // System.out.println("matrix1row: "+startingPointRow1 +
                        // " matrix1Col: " + startingPointColum1 +
                        // " matrix2row: "+startingPointRow2 +
                        // " matrix2Col: " + startingPointColum2
                        // + " size: "+size);
                        if (compareSquares(startingPointRow1,
                                startingPointColum1, startingPointRow2,
                                startingPointColum2, size))
                            return true;
                    }
                }
            }
        }
        return false;
    }

    public static boolean compareSquares(int square1Row, int square1Column,
            int square2Row, int square2Column, int SquareLength) {
        comparison++;
        for (int i = 0; i < SquareLength; i++) {
            for (int j = 0; j < SquareLength; j++) {
                if (matrix1[square1Row + i][square1Column + j] != matrix2[square2Row
                        + i][square2Column + j]) {
                    return false;
                }
            }
        }
        return true;
    }

}
 

Read More

Rasta and Darie

A Darie is a special circle. Numbers 1, 2, ..., n are written clockwise around this circle in order. You can stand on a number! Initially Rasta is on number 1. In each step, he jumps exactly p numbers clockwise. For example if n = 3 and he is standing on number 1:
If p = 1 then he jumps to number 2.
Or if p = 2 he jumps to number 3.
He does this until he reaches a number he's been on before (for example, if n = 3, p = 1 he stops after three jumps).
Then he writes down the numbers he had been on, as a sequence s in increasing order.
He's not a Mr.Memmory, so he can't remember this sequence. He asks you to help him by telling him the k-th number in this sequence (or -1 if size of s is less than k).

Input format

The first line of input contains an integer t, the number of testcases (1 ≤ t ≤ 10⁵).
Each testcase is given in one line, which contains three integers n, p, k (2 ≤ n ≤ 10⁶, 1 ≤ p ≤ n - 1, 1 ≤ k ≤ 10⁶).

Output format

Print the answer of each testcase in one line.

---

Sample Input

3
12 5 3
12 3 2
3 2 2

Sample Output

3
4
2

---

Time Limit: 2 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

 

For this problem you need a bit of math knowledge, after that it becomes really simple.
First let's move to 0-indexed numbering. It will make things looking simpler. Instead of 1, p+1, 2p+1,... now we have 0, p, 2p,... Let's notice that position after X moves is pX%n.
The key fact required to solve this one is that if p and n are coprime, then Darie will cover all possible values (he will make it with first n moves: pn, 2p%n, 3p%n, ... , np%n will give you a permutation of numbers 0, ..., n-1).

Let's make them coprime :) Assume we have gcd(n,p)=q. Lets denote N=n/q, P=p/q. Now we know that P and N are coprime (otherwise we can multiply q by their common divisor). Also we know that P%N, 2P%N, ... , NP%N covers all values in range 0, ..., N-1. Now move back to original values. After multiplying by q we have values 0, q, 2q, ..., (N-1)q covered. These N values are all positions which can be reached by Darie. If you are asked about position which has index higher than size of this list - answer is -1; otherwise you may find answer as (k-1)q. Don't forget to output it as (k-1)q+1, because we have 1-based numbering in original problem.
 

 

 

Code : 

 

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;

public class Test{
    static int temp;

    public static void main(String[] args) throws IOException {
        Reader reader = new Reader();
        PrintWriter out = new PrintWriter(System.out, false);
        int T = reader.nextInt();
        while (T-- > 0) {
            int n = reader.nextInt();
            int p = reader.nextInt();
            int k = reader.nextInt();
            --k;
            int q = gcd(n, p);
            if ((1L * k * q) >= n)
                out.println("-1");
            else
                out.println((1L * k * q) + 1);
        }
        out.close();
    }

    static int gcd(int c, int d) {
        int temp;
        while (d != 0) {
            temp = c % d;
            c = d;
            d = temp;
        }
        return c;
    }

    @SuppressWarnings("unused")
    private static int findGCD(int number1, int number2) {
        if (number2 == 0) {
            return number1;
        }
        return findGCD(number2, number1 % number2);
    }

    static int partition(int arr[], int l, int r) {
        int x = arr[r], i = l;
        for (int j = l; j <= r - 1; j++) {
            if (arr[j] <= x) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }
        temp = arr[i];
        arr[i] = arr[r];
        arr[r] = temp;
        return i;
    }

    static int test(int arr[], int l, int r, int k) {
        int pos = 0;
        if (k > 0 && k <= r - l + 1) {
            pos = partition(arr, l, r);
            if (pos - l == k - 1)
                return arr[pos];
            if (pos - l > k - 1)
                return test(arr, l, pos - 1, k);
            return test(arr, pos + 1, r, k - pos + l - 1);
        }
        return k;
    }

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public final String readString() throws IOException {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (c == '.')
                while ((c = read()) >= '0' && c <= '9')
                    ret += (c - '0') / (div *= 10);
            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }
}
 

Read More

Rasta and Tavas

Rasta calls a number like a Tavas if and only if 1 ≤ a ≤ n and the sum of all primes (like p) that p | a is exactly equal to k.
He asks you to find the number of Tavases.

Input format

The first and only line of input contains two integers, n and k (1 ≤ n, k ≤ 10⁶).

Output format

Print a single integer, the number of Tavases.

---

Sample Input

20 7

Sample Output

3

Explanation

The only Tavases are 7, 10 and 20.

---

Time Limit: 2 sec(s) for each input file.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

Code:  

 

/* IMPORTANT: class must not be public. */

/*
 * uncomment this if you want to read input.*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.BitSet;
import java.util.HashMap;
import java.util.Map.Entry;


class TestClass {
    public static void main(String args[] ) throws Exception {
        /*
         * Read input from stdin and provide input before running
*/
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String input[]= new String[2];
        input = line.split(" ");
        printTavas(Integer.valueOf(input[0]),Integer.valueOf(input[1]));

       
    }
   
   
   public static void printTavas(int n, int k){
    int pr[]=new int[n+2];
    for(int i=2;i<=n;i++){
        if(pr[i]==0){
            for(int j=i;j<=n;j+=i){
                pr[j]+=i;
            }
        }
    }
    int count=0;
    for(int i=0;i<=n;i++){
        if(pr[i]==k)
            count++;
    }
    System.out.println(count);
}
}
 

Read More

Magnificent Fountains

I and my flatmate ,Sayan, went to see the magnificient fountains in the Jubilee park on 3rd March.It was the eve of the 184rd Bithday of the late Mr. J.N.Tata and the fountains were set to blow at regular intervals. I sat down praising the scenic beauty of the fountains.But Sayan, who is a bit wierd, came up with a challenge.
He asked me, "Given that all fountains start off at the same time ,can you tell me when will all the fountains fire simultaneously again". Now, I being a bit dumbo, am asking for your help.You will be given the intervals at which each of the fountain fires.And all you need to do is tell me precisely at what time the fountains will fire simultaneously again.
For example, say there are 4 fountains with firing intervals of 2, 3, 1, and 1 respectively, then if they fire all together at t=0, they will fire together again at t=6.
INPUT
First line contains the T , the number of test cases. T test cases follow. Each of the test case contains 2 lines of input. The first line contains a single number n , denoting the number of fountains. The next line contains n space separated numbers denoting the interval time of the n fountains.
OUTPUT
Output T lines each containing only one number - the answer to the question (modulo 1000000007).
CONSTRAINTS
1<=T<=10
1<=n<=1000
1<=Time intervals<=10000

---

Sample Input

1
4
2 4 6 8

Sample Output

24

---

Time Limit: 3 sec(s) for all input files combined.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

Code: 

 

/* IMPORTANT: class must not be public. */

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class TestClass {
    public static void main(String args[] ) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int numOfTests = Integer.parseInt(br.readLine());
        String[] strArr;
        long lcm;
        long divisor = 1000000007;
        List<Integer> primeList = new ArrayList<Integer>();
        Set<Integer> inputSet = new HashSet<Integer>();
        List<Integer> inputList = new ArrayList<Integer>();
        List<Integer> inputList2 = new ArrayList<Integer>();
        List<Integer> indicesList = new ArrayList<Integer>();
        boolean isDivisible = false;
        int inputNum, primeNum2, num;

        primeList.add(2);
        for(int i=3; i<10000; i+=2){
            for(int primeNum : primeList){
                if(i%primeNum == 0){
                    break;
                }else if(primeNum*primeNum > i){
                    primeList.add(i);
                    break;
                }
            }
        }
       
        for(int i=0; i<numOfTests; i++){
            br.readLine();
            strArr = br.readLine().split(" ");
           
            for(int j=0; j<strArr.length; j++){
                inputNum = Integer.parseInt(strArr[j]);
                if(inputNum != 1)
                    inputSet.add(inputNum);
            }
           
            inputList.addAll(inputSet);
            lcm = 1;
           
            for(int k=0; k<primeList.size(); k++){
                primeNum2 = primeList.get(k);
                isDivisible = false;
                for(int l=0; l<inputList.size(); l++){
                    num = inputList.get(l);
                    if(num % primeNum2 == 0){
                        isDivisible = true;
                        indicesList.add(l);
                        if(num/primeNum2 != 1)
                            inputList2.add(num/primeNum2);
                    }
                }
                if(isDivisible){
                    lcm = (lcm*primeNum2)%divisor;
                   
                    if(inputList.size()-indicesList.size() == 0 && inputList2.size() == 0){
                        break;
                    }else{
                        for(int l=indicesList.size()-1; l>=0; l--){
                            inputList.remove((int)indicesList.get(l));
                        }
                        inputList.addAll(inputList2);
                        inputList2.clear();
                        indicesList.clear();
                        k--;
                    }
                }
                if(inputList.size() == 1){
                    lcm = (lcm*inputList.get(0))%divisor;
                    break;
                }
            }
            System.out.println(lcm);
        }
    }
}
 

Read More

Birthday Party

My flatmate, Sayan, once invited all his relatives and friends from all over the city to join him on his birthday party. He is also famous for boasting that all his friends and relatives belong to "proper" families. Now, he appointed a gaurd to allow only his relatives and friends into the party. It is gauranteed that all the relatives and friends come with their families all at once ,i.e, all members belonging to the same family reach all at once. Now gaurd's task is to count the number of "proper" families who came in the party. All families have a unique "special number" assigned to them ,i.e., all members of the same family share the same "special number". A family is said to be proper only if the number of members in the familiy is a number which can be made by adding numbers from a given set of "valid" numbers N. Further constraint is that each valid number can be used only once.
Take an example:-
if N={1,2,8} then all the families with 1,2,3,8,9,10 , or 11 members are allowed in the party , where as families with 4,5,6,7, etc members are not allowed.
The gaurd being a lazy fellow came to you for help.You need to write a program that computes the number of "proper families" in who turned up.
INPUT.
First line of input contains a number T denoting the number of test cases.T test cases follow. In each test case, the first line contains the number(P) of total number of people coming for the party and the number (M) denoting the number of "valid" numbers. The 2nd line contains M numbers, the set N ,containing all distinct "valid" numbers separated with spaces. The 3rd line contains P numbers, the "special" number of the members separated with spaces.
OUTPUT.
Output a single line for each of the test cases that denotes the number of "proper families" who turned up for the party.
CONSTRAINTS:
1<=T<=5
1<=P,N,M<=1000

---

Sample Input

2
8 3
1 2 8
2 2 2 3 4 4 4 4
10 3
2 4 6
2 9 9 9 19 19 19 19 19 20

Sample Output

2
0

Explanation

In the first case: Clearly, The families with 1,2,3,8,9,10 and 11 members are allowed in the party. The family with "Special" number 2 has 3 members in it which is allowed.Same for the family with "special" number 3. But for the family with "special" number 4 has 4 members, which is not allowed. So the total number of "proper" families = 2.

---

Time Limit: 3 sec(s) for all input files combined.

Memory Limit: 256 MB

Source Limit: 1024 KB 

Code: 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.StringTokenizer;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
class BirthdayParty {

    static PrintWriter out = new PrintWriter(System.out);
    static InputReader Reader = new InputReader(System.in);

    public static void main(String[] args) {
        int numTests = Reader.nextInt();
        Map<Integer, Integer> familyMemCount = new HashMap<Integer, Integer>();

        for (int index = 0; index < numTests; index++) {
            familyMemCount.clear();
            int NumPeople = Reader.nextInt();
            int NumSpecialNumbers = Reader.nextInt();

            int[] splNumbers = new int[NumSpecialNumbers];
            for (int i = 0; i < splNumbers.length; i++) {
                splNumbers[i] = Reader.nextInt();
            }

            for (int i = 0; i < NumPeople; i++) {
                int spl = Reader.nextInt();

                if (familyMemCount.containsKey(spl)) {
                    int val = familyMemCount.get(spl);
                    familyMemCount.put(spl, ++val);
                } else {
                    familyMemCount.put(spl, 1);
                }
            }

            int properFamily = 0;
            for (Iterator<Map.Entry<Integer, Integer>> it = familyMemCount.entrySet().iterator(); it.hasNext();) {
                Map.Entry<Integer, Integer> entry = it.next();

                if (isSubSetSum(splNumbers, NumSpecialNumbers - 1, entry.getValue())) {
                    properFamily++;
                }

            }

            out.println(properFamily);
            out.flush();
        }

        out.close();
    }

    /**
     *
     * @param i
     * @param i0
     * @param value
     * @return
     */
    private static boolean isSubSetSum(int[] array, int index, Integer sum) {
        // Base Cases
        if (sum == 0) {
            return true;
        }

        if(sum < 0) {
            return false;
        }

        if (index < 0 && sum != 0) {
            return false;
        }

        return isSubSetSum(array, index - 1, sum) || isSubSetSum(array, index - 1, sum - array[index]);
    }

    /** Class for buffered reading int and double values */
    static class InputReader {

        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}
 

Read More

Minimal Combinatorial

Given two integers - n and r, your task is to calculate the combinatorial nCr.
nCr = n! / r! (n-r)!
The caveat is that you have to write code to do this calculation in minimum number of characters.

UPDATE: The testcases for this problem have been fixed. Please try submitting your solution again.

Input
The first line will be number of testcases T. Then T lines follow, each containing two positive integers - n and r.

output
Print T lines, each line containing the value of nCr.

Constraints
1 <= T <= 100
1 <= r <= n <= 1000

You can assume that the value nCr will fit into a signed 64 bit integer.

Scoring
If your program passes all the testcases, the score will be assigned according to the following formula:
num_chars = length of source code
Score = (1000 - num_chars) / 10

You can understand that you have to reach as close to 100 as possible. Have fun :)

---

Sample Input

1
100 10

Sample Output

17310309456440

---

Time Limit: 2 sec(s) for all input files combined.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

Code: 

 

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.math.BigInteger;
class TestClass{

 

public static BigInteger fact(int n){

if(n==1) return BigInteger.valueOf(n);

 

 else return BigInteger.valueOf(n).multiply(fact(n-1));

}
public static void main(String args[]) throws Exception{

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

int c=Integer.parseInt(br.readLine());

for(int i=0;i<c;i++){

String[] p=br.readLine().split(" ");

int n=Integer.parseInt(p[0]),

r=Integer.parseInt(p[1]);

System.out.println(fact(n).divide(fact(r).multiply(fact(n-r))));

}

}

} 

Read More

Lunch Boxes

Masao and Naini, both Shinchan friends, are playing "home-home". But wait, they both forgot to bring any lunch box. Being a good partner Naini cannot allow Masao to go office without luch box. So she asked Masao to buy some.

Naini has N food items to be packed in the lunch box and maximum weight each lunch box can hold is W units. Let the weight of N items be w_0, w_1, ..., w_(N-1) units and each item's weight lies between 1 and W (inclusive). Find the arrangement so that the number of lunch box required to pack all food items is minimised.

Let's say Masao bought K lunch box (b_0, b_1,..., b_(K-1)) for packing N items. For each i'th box in [0, K-1], print the indices of food items, j in [0, N-1], which is placed in it. Each food item must be placed in only one box.

Help Masao in finding K and respective placement of food items in these boxes.

Constraints
1 <= N <= 10^5 1 <= W <= 10^5 1 <= w_i <= W

Input
First line of input contains two space separated integers, N W, numbers of food items to be packed and maximum weight each lunch box can hold.
Next line contains N space separated integers, w_0, w_1...w_(N-1), weights of 0'th item, 1'st item, ..., (N-1)'th item.

Output
In first line print an integer, K, numbers of lunch box required for packing all the food items. Then print K lines. Each of these line represents the content of a box. Each of these lines contains a number M (1 <= M), number of food items to be placed in current box followed by M space separated indexes of food items.

Scoring
Maximum number of lunch box required is N. The score will be equal to (N - K) / N * [Score of problem]

---

Sample Input

6 6
1 2 4 3 5 3

Sample Output

4
3 0 1 5
1 3
1 2
1 4

Explanation

In the give sample input/output, Naini used 4 boxes. 1st box contains 3 items, w_0 = 1, w_1 = 2, w_5 = 3. 2nd box contains 1 item, w_3 = 3. Similarly 3rd and 4th box contains 1 item each, w_2 = 4 and w_4 = 5, respectively.
Score for Input #1: 66.67.
Similarly, consider the following example.
Sample Input #2: 6 6 1 2 4 3 5 3
Sample Output #2: 3 2 0 4 2 1 2 2 5 3
Score for Input #2: 100.00
Naini used 3 boxes. 1st box contains 2 items, w_0 = 1, w_4 = 5. 2nd box contains 2 items, w_1 = 2, w_2 = 4. 3rd box also contains 2 items, w_5 = 3, w_3 = 3.

---

Time Limit: 6 sec(s) for all input files combined.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

Code: 

 

/*
 * uncomment this if you want to read input.*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;


class TestClass {
    static int[] w;
    public static void main(String args[] ) throws Exception {
       
        BufferedReader br =
            new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        String[] nums = line.split(" +");
        int N = Integer.parseInt(nums[0]);
        int W = Integer.parseInt(nums[1]);
        w = new int[N];
        String line2 = br.readLine();
        String[] wis = line2.split(" +");


        for (int i = 0; i < N; i++) {
            w[i] = Integer.parseInt(wis[i]);

        }

        Integer[] index = new Integer[N];
        for (int t = 0; t < N; t++) {
            index[t] = t;
        }
        Comparator<Integer> com = new Comparator<Integer>() {

            public int compare(Integer o1, Integer o2) {
                return w[o1] - w[o2];
            }
        };
        Arrays.sort(index, com);

        ArrayList<ArrayList<Integer>> lists =
            new ArrayList<ArrayList<Integer>>();

        int start = 0;
        int end = N - 1;
        while (start <= end) {
            ArrayList<Integer> list = new ArrayList<Integer>();

            int cap = W;
            while (end >= 0 && w[index[end]] <= cap) {
                list.add(index[end]);
                cap -= w[index[end]];
                end--;
            }
            while (start <= end && start <= N - 1 && w[index[start]] <= cap) {
                list.add(index[start]);
                cap -= w[index[start]];
                start++;
            }
            lists.add(list);
            if(start==end){
                list = new ArrayList<Integer>();
                list.add(index[start]);
                lists.add(list);
                break;
            }
           
           
        }
        System.out.println(lists.size());
        int lsize = lists.size();
        for (int i = 0; i < lsize; i++) {
            int asize = lists.get(i).size();
            System.out.print(asize + " ");
            for (int j = 0; j < asize; j++) {
                System.out.print(lists.get(i).get(j) + " ");
            }
            System.out.println();
        }
     
    }
} 

Read More

Modify Sequence

Suppose we have a sequence of non-negative integers, Namely a_1, a_2, ... ,a_n. At each time we can choose one term a_i with 0 < i < n and we subtract 1 from both a_i and a_i+1. We wonder whether we can get a sequence of all zeros after several operations.
Input
The first line of test case is a number N. (0 < N <= 10000) The next line is N non-negative integers, 0 <= a_i <= 109
Output
If it can be modified into all zeros with several operations output “YES” in a single line, otherwise output “NO” instead.

---

Sample Input

2
1 2

Sample Output

NO

Explanation

It is clear that [1 2] can be reduced to [0 1] but no further to convert all integers to 0. Hence, the output is NO.
Consider another input for more clarification:
2 2 2
Output is YES as [2 2] can be reduced to [1 1] and then to [0 0] in just two steps.

---

Time Limit: 3 sec(s) for all input files combined.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

Code: 

 

import java.io.*;
public class ModifySequence {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n,i,a[];
        long odd=0,even=0;
        n = Integer.parseInt(br.readLine());
        String s[] = br.readLine().split(" ");
        a = new int[n];
        for(i=0;i<n;i++)
        {
            a[i] = Integer.parseInt(s[i]);
            if(i%2 == 0)
            even = even + a[i];
            else
            odd = odd + a[i];
        }
        if(even == odd)
        System.out.println("YES");
        else
        System.out.println("NO");
    }
} 

Read More

Crazy Matrix

Praveen went crazy yesterday and created an arbitrary matrix consisting of 0, 1 or 2. There was no rule observed in forming this matrix. But then he made up some rules himself.
If there are adjacent 1's, they are said to be connected. Similarly, if there are adjacent 2's, they are said to be connected. Here adjacent means all the surrounding positions along with the diagonal positions.
Now given a matrix of 0, 1 or 2, do your computation according to the following rules:

1. If there is a path from any position in top row to any position in bottom row consisting only of 1, then print 1.
2. If there is a path from any position in first column to any position in last column consisting only of 2, then print 2.
3. If both Rule 1 & Rule 2 are true, print AMBIGUOUS.
4. If none of Rule 1, Rule 2 or Rule 3 satisfies, print 0.

Input format
First line of input contains a positive integer N, the size of matrix. Then N line follows, each containing N integers which are either 0, 1 or 2.
Output format
Print a single line containing the output according to the rule mentioned. Clearly, the output can only be 0, 1, 2 or AMBIGUOUS.
Input constraint
1 <= N <= 100
Example
4
0 0 0 0
2 0 1 0
0 2 1 2
0 1 2 0
Here the output is 2, as there is a connected path of 2 from first column to last column.

---

Sample Input

3
0 0 1
0 1 2
2 2 1

Sample Output

AMBIGUOUS

Explanation

In the sample input, there is a connected path of 1 from first row to last row, and there is a connected path of 2 from first column to last column as well. So, the result is 'AMBIGUOUS'.

---

Time Limit: 2 sec(s) for all input files combined.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

Code : 

 

/* IMPORTANT: class must not be public. */


import java.util.Scanner;



class TestClass {
    static int visited[][];
    static int N;
    static int[][] matrix;
    public static void main(String args[] ) throws Exception {
       
         Scanner sc = new Scanner(System.in);
         N = sc.nextInt();
         matrix = new int[N][N];
         visited = new int[N][N];
        
         for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        
      
       boolean one = false;
       boolean two = false;
       
        //Reset the visted matrix
        for(int i = 0; i < N; i++) {
            for (int j = 0 ; j < N ; j++) {               
                visited[i][j] = 0;
            }
        }
        for (int i = 0; i < N; i++) {
            if(matrix[0][i] == 1) {
                one = connectedOne(matrix, 0, i);
                if(one) {
                    //System.out.println("Two chain found");
                    break;
                }
            }
        }
       
        // Reset the visited matrix
        for(int i = 0; i < N; i++) {
            for (int j = 0 ; j < N ; j++) {               
                visited[i][j] = 0;
            }
        }
       
        for (int i = 0; i < N; i++) {
            if(matrix[i][0] == 2) {
                two = connectedTwo(matrix, i, 0);
                if(two) {
                    //System.out.println("Two chain found");       
                    break;
                }
            }
        }
       
        if(one && two) {
            System.out.println("AMBIGUOUS");
        } else if(one) {
            System.out.println("1");
        } else if(two) {
            System.out.println("2");
        } else {
            System.out.println("0");
        }
    }
   
    static boolean connectedOne(int[][] matrix, int x, int y) {
        if(isSafe(matrix, x, y) && x == (N - 1)) {
            if(matrix[x][y] == 1) {
                return true;
            } else {
                return false;
            }
               
        }   
       
        if(isSafe(matrix, x, y) == true && matrix[x][y] == 1) {   
           
            visited[x][y] = 1;
            if(connectedOne(matrix , x, y+1) == true) {
                return true;
            }
            if(connectedOne(matrix , x+1, y) == true) {
                return true;
            }
           
            if(connectedOne(matrix , x+1, y+1) == true) {
                return true;
            }
           
            if(connectedOne(matrix , x-1, y) == true) {
                return true;
            }
           
            if(connectedOne(matrix , x-1, y+1) == true) {
                return true;
            }
           
            if(connectedOne(matrix , x-1, y-1) == true) {
                return true;
            }
           
            if(connectedOne(matrix , x, y-1) == true) {
                return true;
            }
           
            if(connectedOne(matrix , x+1, y-1) == true) {
                return true;
            }
           
            return false;
           
        }
       
        return false;
       
    }
   
    static boolean connectedTwo(int[][] matrix, int x, int y) {
       
        if(isSafe(matrix, x, y) && y == (N - 1) ) {
            if(matrix[x][y] == 2) {
                return true;
            } else {
                return false;
            }
        }
       
       
       
        if(isSafe(matrix, x, y) == true && matrix[x][y] == 2) {
           
            visited[x][y] = 1;
           
            if(connectedTwo(matrix , x, y+1) == true) {
                return true;
            }
            if(connectedTwo(matrix , x+1, y) == true) {
                return true;
            }
           
            if(connectedTwo(matrix , x+1, y+1) == true) {
                return true;
            }
           
            if(connectedTwo(matrix , x-1, y) == true) {
                return true;
            }
           
            if(connectedTwo(matrix , x-1, y+1) == true) {
                return true;
            }
           
            if(connectedTwo(matrix , x-1, y-1) == true) {
                return true;
            }
           
            if(connectedTwo(matrix , x, y-1) == true) {
                return true;
            }
           
            if(connectedTwo(matrix , x+1, y-1) == true) {
                return true;
            }
           
            return false;
           
        }
       
        return false;       
    }
   
     private static boolean isSafe(int[][] matrix, int x, int y) {
           
            if(x < matrix[0].length && x >= 0 && y < matrix[0].length && y >= 0
                     && visited[x][y] == 0) {
                return true;
            }
            return false;       
        }
}
 

Read More

Radiator Springs

We all know the town Radiator Springs, connected to California by direct road (Route no. 66). After a commendable performance by Lighting McQueen at the Piston Cup, the town of Radiator Springs became famous. In order to improve the traffic capacity of the road, the town's judge and doctor, Doc Hudson ordered to place on traffic sign, thus limiting the maximum speed. The traffic sign in the town of Radiator Springs seems to be a bit odd. The reason being, they only limit the speed where the traffic signals are placed and just after passing the sign the cars are allowed to drive at any speed.
It is given that the cars of Radiator Springs has an average accerleration/deceleration of x km/h², and has a maximum speed of y km/h. The road has the length of L km, and the speed sign, limiting the speed to w km/h, is placed d km (1 <= d <= L) away from the Radiator Springs. You have to find the minimum time that an average Radiator Spring car will need to get from the California, if the car drives at the optimal speed.
Note : The car has a zero speed at the beginning of the journey.
Input format
The first line of the input file contains two integer numbers x and y (1 <= x, y <= 10000). The second line contains three integer numbers L, d and w (2 <= L <= 10000; 1 <= d < L; 1 <= w <= 10000).
Output format
Print the answer with nine digits after the decimal point.
Partial Scoring
This problem has 20 test input files,each of them having score of 5. It means even if 10 input are passed, you will get score as 50 and solution will be marked as accepted. But If the total time limit or memory limit exceeds, then the submission is marked unaccepted even if few testcases might have passed.

---

Sample Input

1 1
2 1 3

Sample Output

2.500000000

---

Time Limit: 3 sec(s) for all input files combined.

Memory Limit: 256 MB

Source Limit: 1024 KB 

 

Code: 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.DecimalFormat;


class TestClass {
public static void main(String[] args) {
        // TODO Auto-generated method stub
        double x=0,y=0,L=0,d=0,w=0,maxspeed=0,t=0,temp=0;
        String[] s;
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        DecimalFormat numberFormat = new DecimalFormat("#.000000000");
        try {
            s=in.readLine().split(" ");
            x=Double.parseDouble(s[0]);
            y=Double.parseDouble(s[1]);
            s=in.readLine().split(" ");
            L=Double.parseDouble(s[0]);
            d=Double.parseDouble(s[1]);
            w=Double.parseDouble(s[2]);
            if(y>w){
                //before d
                if((Math.pow(y,2)/2*x)+((Math.pow(y,2)-Math.pow(w,2))/2*x)<=d){
                    t=(y/x)+(d-((Math.pow(y,2)/2*x)+((Math.pow(y,2)-Math.pow(w,2))/2*x)))/y+((y-w)/x) ;
                }
                else{
                    temp = Math.sqrt((Math.pow(w,2)+(2*x*d))/2);
                    t= ((2*temp)-w)/x;
                }
                //after d
                if((Math.pow(y,2)-Math.pow(w,2))/(2*x)<=(L-d)){
                    t+=(y-w)/x+((L-d-((Math.pow(y,2)-Math.pow(w,2))/(2*x)))/y);
                }
                else{
                    t+=(Math.sqrt(Math.pow(w,2)+(2*x*(L-d)))-w)/x;
                }
                //System.out.println("hi!!!!!!");
            }
            else{
                maxspeed = y;
                if(Math.pow(maxspeed,2)/(2*x)<=L){
                   
                   
                    t=(maxspeed/x)+((L-(Math.pow(maxspeed,2)/(2*x)))/maxspeed);
                }
                else{
                    t=Math.sqrt((2*L)/x);
                    //System.out.println("hi!!!!!!");
                   
                }
            }
            System.out.println(numberFormat.format(t));
           
        } catch (NumberFormatException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }

    }
} 

Read More