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

 

This is a discussion of an Olympiad problem on palindromes in Informatics. 

The problem is stated this way: Some words can be divided into even length palindromes. The word  

aabbaaabbaaa can be divided into 3 even length palindromes.  

aabbaaabbaaa   = aabbaa | abba | aa 

What is the smallest number of even length palindromes in a division of the word: 

(a) aabbaabaabaabbbb? 

(b) aaaaabbaaabbabbabbbb? 

(c) baabbbbaabaabaabbbbb? 

(d) aabbaabaabaabbbbbbbb? 

(e) aaaabbaaabbabbaabbbb? 

Below are the optimal divisions of the words from all subtasks: 

(a) aabbaabaabaabbbb = aa|bbaabaabaabb|bb 

(b) aaaaabbaaabbabbabbbb = aa|aaabbaaa|bbabbabb|bb 

(c) baabbbbaabaabaabbbbb = baab|bbbaabaabaabbb|bb 

(d) aabbaabaabaabbbbbbbb = aa|bbaabaabaabb|bbbbbb 

(e) aaaabbaaabbabbaabbbb = aa|aabbaa|abba|bbaabb|bb 

The given words have the following property: 

If we are looking for prefixes in the given word that are the longest even length palindrome to select as a division, it does not yield the optimal choice 

If we are looking for suffixes in the given word that are the longest even length palindrome to select as a division, it does not yield the optimal choice 

Therefore we cannot apply the greedy strategy. 

Instead we can apply the dynamic programming technique. 

To solve this problem, we apply dynamic programming by following the four-step sequence: 

1.     Characterize the structure of an optimal solution 

2.     Recursively define the value of an optimal solution 

3.     Compute the value of an optimal solution 

4.     Construct an optimal solution from computed information 

In this case we say the optimal structure is as follows: 

The optimal solution for the sequence in the word W (W1,W2,… Wn) is the same as finding the optimal solution of two sub-problems obtained by splitting the range into two involving A1…Ak and Ak+1 .. An and then combining these optimal subproblems. 

In this case we test each partition for the following when combining: 

• Is the left and right division containing only even length palindromes 

The termination condition is when  

• There is a no division and the count at this stage is 0 
• The given word is already an even length palindrome  and the count at this stage is 1 

The progress condition is when palindrome 

• One of the divisions has an even length palindrome 

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

Recursive-Even-Length-Palindrome(W, I, j) 

If I == j 

   Return 0 

If IsEvenLengthPalindrome(W,I,j)  

   Return 1 

m[i,j] = infinity 

For k = I to j-1
     leftcost, leftvalid = Recursive-Even-Length-Palindrome(W,I,k)
     rightcost, rightvalid = Recursive-Even-Length-Palindrome(W, k+1, j) 

     q =  leftcost+rightcost 

     If q < m[I,j] 

             M[I,j] = q 

  return m[I,j], leftvalid && rightvalid 

ISEvenLengthPalindrome(W,I,j) = IsPalindrome(W,I,j) && (j-i+1) %2 == 0 

Also the iterations could be optimized by using incrementing k by 2 to j-2 from i since we only consider even lengths. It will require adjusting the termination conditions.

Today we complete the review of the book "Give and Take". We discussed the two categories within the givers. Today we discuss Chump Change and the Scrooge shift. Negotiations is an area where such roles demonstrated differences very well. Givers are uncomfortable being assertive and advocating their own interests. Takers on the other hand are focused on claiming value and they see then negotiations as zero-sum win-lose contests and didn't trust their opponents. They bargain aggressively overlooking the understanding of their counterpart's interests. The selfless givers made too many concessions. Dutch psychologist Carsten De Dreu showed that successful negotiators are not selfless givers or takers but those that operate in the 'otherish' manner described earlier.
They had high concern for their interests and high concern for their counterpart's interests. They are able to think in more complex ways and expanding the pie. They find win-win solutions that both takers and selfless givers miss.
Successful givers realize their everyday choice shape the results they achieve in competitive confrontational situations. Although they start from trusting others' intentions, they are careful to scan the environment for potential takers, always ready to shift from feeling a takers emotions to analyzing a takers' thoughts and flex from giving unconditionally to a more generous tit for tat. And when they feel inclined to back down, successful givers are prepared to draw reserves of assertiveness from their commitments to the people who matter to them.
A question may be asked that when the world operates as a flea market, could it function on giving instead of matching ? Deron Beal created a website called Freecycle to connect people with goods to people who need them. Although takers and matchers joined it to get something, Beal noticed that they used the same website to give back when they didn't the goods any longer. For example, parents who wanted products for their babies, passed it on after use. People who joined with the intention of taking ended up giving.
Finally the author concludes this discussion of roles and their definitions of success with an acknowledgement that there is a fine line between giving and clever matching that often gets blurred where the reciprocity styles are governed by actions themselves, the motives behind them or some combination of the two. On the one hand even if motives are mixed, helping behaviors often add value to others, increasing the total amount of giving in a social system. Because efforts that are not authentic have their own peril, would-be matchers are best served by giving in ways that they find enjoyable to recipients whose well being matters to them. This way matchers will operate in a givers mindset, leading their motives to appear and become more pure.

Today we continue reviewing the book Give and Take by Adam Grant. We talked about how givers, takers and matchers differ in their abilities to influence people. On the two paths of dominance and prestige, takers specialize in powerful communication to establish dominance. They send powerful verbal and non-verbal signals. As  a result, takers tend to be more effective than givers in gaining dominance.But is that the most sustainable path to influence ? The opposite of this style is called powerless communication. Powerless communicators tend to speak less assertively, expressing plenty of doubt and relying heavily on advice of others. They signal vulnerability, revealing their weaknesses and making use of disclaimers, hedges and hesitations. By using powerless communication they build up prestige and they do so in four domains of influence. presenting, selling, persuading and negotiating. Because they value the perspective and interests of others, they are more inclined towards listening rather than imposing their views.
The value of vulnerability is evident form Pratfall effect. In a taped recording of two students - one a expert and another an average in auditioning for a Quiz Bowl team, the audience liked the expert over the average but when both of them make a gaffe such as spilling coffee on their new suit, the audience liked the average candidate even less and the better candidate even more. This vulnerability made the expert more human and approachable.
Givers tend to demonstrate this better than takers who are more assertive. In an interview for an opportunity to lead multiple business units, a marketing manager answered the opening question to enumerate his successes in a less assertive manner often extolling his team. Although he was the front runner, he did not get the job. At the same time, he earned prestige and his team became more successful than earlier.
We now discuss why givers are at a higher risk of burn out than others. Givers climb up based on their unique style of building networks, collaboration, communication, influence and helping others achieve their potential.  They end up making sacrifices for their collaborators. Adam says that success is not only about capitalizing on the strengths of giving but also avoiding pitfalls Too much giving is too much expense of energy and consequently the givers are at a higher risk of exhaustion and productivity loss leading them to the bottom of the chain.  Based on this Adam separates the givers into two categories - the pathological givers which he calls the selfless givers due to their unhealthy focus on others and the otherish givers which he refers to as those who are mostly givers but still holding to some of their interests. In this latter group, there is more balance between concern for others and for self as opposed to that in the former group and they are better positioned to flourish.
#codingexercise
double Pow(int x, int y)
{
  double res = 1.0;
  if y == 0 return res;
  for (int i =0; i< Math.Abs(y); i++)
      res = res * x;
   if (y > 0){
       return res;
   } else{
       return (1/res);
   }
}