LINK :: Question

Required Concepts : Partial Difference

Explanation : A number n will be a possible answer if the number of people having n in their range is exactly n (Byteknights always tell truth and knaves lie ). Therefore for each a and b input we need to increment its value by 1 so that in the end we have an array that represents how many people have told element i to be in their range . Let this array be KNUM, then element i can be a byteknight if KNUM[i]=i

         Instead we store a partial difference array with diff[i]=knight[i]-knight[i-1] . Thus for each a,b we need to increase diff[a] and decrease diff[b+1] for ith entry.

Thus ,

                                      KNUM[i]=diff[0]+diff[1]...diff[i]

If every n is a value in between limits of ith bytelandian then he has to be a knight else for a value he can become a byteknave and this is needed to print the lexicographic smallest one. And since he will be a byteknave his limit should be excluded from the range of n we have taken as possible because he speaks lie always.

CODE EXPLAINED :

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

int main(){
    int T;          //the number of test cases
    for(scanf("%d", &T); T--; ){
        int N, lo[50000], hi[50000], diff[50002]={0};     

        //the arrays to store ranges and diff
        scanf("%d", &N);
        for(int i=0; i<N; i++){
            scanf("%d%d", lo+i, hi+i);
            diff[lo[i]]++;
            diff[hi[i]+1]--;
        }
        set<int> good;      //set of all possible byteknights
        int ans=0, count=0;
        //if knights[n]=n then it can be a byteknight and
        //knights[n]=sum diff[i] from 0 to n
        for(int i=0; i<=N; i++){
            count+=diff[i];
            if(count==i){
                ans++;
                good.insert(i);
            }
        }
        printf("%d\n", ans);
        for(int i=0; i<N; i++){
        //tells truth i.e all possible knights are in his range
         //he has to be a byteknight
            if(lo[i]<=*good.begin() && *good.rbegin()<=hi[i])  
                putchar('1');
            else{
                putchar('0');
      //is made a knave and his range can be excluded from good set
                good.erase(good.lower_bound(lo[i]), good.upper_bound(hi[i]));
            }
        }
        putchar('\n');
    }
    return 0;
}

From this week on we start solving problems on Codechef, Interviewstreet etc. . with the view to improve your problem solving skills ..
          Apart from the code we will give a detailed mathematical and logical explanation about the problem.So lets start with something easy ..

LINK :: Question 1

Required Concepts : Euclid Algorithm

Well for both chefs we have A,B and C,D units that they can go .. so any length that is traversable by first chef is a multiple of gcd(A,B) and similarly any length that is traversable by second chef is a multiple of gcd(C,D) .. Hence units which are traversable by both are multiples of lcm=LCM(gcd(A,B),gcd(C,D)).Thus for the positive half of 1 to K number of such units equals K/lcm which is same on the other side of the rope. Hence our answer is 2*(K/lcm) + 1(bcz 0 is traversable by both as both can go forward and come back by same value).

typedef unsigned long long LL;
int T;
LL A,B,C,D,K;

LL gcd(LL a,LL b)    //euclid method for fast gcd
{
    if(b>a)
    return gcd(b,a);
    else
    return b==0?a:gcd(b,a%b);
}

int main()
{
    cin>>T;
    for(int i=0;i<T;i++)
    {
        cin>>A>>B>>C>>D>>K;
        LL n1=gcd(A,B);
        LL n2=gcd(C,D);
        LL den=gcd(n1,n2);
        LL S=n1/den;     //split the LCM part 1
        LL R=K/S;        //LCM part 2
        LL n4=R/n2;      //the final value
        cout<<(2*n4)+1<<endl;
    }
    return 0;
}

For finding LCM of a and b we used (a*b/gcd(a,b)) ..

Ever been troubled by segmentation faults .. now use gdb to take a closer inspection..

GDB stands for GNU Debugger which is a debugger for C and C++ .For any file you need to add -g to enable default debugging support.For enabling gdb just type gdb or gdb <filename> .If you did not mention the file earlier you can mention it by using the file command.
(gdb) file prog1.x
To run the program:
(gdb)run
If the program does have issues you will get information about where the program crashed i.e the line number and parameters to the function that caused the error.

The break command is used for setting the breakpoints in the program.For setting breakpoints in the file line pair use:
(gdb) break file.c:8
For breaking at a particular function use:
(gdb)break fib_func

To proceed to the next breakpoint use the continue statement:
(gdb)continue
To proceed one step at a time use the step statement:
(gdb)step

To print the value of the variables at any given time use the print command which prints the value of the variables and the print/x which gives the value of the variables mentioned in the program as hexadecimal.

Breakpoints stop the program at the points in the program ..whereas watchpoints watch over changes in the variables .
(gdb) watch i
whenever i is modified the program interrupts and prints out the old and the new values.Other useful commands are:
backtrace - produces a stack trace of the function calls that lead to a seg fault
finish - runs until the current function is finished
delete - deletes a specified breakpoint
info breakpoints - shows information about all declared breakpoints
                                                                                                                                                                                                                                                
Breakpoints are a tedious task of getting data always out of programs.To get specific
parts you can use conditional breakpoints like:
(gdb)break file1.c:6 if i >= ARRAYSIZE

So now you can try out various commands in your terminal and check out the gdb
manual for more details.

A Randomized Algorithm is one in which we use a randomizer or some kind of random number.Some decisions made in the algorithm depend on the output of the randomizer.Hence they have different runtime each time they are run even if the input is correct.
      Randomized algorithms can be divided into two categories:
Las Vegas Algorithms : These algorithms always give the correct output, however their runtime differ based on the output of the randomizer
Monte Carlo Algorithms: These algorithms give the correct answer for most of the cases however they may give incorrect answers for a small percent of values.

Primality testing using Miller-Rabin's Method: This algorithm makes use of Fermat theorem i.e. if n is prime than a^(n-1) %n=1 for any a<n.

Th2: The equation x^2%n=1 has exactly two solutions namely 1 and n-1
Th3: The equation x^2(mod n)=1 has roots other than 1 and n-1 then n is composite

The algorithm fails for some composite numbers (Carmichael numbers) for which every a that is less than and relatively prime to n will satisfy Fermats theorem.e.g 561 and 1105

Implementation:

int prime(int n,int alpha)
{
  int q=n-1;int i;
  int up=(int)alpha*log(n);
  int m,y,a,z,x;
  for(i=0;i<up;i++)
    {
      m=q;y=1;
      a=rand()%q+1;
      //choosing a random number in the range [1,n-1]
      z=a;
      //compute a^n-1 mod n
      while(m>0)
    {
      while(m%2==0)
        {
          x=z;
          z=(z*z)%n;
          if((z==1)&&(x!=1)&&(x!=q))
        return 0;
          m=(int)m/2;
        }
      m=m-1;y=(y*z)%n;
    }
      if(y!=1)
    return 0;
      //if a^n-1 mod n is not 1 n is not a prime
    }
  return 1;
}

#include<stdio.h>
#include<assert.h>
#include<conio.h>
/* maxVertices represents maximum number of vertices that can be present in the graph. */
/*graph is undirected and not weighted*/
#define maxVertices   100
void Dfs(int graph[][maxVertices],int *size,int presentVertex,int *visited)
{
     printf("Now visiting vertex %d\n",presentVertex);
     visited[presentVertex]=1;
     /* Iterate through all the vertices connected to the presentVertex and perform dfs on those
           vertices if they are not visited before */
     int iter;
     for(iter=0;iter<size[presentVertex];iter++)
     {
             if(!visited[graph[presentVertex][iter]])
             Dfs(graph,size,graph[presentVertex][iter],visited);
     }
     return;
}
/* Input Format: Graph is directed and unweighted. First two integers must be number of vertces and edges 
   which must be followed by pairs of vertices which has an edge between them. */
int main()
{
        int graph[maxVertices][maxVertices],size[maxVertices]={0},visited[maxVertices]={0};
        int vertices,edges,iter;
        /* vertices represent number of vertices and edges represent number of edges in the graph. */
        scanf("%d%d",&vertices,&edges);
        int vertex1,vertex2;
        for(iter=0;iter<edges;iter++)
        {
                scanf("%d%d",&vertex1,&vertex2);
                assert(vertex1>=0 && vertex1<vertices);
                assert(vertex2>=0 && vertex2<vertices);
                graph[vertex1][size[vertex1]++] = vertex2;
        }
        int presentVertex;
        for(presentVertex=0;presentVertex<vertices;presentVertex++)
        {
                if(!visited[presentVertex])
                {
                        Dfs(graph,size,presentVertex,visited);
                }
        }
        getche();
        return 0;

}     


--------------------------------------PYTHON IMPLEMENTATION---------------------------------------------

def dfs(graph,p_vertex,visited):
    print("Visiting vertex {0}".format(p_vertex))
    visited[p_vertex]=1
    #print(len(graph[p_vertex]))
    for itr in range(0,len(graph[p_vertex])):
        if(visited[graph[p_vertex][itr]]==0):
            #print("sent to visit vertex {0}".format(graph[p_vertex][itr]))
            dfs(graph,graph[p_vertex][itr],visited)
    return

vertices=int(input("Enter number of vertices::"))
edges=int(input("Enter the number of edges::"))
graph=[]
visited=[0]*vertices

#create the vertices
for i in range(0,vertices):
    v=[]
    graph.append(v)
#take input
for i in range(0,edges):
    v1,v2=input().split()
    v1,v2=int(v1),int(v2)
    assert(v1>=0 and v1<vertices)
    assert(v2>=0 and v2<vertices)
    graph[v1].append(v2)

print(graph)

for p_vertex in range(0,vertices):
    if(visited[p_vertex]==0):
        dfs(graph,p_vertex,visited)

# breadth first search in PYTHON 3.2 #
from queue import *

def bfs(graph,p_vertex,visited):
    q=Queue()
    q.put(p_vertex)
    visited[p_vertex]=1
    while q.qsize()>0:
        t=q.get()
        print("Visiting vertex {0}".format(t))
        #i.e if t is what we want return t
        for child in range(0,len(graph[p_vertex])):
            if(visited[graph[p_vertex][child]]==0):
                visited[graph[p_vertex][child]]=1
                q.put(graph[p_vertex][child])
    return

vertices=int(input("Enter number of vertices::"))
edges=int(input("Enter the number of edges::"))
graph=[]
visited=[0]*vertices

#create the vertices
for i in range(0,vertices):
    v=[]
    graph.append(v)
#take input
for i in range(0,edges):
    v1,v2=input().split()
    v1,v2=int(v1),int(v2)
    assert(v1>=0 and v1<vertices)
    assert(v2>=0 and v2<vertices)
    graph[v1].append(v2)
print(graph)

for p_vertex in range(0,vertices):
    if(visited[p_vertex]==0):
        bfs(graph,p_vertex,visited)


----------->For those interested in C implimentation might find this a little long then python but here it is-------------->


#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
/* maxVertices represents maximum number of vertices that can be present in the graph. */
#define maxVertices   100
typedef struct Queue
{
        int capacity;
        int size;
        int front;
        int rear;
        int *elements;
}Queue;
/* crateQueue function takes argument the maximum number of elements the Queue can hold, creates
   a Queue according to it and returns a pointer to the Queue. */
Queue * CreateQueue(int maxElements)
{
        /* Create a Queue */
        Queue *Q;
        Q = (Queue *)malloc(sizeof(Queue));
        /* Initialise its properties */
        Q->elements = (int *)malloc(sizeof(int)*maxElements);
        Q->size = 0;
        Q->capacity = maxElements;
        Q->front = 0;
        Q->rear = -1;
        /* Return the pointer */
        return Q;
}
void Dequeue(Queue *Q)
{
        /* If Queue size is zero then it is empty. So we cannot pop */
        if(Q->size==0)
        {
                printf("Queue is Empty\n");
                return;
        }
        /* Removing an element is equivalent to incrementing index of front by one */
        else
        {
                Q->size--;
                Q->front++;
                /* As we fill elements in circular fashion */
                if(Q->front==Q->capacity)
                {
                        Q->front=0;
                }
        }
        return;
}
int Front(Queue *Q)
{
        if(Q->size==0)
        {
                printf("Queue is Empty\n");
                exit(0);
        }
        /* Return the element which is at the front*/
        return Q->elements[Q->front];
}
void Enqueue(Queue *Q,int element)
{
        /* If the Queue is full, we cannot push an element into it as there is no space for it.*/
        if(Q->size == Q->capacity)
        {
                printf("Queue is Full\n");
        }
        else
        {
                Q->size++;
                Q->rear = Q->rear + 1;
                /* As we fill the queue in circular fashion */
                if(Q->rear == Q->capacity)
                {
                        Q->rear = 0;
                }
                /* Insert the element in its rear side */
                Q->elements[Q->rear] = element;
        }
        return;
}



void Bfs(int graph[][maxVertices], int *size, int presentVertex,int *visited)
{
        visited[presentVertex] = 1;
        /* Iterate through all the vertices connected to the presentVertex and perform bfs on those
           vertices if they are not visited before */
        Queue *Q = CreateQueue(maxVertices);
        Enqueue(Q,presentVertex);
        while(Q->size)
        {
                presentVertex = Front(Q);
                printf("Now visiting vertex %d\n",presentVertex);
                Dequeue(Q);
                int iter;
                for(iter=0;iter<size[presentVertex];iter++)
                {
                        if(!visited[graph[presentVertex][iter]])
                        {
                                visited[graph[presentVertex][iter]] = 1;
                                Enqueue(Q,graph[presentVertex][iter]);
                        }
                }
        }
        return;


}
/* Input Format: Graph is directed and unweighted. First two integers must be number of vertces and edges
   which must be followed by pairs of vertices which has an edge between them. */
int main()
{
        int graph[maxVertices][maxVertices],size[maxVertices]={0},visited[maxVertices]={0};
        int vertices,edges,iter;
        /* vertices represent number of vertices and edges represent number of edges in the graph. */
        scanf("%d%d",&vertices,&edges);
        int vertex1,vertex2;
        for(iter=0;iter<edges;iter++)
        {
                scanf("%d%d",&vertex1,&vertex2);
                assert(vertex1>=0 && vertex1<vertices);
                assert(vertex2>=0 && vertex2<vertices);
                graph[vertex1][size[vertex1]++] = vertex2;
        }
        int presentVertex;
        for(presentVertex=0;presentVertex<vertices;presentVertex++)
        {
                if(!visited[presentVertex])
                {
                        Bfs(graph,size,presentVertex,visited);
                }
        }
        return 0;
}

------------------------------------------------------->END<------------------------------------------------------------------

Here is another important graph algo for finding the minimum weighted spanning tree imlimented in C.Input is taken from adj matrix with non-conn terms having val in #define MAXVAL & the number of vert changed by changing #define MAXVAL...


/*KRUSKAL ALGORITHM IN C*/
#include<stdio.h>
#define VERT 4 //predefined number of vertices
#define MAXVAL 99
void kruskal(int a[][VERT],int n);
int gethead(int vert,int par[]);
void vertex_union(int v1,int v2,int par[]);

void vertex_union(int v1,int v2,int par[])
{
    if(v1>v2)
    par[v1]=v2;
    else
    par[v2]=v1;
}

int gethead(int vert,int par[])
{
    while(par[vert]!=vert)
    {
        vert=par[vert];
    }
    return vert;
}

void kruskal(int a[][VERT],int n)
{
    int nofedges,i,parent[VERT],min,j,k,u,v,path[VERT-1][2],sum;
    nofedges=k=sum=0;
    for(i=0;i<n;i++)
    parent[i]=i;//sets parent
    while(nofedges<n-1)
    {
        min=MAXVAL;
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        if(a[i][j]<min)
        {
            min=a[i][j];
            u=i;
            v=j;
        }//gets the min for each turn
        if(min!=MAXVAL)
        {
            i=gethead(u,parent);
            j=gethead(v,parent);
            /*printf("==>%d %d %d %d\n",i,j,u,v);
            int ii;
            for(ii=0;ii<VERT;ii++)
            printf("%d ",parent[ii]);
            printf("\n");*/
            if(i!=j)
            {
                //printf("-->adding vertex %d %d",u,v);
                path[k][0]=u;
                path[k][1]=v;
                k++;
                sum+=min;
                vertex_union(i,j,parent);
                nofedges+=1;
            }
            a[u][v]=a[v][u]=999;
        }
    }
    if(nofedges!=n-1)
    printf("Invalid Spanning Tree");
    else
    {
        printf("Minimum cost=%d\n",sum);
        printf("The edges included are ::\n");
        for(i=0;i<n-1;i++)
        printf("%d %d \n",path[i][0],path[i][1]);
    }
}

int main()
{
    int cost[VERT][VERT],i,j;
    for(i=0;i<VERT;i++)
    for(j=0;j<VERT;j++)
    scanf("%d",&cost[i][j]);
    //adjacency matrix entered
    kruskal(cost,VERT);

}

Hope you enjoyed this..