Rom/Column Inversion

You are given a matrix m*n (need not be square) of positive/negative integers. The only operations permitted are you invert the signs of an entire row or an entire column. And that is counted as one step. The goal is the to reach the maximum sum possible (of all elements) of the matrix with such a series of operations. 

Q. Does the process converge. If yes, then what is the complexity ?

Clue: When would you do such an operation ? And when you do that what happens to the total sum? What is the max sum which can be reached. 

Locker

Imagine you are at a school that still has student lockers. There are 1000 lockers, all shut and unlocked, and 1000 students.

Here's the problem:

1. Suppose the first student goes along the row and opens every locker.
2. The second student then goes along and shuts every other locker beginning with number 2.
3. The third student changes the state of every third locker beginning with number 3. (If the locker is open the student shuts it, and if the locker is closed the student opens it.)
4. The fourth student changes the state of every fourth locker beginning with number 4. Imagine that this continues until the thousand students have followed the pattern with the thousand lockers. At the end, which lockers will be open and which will be closed? Why?

Try the problem for n=10,20 and observe the results.

Hint / Spoiler : http://www.math.msu.edu/~nathsinc/java/Lockers/

A related problem to prove the solution to the one above

How many perfect square factors does the number 46,656 have?

Horses on Induction

Theorem. All horses are the same color.

Proof. Induct on the number of horses. Base case: 1 horse. Clearly with just 1 horse, all horses have the same color.

Now, for the inductive step: let's show that if it is true for any group of N horses, that all have the same color, then it is true for any group of N+1 horses.

Well, given any set of N+1 horses, if you exclude the last horse, you get a set of N horses. By the inductive step these N horses all have the same color. But by excluding the first horse in the pack of N+1 horses, you can conclude that the last N horses also have the same color. Therefore all N+1 horses have the same color. QED.

Q. Where is the flaw in the induction argument ?

Clue: Double - check the induction argument at a specific case, P(2) => P(3). Strong induction ?

More questions:

Is there anything else besides the above mentioned problem in the induction argument ?

Ant Problem

The noted gourmet Pangolini Aardvark is preparing a late night snack of "Ant au Chocolat" and "Ant au Fromage". This requires the use of a five foot pole. One end of the pole is over a bucket of melted chocolate and the other is over a bucket of melted cheese.

Pangolini sprinkles some ants onto the pole. They immediately start scampering along the pole in random directions. If two ants run into each other then they both instantaneously reverse their directions and are now moving away from each other. An ant can change direction many times. Eventually, all of the ants will fall off one or other end of the pole. If each ant travels at a speed of one inch per second, what is the maximum time until all ants have fallen off?

Suppose now that n ants are placed on a circle of five foot circumference and randomly choose their direction of travel and again reverse direction when they bump into each other. One of the ants is named Alice. What is the probability that Alice is back where she started, one minute after the ants start their scampering.

Back to the pole. Alice starts in the middle of the pole. There are n other ants placed randomly on the pole and they start scampering in random directions. Alice has a cold. When an ant with a cold bumps into another ant, the uninfected ant catches a cold too. What is the expected number of ants who catch cold before they all fall off the pole?

Clue:

This one is vague but very much relevant - What happens in an elastic collision of identical balls ?

level order tree traversal

How would you print out the data in a binary tree, level by level, starting at the top?

Clue:

How about using a Queue. Relate to Dijkstra's SP algorithm.

typrewriter Gib

On April 1st a typist found the hammers of the typewriter resoldered in an arbitrary order, so typing a text resulted in gibberish. The typist decided to type a document in its entirety using this typewriter. Afterwards, if the result does not represent the original text, he will type the result, and so on. Prove that the clear text will emerge sooner or later. How many iterations are enough to guarantee that the clear text will appear, if the typewriter has, say, 46 keys? N keys?

Clue:

Why does it say April 1 ? Is the question poser trying to trick you in deep stuff ? May be. But you can take it to a suitable point and then leave to the crazy math guys.

To take it to the suitable pt:

Decompose a number into such constituents such that the LCM of the constituents is maximized। Think prime! Pray Riemann !

Find the previous alphabet.

khanji has a LOT of characters in their alphabet and are using a way of compressing it so that the most common characters are 1 byte and the less common are 2 bytes. If it's a '1 byte' character, it starts with a 0, If it's a 2 byte character, it starts with a 1. If you're at a particular character (at the beginning), how do you find where the previous character begins?

Now this is an interesting question.
Let the currect char be c (irrelevant), and the first bit of every previous byte be denoted by 1s, 2s....etc.

Some hints:
1. If 1s = 1, then previous char is 2 byte long.
2. If 1s = 2s = 0 then ??
3. If 1s = 0 then all (2...n)s = 1 then the problem is undecidable until you hit
a 0, in which case the answer is ??

DP - max subset of dominating pts.

A DP one.

Q. Consider that you have n 2D pts. Find the largest set of pts such that when sorted (by either axis) produce the same sequence.
Okay, the exact wordings of the original problem -
A circus is designing an act consisting of a tower of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower?

My thoughts -
Sort the pts by say x axis co-ordinates. Then the problem reduces to finding the longest increasing subsequence ( or longest decreasing subsequence Note: we hae to consider both ) in y axis co-ordinates. this is a std DP problem.

More questions :
1. Will it produce the same answer when first sorted in y axis co-ordinates. Or we have to do the both and then take the one of max-length ?

2. How would you generalize the problem to pts coming from dimension d > 2. Need to think over that.

An aside :
See if you could relate some parts of the above problem to the following problem.
Given any sequence of mn+1 real numbers, some subsequence of (m + 1) numbers is increasing or some subsequence of (n+1) numbers is decreasing.

ugly numbers

I lifted it from the career cup site
Design an algorithm to find the kth number divisible by only 3 or 5 or 7. That is, the only factors of these numbers should be 3,5 and 7.

What I have in mind -

Generating the numbers which have prime factors as only 3,5, 7 is not a big thing. but doing so in a sorted order is a little tricky.
Let's call the exponents of 3,5,7 as a,b and c repectively.
Claim: The order of numbers with a = b = c = n to a = b = c = n+1 would be unchanged for any n >= 0.
And that gives an idea to program it. We have to find an order between to successive exponents. Lets start with n = 0. Then we have to find all the numbers ordered ( with their exponents known ) less than 105 ( 3*5*7 ) and greater than 1.
Way 1 -
Write a program to generate all the numbers which are factors of 3 or 5 or 7 ( with their factors recorded. And then keep increasing these factors...
For exp if the factors have exponents (a1,b1,c1), (a2,b2,c2)....(am,bm,cm). then the next cycle of increasing numbers will have exp ( a1+1, b1+1, c1+1 )....(am+1, bm+1, cm+1).
Way 2 -
Generale the numbers thru' the exp. Its clear that they are upper bounded, for n = 0, as a < 5, b < 3, c < 3. So 3 for loops and get all numbers which fall below 105, get their corresponding exp and thats it.

Marble / Egg drop

Problem:

You have a staircase and 2 eggs. The staircase is N steps long. You can drop eggs on this staircase at any point between 0 to N. At a point X on the staircase where X >0 and X < N the eggs begin to break. Your mission, if you choose to accept it, it to find the point X in this staircase by making a minimum number of drops.

O O Step 0
|_
...|_
.......|_
..........|_ - The random point X where the egg breaks
..............|_
..................|_

Analysis:

Solution 1: Ugly

The easiest thing to do is to drop the egg at each step and check if it breaks. The worst case running time of such an algorithm is O(N). However there must be a reason we have 2 eggs to solve this problem. So obviously this is not the optimal solution. Lets think a little more.

Solution 2: A lil better

What can we do to use both the eggs ? Hmmm... Lets do this. Take egg 1 and drop it on odd steps. If it breaks then take the other egg and break it on the last even step before the step where egg1 broke. That is if egg 1 broke at step 5, drop egg 2 on step 4 (last even number before 5). If egg 2 breaks then you know that point is X (since the egg did not break at N=3). If it does not break then you know X is the number where egg 1 broke.

The efficiency of this solution is O(N/2) ~ O(N). But we can do better

Solution 3: I will leave it to you to figure this one out

Its possible to have an efficiency of something better than O(N) for this problem. With the last solution the egg can be dropped at odd intervals. What if we can drop the egg at an interval Z ? How will that help us determine the value of X ? Think about that. How should egg 2 be dropped so that for any interval Z, the value of X can be ascertained.

Performance:

To determine the performance for solution 3, consider making an equation F(Z). F(Z) is a function that determines the number of times (worst case) an egg must be dropped to determine the value of X.

Hint: F(Z) contains 2 component. One that is relevant before egg 1 breaks and one that is relevant after egg 1 breaks.

Once you have this equation in place you can determine the best running time for the worst scenario quite easily.

Hint: Differentiation. F(Z)' and F(Z)''.

This problem can be used to solve some practical difficulties. For example you know that you are to receive a 1024 bit number whose values you must calculate. You know that this number is formatted like so 0000000001111111... but you dont know where the 1s begin. This is like the staircase problem. Applying solution 3 can save time and allow you to quickly calculate the 2nd power of the 1024 bit number.

Rational Pirates (really ??)

k, somebody sent me this question and a quick googling gave me this wikipedia link to the question itself. The question

There are five rational pirates, A, B, C, D and E. They find 100 gold coins. They must decide how to distribute them.

The Pirates have a strict order of seniority: A is superior to B, who is superior to C, who is superior to D, who is superior to E.

The Pirate world's rules of distribution are thus: that the most senior pirate should propose a distribution of coins. The pirates should then vote on whether to accept this distribution; the proposer is able to vote, and has the casting vode in the event of a tie. If the proposed allocation is approved by vote, it happens. If not, the proposer is thrown overboard from the pirate ship and dies, and the next most senior pirate makes a new proposal to begin the system again.

Pirates base their decisions on three factors. First of all, each pirate wants to survive. Secondly, each pirate wants to maximize the amount of gold coins he receives. Thirdly, each pirate would prefer to throw another overboard, if all other results would otherwise be equal.

Wiki link - http://en.wikipedia.org/wiki/Pirate_game

Assuming the reader has read just the question, let me proceed further by strengthening it. What strategy should A employ that he doesn't get thrown overboard ?
Clue: Why not try this with a smaller number of people and then increase to see if it proves to be any helpful.
If n = 2, (say D and E ) are there. Then D obviously splits it as 100:0. So E will always attempt to never reach this situation where only 2 people are left out.
Consider n = 3. C knows that E would not want to in a situation with n = 2, so he would vote for me with any bare min payoff. So he would splits it as 99:0:1.
Now consider n = 4. B clearly knows that D would not want n = 3 situation and by same reasoning would split it as 99:0:1:0 ( note : In this case the casting vote would rule as C and E will vote against the proposition ).

Do you see a pattern readers. Plz note the flipping payoffs. And this is how A would split 98:0:1:0:1.

Easily generalizable. Solved.

Better still, they should all be given swords to finish it off, say, in more pirately manner.