100. 3n+1 problem

>> শনিবার, ২১ নভেম্বর, ২০০৯


Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.


10055 - Hashmat the Brave Warrior

Hashmat is a brave warrior who with his group of young soldiers moves from one place to another to fight against his opponents. Before fighting he just calculates one thing, the difference between his soldier number and the opponent's soldier number. From this difference he decides whether to fight or not. Hashmat's soldier number is never greater than his opponent.


103 Stacking Boxes

                                   Longest Increasing Subsequence
According to Arefin book
Input: Given a sequence
Output: The longest subsequence of the given sequence such that all values in this
longest  subsequence is strictly increasing/decreasing.
O(N^2) DP solution for LIS problem (this code check for increasing values):

for i = 1 to total-1
  for j = i+1 to total
    if height[j] > height[i] then
      if length[i] + 1 > length[j] then
        length[j] = length[i] + 1
        predecessor[j] = i

Example of LIS
height sequence: 1,6,2,3,5
length initially: [1,1,1,1,1] - because max length is at least 1 rite...
predecessor initially: [nil,nil,nil,nil,nil] - assume no predecessor so far

After first loop of j: 
  length: [1,2,2,2,2], because 6,2,3,5 are all > 1
  predecessor: [nil,1,1,1,1]
After second loop of j: (No change)
  length: [1,2,2,2,2], because 2,3,5 are all < 6
  predecessor: [nil,1,1,1,1]
After third loop:
  length: [1,2,2,3,3], because 3,5 are all > 2
  predecessor: [nil,1,1,3,3]
  After fourth loop:
  length: [1,2,2,3,4], because 5 > 3
  predecessor: [nil,1,1,3,4]


  © Rizoan Toufiq , Copy Right @ 2009

Back to TOP