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