TopCoder SRM 567 - Div I Lvl 1

The Square Root Dilemma
-----------------------------------
=> (A*B) is the a perfect square

For a given value of (A), we try to find all possible values of B which make A*B a perfect square.

A = OA * EA,  where EA is the perfect square factor of A and OA is the other factor

So, (A*B) is perfect square when B can be factored as OA*(a perfect square).


def srm567(a,b):
    ctr = 0
    for i in range(1,a+1):
        j = 2
        s = 1
        while (j*j)<= i:
            if i%(j*j) == 0:
                s = j*j
            j += 1

        r = i/s
        #print "i,s:",i,s
        y = 1
        while (y*y*r)<=b:
            ctr+= 1
            y += 1
    return ctr

TopCoder SRM 569 - Div I Lvl 1

We need to be able to find the Operation of each bit, i.e. whether it is OR, AND , XOR.

If you see the truth table for these operations:

A	B	OR	AND	XOR
0	0	0	0	0
0	1	1	0	1
1	0	1	0	1
1	1	1	1	0

You see that the first combination where both bits A/B are '0' all the results are zero, so this combination of bits doesn't help us identify the operation. => If we have bits 0,1,1 available to be inputted at a bit position we can identify the operation.

So, now the problem reduces to finding the no. of plates to be added so that there is a combination of 011 bits available at each position.


 def srm569(plates):
    more_plates_needed = 0
    M = len(plates[0])
    for i in range(0,M):
        bits_needed = ['0','1','1']
        for j in range(0,len(plates)):
            if plates[j][i] in bits_needed:
                bits_needed.remove(plates[j][i])
        more_plates_needed = max(more_plates_needed,len(bits_needed))
    return more_plates_needed


Examples:
=======

srm569(["01010101",
 "10101010"])
Out[34]: 1

srm569(["10010101011",
 "00010101001",
 "00100010111",
 "00101010101",
 "01010111101"])
Out[35]: 1

srm569(["1101001011010",
 "0010000010101",
 "1010101011110",
 "1101010100111",
 "1011111110111"])
Out[36]: 0

TopCoder SRM 571 - Div I Lvl 1

http://community.topcoder.com/stat?c=problem_statement&pm=12436&rd=15491
The following code prints the first 50 lexicographically sorted values of the records names:


class Test:
def __init__(self):
self.res = []
def f(self,n,x):
if x >n:
return
if len(self.res) < 50:
self.res.append(x)
#print x
else:
return

self.f(n,x*10)
rem = x%10
if rem != 9:
self.f(n,x+1)
def getRes(self,n,x):
self.f(n,x)
print self.res

Sample values printed from the program:
Test().getRes(1010,1)


1
10
100
1000
10000<
1001
10010<
1002
1003
:
1009
101
1010

TopCoder SRM 572 - Div I Lvl 1

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15492


def myfunc(s,k):
    res = 0
    incr = len(s)-k
    for i in range(0,incr):
        # find the first set of alphabets which don't match
        j = i
        t = {}
        ctr = 0
        #print "i:",str(i)
        while j<len(s):
            #print "j:",str(j)
            if s[j] in t:
                t[s[j]] += 1
            else:
                t[s[j]] = 1
            j += incr
            ctr += 1
        mx = max(t.values())
        res += ctr - mx
   
    return res

TopCoder SRM 573 - Div I Lvl 1

Div II Lvl 2 problem: easier version solution
http://community.topcoder.com/stat?c=problem_statement&pm=12471&rd=15493


def myfunc(s):
    our_strength = sum(s[0:3])- min(s[0:3])
    rst = s[3:]
    #print our_strength
    if len(rst) == 0:
        return 1
    # find the rank of our team, start with rank 1 and increment it as you find better ranks
    res = 1
    rst.sort()
    #print rst
    found = True
    while found == True:
        # get the max element
        max = rst[-1]
        rst.remove(max)
        # find the min element which is greater than our_rank
        found = False
        for i in rst:
            if i+max > our_strength:
                rst.remove(i)
                found = True
                res += 1
                break
    return res

http://apps.topcoder.com/wiki/display/tc/SRM+573

TopCoder SRM 575 - DIV 1 Level 1

http://community.topcoder.com/stat?c=problem_statement&pm=12496&rd=15495

The solution for the smaller problem:


def myfunc(n):
    f = [0] *(n+1)
    for i in range(2,n+1):
        for j in range(2,i):
            if(i%j==0 and f[i-j]==0):
                f[i] =1
    print [ (i,f[i]) for i in range(0,len(f))]

The solution for the bigger problem involves getting a pattern from the above solution.
http://apps.topcoder.com/wiki/display/tc/SRM+575

Generate the list of ugly numbers

http://www.geeksforgeeks.org/archives/753

Prime No., GCD, LCM calculations

// Calculate all primes upto N, set the boolean to true for all composites

  boolean isComposite[] = new boolean[N+1];
// calculate all primes upto N
for(int i=2;i*i<=N;i++){
if(!isComposite[i]){ // if prime
for(int j=i*i;j<=N;j+=i){
isComposite[j] = true;
}
}
}

// Calculate the GCD of 2 no.s using recursive euclidean algorithm

  private static long gcd(int a, int b) {
if(a<b){
// swap numbers
a = a^b;
b = b^a;
a = a^b;
}
if(b == 0)
return a;
return gcd(b,a%b);
}

private static long lcm(int a, int b) {
return a*b/gcd(a,b);
}

EQUATIONS

Solution:
1/x + 1/y = 1/N!
=> x = y*N!/(y-N!)

Say y = N!+Z,
=> x = (N!+Z)*N! / Z = N!^2 / Z + N!.
For 'x' to be integer, 'Z' can take values equal to the no. of divisors of N!^2.

No .of divisors is calculated in the following manner: http://technocratme.blogspot.in/2012/07/divisor-counting.html

import java.util.Scanner;

public class EQUATIONS {

public static int getPowerOfPrimeInNFact(int N,int prime){
int pow = N/prime;
int tmp = 0;
while(pow>0){
tmp +=pow;
pow = pow/prime;
}
return tmp;
}
public static void main(String args[]) throws Exception {
Scanner in = new Scanner((System.in));
//System.out.println(getPowerOfPrimeInNFact(18,3));
int N = in.nextInt();
boolean isComposite[] = new boolean[1000001];
int [] powPrimes = new int[1000001];
// calculate all primes in first 1 million
for(int i=2;i<=1000;i++){
if(!isComposite[i]){ // if prime
for(int j=i*i;j<=1000000;j+=i){
isComposite[j] = true;
}
}
}
long no_div = 1;
for(int i=2;i<=N;i++){
if(!isComposite[i]){ // if prime
//System.out.println(i);
// Find powers of all primes
powPrimes[i] = getPowerOfPrimeInNFact(N,i);
// find the continual mod of the tot. no. of divisors of N!*N!
no_div = ((2*powPrimes[i]+1)*no_div)%1000007;
}
}
System.out.println(no_div);
}
}

Longest palindrome

Write algo for longest palindrome?


http://www.careercup.com/question?id=12697674

Find the kth permutation of the string

Print the kth permutation of the given string.
e.g.
5th permutation of "abc" is "cab", because its comes on 5th position in the ordered list of its permutations as shown below:
abc
acb
bac
bca
cab
cba

My Code:

import java.util.Arrays;




public class Main {


    public static String getStr(StringBuffer perm, int k){ // perm is not the original string it has the non repeating string chars
        String r = "";
        //System.out.println(perm);
        
        if(k<1)
            return perm.toString();
        int n = 0, t= 1, ctr = 1, k_n = 0;;
        for(int i=1;;i++){
            t *= i;
            if(t>k){
                break;
            }
            ctr = i;
            n = t;
        }
        k_n = k/n;
        // take care of this n, i.e. reverse upto position i
        int pos = perm.length()-ctr;
        if(pos<0){
            //System.out.println("ERROR !!");
        }
        //mov e bfor b
        int e = pos-1+k_n;
        int b = pos-1;
        if(b<0){
            return getStr(perm, k-(n*k_n));
        }
        String tmp = perm.substring(0,b)+ perm.charAt(e) + perm.substring(b,e) ;
        if(e+1<perm.length()){
            tmp += perm.substring(e+1);
        }
        
        /*System.out.println(perm);
        System.out.println("\n ** nxt level ***\n");*/
        return getStr(new StringBuffer(tmp), k-(n*k_n));
        //return r;
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
      System.out.println(getStr(new StringBuffer("abcd"),5));
    }
}

Find the Longest common sub sequence between two strings in java

My code:

static void LCS(String x, String y){
               int m = x.length();
               int n = y.length();
               int len[][] = new int[m+1][n+1]; // by default init. to zeros
               int b[][] = new int[m+1][n+1]; // by default init. to zeros
               for(int i=0;i<=m;i++){
                       for(int j=0;j<=n;j++){
                               if(i==0 || j==0){
                                       len[i][j] = 0;
                               }
                               else{
                                       if(x.charAt(i-1)==y.charAt(j-1)){
                                               len[i][j] = len[i-1][j-1] + 1;
                                               b[i][j] = -2;
                                       }
                                       else{
                                               if(len[i][j-1]>len[i-1][j]){
                                                       len[i][j] = len[i][j-1];
                                                       b[i][j] = -3;
                                               }else{
                                                       len[i][j] = len[i-1][j];
                                                       b[i][j] = -1;
                                               }

                                       }
                               }
                       }
               }
               System.out.println("length of LCS " + len[m][n]);
               int i=m,j=n;
               String res= "";
               while(true){

                       if(b[i][j] == -1){
                               i--;
                       }
                       if(b[i][j] == -2){
                               res = x.charAt(i-1)+ res;
                               i--;j--;
                       }
                       if(b[i][j] == -3){
                               j--;
                       }
                       if(res.length()==len[m][n])
                               break;
               }
               System.out.println("LCS " + res);
       }

Permutations of a string in java

Print all permutations of a string in java:


public static void permutate(String o, String t,boolean used[]){
               if(t.length()==o.length()){
                       System.out.println(t);return;
               }
               boolean used2[] = new boolean[o.length()];
               for(int i=0;i<o.length();i++){
                       if(used[i])continue;
                       System.arraycopy(used, 0, used2, 0, o.length());
                       used2[i] = true;
                       permutate(o,t+o.charAt(i),used2);
               }
       }

An Arithmetic interview puzzle

Given a list of integer numbers, find a correct way of inserting arithmetic signs (operators) such that the result is a correct equation. Example: With the list of numbers [2,3,5,7,11] we can form the equations 2-3+5+7 = 11 or 2 = (3*5+7)/11 (and ten others!).

Any thoughts on how to solve this ?

Matrix rotate

GIven a 2D NxN matrix, visualize it as concentric circles. You have to find the rotated matrix where each element in the circle is rotated by 1 position layer by layer in an alternate clockwise and anticlockwise direction.

Sample Input:

4

2 3 4 5

1 6 7 8

4 2 1 9

5 3 2 4

Sample Output:

1 2 3 4 

4 7 1 5 

5 6 2 8 

3 2 4 9

My Code:

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


public class Solution {


public static void main(String[] args) {


int N =0;
int a[][],b[][];

BufferedReader br = 
         new BufferedReader(new InputStreamReader(System.in));
try {
String s = br.readLine();
N = Integer.parseInt(s);
a = new int[N][N];

for(int i=0;i<N;i++)
{
s = br.readLine();
String tmp[] =s.split(" ");
for(int j=0;j<N;j++){
a[i][j]= Integer.parseInt(tmp[j]);
//System.out.print(a[i][j]+" ");
}
//System.out.println();
}
int dist = 0;
int ii,jj;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
dist = Math.min(Math.min(i,N-1-i),Math.min(j,N-1-j));
ii=i;jj=j;
if(dist%2==0){ // do clockwise rotation
if(dist==i){// top row
jj = j-1;
ii = i;
if(jj<dist){
jj = j;
ii = i+1;
}
}
else if(dist==j){// left col
jj = j;
ii = i+1;
if((N-1-ii)<dist){
jj = j+1;
ii = i;
}
}
else if(dist==(N-1-i)){// bottom row
jj = j+1;
ii = i;
if((N-1-jj)<dist){
jj = j;
ii = i-1;
}
}
else if(dist==(N-1-j)){// right col
jj = j;
ii = i-1;
if(ii<dist){
jj = j-1;
ii = i;
}
}
}
else{ // anti clockwise
if(dist==i){// top row
jj = j+1;
ii = i;
if((N-1-jj)<dist){
jj = j;
ii = i+1;
}
}
else if(dist==j){// left col
jj = j;
ii = i-1;
if(ii<dist){
jj = j+1;
ii = i;
}
}
else if(dist==(N-1-i)){// bottom row
jj = j-1;
ii = i;
if(jj<dist){
jj = j;
ii = i-1;
}
}
else if(dist==(N-1-j)){// right col
jj = j;
ii = i+1;
if((N-1-ii)<dist){
jj = j-1;
ii = i;
}
}
}
if(Math.min(ii,N-1-ii)<dist){
ii=i;
}
else if(Math.min(jj,N-1-jj)<dist){
jj=j;
}
System.out.print(a[ii][jj]+" ");
}
System.out.println();
}

} catch (IOException e) {
e.printStackTrace();
}


}


}