BASE - SPOJ SOLUTION :-

     This one may be the easy one after the life, universe, everything in the spoj. This one is my 101th classical problem in spoj. In the midst of too much of personal confusions on this night I did this one and got AC in one go which really suppressed all those feelings a bit. Yeah I'm addicted to that green (accepted) you know.

Problem Statement :

         Go go...it's there in spoj's problems archive. I just redirect you there.

          Click HERE to get REDIRECTED

Constraints :

      You just need to take care of reading the input. Yeah the numbers given may contain alphabets too...

         

         Don't make this simple problem too tough by assuming anything that is not given in the problem statement. Alphabets only contains Uppercase letters and not any lowercase or other symbols.

         This section doesn't deserve this name,yeah I know but take some moment to read this to prevent yourself from some WA's...

TAKE CARE OF THIS...!!!   

• It will have a 7-digital display.
• Its buttons will include the capital letters A through F in addition to the digits 0 through 9.
• It will support bases 2 through 16.

Hint :

        All you need to do is to convert the given number to some intermediate base. Be wise,while choosing this one. Your intermediate base must act faster than the other one's. I have chosen 10 and yeah it did it's job quite well and passed my python code in 0.00s. Do the rest conversion with this base 10 number converted from the given base.

       Check if the result is greater than 7 in length. Since it is 7-digit display,How can we expect it to hold a number greater than length 7.So just print "Error" to the stdout in this case.

       Right justify your output to 7 places.Yeah really this rjust() function in python helped a lot with formatting.

Source Code : IDEONE

""" AUTHOR :  PVKCSE

    STUDENT AT  :  ACCET,KKDI

    TASK        :  BASE - SPOJ """

import sys

symbol_table=[i.upper() for i in "abcdefg"]

for line in sys.stdin :

    a = line.strip().split()

    num = a[0]

    base_from = int(a[1])

    base_to = int(a[2])

    num_10 = 0

    prog = 1

    inc = 0

    for i in reversed(num) :

        if ord(i) >=65 :

            i = (ord(i) - 65)+10

        num_10+=((int(i))*(base_from**inc))

        inc +=1

    result = ""

    if base_to != 10 :

        while num_10 > 0 :

            temp=(num_10%base_to)

            if temp >= 10 :

                result+=symbol_table[temp-10]

            else :

                result+=str(temp)

            num_10/=base_to

        ans=""

        for i in reversed(result) :

            ans+=i

        result = ans

    else :

        result+=str(num_10)

    if len(result) > 7 :

        result = "ERROR"

    print str(result).rjust(7)

NOTE : IF YOU HAVE ANY PROBLEM IN UNDERSTANDING THE CODE, JUST VISIT AND HAVE SOME TOUCH WITH THE COMMENT BOX.THANKS FOR READING...!!!

Read More

USING LISTS IN DICTIONARY :-

Problem :

          Confusing, yes it will confuse you.Actually if you want to hold a list in the key of a dictionary,what would you do.problem seems quite interesting na. Actually it's not. Yeah just adding a line in your source will resolve this issue.

Explanation :

      Usually python dictionaries allows you to store key value pairs. You can't store a list in the corresponding key if you use the normal dictionary. It will raise an exception. So just add a line in your source.what's that line...???

      It's simple.Are you aware of the defaultdict subclass of the dict type...???If not,just know it here.Everything about defaultdict is clear now,let's hope it is.We can utilize this one to make the dictionaries to hold the list. just add defaultdict(list) and everything is set now.just use it in the program like below.

SOURCE CODE :  IDEONE

__AUTHOR__     = "pvkcse"

__STUDENTAT__  = "Accet,Kkdi"

__ALGO__       = "Counting Sort"

try:

    from collections import defaultdict

    import sys

except ImportError :

    sys.stderr.write("Error In Importing The Modules...\n")

    pass

def __sort(lists,key=lambda x : int(x)) :

    answer,freq_list=[],defaultdict(list)

    for i in lists :

        freq_list[key(i)].append(i)

    for i in range(min(freq_list),max(freq_list)+1) :

        answer.extend(freq_list[i])

    return answer

def main(*args,**kwargs) :

    try :

        lists=list(map(int,sys.stdin.readline().split(' ')))

    except ValueError:

        sys.stderr.write("Enter valid number...\n")

    try :

        print " ".join(str(__sort(lists)[i]) for i in range(len(lists)))

    except :

        sys.stderr.write("Error in writing the data...\n")

if __name__ == "__main__" :

    main()

This is the simple program for implementing the counting sort in python.

If you find anything wrong in the implementation,then just notify it in the comment box .

Read More

ArraySub SPOJ Solution :

Problem Statement :

                      No need to write it here. Instead I'll provide the link.

         

           URL : ArraySub - SPOJ

Constraints :

        n < 10^6

        1 <= k <= n

        0 < ai < 10^6 (Don't assume -ve numbers are there)

IMPLEMENTAION :

        It's easy from the problem to understand that if we use the segmentation trees, the queries can be answered efficiently. Yes there is only a slight modification in the problem statement. It asks you for the contiguous subarray maximum values of length k. If you implement this efficiently, then you will get it accepted in the first attempt itself. 

       All you need to do is to update the internal nodes with the maximum value of their leaf nodes. Usually in a segmentation tree, data are stored in the leaf nodes and their internal nodes are updated according to what the problem asks.

       As usual sticking to the python,this is implemented...

Source Code : IDEONE

       

import sys

sys.setrecursionlimit(10**9+7)

Seg_Tree=[0]*4000010

def Construct_Tree(index,left,right,lists) :

    if left == right :

        Seg_Tree[index] = lists[left-1]

    else :

        Construct_Tree(2*(index),left,(left+right)//2,lists)

        Construct_Tree(2*(index)+1,(left+right)//2+1,right,lists)

        Seg_Tree[index] = max(Seg_Tree[index*2],Seg_Tree[(index*2)+1])

def Answer_Queries(pos,left,right,low,high) :

    if low > right or high < left :

        return False

    elif low <= left and high >= right :

        return Seg_Tree[pos]

    else :

        return max(Answer_Queries(2*pos,left,(left+right)//2,low,high),Answer_Queries((2*pos)+1,(left+right)//2+1,right,low,high))

def main(*args,**kwargs) :

    n = input()

    lists = list(map(int,sys.stdin.readline().split()))

    k = input()

    Construct_Tree(1,1,n,lists)

    i,answer=1,[]

    while n >= i+k-1 :

        answer.append(Answer_Queries(1,1,n,i,i+k-1))

        i+=1

    print " ".join(str(i) for i in answer)

if __name__ == "__main__" :

    main()

That's it. Yes it looks pretty simple but be careful about the input/output. Output contains space between the each numbers.And also be careful in allocating the space for seg_tree.Yes,It costed me several RE in Spoj and still struggling to get out of it though my algo is correct.

If you find any mistake in the implementation,just note it down in the Comment box...HAPPY CODING =D =D =D.

Read More

Generating the sub-sets of a string in python :

                          If you are searching for a program to generate all the sub sets of a string in python, this one could be the place where you have to end up your searching process.Yes this post is all about generating all the sub-sets of a string in python.

What is  a sub set of a string...???

                   You are in the situation that you need to consider all the subsets. What are you going to do.I noticed my friend doing a code which looks like this. He ran two for loops and then generated some strings out of the original string.This is what the origin for this post.

           consider "abc" is your string then the subsets of this string are...[](CONFUSING...Yes,refresh your set theory knowledge...empty set is also a subset of a string),[a],[b],[c],[ab],[bc],[ca],[abc]...consider Bi is a subset of A then the elements in the subset Bi should belong to the set A.

           if 'N' is a length of your SET then the total number of subsets possible is given by the relation...

              Tot. No. of SubSets = 2**n

I Think there is no need to explain the algorithm since it is very simple for you to understand it from the program...

CODE IN "PYTHON"   :

                       def Set(s):

              n = len(s)

              masks = [1<<j for j in xrange(n)]

              for i in xrange(2**n):

                  yield [s[j] for j in range(n) if (masks[j] & i)]

That's it you are now with your subsets...all you need to do is to use this function like below...

                      lists=[]

           for i in Set(s) :

              lists.append(i)

Yes that's it...now go and code your own....

FOR MORE ON THIS TOPIC GO HERE :

                     For Understanding the concept deeply....

                     For implementation in c...

NOTE : Wait...if you have any doubt on any topic related to python...just have some touch with the comment box of the post...!!!

Read More

Binary Search Tree in Python  :

            Implementing the binary search tree in python looks hard job at the first sight if you are trying to transform your implementation from c/c++. Actually it is not, you can do it in an easy way.

What is Binary Search Tree :

                       Hope you are well-verse with the binary tree concepts.It's okay, just refresh it again here.THANKS for coming back again. Hope you gathered/refreshed the complete(somewhat) knowledge on binary search trees.Now we can proceed further. 

What's there in this article... ?

         Yes,I'm going to through some light on implementing the binary search tree in python. here you can get the implementation for insert, search and Traversal functions. Delete is in another article. Go for it as it's an interesting topic that i thought it must be discussed in a separate post.

A Sort Intro about My Implementation :

         Here I am going to use Node of a tree as an object . yes it is an object looks like this.
         class Node :
             def __ init__(self,data) :
                 self.data=data
                 self.left=None   #LeftChild - Initially None
                 self.right=None  #RightChild - Initially None
Now we just made the new node of our tree(consider).

Insertion is Easy as you think now... Yeah the procedure is as same as what we do in c/c++ but in python style.Decide where to insert the new node whether in the left or right. Once decided check if that node is None or not.If it is then just create a new object of the type Node class and assign the data.If not just make a recursive call with that node(usually SubTree).It looks something like this...
         def insert(self,data) : 
            if data < self.data :
                if self.left is None :
                    self.left=Node(data)
                else :
                    self.left.insert(data)
            elif data > self.data :
                if self.right is None :
                    self.right=Node(data)
                else :
                    self.right.insert(data)
Yes you are right, we just built a tree now. Tree Traversals are the easiest procedures to implement with recursion.I don't want to elaborate more on this topics.You just take a look at the code...
        def InOrder(self) :
            if self.left is not None :
                self.left.InOrder()
            sys.stdout.write(str(self.data)+" ")
            if not self.right is None :
                self.right.InOrder()
This is for preorder traversal of a tree...
       def PreOrder(self) :
           sys.stdout.write(str(self.data)+" ")
           if self.left is not None :
               self.left.PostOrder()
           if self.right is not None :
               self,right.PostOrder()
Please do the post order traversal yourself...
Now We just need to implement the search procedure,a hero of BST...It is so simple with recursion...I don't want to elaborate procedure as you already know how it has to be done. so please take a look at the code here...
       def Search_BST(self,data) :
           if self.data is data :
               return True
           elif self.data > data :
               if self.left is not None :
                   return self.left.Search_BST(data)
               else :
                   return False
           elif self.data < data :
               if self.right is not None :
                   return self.right.Search_BST(data)
               else :
                   return False
           else :
               return False

Yup,You did it,You just learnt implementing BST in python what you thought somewhat hard one with python.Also get the complete source here...
import sys
from collections import defaultdict

class Node :
    def __init__ (self,data) :
        self.data=data
        self.left=None
        self.right=None

    def insert(self,data) :
       if data < self.data :
            if self.left is None :
               self.left=Node(data)
            else :
                self.left.insert(data)
       elif data > self.data :
            if self.right is None :
                self.right=Node(data)
            else :
                self.right.insert(data)
                
    def InOrder(self) :
        if self.left is not None :
            self.left.InOrder()
        sys.stdout.write(str(self.data)+" ")
        if not self.right is None :
            self.right.InOrder()

    def PostOrder(self) :
        if self.left is not None :
            self.left.PostOrder()
        if self.right is not None :
            self.right.PostOrder()
        sys.stdout.write(str(self.data)+" ")

    def PreOrder(self) :
        sys.stdout.write(str(self.data)+" ")
        if self.left is not None :
            self.left.PostOrder()
        if self.right is not None :
            self.right.PostOrder()

    def Search_BST(self,data) :
        if self.data is data :
            return True
        elif self.data > data :
            if self.left is not None :
                return self.left.Search_BST(data)
            else :
                return False
        elif self.data < data :
            if self.right is not None :
                return self.right.Search_BST(data)
            else :
                return False
        else :
            return False

print "Building BST..."
for __ in range(input()) :
    if __ is 0 :
        root=Node(input())
    else :
        root.insert(input())
print "Build Completed..."
print "InOrder Traversal.."
root.InOrder()
print
print "PreOrder Traversal..."
root.PreOrder()
print
print "PostOrder Traversal..."
root.PostOrder()
print
print "Searching Starts...\nEnter the no. of elements to search..."
for __ in range(input()) :
    if root.Search_BST(input()) :
        print "YEAH...Data Found"
    else :
        print "OOPS...Data is Not There"
print "Thanks For Reading My Post.Hope you got something Here...!!!"

 I am writing this only to those who feel implementing BST in python is harder.If you are an expert in python, thanks for showing such a great silence in going through this article. If you are the one for whom i'm writing this post, Comment Box is waiting for you...Just go there and post your comments...HAPPY CODING...!!! 

NOTE  : PLEASE GO THROUGH THIS TO GET IDEA AND IMPLEMENT THE SAME ON YOUR OWN.COPY AND PASTE IS EASY BUT NOT WORTHY. IF YOU ARE HAVING TROUBLE IN IMPLEMENTING OTHER BST FUNCTIONS(OTHER THAN THOSE WHICH ARE NOT PUBLISHED HERE)PLEASE COMMENT IT OUT.

y
We

       

Read More