[cupidvogel]

Hi, I am trying to solve the problem posted at http://www.codechef....roblems/FINDSEQ. I have successfully written a code with this logic, for each index upto the fifth last, starting from 0, a tree is constructed with it as father. Then all the further indices are checked to see whether they will fit in as a next possible index (through the test function and the two nested list comprehensions to filter the children of the parent node). Once a list is found, the first element from the list becomes the parent node, and the process continues. When no such children are found, or if all the children have been tried and tested, the parentage is transferred to the current node's father and so on. Each node has a list (leg) comprising of all the elements of its ancestors plus its own data, so that the moment a length 5 list is attained, that can be returned immediately. I cannot think of a more efficient solution, but obviously there is some, for there have been 16 successful submissions for this code, whereas mine wasn't accepted, stating that the time limit has exceeded. However it is correct, as it gives correct answers for all test cases I test it with. Any suggestion as to how to optimize it?

import re,copy,sys
sys.setrecursionlimit(2**30)
class linklist():
    def __init__(self):
        self.head = None
        self.last = None
        self.size = 0

    def push(self,data):
        if not self.head:
            self.head = tree(data)
            self.last = self.head
        else:
            self.last.next = tree(data)
            self.last.next.prev = self.last
            self.last = self.last.next
        self.size = self.size + 1    

    def __len__(self):
        return self.size

class tree():
    def __init__(self,data):
        self.data = data
        self.children = linklist()
        self.father = None
        self.number = 0
        self.next = None
        self.prev = None
        self.counter = 0
        self.level = 0
        self.c1 = []
        self.c2 = []

    def addchild(self,data):
            self.children.push(data)
            self.children.last.father = self
            self.number += 1
            self.children.last.leg = copy.copy(self.leg)
            self.children.last.leg.append(data)
            self.children.last.level = self.level + 1

    def findchild(self,data):
            curnode = self.children.head
            while True:
                if curnode.data == data:
                    return curnode
                curnode = curnode.next

def test(data):
    global ind,fat
    tmp = copy.copy(fat.leg)
    tmp.append(data)
    t1 = copy.copy(tmp)
    tmp = [main[x] for x in tmp]
    if  ind == sorted(tmp).index(main[data]):
        return True
    return False

def chain(typ):
    global fat,ind
    if typ:
     if len(fat.leg) == 5:
         return fat.leg
     other = [main[x] for x in fat.leg]
     ind = sorted(ref[:fat.level+2]).index(ref[fat.level+1])
     fat.c1=[x for x in range(fat.data+1,leng) if (main[fat.data]-main[x]) \
                *(ref[fat.level]-ref[fat.level+1]) > 0 and main[x] not in other]
     fat.c1 = [x for x in fat.c1 if test(x)]
     if len(fat.c1) > 0:
         fat.addchild(fat.c1[0])
         fat.c2.append(fat.c1[0])
         fat = fat.findchild(fat.c1[0])
         return chain("abracadabra")
     else:
         if not fat.father:
		 return None
	 else:
		 fat = fat.father
		 return chain(None)
    else:
        temp = [x for x in fat.c1 if x not in fat.c2]
        if len(temp) == 0:
            if not fat.father:
                return None
            else:
                fat = fat.father
                return chain(None)
        else:
            fat.c2.append(temp[0])
            fat.addchild(temp[0])
            fat = fat.findchild(temp[0])
            return chain("abracadabra")
            
count = int(raw_input())   
for cc in range(count):
    leng,ref = [int(x) for x in re.findall("""\d+""",raw_input())]
    main =  [int(x) for x in re.findall("""-?\d+""",raw_input())]           
    ref = [int(x)-1 for x in str(ref)]
    ran = leng - 5
    for i in range(ran + 1):
        fat = tree(i)
        fat.leg = [i]
        res = chain("abracdabra")
        if res:
            break
    if res:
     print " ".join([str(x) for x in res])
    else:
     print -1

This post has been edited by cupidvogel: 06 February 2012 - 09:37 AM

[LaughingBelly]

To figure out efficiency problems like these, you have to analyze your algorithm to identify worst case scenarios. With your algorithm, it would take too much time on a sorted input with a permutation like 23451. Your algorithm would repeatedly find good candidates for 2345 and keep failing on 1.

A couple of things to think about:
- Is there any other information from the problem statement that you can use to terminate your search early?
- Is there information that you computed in previous searches that you can apply to terminate your search early?

I am positive that both have positive answers and can be applied to your algorithm. perhaps by trading some space for time complexity.

[cupidvogel]

Well, you have surely seen the question. Can you give answers to either question? I have thought very hard, and haven't got anything...

[LaughingBelly]

I intentionally left the questions unanswered to give you time to think about them.

Here are some more pointers for question 1:
Take example sequence 10 11 12 13 14 15 16 17 18
and permutation 23451

your algorithm selects these sets till it figures out that there is no solution.
(10,11,12,13,?)(10,11,12,14,?)(10,11,12,15,?)...
(10,11,13,14,?)(10,11,13,15,?)(10,11,13,16,?)...
(10,11,14,15,?)(10,11,14,16,?)(10,11,14,17,18)
(10,11,15,16,?)(10,11,15,17,18)
(10,11,15,17,18)
(10,11,16,17,18)
(10,12,13,14,?).... you get the idea.
Notice anything common? we are repeatedly selecting items and comparing them over and over again. lets say we now create two additional arrays that keep track of how many smaller numbers come after a number and how many larger numbers come after a number

smallcount array: 0 0 0 0 0 0 0 0 0 (each number represents the number of smaller numbers that appear after that index)
largecount array: 8 7 6 5 4 3 2 1 0

generate similar arrays for the permutation:
small count: 1 1 1 1 0
large count: 3 2 1 0 0

Now, lets do the same exercise again by using this information:
can we pick 10 as the first number? according to permutation, we need the first choice to have atleast 1 smaller number after it and 3 larger numbers after it. We cannot pick 10 as first number because there are no smaller numbers after it. same goes for all candidates for first choice and we terminate search. Let me know if you need more input understanding this. I imagine there are other things we can do that can aid this further.

Lets consider question 2 now.
consider this example sequence 10 20 14 12 11 10 15 8 13 3 2 12 16
and the permutation 14325
the first sets we compute look like this
(10, 20, 14, 12, ?)(10, 20, 14, 11, ?)(10, 20, 14, 13, ?)...
do you notice anything here? we always fail to pick the last number in the sequence because of number 20. So if we failed to pick a number for the first set because of number 20, would it be prudent to say that we will not be able to pick a number regardless of what numbers we pick for index 3 and 4? so we can eliminate all those sets just by computing the first set. we can move on to the next attempt which is (10, 14, 12, 11, ?) by changing the second number.

Make sense now? Also note that these are not the only things that can provide you short cuts. If you read more about set theory(Discrete Math), you can find more examples on finding subsequences.

This post has been edited by LaughingBelly: 08 February 2012 - 01:14 PM

[cupidvogel]

The first solution was cool. In fact I had thought of something similar before making this tree solution, then rejected it and went right ahead with the one I have provided here. I understand the second one too, though I have no idea how to implement that programatically.