What is 1000000007 ?

Hello Guys,

As a newbie on online Coding contests, I was initially fed-up with 1000000007.I hardly understood the logic behind it.

Some guys give an hint that "its the first 10 digit prime..", so what ?
There were 2 questions in my mind.
1) Why only a prime.
2) Why not 2nd or 3rd prime

Instantly I got an partial answer from myself for the first question, A prime because we need (ans % Prime) as the actual answer, so the o/p should be unique.

But, there was a lot behind that word Prime in this case (Explained later)

The 2nd question what still open, but lately I understood that 1000000007 is easy to represent as 10^9+7. Any greater Prime would have served the purpose but this was easy to write. Infact some times we find the 2nd 10 digit prime which is again easy to represent 1000000009.

This would have been very well understood by everyone now.


Coming to the actual point.

All of us might have noticed that 1000000007 comes only when our answers are expected to be very large, more commonly when we implement combinations n(c,k) or nCk.

The combination formula is n!/(r!(n-r)!).

We are asked mod operation with 1000000007 for 2 reasons,
1) Obviously, so as to restrict our answer to 10 digit and
2) Help us with large multiplications and divisions.

Did u read Division ? yes !!!

We must know that (%) is distributive over multiplication,addition etc, but not over division.
So, how to do large divisions ?

There`s a theorem known as "Fermat's little theorem".
It say`s that (A/B) % MOD = ((A % MOD)*(B^(MOD-2) % MOD))%MOD (You can refer wiki for actual theorem)

Now, we can see that, Fermat's theorem essentially convert all our division to multiplication.So we can use our mod (%) operation.

If you have any issues/queries, please comment the same... I will try my best to answer it.

Continue

Techgig Monthend challenge : Foreign Trip : Level Easy

Problem Statement

A company organizes two foreign trips for its employees yearly. Aim of the trip is to increase interaction among the employees of the company and hence company wants each of his employee to see new people on the trip and not even a single person with whom he has worked in past. Therefore it is a rule in company that in any of the trips, all the employees should be new to each other and no two of them should have worked together in past.

Given the work history of each employee (which people he has worked with sometimes in past), you have to tell whether all of the employees can be accommodated within trips without violating the above rule or not. Each employee is given a unique integer ID by which they are recognized. You can also assume that each employee has worked with at least one other employee in past.

Note: No employee can be in both trips and every employee must be part of one trip.

Examples

Example: 

i) Suppose the work history is given as follows: {(1,2),(2,3),(3,4)}; then it is possible to accommodate all the four employees in two trips (one trip consisting of employees 1& 3 and other having employees 2 & 4). Neither of the two employees in the same trip have worked together in past.

ii) Suppose the work history is given as {(1,2),(1,3),(2,3)} then there is no way possible to have two trips satisfying the company rule and accommodating all the employees.

==========================================================================

This is an old Question on Techgig, but lets discuss it as we are finding it difficult to approach the problem.

Well, I had solved this question few months back and scored just 90. Unable to 100 (Maybe I am missing a corner case, not sure though).

I can`t recollect the exact thought process of mine towards this problem but I will explain the final approach used by me.

As per the question, they are giving us the set of employees who have worked with each other. So lets keep a mapping of the employees who have worked with each other.

Then, if an employee has worked with someone, check for all combinations of employee such that the intersection should not be marked as "1" (i.e worked with each other)

Here is the code : (Fetches only 90)

#include
#include

char* emp_violating(int input1,char* input2)
{
    int i=0,j=0,k=0;
    int a=0,b=0;
    int map[input1+1][input1+1];
    int cnt[input1+1];
    for(i=0;i<=input1;i++)
    {    for(j=0;j<=input1;j++)
            map[i][j]=0;
            cnt[i]=0;
    }
    while(1)
    {
        while(*input2 != '(') 
    {input2++;}
        input2++;
        while(*input2>='0' && *input2<='9')    /*For more than 1 digit numbers*/
        {
            a=a*10 + (int)*input2++ - '0';
        }
        while(*input2 != ',') 
        input2++;
        input2++;
        while(*input2>='0' && *input2<='9')    /*For more than 1 digit numbers*/
        {
            b=b*10 + (int)*input2++ - '0';
        }
        map[a][b]=1;map[b][a]=1; /*Mark that both guys have been with each other*/
        cnt[a]++;cnt[b]++; /*Increment the count to identify that they have been to a picnic. This can also just set to be dirty*/
        input2++;
        if(*input2!=',')
        break;
        a=0;b=0;
    }

    for(i=1;i<=input1;i++)
    {
        if(cnt[i]>1)
        {
            for(j=1;j<=input1;j++)
            {
                for(k=j+1;k
                {
                    if(map[i][j]==1 && map[i][k]==1)
                    {
                        if(map[j][k]==1) return "no";
                    }
                }
            }    
        }
    }
    return "yes";
}

int main() /*Driver*/
{
    char *a="(10,2),(2,3),(3,4)";
    printf("%s\n",emp_violating(10,a));
    return 0;
}

Continue

Techgig July contest : Musical Pillow : Level (Medium)

Problem Statement

In a family party, people are playing the musical pillow game in which people sit in a circle. Starting from the first person, they transfer the pillow to the person to their left. For simplicity, we’ll assume that people are assigned an integer tag from 1 to n(which is the total number of people) in the clockwise manner, so that during the game pillow is passed in the increasing sequence of. When game starts, a song is played and the person with the pillow at the end of the song, is eliminated and game starts again till there is only one person is left, which is declared as the winner of the game.

                                                You are give total number of people playing the game and the duration of the song in seconds. If game starts with pillow being put on a table & person1 (person with tag number 1)picking it up(at the end of first second [time], pillow will be with person1) and each person takes one second to transfer the pillow to the next person, you have to tell which person (tag number) which will win the game.

Examples

Example 1: Let there are 5 people and duration of the song is 2 seconds(every second person present in the clockwise manner will be eliminated) then people will be eliminated in the following order: 2,4,1, 5 and person with tag 3 will be the winner.

Example 2: If there are 11 people in the beginning of the game, and song duration is 4 seconds then people will be eliminated in following order: 4,8,1,6,11, 7, 3,2,5, 10 and winner will be the person with tag no. 9.

==============================================================================

Dont know why they called it as a medium level problem after that Bitonic problem (Easy level) which ruined a couple of days of my life.. :(

Lets come to the problem, its a very easy problem to solve. A new programmer would face only one problem i.e to start the loop from first position when we reach the end of our sequence.

Here`s the logic :

i) First we declare an array with the number of persons (input1) and fill it with 0.

ii) Then, as the games starts and a person gets out, that position is to be marked as 1. Because while the next round this position needs to be ignored as the person is already out.

ii) Continue till only a single person remains.

The tricky point here is, how to traverse through the loop. The answer to this is, just maintain a flag which is updated only when we encounter a 0 at that position in the array else just move on until flag becomes equal to input2. In case, we reach the end of array, start from 1 again without resetting the flag.

If you have doubts or you want the source code for reference the comment below with your email address.

EDIT: Just learnt to find that this is called as "Josephus Problem" and a recursive solution can be written for it.

Continue

Techgig May contest : Partition problem : Level Easy

Problem Statement

You are given a set of positive integers. your task is to solve partition problem.

Lets define the partition problem.

Partition problem is the task of deciding whether a given multiset of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the elements in S1 equals the sum of the elements in S2.

Example 1:
array[] = {1, 5, 11, 5}
Output: Yes
This array can be divided into to subsets {1, 5, 5} and {11} these two have equal sum.

Example 2: 
array[] = {1, 5, 3}
Output: No
This array cant be divided into two subsets of equal sum.

===============================================================================

The level set was easy but this was really a nice question, took half hour to code it.. :P

Well, Most of us get the answer just by reading the question... "Divide the array such that sum of each partition is equal", but as soon we we try to write the code, out mind keeps wondering "how the hell do I implement this ?"

I thought for some time and then realized that, The worst case of forming the partitions for N element is; One partition of 0 elements and the other of N elements, but this wont help us.

Now lets move forward in the same line. One partition of N-1 elements and the other of 1 element.This is our first step.

This can be easily achieved with a for loop. But, the problem is, there are many different ways for selection 2 partitions each of N-1 and 1 elements respectively. To be precise they are N ways.

First thing to be taken care of is to cover all the N ways. Next, every time the partition should be increase and decrease respectively keeping in mind all the cases.

Here is the code,

#include
#include

char* partition(int input1[])
{
           int i=0,n,total=0,loop,round,s1=0;
           while(input1[i]>-1)
           {
                if(input1[i]==0)return "Invalid";
                total+=input1[i++];
           }
           n=i;
           round=0;
           while(round < N)
           {
                loop=round;
                for(i=0;i<=round-1;i++)
                s1=s1+input1[i];
                while(loop < round)
               {
                   s1=s1+input1[loop];
                   if(s1==(total-s1))return "Yes";
                   s1=s1-input1[loop];
                   loop++;
               }
               s1=0;
               round++;
            }
            return "No";
}

Let me know if you have any doubts.

Continue

Techgig June contest : Disks in a Pile : Level (Easy)

Problem Statement

Rahul is playing a very interesting game. He has N disks ( each of equal radius). 

Every disk has a distinct number out of 1 to N associated with it. Disks are placed one over other in a single pile.

Rahul wants to sort this pile of disk in increasing order from top to bottom. But he has a very very special method of doing this. In a single step he can only choose one disk out of the pile and he can only put it at the top. 

Rahul wants to sort his pile of disks in minimum number of possible steps. So help Rahul in doing so. So don't have to show the actual steps just answer the minimum number of possible steps to sort the pile so that that Rahul can check whether he is doing his work right or wrong

===============================================================================

This was a very easy question, but Some of us found it difficult.

Here goes the explanation,

If you write it down on a paper then you will notice that We first track the highest numbered disk and then just move the disks with the decreasing number on top of it.

For example lets take 3 4 5 1 2  as the numbering. 

Here, since 5 is the highest number I will move only 2 and then 1 on top of it, so the ans comes as 2. 

There are two steps to solve this problem
1) First find the max element. then,
2) Find (P) the number of elements before the max element which are in increasing order. Total-1-P is the ans.

This logic fetches 100 ont Techgig.

If anyone wants the code then just give a comment.

Continue

Techgig July contest : Bitonic Sequence : Level(Easy)

Problem Statement

You are given an array A[] containing n positive integers. Lets define Bitonic subsequence. A subsequence of array A[] is called Bitonic if it is first strictly increasing and then strictly decreasing. Your task is to find the length of largest bitonic subsequence given an array.

Note- A sequence sorted in increasing order is considered as Bitonic with decreasing part as empty. Similarly, A sequence sorted in decreasing order is also considered as bitonic with increasing part as empty

How many of you guys have got the solution for this problem ?

Well, I have got the logic which work perfect but unfortunately It doesn`t fetch 100 on the Techgig compiler. The problem is not with my Code/Loigc but the problem is Techgig`s definition for Bitonic subsequence. Which can be found here

Techgig say that the sequence should be strictly increasing and then decreasing where as it can be either way and that too in circular fashion.

If you refer the previous link we can see that

3 5 8 9 7 4 2 1

5 8 9 7 4 2 1 3

both are bitonic such that 2nd sequence can be converted to first by a circular shift.

Lets, come to the basic question on Techgig and see how to implement a logic for it.

I am considering a sequence for example given below.

9,10,1,3,5,8,2,1,7,5,3,1

Here starts the actual logic :-

As we want an subsequence which is first increasing and then decreasing let find the increasing numbers.

We will be going number by number.

step 1 : Consider 9, It is the first number so directly put it into a list(Array)

             9 (List)

step 2: next is 10, since 10 is greater and 9, put it into same list

            9,10

step 3: 1, since 1 is less than 10 and we are searching for increasing number, we will create a new list

           9,10

           1

           At this point, If we had any numbers less then 1 in the previous list then those needed to be first      i inserted in the new list and then 1. But we didnt have any here

step 4: Once we have more than 1 list, every new number has to be checked with the last number of that list and if the new number is greater then it has to be appended to that list. The next number is 3,first check in the previous list if 3 is greater than the last number if it. In our case we have 10 as the last number so we need not append 3.

Now, 3 is greater than 1, so just append it.

           9,10

           1,3

Repeat the above steps, we get

          9,10

          1,3,5,8

          1,2

          1,7

          1,5

          1,3

          1

These are the various lists which we get. Now we can see here that 2nd list has the largest length. But that wont help us, because it may happen the there is not decreasing subsequence for it or may be some other list has a decreasing sequence of greater length.

Hence, once these lists are formed we perform a similar process for decreasing lists.

The important thing to keep in mind is the position(in input1[]) of last number in our lists.Because, we need to find the decreasing sequence only after that position.

For example, lest take our first list 9,10 and try to find the various decreasing sequences for it.

step 1 :1

step 2: 1

           3

step 3: 1

           3

           5   

step 4: 1

           3

           5

           8

step 5: 1

           3,2

           5,2

           8,2

step 6: 1 

           3,2,1

           5,2,1

           8,2,1

step 7: 1 (Important)

           3,2,1

           5,2,1

           8,2,1

           8,7

step 8: 1 (Important)

           3,2,1

           5,2,1

           8,2,1

           8,7,5,3,1

Now, we can see that for increasing order 9,10; we have a decreasing order 8,7,5,3,1 of length 5, so 5+2=7 is the length of this Bitonic.

Similarly, we can find the decreasing sequences for other lsit`s generated in part I and check the largest length.

           

Hope this was helpful. There may be other logic for the implementation but this was my own from scratch.

Also, this can be modified for the circular sequence.

If anyone want the code for this just put a comment below, and I would share the same.

Continue