David and his Obsession

problem statement is here


#include<stdio.h>
int main(){
printf("1/420\n");
return 0;
}

A Summatory

problem statement is here

#include <stdio.h>

#define M 1000010

int t,c;

long long int sum[M];

int main(){

      long long int i, a = 0;

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

                  a = (a + i*i*i) % 1000000003;

                  sum[i] = (sum[i-1] + a) % 1000000003;

                   }

           scanf("%d", &t);

           while (t--){

              scanf("%d", &c);

              printf("%lld\n", sum[c]);

               }

           return 0;

}

GETTING AN AP

problem statement is here

#include<stdio.h>

long long gcd(long long m,long long n){

 if(n==0)

  return m;

 else 

  return gcd(n,m%n);

}

long long calcu(long long a,long long n){

long long u,c,d;

u=0;

if(n%2==0){

c=(a-n)/2;

c--;

d=(a-1)/2;

u=(d*(d+1))/2;

u=u-(c*(c+1))/2;

u*=2;

}else{

c=(a-n)/2;

c--;

d=(a-2)/2;

u=(d*(d+1))/2;

u=u-(c*(c+1))/2;

u*=2;

u+=((a-1)/2);

}

u+=n;

return u;

}

int main(){

long long a,b,n,p,t;

scanf("%lld",&t);

while(t--){

scanf("%lld",&n);

a=calcu(3*n,n)+calcu(n,n-2);

a-=(n-2);

p=n*2*n*3*n;

b=gcd(a,p);

a/=b;

p/=b;

printf("%lld/%lld\n",a,p);

}

return 0;

}

Large subsequence Problem

problem statement is here

#include<stdio.h>
#include<string.h>
#define mod 1000000007
int main(){
int c=1,i,n,t,u,v,s;
char ar[10011];
scanf("%d",&t);
while(t--){
s=0;
int br[11]={0};
scanf("%s",ar);
n=strlen(ar);
for(i=0;i<n;i++){
v=u=ar[i]-48;
while(v--){
br[u]=(br[u]+br[v])%mod;
}
br[u]++;
}
for(i=0;i<=9;i++){
s=(s+br[i])%mod;
}
printf("Case %d: %d\n",c,s);
c++;
}
return 0;
}

Distracted judges

problem statement is here

#include<stdio.h>

int main(){

long a,b,c,d,i,j,t,n;

scanf("%ld",&t);

long ar[100005],br[100005],cr[100005]={0};

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

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

}

j=0;

br[j]=t;

j++;

a=1;

for(i=t-2;i>=0;i--){

if(ar[i]==a){

br[j++]=i;

cr[i]=1;

}else if(cr[i+ar[i]+1]==1){

br[j++]=i;

cr[i]++;

}

a++;

}

for(i=j-1;i>=0;i--){

if(br[i]!=0)

printf("%ld\n",br[i]);

}

return 0;

}

Gallantry

problem statement is here

#include<stdio.h>

#include<algorithm>

using namespace std;

int main(){

int a,b,c,d,ar[10004],br[10000],n,i,j,t;

scanf("%d",&t);

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

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

}

sort(ar,ar+t);

b=0;c=0;

for(i=0;i<t;i+=2){

br[b]=ar[i+1]-ar[i];

c+=br[b];

b++;

}

if(c==0){

printf("-1\n");

}else{

a=t/2;d=0;n=0;

sort(br,br+a);

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

if(c-br[i]>n+br[i]){

c-=br[i];

d++;

n+=br[i];

}else{

break;

}

}

printf("%d\n",d);

}

return 0;

}

Breadth first traversal for undirected graph

here we are assuming that all the nodes are connected


#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
void bfs(vector<int> ar[],int visited[],int i,int n){
  int j;
  queue<int> que;
  visited[i]=1;
  que.push(i);
  while(que.size()>0){
   i=que.front();
   que.pop();
   printf("%d\n",i);
   for(j=0;j<ar[i].size();j++){
          if(visited[ar[i][j]]==0){
              que.push(ar[i][j]);
              visited[ar[i][j]]=1;
          }
      }
  }

}
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);
   printf("Enter edges\n");
   for(j=0;j<m;j++){
     scanf("%d %d",&a,&b);
     ar[a].push_back(b);
     ar[b].push_back(a);
   }
   printf("from which node to traverse\n");
   scanf("%d",&i);
   bfs(ar,visited,i,n);
  return 0;
}

Crucial Equation

problem statement is here

#include<stdio.h>

gcd(int m,int n){

if(n==0)

return m;

else 

return gcd(n,m%n);

}

int main(){

int a,b,c,t,g,e=1;

scanf("%d",&t);

while(t--){

scanf("%d %d %d",&a,&b,&c);

g=gcd(abs(a),abs(b));

if(c%g==0)

printf("Case %d: Yes\n",e);

else 

printf("Case %d: No\n",e);

e++;

}

return 0;

}

Pigeonhole Tower

problem statement is here

#include<stdio.h>

#include<math.h>

int main() {

long long a,b,c=1,d,i,j,t,n;

scanf("%lld",&t);

while(t--){

scanf("%lld",&n);

if(n<3){

a=0;

}else{

b=sqrt(n);

while(1){

if(b*(b+2)<=n){

a=b;

break;

}else{

b--;

}

}

}

printf("Case %lld: %lld\n",c,a);

c++;

}

return 0;

}

spoj dota heroes

problem statement is here

#include<stdio.h>
int main(){
    int a,i,j,k,h[100000],d,t,n,l;
    scanf("%d",&a);
    for(i=0;i<a;i++){
        scanf("%d %d %d",&n,&t,&d);
        for(j=0;j<n;j++){
            scanf("%d",&h[j]);
        }
        l=0;
        for(k=0;k<t;k++){
            for(j=0;j<n;j++){
            if(h[j]>d){
                    h[j]=h[j]-d;
                    l=l+1;
                    break;
            }
            }
        }
        if(l==t)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

Boring factorials

problem is here

This can be solved using Wilson theorem
   (1). if n>=p  ans would be 0
   (2). then we have to use Wilson's theorem
             (p-1)!   ≡  -1 (mod p)
             1*2*3*.........*(n-1)*(n)*..............*(p-1)  ≡   -1 (mod p)
             n!*(n+1)*...........*(p-1)   ≡   -1 (mod p)
             n!  ≡    -1*[(n+1)*...............(p-2)*(p-1)]^-1 (mod p)


#include<stdio.h>
long long power(long long a,long long b,long long m){
  long long x=1,y=a;
  while(b>0){
  if(b%2!=0){
  x=(x*y)%m;
  }
  y=(y*y)%m;
  b>>=1;
  }
  return x;
}
int main(){
  int t;
  long long n,p,i,result,z,x;
  scanf("%d",&t);
  while(t--){
  result=-1;
  scanf("%lld %lld",&n,&p);
  if(n>=p){
    printf("0\n");
    continue;
  }
  x=1;
  for(i=n+1;i<p;i++){
  x=(x*i)%p;
  }
    z=power(x,p-2,p);
    result=(result*z)%p;
  printf("%lld\n",p+result);
  }
  return 0;

}

Interesting Selection

problem statement is here

here we have two possibilities
        (1). we take cold drink from 1st position
        (2). we take poison from 1st position
rest can be easily calculated using dp


#include<stdio.h>
long long ar[100006],br[100007];
long long max(long long a,long long b){
if(a>b){
return a;
}else{
return b;
}
}
long long check(long long a,long long b){

if(a>b){
return 0;
}
long long cr[b+1],i;
cr[a]=ar[a];
cr[a-1]=0;
for(i=a+1;i<=b;i++){
cr[i]=max((cr[i-2]+ar[i]-br[i-1]),cr[i-1]-br[i]);
}
return cr[b];
}
int main(){
long long a,b,c,i,j,n,x,y,z;
int t;
scanf("%d",&t);
while(t--){
scanf("%lld",&n);
for(i=0;i<n;i++){
scanf("%lld",&ar[i]);
}
for(i=0;i<n;i++){
scanf("%lld",&br[i]);
}
if(n==1){
x=ar[0];
}else if(n==2){
x=max(ar[0]-br[1],ar[1]-br[0]);
}else{
y=ar[0]-br[n-1]-br[1]+check(2,n-2);
z=check(1,n-1)-br[0];
x=max(y,z);
}
printf("%lld\n",x);
}
return 0;
}

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;
}