USAMO-2004

Alice and Bob play a game on a 6 x 6 grid. On his or her turn, a player chooses a rational number not yet appearing in the grid and writes it in an empty square of the grid. Alice goes first and then the players alternate. When all of the squares have numbers written in them, in each row, the square with the greatest number in that row is colored black. Alice wins if she can then draw a path from the top of the grid to the bottom of the grid that stays in the black squares, and Bob wins if she can’t.(A path is a sequence of squares such that any two consecutive squares in the path share a vertex). Find, with proof, a winning strategy for one of the players.

The intuition here is that any path from top to bottom can be broken with a diagonal that does not comprise of black squares. Since there are only two such diagonals and they are symmetric, the winning strategy is simply the one that can maintain a diagonal of non-black squares. To form such a diagonal the opponent must be forced into the adjacent corners from each diagonal tip. In other words the black squares occupy the vicinity of two corners opposite from each other without meeting in the center where the diagonal of non-black runs through. How does Bob force the opponent into these two corners and maintain his winning strategy ? For any given row, Alice can either choose a small number in which case it cannot be a black or a big number in which case it will be a black. Since Alice is picking a square with her number, we can choose the opposite -  a big number for her small or a small number for her big forcing her number or ours to be a black and determining the position of the black in the row. Given that we already have mapped where the blacks should fall, we can play this kind of moves for all rows, thereby clustering the blacks around two corners without meeting each other in the center where the diagonal runs through.

Let us try a different problem now.
Saint Petersburg 1997 The number N is the product of k different primes (k ≥ 3). A and B take turns writing composite divisors of N on a board, according to the following rules. One may not write N. Also, there may never appear two coprime numbers or two numbers, one of which divides the other. The first player unable to move loses. If A starts,who has the winning strategy?
Solution: since we want to determine the win, we only have to split the number N into two prime factors p and q and write down pq.  This way we can reserve one move at the end for the person starting the game which is A. Then as the other player writes a number qm, A can write qn in a move that copies the attempt of B. Finally A has one move left.

We continue discussing Olympiad problems and their solutions.
A natural number is written in each square of an m x n chessboard. The allowed move is to add an integer k to each of the two adjacent numbers in such a way that non-negative numbers are obtained (two squares are adjacent if they share a common side). Find a necessary and sufficient condition for it to be possible for all numbers to be zero after finitely many operations.

The chessboard happens to be black and white alternatively with equal numbers of black and white. If we pick adjacent numbers one will be on a black square and another will be on a white square. Since we add equally at each step, the sum of the numbers on the black square must be the same as the sum of the numbers on white square at any point of time! - at the beginning, at the end  and every step of the progressive conversion to zero in between the beginning and the end.
But how do we pick these adjacent squares ? For the progression, the choice of squares don't matter because any two adjacent squares we pick we should be able to make them both zero and if we don't revisit the squares we have made zero, we can progress towards the end. If we can make two adjacent squares in a row zero in each step, then we can repeat this for all the rows while leaving only the last two in each row. Then we can descend down the last two columns a row at a time, thus sweeping the chessboard without revisiting the squares. By symmetry of a chessboard, the same can be done by sweeping columns at a time until the last two rows and then sweeping the last two rows.
Having discussed the way to progress without revisiting the squares converted to zero, let us now look at how to convert each pair of adjacent squares. Let us call the two adjacent squares in a row a and b. If a < b then we can add -a to both and make one zero. if a > b and b is adjacent to c, then we can add a-b to both b and c . b becomes a at this point and both a and b can become zero by adding -a. Thus we convert one square or both squares to zero. Since a-b is a positive number and the numbers on the chess board were natural numbers to begin with, we don't diminish the squares we have not covered and we progress towards the goal.

#codingexercise
Node GetSecondLargestInBST ( node root){
Node largest = GetRightmost (root);
Return  GetPredecessor(largest);
}

Olympiad Question [ Russia 2005, Indian TST 2012, France 2006]: 

In a 2 x n array, we have positive reals such that the sum of the numbers in each of the n columns is 1. Show that we can select one number in each column such that the sum of the selected numbers in each row is at most (n+1)/4 

In this problem each column consists of a pair of numbers that total to 1.0   The sum (n+1)/4 can be violated easily when  we pick the higher fractions in each column. Therefore, one strategy could be to pick the smallest numbers in each column. Unfortunately that also breaks the limit of (n+1)/4 in some cases such as for instance when the smaller fractions are all 0.4 and appear in the top row. Let the numbers in the top row be sorted in non-decreasing order as a1,a2, … an with their bottom counterparts as b1, b2, .. bn. The sum of the top row is assumed to be smaller or equal to that of the bottom row. 

One algorithm suggested by the book Olympiad Combinatorics is as follows: Starting from a1, keep choosing the smallest remaining element in the top row as long as possible. In other words, select a1, a2, …ak,  such that a1 + a2 + … + ak  <= (n+1)/4 but a1 + a2 + … + ak  + ak+1 > (n+1)/4. Now we cannot select any more from the top row. And so from the bottom row we choose the remaining elements.  All that is left to prove at this point is that the sum of the chosen elements in the bottom row is at most (n+1) /4 . 

The k+1 th element in the top row in the top row is at least the average of the k+1 elements including itself which is  more than (n+1)/4(k+1) . 

Therefore the bottom element for k+1th column has to be 1- ak+1  = 1 – (n+1)/4(k+1) but bk+1 is the largest of the chosen elements  in the bottom row (because we sorted the upper row in ascending order, the bottom row is in decreasing order and the first element we  picked is this one. So the sum of the chosen elements in the bottom row cannot exceed  b at k+1 times (n-k).  which if we simplify and substitute from the value above we get : 

                (1 – (n+1)/4(k+1)  ) (n-k)  

        =   (n – k – (n+1)(n-k)/4(k+1)) 

        =  ((n+1)/4) (4(n-k)/(n+1) – (n+1)(n-k)/4(k+1)) 

          <= (n+1)/4  

In a graph G with V vertices and E edges, show that there exists an induced subgraph H with each vertex having degree at least E/V. In other words, a graph with average degree d has an induced subgraph with minimum degree at least d/2. 

The degree of a graph is the number of edges incident to the vertex with loops being counted twice. The total degree for all the vertex therefore adds up to twice the number of edges because the same undirected edge counts twice for both the vertices. Therefore the average degree of a vertex is 2.E/V 

To get a subgraph with degree at least E/V, we start with the graph G and start deleting vertices with degree < E/V. In other words, we try to get rid of bad vertices. However in the process of doing so, we are also eliminating edges and vertices that were once good on the basis of their degree might now become bad. This is quite ok as long as there is at least one vertex left. In this case we satisfy the problem’s condition. However what happens if there are no vertex left. Fortunately such a possibility does not exist because the ratio of edges to vertices is strictly increasing on every delete. It starts at E/V and each time we deleted a vertex, less that E/V edges were deleted by the condition of our algorithm. Hence it is impossible to reach a stage when only 1 vertex is remaining, since in this case the edges to vertices ratio is 0. Since there will at least be more than one vertex, where each of them have a degree at lease E/V, we are guaranteed that the number of deletes is bounded and a valid solution will remain at that point. 

A set of three non-negative integers {x,y,z}  with x < y < z satisfying {z-y, y-x} = {1776, 2001} is called a historic set. Show that the set of all non-negative integers can be written as a disjoint union of historic sets.

We can rewrite the historic set of the form {x, x+a, x+a+b} where a and b are interchangeable and therefore lead to 'small' and 'big' sets. We use the integers from the number line because it is sorted.
Every number must be covered but no number must be covered twice. We use the following guidelines:
1: The smallest number not yet covered is the most "unsafe". We should choose x as the smallest "unsafe" number
2: Since we prefer small numbers, we should prefer "small" sets to "big" sets.
Now we can prove by contradiction where we suppose it fails and show that it doesn't.

Let us suppose the algorithm to pick the smallest number not yet covered and the subsequent step to pick the ‘small’ set first or the big set fails when we are in iteration n+1. At this time, the value of (Xn+1) + a + b will not be covered because it is greater than all the covered numbers. So Xn+1 + a or Xn+1 +b must have been covered which is why the process is failing. Further Xn+1 + a  is smaller than Xn+1 +b so the latter must be the largest number in the set and the smallest number in the set would be Xn+1+b-(a+b) = Xn+1-a  but at this stage the small set should have been used and xn+1 should have been in that set which is  a contradiction.

 we discuss a few Olympiad Combinatorics problems from the chapters of the book by the same title.  

In a graph G with n vertices, no vertex has a degree greater than delta. Show that one can color the vertices using at most delta + 1 colors, such that no two neighboring vertices are the same color. 

History: As with most graph coloring problems, the chromatic number of a graph refers to the smallest number of colors for which a coloring of the vertices exists such that adjacent vertices receive different colors. In addition, we are reminded of the four color theorem which states that every planar map can be colored with four colors such that adjacent countries receive different colors. Laszlo Lovasz is accredited with bringing this graph theory to the forefront by introducing a complex geometry to a graph in such a way that the topology of the complex provides some information about the chromatic number of the graph. 

Problem understanding : The degree of a graph is the number of edges incident to the vertex, with loops counted twice. A regular graph is one where each vertex has the same number of neighbors i.e. every vertex has the same degree. In this problem we arrange the colors as 1,2,3… and use a greedy algorithm as follows. 

We arrange the vertices in an arbitrary order and color the first vertex with color 1. Then in each stage, we take the next vertex in the order and color it with the smallest color that has not yet been used on any of its neighbours. The greedy choice makes sure we are using the smallest number for the colors. Since any vertex cannot have more than delta neighbors  and the greedy choice is picking a color different from the node, we are guaranteeing the following two properties: 

1. No two adjacent vertices will have the same colors 

2. At most delta + 1 colors are used. 

The latter property follows from the fact that when a vertex v is colored different from the delta neighbors, there will be one color in the delta + 1 set that has not been used. Since the minimum of such colors is used for the vertex v, all the vertices are colored using colors in the set {1,2,3,…. Delta + 1} 

By saving the larger number colors when we really need them, we are using the colors from the smallest numbers and therefore they are bounded by the set 1,2,3, … delta + 1. 

The greedy choice property solves this problem while proving that the delta + 1 color suffices. 

void ChromaticColoring (Node vertex, int[] colors ) 

{ 

     If (vertex != null) 

    { 

        usedColors = [] 

foreach (Node v in vertex.adjacents()) 

{ 

   if (v.color != UNKNOWN) 

     usedColors.Add(v.Color); 

} 

Sort(usedColors); 

Var availableColors = Colors.except(usedColors); 

vertex.color = availableColors.min(); 

Foreach (Node v in vertex.adjacents()) 

{ 

ChromaticColoring(v, colors); 

} 

 } 

} 

Today we continue reviewing the book Rainmaking Conversations.

RAIN making conversations follows a process, beginning with helping us take stock of our readiness to succeed in a sales role, planning your actions and helping us build skills and knowledge, and providing a process for our rainmaking conversations.

In the conversation readiness stage of the RAIN making conversations roadmap, we begin by defining what success readiness is. This and goal setting affect each other.  Goal setting determines the sales knowledge we need. Consequently sales knowledge leads to success readiness. Between these three stages, we articulate our objectives in a way that we can start planning actions. Therefore Action Planning follows goal setting.  Action Planning leads to both Conversation Planning and Conversation Generation.  Conversation planning also affects conversation generation.

When the conversations are planned and generated we can transition from RAMP stage to RAIN stage where the first step is to build a rapport. Armed with the readiness and conversation planning, we proceed to building the rapport with our customer. Throughout our engagement from rapport to commitment, we maintain the influence and trust.  The authors developed the Rainmaking Conversations to provide a framework, a road map and a learning process to those who want to become rainmakers. To realize this, we should take the following ten principles to heart: 1. Play to win-win  : satisfy the best interests of both the prospects and clients as well as ourselves. The play-to-win part is never lost though.
2. Live by goals - Rainmakers are goal-setting and goal-following fanatics. Goals are their part of daily rituals.
3. Take action - Rainmakers realize the goal without actions don't get us very far. Rainmakers do it.
4. Think buying first, selling second - The selling processes is mapped to the customer's processes and psychology of buying.
5. Be a fluent expert  - Rainmakers are masters of the market knowledge, customer needs and their products and services, their value, their competition and everything else they need to know to succeed at selling.
6. Create new customers every day. Rainmakers never coast. They do not let a single day go by without speaking to customers, prospects, and referral sources, with the intent to source new business.
7. Lead masterful rainmaking conversations - Rainmakers lead the conversations through prospecting, discovery, closing and account management.
8. Set the agenda, be a change agent - Rainmakers recommend, advise and assist.  They are change agents who are not afraid to push when it benefits the customer.
9. Be brave - Rainmakers rise to the occasion in sales no matter how difficult the challenges may be. 10. Assess yourself, get feedback and improve continuously - Rainmakers are never afraid to learn the cold hard truth about themselves. They take what they discover - the good and the bad - to learn grow and change for the better. They never stop their cycle.

Today we review a book named Rainmaking Conversations by Mike Schultz and John Doerr. This book is about dialogs that rise about the noise and create engagements. Its a sales book and it teaches the skills, knowledge and processes to excel at winning new business. In this book we get to see that anybody can be a rainmaker with hard work, preparation and proven methods.
RAIN, RASP and the ten rainmaker principles form the core of the RAIN Selling method - the training and the development program that the author's RAIN group use to help create dramatic improvements in sales.
RAIN is an acronym for Rapport, Aspirations and Afflictions, Impact and New Reality. These concepts are the core concepts we use to lead a rainmaking conversation. RAIN is about the things we do between the first meeting where we build rapport to the time when we gain commitment. During this process start finding the gaps that get bigger and bigger between the impact of success and failure and start closing on them to the point where we win commitment. This process is elaborate and we discover more about it in this book. During the discovery of this increasing gaps, we find the initial value gap at the point when we help articulate aspirations and afflictions. The high point in gap occurs when we find the true value gap. At this point, we fully realize the gap between the impact of success and failure.  Then we start altering the new reality to craft a solution that closes the gap.
There are essentially six types of rainmaking conversations.
1. Conversations with anybody - where we begin new relationships, enhance current ones and answer questions like "what do you do "?
2. Prospecting conversations - where we create a conversation that will eventually lead you to sale.
3. Core sale conversations - where we lead each sales call from the first sale to the close.
4. Presentations and product demonstrations - where we deliver key messages and content, share specifics about products and service capabilities.
5. Winning the deal - where we close the sale stage of the process - and open the customer stage
6. Account management and expansion - when we work to service, resell, cross sell, and up sell our current clients.
RASP is about the four keys to rainmaking success.
Companies and individuals  that achieve significantly higher sales results than the rest focus of four areas: Role readiness, action, skills and knowledge, and process (RASP). This is what the best do. The authors note that too often the sales methods focus on sale process and skills, but rarely on readiness, action or knowledge.  The author says this is backward because:
Role readiness:  the degree to which a person is fundamentally prepared to succeed in sales.
Action:  the execution of activities that will lead to sales.
Skills and knowledge: Skills - the various abilities needed to sell, and a degree to which a person can perform them well. Knowledge - the grasp of information needed for selling and the ability to discuss relevant information and topics fluently.
Process: A system or framework in which to perform actions to achieve the best possible sales results.
In short, there is a ton of effort in conversation readiness before the rainmaking conversation that helps to build influence and trust from rapport to commitment.

#coding exercise
Explain sister delegation
public class root { virtual void foo(); }
public class sibling1 { void bar() { foo();}}
public class sibling2 {void foo() { std::cout << "here"; }}

 

#codingexercise
Generate n numbers in ascending orders which are having given k factors.
For example, if we are given {2,3,4,7}
The numbers generated would be 2,3,4,6,7,8,9,10...
Let us assume that there are no duplicates in the number.

# http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF

n = 15

bases = [2, 3, 4, 7]

nums = [1] * n

candidates_indexes = [0 for _ in bases]

candidates = [base for base in bases]

for i in range(1, n):

    nextn = min(candidates)

    nums[i] = nextn

    for index, val in enumerate(candidates):

        if val == nextn:

            candidates_indexes[index] += 1

            candidates[index] = bases[index] * nums[candidates_indexes[index]]

print(nums)
Start:
candidates=[]

candidate_indexes []
nums[2]

From Stackoverflow
The original design talked about prime factors. Here we have liberally used non primes.