Today we start the review of a book : "The road to reinvention  - How to drive disruption and accelerate transformation" by Josh Linkner.  Every now and then we lose the momentum from our previous successes and must find ways to make new Successful companies, brands and individuals regularly reinvent their business strategies. This book lays out a systematic approach to continually challenge and reinvent yourself. Either we bring the change ourselves or get disrupted by it. In this book, we learn why we cannot rest on our laurels, the guiding principles for rejecting the status quo and repeatedly reinventing your organization and career for continued success and inspiring examples of reinvention by people who envisioned their futures and soared over competition.
First let us delve into the disrupt or be disrupted part. Hard skills we earned earlier including manufacturing expertise. strong customer skills and even accounting excellence, are now outsourced or allocated to technology. Creativity is the new most effectively sustainable competitive advantage. Therefore change has to be embraced. The author quotes Rupert Murdoch as saying "Big will not beat small anymore.It will be fast beating the slow." Even after making the first leap towards innovation, we fall short of our goals because we think the reinvention is one time. On the other hand, reinvention is a  life long process.
The next step is to differentiate reinvention from turnaround. They don't mean the same thing. Turnarounds are reactionary and shortsighted. By the time turnaround is necessary, it is often too late.
Both these things indicate that we don't want to get to a stage that needs turnaround. Decay like growth does not move in  a straight line.
To embrace the reinvention ethos, we review its eight principles as outlined in the book.
1. Let go of the past - The past is a great teacher, but its a horrible master. Your own grit and determination will become your safety net.
2. Encourage courage - The best organizations focus on celebrating new ideas, instead of punishing them.
3. Embrace failure - "Even bull's eye is the result of 100 misses." adage applies here.
4. Do the opposite -  Sometimes you have to go against the grain for new experiences
5. Imagine the possibilities -  When we get bogged down in the swamp and fighting the alligator, we miss the bank and the forest. Imagine beyond what's visible.
6. Put yourself out of business - This is a way of getting to a point well before the competition does it to you.
7 Reject limits -  The world is filled with nay sayers. Crush supposed limits and refuse to accept the reflexive no
8 Aim beyond - Whether you are launching a product, opening a fashion boutique, seeking a job, or rebuilding a broken community, your focal point must be ahead of you.
Living these principles will develop your innovative muscles.
A good litmus test to ensure you HOSE the competition by delivering new product or service is
1. High Value: Your new product must deliver exceptional value to your customer.
2. Original : Keep your offering uniquely you so it always stands out.
3. Significant:  Go big by breaking the mold of the past.
4. Emotionally charged : If your product evokes passion, customers will line up to buy,
#codingexercise

Double

GetProductNthAlternatePower (Double [] A,Double  p)


{


If ( A== null) return 0;


Return A.GetProductNthAlternatePower(p);


}

Today we continue our discussion with another problem that appeared in Algorithmic Engagements.
Problem statement:

I own a parcel of a polygonal shape. It has 10 sides and its area equals 23 (that is, it con­tains 23 unit squares). The corners of the parcel are: B2, B5, E5, E4, F4, F8, I8, I3, C3, C2, see figure.

Can you draw a polygon with:

(a)    6 sides and area 6?

(b)   8 sides and area 8?

(c)    10 sides and area 10?

(d)   12 sides and area 12?

(e)   14 sides and area 14?

Or a polygon with 13 sides and area 13? All sides of the polygon must be contained in grid lines. Each two consecutive sides must be perpendicular.

Solution:

 The given answer to all the questions is yes and there are quite a few solutions possible for each.
There is no polygon with 13 sides and area 13. Given that every two consecutive sides are perpendicular, the alternate sides have to be either all horizontal or all vertical.
In order for the polygon to bound, we must have equal number of horizontal and equal number of vertical edges. A polygon cannot be formed on a grid with odd number of edges.

The optimal solution can be described in a top down recursive strategy as follows: 

DrawPolygon(W, I, j, numEdges, ishorizontal, startx, starty, totalEdges) 

If I == startx and j == starty  and numEdges == totalEdges

   Return true

if numEdges > totalEdges
   return false;
for delta = -1 and 1
if isHorizontal:

    if (DrawPolygon(W, I, j+delta, numEdges+1, false, startx, starty, totalEdges))
      return true
else
    if (DrawPolygon(W, I+delta, j, numEdges+1, true, startx, starty, totalEdges))
       return true
return false;
}


#codingexercise
Double
GetSumNthAlternatePower (Double [] A,Double  p)

{

If ( A== null) return 0;

Return A.GetSumNthAlternatePower(p);

}

 

Today we discuss another Olympiad problem on Informatics and mentioned by Radoszewski.
Problem Statement:  this is a problem on track siding with an incoming track A and an exit track B - and two auxiliary tracks 1 and 2.

Track A contains 7 wagons numbered 1 through 7. The wagons arrive on track A  in the following order:

(a)    6, 3, 2, 5, 1, 7, 4

(b)   5, 2, 4, 1, 6, 3, 7

(c)    6, 2, 5, 1, 3, 7, 4

(d)    7, 5, 2, 4, 1, 6, 3

(e)   6, 1, 3, 5, 2, 7, 4

The wagons are to exit via track B in increasing order of numbers 1, ...7. Each wagon is to be moved from track A to one of the tracks 1,2 and then to track B exactly once. There can be arbitrary many wagons on each track at the same time.

Can this task be completed successfully? If so, to which auxiliary track should the subsequent wagons be moved?

(For example, if the initial order of wagons was 5, 2, 6, 4, 1, 3, 7 then the answer would be positive. The wagons could be moved using the auxiliary tracks 1, 1, 2, 2, 1, 1, 1 respectively.)

Solution:  The solutions found by trial and error include:
(a) 1, 2, 2, 1, 1, 2, 1
(b) 1, 2, 1, 1, 2, 1, 1
(c) 1, 2, 1, 1, 1, 2, 1
(d) 1, 1, 2, 1, 1, 2, 1
(e) 1, 1, 2, 1, 1, 2, 1

One of the important things to notice is that at all moments, all wagons on each auxiliary track must be sorted in increasing order from the smallest to the highest number  There is a natural greedy approach to this problem but it doesn't always work. For example, we put the next wagon on the auxiliary track where the first wagon has the smallest number. In the first sequence, we should obtain wagons 1,2,3, and 6 on one auxiliary track and 5 in the other. Then if we move 1,2,3, to B then 7 cannot be moved to either auxiliary track. That is the greedy strategy does not work for all permutations. But we can exhaust the search space. One hint provided with this question is that  the subtasks are constructed in such a way that a solution exists. But do we have an optimal substructure? The subtasks are usually increasing order in either auxiliary tracks that can be moved out to B. However, the order need not be strictly consecutive. And it is better to utilize more and more auxiliary tracks when the subsequences cannot be consecutive or increasing.
Therefore there are really three moves possible for a wagon
Move(wagon):
If a wagon can go directly to B from auxiliary tracks, move it to B
If a wagon can go directly to B from A, put it in auxiliary track 1 and move it to B
If a wagon has to go into one of the auxiliary tracks and not to B then
        pick the one which has a consecutive higher number. (or if its distant by less than half of the total length of initial wagon set - so as to increase the likelihood of encountering a further number that can start a new stack)
        pick the one which is empty
        pick the one which has a higher number

The third step above should be simplified to pick the auxiliary track which has a higher number. The refinement above helps in quicker convergence.
Generally these moves accumulate the wagons on the auxiliary track until the first wagon reaches there.

Backtracking works here because it never considers an invalid option (a wagon moving over a lower numbered wagon on the auxiliary stack) and reduces the number of options from the permutations. We can choose one of the two auxiliary tracks as possible choices. The size of the auxiliary track does not matter so long as the wagons can be put in the order mentioned above. The termination conditions are when the next wagon from A does not have an
auxiliary track to be put in and when the wagons in A have been exhausted. The recurrence is based on the either auxiliary track receiving the wagon or the wagon exiting to make space for a
new wagon from A.

There are alternate solutions possible too such as where we don't check for each move but at the end of a sequence. For example,
we could think of each wagon getting an end result of 1 or 2 as the auxiliary track to use. Hence the entire sequence is a permutation and combination of these two choices. And for each sequence generated we can test whether it is valid or not with some bailing quickly than others. The generation of permutation is discussed earlier in this blog.

 

 

 

This is a problem that appeared in Algorithmic engagements 2007 and discussed by Kubica and Radoszewski 

The problem statement: 

An anti-binary set is a set of integers that does not contain two numbers of the form m and 2m. For example, the set: 

A = {2, 3, 5, 8, 11, 13} 

is anti-binary whereas the set: 

B = {2, 3, 5, 6, 8, 11, 13} 

is not, since both 3 and 6 are its elements. 

What is the largest size of an anti-binary set that is a subset of 

1. {1, … , 11} 

2. {1, … , 12} 

3. {1, … , 13} 

4. {1, … , 14} 

5. {1, … , 15} 

How many different anti-binary subsets of the same size exist? 

The Solution: 

In this case a graph like this helps: 

1 --> 2 -->4-->8 

               3-->6-->12 

                5-->10 

              7 9 11 13 

Where --> denotes an edge when elements are connected by the relation m-->2m 

The elements that don’t connect are mentioned last. 

We can select all of the elements in the last row, one element from the second last row, the first and the last element from the second row and alternate elements from the first row giving us the cardinality of 9. 

More generally, let us say that for a path of size n, the number of anti-binary subsets is An. Then the number of all anti-binary subsets of the given sequence is A1 power 4 times A2 power 1 times A3 power 1 and A4 power 1 by permutations. A1 = 2 and A2  = 3 because we say whether those anti-binary element or its combination is included or not. 

Since the pattern of picking the anti-binary set is that of picking alternate elements in the series m[Symbol]2m, we say that if an anti binary set contains the last element, it does not contain its predecessor.  Hence the number of such sets equals An-2. Given that the last element can be included or not, we establish an optimal substructure as An = An-1 + An-2 

And hence a recursive relation where A1 = 2 and A2 = 3. 

This therefore is the Fibonacci series where An = Fibonacci(n-2) 

int Fibonacci(int n)  {  

if (n <= 0 ) return 0; 

 int value = Fibonacci(n-1) + Fibonacci(n-2);  

return value;  

} 

And we can count all the subsets as follows: 

AllAntiBinarySets(A, n)  

If n == 0   Return 0  

q = 1  

int r = n %2 == 0 ? n: n+1 

For k = I to log(r) 

     If (graph-exists(A,k)) 

            q *=  Fibonacci(k)*numberofGraphs; 

  return q 

 

 

 

  

 

This is a discussion of an Olympiad problem from Kubica and Radozewski: 

Problem statement: 

You are given coins with the values being powers of two. 1,2,4,8,16,32,… and you have exactly one coin of each value. Then you could pay any (positive integer) amount of money using these coins(for example, 45 = 1 + 4 + 8 + 32) 

What is the smallest amount of money, which cannot be paid using the following set of coins: 

1. 6, 3, 2, 10, 21, 46, 1, 48? 

2. 12, 7, 3, 2, 31, 27, 28, 1? 

3. 27, 56, 1, 13, 60, 4, 7, 2? 

4. 44, 39, 5, 1, 9, 1, 18, 2? 

5. 62, 3, 26, 12, 53, 2, 1, 7? 

You have exactly one coin of each kind. 

Solution: 

The first step is to sort the sequence of coins in a non-decreasing order, for the sequence in the first subtask we have: 

1. 1,2,3,6,10,21,46,48 

Using the first two coins we can pay any integer amount from [1,3]. With the first three, we can pay any amount from [1,6] With the first four, we can pay any amount from [1,12] Note that for any amount 1-6 we do not have to use the last coin in the current sequence and for amount higher than that we have to use the last coin. 

In general, if the range of amounts that can be paid using the first k coins is from 0 to r, and the following coin has value x, then either: 

• x <= r+1 and it is possible to pay any amount from 0 to r +x using the first k +1 coins, or 

• x > r + 1 and it is not possible to pay the amount of r + 1, since x and all the following coins have greater values. 

Using this observation, we obtain the following sequence of included coins and ranges of amounts that can be paid: 

Coins                        1    2    3    6    10    21    46    48     

Maximum amount 1   3    6    12  22    43     

The amount 44 cannot be paid. 

The approach here is also dynamic programming although the strategy above uses greedy choice We generate all the subsequences of a given non-empty prefix and divide it into two groups: those containing the last element of the prefix and those not containing it. 

MaxSumUnPaid(Coins, I, j) 

If len(Coins) == 1 

   Return Coins[0]  

m[i,j] = 0  

For k = 0 to j-I-1 

     if (jth coin <= MaxSumUnPaid(Coins Choose K, I,j-1)  

           q =   MaxSumUnPaid(Coins Choose K, I,j-1) + MaxSumUnPaid(Coins with jth coin only, j,j) 

     If q > m[I,j]  

             M[I,j] = q  

  return m[I,j]

This is a discussion of another Olympiad problem on Informatics:

Question:

We are given 11 line segments of the following lengths:

(a)    1, 49, 11, 3, 338, 128, 30, 78, 17, 208, 6

(b)   103, 1, 15, 8, 167, 271, 5, 3, 64, 25, 38

(c)    94, 154, 5, 8, 248, 35, 2, 1, 58, 23, 13

(d)   87, 3, 20, 12, 141, 4, 228, 52, 1, 33, 8

(e)   108, 25, 178, 15, 3, 42, 9, 68, 1, 4, 286

Is it possible to pick three different line segments from the set and use them to obtain a triangle with positive area? If so, which three segments to choose?

Solution: A triangle is formed when we choose segments such that the longest segment is strictly shorter than the total length of the smaller two. Say a + b > c

In each of the above we can pick three segments that suit this condition and can be used to form a triangle and these solutions are:

(a)    30, 49, 78

(b)   15,25,38

(c)    13,23,35

(d)   20,33,52

(e)   42,68,108

Notice if we arrange the lengths of the segments in sorted order, we only have to progress until we meet the criteria above. For example,

(a)    1,3, 6, 11, 17, 30, 49, 78, . . .

We progress picking consecutive three until we pick 30, 49 and 78.

In other words the algorithm for this task involves a greedy strategy. The greedy choice property is justified with the following: we start with three segments in sorted order and show that by increasing the lengths of the smaller two (without exceeding the lengths of the longer one) we limit the available choices and raise the odds of obtaining a solution.

Hence we can write the solution as:

PickThree(Segments, I,j)

SortSegments(Segments)

for k =  I+2 to j

   if Segments[k-1] + Segments[k-2] > Segments[k]

        return Segments[k-2], Segments[k-1], Segments[k]

return null