Sum

problem statement is here

#include<stdio.h>

int main(){

long a,b,n,i,j,ar[1002],u,m;

scanf("%ld",&n);

for(i=0;i<n;i++){

scanf("%ld",&ar[i]);

}

for(i=1;i<n;i++){

for(j=0;j<n;j++){

scanf("%ld",&u);

if(i==1 && j==2){

m=u;

}

}

}

if(n==2){

printf("1 %ld\n",ar[1]-1);

}else{

a=(ar[1]+ar[2]-m)/2;

printf("%ld",a);

for(i=1;i<n;i++){

b=ar[i]-a;

printf(" %ld",b);

}

printf("\n");

}

return 0;

}

Interesting Numbers

problem statement is here

#include<stdio.h>
#include<algorithm>
#include<limits>
using namespace std;
int main(){
long long a=0,b,c,y,n,i,j,d,e,min;
scanf("%lld",&n);
long long ar[n+1];
for(i=0;i<n;i++){
scanf("%lld",&ar[i]);
}
sort(ar,ar+n);
a=ar[0];d=1;
for(i=1;i<n;i++){
if(ar[i]==a){
d++;
}else{
break;
}
}
a=ar[n-1];e=1;
for(i=n-2;i>=0;i--){
if(ar[i]==a){
e++;
}else{
break;
}
}
if(n==d){
b=(n*(n-1))/2;
}else{
b=d*e;
}
min=LLONG_MAX;
for(i=0;i<n-1;i++){
if(ar[i+1]-ar[i]<min){
min=ar[i+1]-ar[i];
}
}
// printf("%lld\n",min);
if(min==0){
c=0;
a=ar[0];d=1;
for(i=1;i<n;i++){
if(ar[i]==a){
d++;
}else{
c+=((d*(d-1))/2);
d=1;
a=ar[i];
}
}
c+=((d*(d-1))/2);
}else{
c=0;
for(i=1;i<n;i++){
if(ar[i]-ar[i-1]==min){
c++;
}
}
}
printf("%lld %lld",c,b);
return 0;
}

Friends of Friends

problem statement is here

#include<stdio.h>
int main(){
int a,i,j,n,m[200],ar[10009]={0},ans=0,b;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d %d",&m[i],&a);
for(j=0;j<a;j++){
scanf("%d",&b);
ar[b]=1;
}
}
for(i=0;i<n;i++){
ar[m[i]]=0;
}
for(i=0;i<10000;i++){
if(ar[i]==1){
ans++;
}
}
printf("%d\n",ans);
return 0;
}

Minimum spanning tree kruskal algorithm

Time complexity O(eLoge + eLogv)
steps:-
        sort all the edges according to their weights
        pick minimum weighted edge and check for cycle
                     if(makes cycle) -> discard that edge
                     else -> take it
        repeat it until we get  v-1 nodes 

no of edges in final tree = v-1


#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int e,v;
struct nodes{
int a;
int b;
int w;
};
struct checker{
int parent;
int rank;
};

bool compare (nodes p1, nodes p2){
return (p1.w > p2.w);
}

int find( struct checker br[], int i){
    if (br[i].parent != i){
    br[i].parent = find(br, br[i].parent);
    }
  return br[i].parent;
}

void Union(struct checker br[],int x,int y){
    int xroot = find(br, x);
    int yroot = find(br, y);
    if (br[xroot].rank < br[yroot].rank){
    br[xroot].parent = yroot;
    }else if (br[xroot].rank > br[yroot].rank){
    br[yroot].parent = xroot;
    }else{
        br[yroot].parent = xroot;
        br[xroot].rank++;
    }
}
int kruskal(vector<nodes>& ar){
int weight=0;
struct checker br[1000];
int i;
sort(ar.begin(),ar.end(),compare);
for(i=0;i<v;i++){
br[i].parent=i;
br[i].rank=0;
}
int z=0;
for(i=e-1;i>=0;i--){
int x=find(br,ar[i].a);
int y=find(br,ar[i].b);
if(x!=y){
Union(br,ar[i].a,ar[i].b);
weight+=ar[i].w;
z++;
}
if(z==v-1){
break;
}
}
return weight;
}

int main(){
int c,d,r,i,j,n,m;
vector<nodes> ar(1000);
        printf("Enter no of vertexes and edges\n");
scanf("%d %d",&v,&e);
        printf("Edges\n");
for(i=0;i<e;i++){
scanf("%d %d %d",&ar[i].a,&ar[i].b,&ar[i].w);
}
c=kruskal(ar);
printf("%d\n",c);
return 0;
}

Easiest loop 1

//http://www.spoj.com/problems/SNGLOOP1/

here after solving the equation

    p=(10*m+15+4*Sm)/(10*n+15+4*Sn)     

and for any m or n 

   p=3^(m-n)

#include<stdio.h>
int main(){
    long long t,m,n,p;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld %lld",&n,&m);
        p=(m-n)%4;
        if(p==1)
            printf("3\n");
        else if(p==2)
            printf("9\n");
        else if(p==3)
            printf("7\n");
        else
            printf("1\n");
    }
    return 0;
}

potions class

  problem statement is here

#include<stdio.h>
int main(){
long long a,b,c,w,x,y,z,q,i,t,n,ar[100007],br[100006],l;
scanf("%lld",&t);
while(t--){
ar[0]=0;br[0]=0;
scanf("%lld %lld",&n,&q);
for(i=1;i<=n;i++){
scanf("%lld",&l);
ar[i]=ar[i-1]+l;
br[i]=br[i-1]+(l*i);
// printf("%lld %lld\n",ar[i],br[i]);
}
while(q--){
scanf("%lld %lld %lld %lld",&w,&x,&y,&z);
a=(w-x)*(ar[x+z]-ar[x+y-1]);
b=br[x+z]-br[x+y-1];
c=a+b;
c%=1000000007;
printf("%lld\n",c);
}
}
return 0;
}

Dijkstra’s algorithm using adjacency matrix

this program finds distance of all vertexes from a given source vertex
time complexity using adjacency matrix is O(v^2)
it doesn't work for negative weighted graphs


#include <stdio.h>
#include <limits.h>
int n;
int takemin(int dist[],int visited[]){
   int min=INT_MAX,min_index,i;
  for(i=0;i<n;i++)
     if(visited[i]==0 && dist[i] <= min){
      min=dist[i];
min_index=i;
     }
  return min_index;
}

int printfinal(int dist[],int n){
int i;
   printf("Vertex   Distance from Source\n");
   for(i=0;i<n;i++)
      printf("%d                 %d\n",i,dist[i]);
}

void dijkstra(int graph[n][n], int source){
     int dist[n],visited[n],i,j,u;
     for(i=0;i<n;i++){
      dist[i]=INT_MAX;
visited[i]=0;
     }
     //taking distance of source as 0
    dist[source]=0;
    for(j=0;j<n-1;j++){
       //take min distance vertex which is not taken yet
       u=takemin(dist,visited);
  //mark the picked vertex as visited
       visited[u]=1;
//update the distances of vertexes adjacent to the picked vertex
       for(i=0;i<n;i++){
        if(graph[u][i]>0 && visited[i]==0){
        if(dist[u]+graph[u][i]<dist[i] || dist[i]==INT_MAX){
        dist[i]=dist[u]+graph[u][i];
        }
        }
    }
    }
    printfinal(dist,n);
}

int main(){
int i,j;
printf("Enter no of vertexes\n");
scanf("%d",&n);
int graph[n][n];
printf("Enter adjacency matrix\n");
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&graph[i][j]);
}
}
  dijkstra(graph, 0);
  return 0;
}

Hackerrank candies

// https://www.hackerrank.com/challenges/candies

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    long a=0,n,i,j,ar[100003],dp[100003];
    scanf("%ld",&n);
    scanf("%ld",&ar[0]);
    dp[0]=1;
    for(i=1;i<n;i++){
        scanf("%ld",&ar[i]);
        if(ar[i]>ar[i-1]){
            dp[i]=dp[i-1]+1;
        }else{
            dp[i]=1;
        }
    }
    for(i=n-2;i>=0;i--){
        if(ar[i]>ar[i+1] && dp[i]<=dp[i+1]){
            dp[i]=dp[i+1]+1;
        }
    }
    for(i=0;i<n;i++){
        //printf("%ld  ",dp[i]);
        a+=dp[i];
    }
    printf("%ld\n",a);
    return 0;
}

red john is back

// https://www.hackerrank.com/challenges/red-john-is-back

problem statement is here

#include<stdio.h>
int ar[300000]={0};
long long fact(long long a){
long long i,b=1;
for(i=2;i<=a;i++){
b*=i;
}
return b;
}
int main(){
    long long x,a,b,c,d,e,i,j,z;
    ar[0]=ar[1]=1;
    for(i=2;i<3000;i++){
    if(ar[i]==0){
    for(j=i*2;j<300000;j+=i){
    ar[j]=1;
    }
    }
    }
scanf("%lld",&d);
    while(d--){
        scanf("%lld",&a);
        if(a<4){
            b=1;
        }else{
            e=a/4;
            b=1;
            for(i=1;i<=e;i++){
            z=1;
            for(x=a-i*4+1;x<=a-i*4+i;x++){
            z*=x;
            }
            z/=fact(i);
            // printf("z=%lld\n",z);
            b+=z;
            }
        }
        c=0;
        for(i=2;i<=b;i++){
            if(ar[i]==0){
                c++;
            }
        }
        printf("%lld\n",c);
    }
 
    return 0;
}

tip top game

 problem statement is here

#include<stdio.h>
#include<math.h>
int main(){
    long long int a,b,c=1;
    long int t;
    scanf("%ld",&t);
    while(t--){
               scanf("%lld",&a);
               b=sqrt(a);
               if(b*b==a){
                printf("Case %lld: Yes\n",c);
               }else{
                printf("Case %lld: No\n",c);
               }
               c++;
    }
        return 0;
     }

Spoj prime time

// http://www.spoj.com/problems/PTIME/

#include<stdio.h>
int sieve[100010]={0};
long prime_table() {
    int i, j;
    for (i = 2; i <=50000; i+= 2)
           sieve[i]=1;

        for (i = 3; i <=50000; i += 2){
                if (sieve[i]==0){
                    for (j=i; (j*i) <=50000; j += 2){
                        sieve[j*i] = 1;
                    }
                }
        }
}
int main(){
prime_table();
long long a,t,n,i,j,u,x,v,p,s;
scanf("%lld",&n);
a=n;x=0;p=2;
while(a){
a=n;
x+=(n/p);
p*=2;
a/=p;
}
printf("%lld^%lld",2,x);
for(i=3;i<=n;i+=2){
if(sieve[i]==0){
a=n;x=0;p=i;
while(a){
a=n;
x+=(n/p);
p*=i;
a/=p;
}
printf(" * %lld^%lld",i,x);
}
}
printf("\n");
return 0;
}

Spoj alia and 3 khans

// http://www.spoj.com/problems/KHANS/

#include<stdio.h>
int main(){
long long t,a,b,n,c,i,j,k,x,u,p=0,s=0,q,l;
int ar[100],br[100];
scanf("%lld",&t);
q=t;
while(t--){
scanf("%lld",&n);
a=n;i=0,j=0,k=0;
while(a>0){
ar[i]=a%2;
a/=2;
br[i]=ar[i];
i++;
}
// printf("%lld\n",i);
x=0;
for(j=0;j<i;j++){
if(ar[j]==0){
if(ar[j+1]==1){
u=ar[j];
ar[j]=ar[j+1];
ar[j+1]=u;
break;
}
}
if(ar[j]==1){
x++;
}
}
//printf("%lld\n",j);
if(j==i){
b=-1;
}else{
for(k=j-1;k>=0;k--){
if(x>0){
ar[k]=1;
x--;
}else{
ar[k]=0;
}
}
b=0;l=1;
for(j=0;j<i;j++){

b+=(ar[j]*l);
l*=2;
// printf("%d  ",mult(2,j));
}
}
ar[i]=0;
br[i]=0;
i++;
x=0;j=0;k=0;
for(j=0;j<i;j++){

if(br[j]==1){
if(br[j+1]==0){
u=br[j];
br[j]=br[j+1];
br[j+1]=u;
break;
}
}
if(br[j]==1){
x++;
}
}
// printf("%lld\n",x);
for(k=0;k<=j-1;k++){
if(x>0){
br[k]=1;
x--;
}else{
br[k]=0;
}
// printf("%d  ",br[k]);
}
c=0;l=1;
for(j=0;j<i;j++){
c+=(br[j]*l);
l*=2;
}
if(n==0){
c=-1;
}
//printf(" %lld %lld %lld\n",n,b,c);
if(n*n==b*c){
p++;
}
s+=(c-b);
//printf("%lld %lld\n",p,s);
}
double y,z;
y=(double)p/(double)q;
z=(double)s/(double)q;
printf("%.6lf %.6lf\n",y,z);
return 0;
}

Spoj alia and handsome devil

// http://www.spoj.com/problems/HDEVIL/

#include<stdio.h>
#include<math.h>
int main(){
long long a,b,c=1,i,j,t,n,ar[1000],m;
ar[0]=0;ar[1]=1;ar[2]=1;
for(i=3;i<100;i++){
ar[i]=ar[i-1]+ar[i-2];
}
// printf("%lld\n",ar[94]);
scanf("%lld",&t);
while(t--){
scanf("%lld %lld",&n,&m);
long long sum=0,sum1=0;
b=0;
a=sqrt(n);
if(a*a==n){
sum+=a;
a--;

}
for(i=2;i<=a;i++){
if(n%i==0){
sum+=i;
sum+=(n/i);
//printf("%lld\n",sum);
}
}
sum+=1;
sum%=m;
a=sqrt(sum);
if(a*a==sum){
sum1+=1;
a--;
}
for(i=2;i<=a;i++){
if(sum%i==0){
sum1+=2;
}
}
sum1+=1;
// printf("%lld\n",sum1);
for(i=0;i<96;i++){
if(ar[i]==sum1){
b=1;
break;
}
}
if(b==1){
printf("Case #%lld : YES.\n",c);
}else{
printf("Case #%lld : NO.\n",c);
}
c++;
}

return 0;
}

Spoj a famous icpc team

// http://www.spoj.com/problems/TEAM2/

#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
   long long int a[4],p;
   int j,i=1;
   while(scanf("%lld ",&a[0])!=EOF)
    {
     
        for(j=1;j<4;j++)
        {  
            scanf("%lld",&a[j]);
           
        }
        sort(a,a+4);
        p=a[3]+a[2];
        printf("Case %d: %lld\n",i,p);
        i++;
    }
    return 0;
}

Spoj Espionage

// http://www.spoj.com/problems/RPLE/

#include<stdio.h>
int main(){
long long int a,n,t,i,j,c=1,r,b;
scanf("%lld",&t);
while(t--){
long int ar[2000]={0},br[2000]={0},u=0;
scanf("%lld %lld",&n,&r);
while(r--){
scanf("%lld %lld",&a,&b);
ar[a]++;
br[b]++;
}
for(i=0;i<n;i++){
if(ar[i]>0 && br[i]>0){
u=1;
break;
}
}
if(u==1){
printf("Scenario #%lld: spied\n",c);
c++;
}else{
printf("Scenario #%lld: spying\n",c);
c++;
}
}
return 0;
}

Spoj princes farida

// http://www.spoj.com/problems/FARIDA/

#include <stdio.h>
unsigned long long int dp[1010];
int t,n;
unsigned long long int max(unsigned long long int a, unsigned long long int b){
return a > b ? a : b;
}
int main(){
int i, h;
scanf("%d", &t);
for(h=1;h<=t;h++){
scanf("%d",&n);
for(i=0;i<n;i++){
int k;
scanf("%d",&k);
dp[i]=max(k+(i>1?dp[i-2]:0),i>0?dp[i-1]:0);
}
printf("Case %d: %llu\n", h, dp[n-1]);
}

return 0;
}

Spoj is it a tree

//http://www.spoj.com/problems/PT07Y/

#include<stdio.h>
struct set{
int parent;
int rank;
};
int find(struct set ar[],int a){
if(ar[a].parent==-1){
return a;
}
find(ar,ar[a].parent);
}
int main(){
int a,b,c,d,e,x,i=0;
scanf("%d %d",&a,&b);
struct set ar[a+1];
for(x=0;x<=a;x++){
ar[x].parent=-1;
ar[x].rank=0;
}
while(b--){
scanf("%d %d",&c,&d);
int g=find(ar,c);
int f=find(ar,d);
if(g==f){
i=1;
}else{
if(ar[g].rank<ar[f].rank)
        ar[g].parent=f;
    else if(ar[g].rank>ar[f].rank)
        ar[f].parent=g;
    else{
        ar[f].parent=g;
        ar[g].rank++;
    }
}
}
if(i==0){
printf("YES\n");
}else{
printf("NO\n");
}
return 0;
}

dfs traversal of a graph using adjacency list

#include<stdio.h>
#include<vector>
using namespace std;
void dfs(vector<int> ar[],int visited[],int i,int n){
  int j;
  visited[i]=1;
  printf("%d\n",i);
  for(j=0;j<ar[i].size();j++){
  if(visited[ar[i][j]]==0){
  dfs(ar,visited,ar[i][j],n);
  }
  }
}
int main(){
  int a,b,i,j,n,m;
  printf("no of nodes\n");
  scanf("%d",&n);
  vector<int> ar[n+9];
  int visited[n+9];
  for(i=0;i<n+9;i++){
  visited[i]=0;
  }
  printf("no of edges\n");
  scanf("%d",&m);
  for(j=0;j<m;j++){
    scanf("%d %d",&a,&b);
    ar[a].push_back(b);
    ar[b].push_back(a);
  }
  for(i=1;i<=n;i++){
  if(visited[i]==0){
    dfs(ar,visited,i,n);
  }
  }
  return 0;
}

Spoj gopi and sandwich

// http://www.spoj.com/problems/GOPI_SW/

#include<stdio.h>
long long arr[1000006];
void solution(){
long i;
arr[2]=2;
for(i=3;i<=1000000;i++){
arr[i]=(arr[i-1]*(arr[i-1]+1))%1000000007;
}
}
int main(){
solution();
long long t,n;
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
printf("%lld\n",arr[n]%1000000007);
}
return 0;
}

Spoj database

//http://www.spoj.com/problems/RPLD/

#include <cstdio>
#include <algorithm>
using namespace std;

pair< long int, long int > ar[100000];

inline bool comp(const pair< int, int > &a, const pair< int, int > &b) {
return (a.first == b.first) ? a.second < b.second : a.first < b.first;
}

int main() {
long int t, i, n, l,r,c=1,u;
scanf("%ld", &t);
while(t--) {
u=0;
scanf("%ld %ld", &r,&n);
for(i = 0; i < n; i++)
scanf("%ld %ld", &ar[i].first, &ar[i].second);
sort(ar, ar + n, comp);
for(i=0;i<n;i++){
if(ar[i].first==ar[i+1].first){
if(ar[i].second==ar[i+1].second){
u=1;
break;
}
}
}
if(u==1){
printf("Scenario #%ld: impossible\n",c);
}else{
printf("Scenario #%ld: possible\n",c);
}
c++;
}
return 0;
}