Hackerrank Back2school 2014

almost-sorted.cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n;
	scanf("%d",&n);
	int d[100050]={0};
	for (int i = 0; i < n; i++)
		scanf("%d",&d[i]);
	if ( n == 2 ){
		if ( d[0] > d[1] ){
			printf("yes\n");
			printf("swap 1 2\n");
		}
		else{
			printf("yes\n");
		}
	}
	else{
		if ( n == 3 ){
			if ( (d[2] < d[0] && d[0] < d[1]) || (d[1] < d[2] && d[2] < d[0])){
				printf("no\n");
			}
			if (d[0] > d[1] && d[1] > d[2]){
				printf("yes\n");
				printf("reverse 1 3\n");
			}
			if (d[0] < d[1] && d[1] < d[2]){
				printf("yes\n");
			}
			if (d[0] < d[2] && d[2] < d[1]){
				printf("yes\n");
				printf("swap 2 3\n");
			}
			if (d[1] < d[0] && d[0] < d[2]){
				printf("yes\n");
				printf("swap 1 2\n");
			}
		}
		else{
			int s = 1 ,e = n - 2;
			int mode = 0;
			while ( d[s] > d[s-1] && s <= n - 1 ){
				if (d[s] > d[s-1] && d[s] > d[s+1])
					break;
				s++;
			}
			if ( s == n - 1){
				printf("yes\n");
			}
			else{
				while ( d[e-1] < d[e]){
					if ( d[e] < d[e+1] && d[e] < d[e-1] )
						break;
					e--;
				}
				if ( s + 1 == e){
					printf("yes\n");
					printf("swap %d %d\n", s, e );
				}
				else{
					int sub_s = s+1;
					int sub_e = e-1;
					int mode = 0; 
					bool flag = false;
					for(int i = sub_s; i <= sub_e - 1; i++){
						if(mode == 0){
							if ( d[i] < d[i+1] )
								mode = 1;
							if ( d[i] > d[i+1] )
								mode = -1;
						}
						else{
							if ( ( d[i] < d[i+1] && mode == 1 ) || ( d[i] > d[i+1] && mode == -1) ){
								continue;
							}
							else{
								flag = true;  /////not satisfied
								break;
							}
						}
					}
					if (flag == true){
						printf("no\n");
					}
					else{
						if ( mode == 1 ){
							if ( d[e] > d[s-1] && d[s+1] > d[e] && d[s] > d[e-1] && d[s] < d[e+1]){
								printf("yes\n");
								printf("swap %d %d\n", s+1,e+1);
							}
							else{
								printf("no\n");
							}
						}
						if ( mode == -1 ){
							if ( d[e] < d[e-1] && d[e] > d[s-1] && d[s+1] < d[s] && d[s] < d[e+1] ){
								printf("yes\n");
								printf("reverse %d %d\n", s+1,e+1);
							}
							else{
								printf("no\n");
							}
						}

					}
				}
			}	
		}
	}
}

covering-the-stains.py

import itertools

N,K = map(int, raw_input().split())
n = N
spots = []
maxX,minX,maxY,minY=[0,0,0,0]
while N:
	ip = map(int, raw_input().split())
	if n == N:
		maxX = ip[0]
		minX = ip[0]
		maxY = ip[1]
		minY = ip[1]
	else:
		if ip[0] > maxX:
			maxX = ip[0]
		if ip[0] < minX:
			minX = ip[0]
		if ip[1] > maxY:
			maxY = ip[1]
		if ip[1] < minY:
			minY = ip[1]
	spots.append(ip)
	N -= 1

X = (maxX-minX)*(maxY-minY)

cnt = 0
for x in itertools.combinations(spots,(n-K)):
	tmpx = [t[0] for t in x]
	tmpy = [t[1] for t in x]
	mix = min(tmpx)
	maxx=max(tmpx)
	miy = min(tmpy)
	may =max(tmpy)
	if (maxx-mix)*(may-miy) < X:
		cnt += 1

print cnt

fibonacci-modified.py

A,B,N = map(int,raw_input().split())

c = [A,B]
for i in range(3,N+1):
	c.append(c[-1]**2 + c[-2])

print c[-1]

Polar-Angles.py

import math
n = input()

def ang(x,y):
	if math.atan2(y,x) < 0:
		return (x,y,2.0*math.pi+math.atan2(y,x))
	else:
		return (x,y,math.atan2(y,x))

M = []
while n:
	n -= 1
	a,b = map(int,raw_input().split())
	M.append(ang(a,b))

for i in sorted(M,key = lambda x:(x[2],x[0]**2+x[1]**2)):
	print i[0],i[1]

The-Grid-Search.py

T = input()
while T:
	T -= 1
	G = []
	R,r = map(int,raw_input().split())
	G_sum = [[0]*(r+1)]
	for j in xrange(R):
		tmp = raw_input()
		g = []
		g_sum =[0]
		ben = 0
		for i in range(0,len(tmp)):
			num = ord(tmp[i])-ord('0')
			g.append(num)
			g_sum.append(ben+num+G_sum[-1][i+1])
			ben += g[-1]
		G_sum.append(g_sum)
		G.append(g)

	# print "G_sum"
	# for i in G_sum:
	# 	for j in i:
	# 		print j,
	# 	print ""
	# print "G"
	# for i in G:
	# 	for j in i:
	# 		print j,
	# 	print ""

	P = []
	P_sum = 0
	C,c = map(int,raw_input().split())
	for j in xrange(C):
		tmp = raw_input()
		p = []
		for i in tmp:
			num = ord(i)-ord('0')
			p.append(num)
			P_sum += num
		P.append(p)

	# print "P_sum"
	# print P_sum

	if C > R or c > r:
		print "NO"
	else:
		flag1 = False
		for i in range(0,R-C+1):
			for j in range(0, r-c+1):
				if P_sum == G_sum[i+C][j+c] - G_sum[i+C][j] - G_sum[i][j+c] + G_sum[i][j]:
					# print i,j
					flag2 = False
					# print i,j
					# print ''
					for x in range(0,C):
						for y in range(0,c):
							# print i+x,j+y
							if G[i+x][j+y] != P[x][y]:
								flag2 = True
								break
					if flag2 == False:
						flag1 = True
						break
				else:
					continue
		if flag1 == True:
			print "YES"
		else:
			print "NO"

the-lovers.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long lld;

lld Ext_gcd(lld a,lld b,lld &x,lld &y){
   if(b==0) { x=1, y=0; return a; }
   lld ret= Ext_gcd(b,a%b,y,x);
   y-= a/b*x;
   return ret;
}

lld Inv(lld a,int m){ 
   lld d,x,y,t= (lld)m;
   d= Ext_gcd(a,t,x,y);
   if(d==1) return (x%t+t)%t;
   return -1;
}

lld Cm(lld n, lld m, lld p)
{
    lld a=1, b=1;
    if(m>n) return 0;
    while(m)
    {
        a=(a*n)%p;
        b=(b*m)%p;
        m--;
        n--;
    }
    return (lld)a*Inv(b,p)%p;  
}

int Lucas(lld n, lld m, lld p)  
{
    if(m==0) return 1;
    return (lld)Cm(n%p,m%p,p)*(lld)Lucas(n/p,m/p,p)%p;
}

int main()
{
    int  T;
    scanf("%d",&T);
    while(T--)
    {
    	lld N,K,n,m;
        scanf("%lld%lld",&N,&K);
        if ((N-K) < (K-1)){
        	printf("0\n");
        }
        else{
       		n = N-K-(K-1);
			m = K+1;
		 	printf("%d\n",Lucas(n+m-1,m-1,100003L));
		}
    }
    return 0;
}

xor-subsequence.py

N = input()
A =[]
n = N
M = {}
res = []
Max = -1
while N:
    tmp = input()
    if tmp not in M:
    	M[tmp] = 1
    else:
    	M[tmp] += 1

    if M[tmp] > Max:
    	res = []
    	res.append(M[tmp])
    	# print res
    	Max = M[tmp]
    elif M[tmp] == Max:
    	res.append(M[tmp])
    	# print res

    if N == n:
        A.append(tmp)
    else:
        A.append(A[-1] ^ tmp)
    N -= 1



A = [0] + A
# print "A:"
# print A


for i in range(n,1,-1):
    for j in range(i-2,-1,-1):
        t = A[i] ^ A[j]
        # print j+1,i,t
        if t not in M:
            M[t] = 1
        else:
            M[t] += 1
        if M[t] > Max:
    		res = []
    		res.append(t)
    		Max = M[t]
    		# print t,res
    	elif M[t] == Max:
    		res.append(t)
    		# print t,res

# print "res"
# print res

# print M,Max

# print M
print sorted(res)[0],Max