Nice DP lecture

I think the book is nicer though.

Number theory

I found a nice Number Theory question, so for those people who want to attack it directly, here it is:

Prove that exp 2^2(x) is eventually constant mod n (as x increases), where n is an arbitrary positive integer.

But since I expect few to solve it from there (main because of notation), I guess I should explain the weird notation.

exp 2^2(x) actually came from my interpretation of the Wikipedia article (wanted to add Knuth's up arrows, but I'm a lazy person). So what it's supposed to mean is 2^2^2^2..., with x number of 2s. This might not be standard notation, but it's what I got from Wikipedia.

Next mod n, for those who don't know, is basically asking what the remainder when the number is divided by n, eg 42=19 (mod 23), and 31 = 5 (mod 26).

So before I go on hinting like a maniac, it's time to talk about number theory in general. Number theory, in general, talks about the properties of integers. For example, number theory attempts to describe the properties of primes. However, Wikipedia lists at least 5 fields of number theory, such as algebraic number theory. In general, fields such as analytic number theory are more for research problems, which are still relatively open problems, but elementary number theory has a large number of solved problems which have elegant solutions and are light to solve (well, not as bad as researching a problem for months).

Number theory is rather interesting; when you look at a problem, it's hard to tell whether it might be easy or hard, with some messes quickly reducing to workable expressions, but stuff like proving that x^n+y^n=z^n has no integer solutions for n>=3 looks simple, but involves elliptic curves (see Fermat's Last Theorem). However, in this case, it both looks easy and is pretty doable.

Now, for people who have done some kind of number theory before, for the original question in this post, it helps to define it as a recurrence relation, with a1=2 and a2=2^a1 = 2^2 = 4. Then it suffices to prove that 2^ai = 2^a(i+1) (mod n) for any sufficiently large i.

Next, it helps to know Euler's Theorem, but is completely unnecessary (really).

The next important thing to know is the idea of induction. The general format of induction can go something like this: Student 1 is a boy. If Student i is a boy, then Student i+1 must necessarily be a boy as well. Therefore, Student 2 is a boy, therefore Student 3 is a boy, et cetera. We thereby conclude that Students 1 to the last student are all boys.

There is a similar form of induction, which works backwards. This works by say, concluding that Student i is a boy if Student i-1 is a boy. Student i-1 is a boy if Student i-2 is a boy, and this traces all the way back to Student 1, who is a boy. We are done.

An important thing to know is that the sequence 2, 4, 8, 16, 32, 64, ... enters a cycle mod n. To prove this, the most primitive way I can think of is to think of the ith term and the (i+1)th term. Say the remainder when i/n is x. This means that 2^i=kn+x, for some integer k. Therefore, 2^(i+1) = 2kn+2x, which when divided by n, gives a remainder solely defined by x. Hence, one can think of walking the remainders like a path, and with finite number of destinations to visit, one must eventually go back to the same point. Since the direction from any starting point is uniquely defined (ie you're forced to walk the same way from any same point), once you get back to the same point, there is no way you're ever going to break out from the cycle.

The substep to prove is that the length of the cycle is less than n. (Hint: consider 0 mod n)

Bad Spoiler Alert: (highlight to see)
Following this, you may realise that if the length of the cycle mod n is x, then the value of 2^i mod n is dependent on the value of 2^i mod x, where x is smaller than n. This is the induction step.

Don't forget your base case when induction though.

P.S.: This post is shorter than I expected it to be, my essay spamming skills must have deteriorated. Ohnoes.

Yet another 26 move chess match

START{
1. H2+3 p3+1 2. P3+1 h2+3 3. C2.1 c2.1
4. R1.2 c8.9 5. C8.7 h8+7 6. C7+3 e3+5
7. C7+1 r9+1 8. H8+7 r1.2 9. E7+5 r9.4
10. C7.3 h3+4 11. A6+5 r2+7 12. R9.6 r2.3
13. H3+4 h4+6 14. C1.7 r4+8 15. A5-6 h6-7
16. R2+3 c1+4 17. C7.9 h++6 18. C9+4 h6+4
19. C9.7 h7+6 20. R2-2 c1+3 21. E5-7 h6+5
22. R2+2 h5-7 23. R2.6 h7+6 24. K5+1 h6-4
25. K5.6 e5+3 26. C7.1 c9.4 }END

Just a chess match

1. H2+3 c2.5 2. H8+7 p7+1 3. C8.9 h2+3
4. R9.8 h8+7 5. P7+1 h7+6 6. R8+5 c8+2
7. R8+1 r1.2 8. R8.7 r2+2 9. C2.1 c8-3
10. R1.2 c8.3 11. R7.9 r2+6 12. R9-1 h6+7
13. R9.3 h7+9 14. E3+1 r9+1 15. R3+4 h3-5
16. R3-4 c3+6 17. E1-3 r9.6 18. R3+1 r6+7
19. A4+5 r2.3 20. E7+5 r3.4 21. A5-4 c5.2
22. C9.8 c2.4 23. A6+5 r4.2 24. R2+7 r2+1
25. A5-6 r6.4 26. A4+5 c3+2 }END

Extended Euclidean Algorithm

Yay, today I learnt (more precisely, relearnt) Extended Euclidean Algorithm. Yay, I can start solving Diophantine Equations again :D

void EGCD(int a,int b){
 if(a < 0 || b < 0){
  EGCD(abs(a),abs(b));
  if(a < 0) x = -x;
  if(b < 0) y = -y;
 }
 else if(b == 0){
  x = 1;
  y = 0;
 }
 else{
  EGCD(b,a%b);
  x1 = y;
  y1 = x-(a/b)*y;
  x = x1;
  y = y1;
 }
}

Below is random experimentation with HTML tags and javascripts on blogs
This is Google



HOW DO I ENABLE ALL THE RANDOM LANGUAGES AND SCRIPTS???

Post drought

To stop this post drought (while the next article on RJT Chess is tentatively being written), I shall post an error code arising from my randomings on C++.

invalid types 'int [((unsigned int)((int)(X*Y)))][]' for array subscript

That's quite a lot of brackets towards the middle.

Sails (IOI 2007 Problem)

The problem roughly goes: You have a ship with N<=100,000 flagpoles, and each flagpole has an integer height up to 100,000. Each flag can only occupy a height of the flagpole at integer heights. Because the ship should be as aerodynamic as possible, air resistance comes into play. For each flag (don't question the question), it contributes a drag of X Newtons, where X is the number of flags behind it (w.r.t. direction of movement) flying at the same height. Your task is to write a program to determine the minimum amount of drag induced by the flags in total given the height and number of flags on each flagpole.

Here is my proposed algorithm: subject to flaws major and minor:

We make a few random observations that I'm not too sure where they appear in the solution, but let's just list them down first:

1) Total drag = summation x(x-1)/2, where x is the number of flags at each height.
1.1) It doesn't matter what order the flagpoles are arranged in.

2) There exists an optimal solution where the number of flags in each height is non-decreasing as the height gets lower.
Proof: Consider an optimal solution (if it exists) where two consecutive heights are such that the higher height has more flags, then the flags can be shifted down (by Pigeonhole Principle or something, because on the same pole there will exist space for the flags to move down)

3) The objective is to try to spread flags out as far as possible.
"Proof": 3+5>4+4 (by 1 Newton of drag), since well, can't be bothered to explain this.

4) Assuming a/b>c/d, a,b>c,d>0,0 (improvised notation ftw), then (a-c)/(b-d)>c/d.

Proposed Solution Part 1: Definitions
-------------------------------------
Define the highest level of the highest flagpole to have height 1, the second highest level to be 2 and so on, until n.

Define g(i) to be the maximum number of flags you can fly at equal to or higher than the level i.

Define f(j,k)= |g(j)-g(k)/(k-j)| (modulus function ftw).

Proposed Solution Part 2: Calculating g(i)
------------------------------------------
Raise all flags to the maximum. The number of flags at or above height i is now g(i).

To calculate all g(i) in O(N) time, we let the flags at each flagpole by represented by a range (after being raised to the maximum).

The sum of the total length of all parts of all ranges above i is then g(i).

Hence, at the start of each range, we add 1 to an array, and minus 1 after the end of each range. (ie a[0]=0, a[1]=a[0]+number of ranges starting at 1 - number of ranges ending at 0)

g(i) is then the sum of a[0]+a[1]+...+a[i] (or something like that).

Proposed Solution Part 3: The Idea
----------------------------------
Since we wish to spread out the flags among heights evenly, we will try to see whether we can do this 100% efficient. As it turns out, we cannot, because the higher levels will not fit as many flags.

So, we will probably wish to stuff as many flags into the higher levels as possible before moving on to the lower levels.

Say for the highest 6 levels we can fit 5, 14, 14, 16, 17, 18 flags respectively. Then clearly the most optimal solution involves putting 3 flags in each level (assuming there are a lot of flags past the 6th level).

After that, we realise we have reduced the problem, but the condition "(assuming there are a lot of flags past the 6th level)" is a bit iffy, so let's formalise it.

If g(k)/k is minimal among all k from 1 to n, then:
1. The heights above k can have either floor(g(k)/k) or ceiling (g(k)/k) flags.
2. That is the most optimal way of arranging the flags.

Hence, if we can find the minimal g(i)/i, we can reduce the problem.

Proposed Solution Part 4: The Problem
-------------------------------------
If the i that minimises g(i)/i is say, 1, then the reduced problem will have different g(i)/i, since the maximal number of flags above a certain level j in the reduced problem is actually equivalent to |f(i,j)*(i-j)| (stupid definitions). Or I think I should say, f(i,j) is not equal to f(0,j). Yep. That makes more sense. Hence the next minimal f(i,j) might not be the minimal f(0,j). Which means that we have to recalculate everything, which is a lot too slow (O(n^2)).

Proposed Solution Part 5: The Win
---------------------------------
We shall pretend we are stupid (slightly) to solve the problem.

At each height, if f(i, i+1) is more than the previous minimum f(a,i), then we plonk it into a list of minimums. (Like, if say g(3)/3 is the true minimum value of g(i)/i, then f(3,4) may be the minimum value of f(3,i) .

If f(i, i+1) is less than the previous minimum f(a,i), then it must be true (by Observation 4) that f(a,i+1)
After this mess, we now know the minimum g(i)/i. We also know the minimum g(i)/i in the reduced problem, the doubly-reduced problem and so on. Hence, we can calculate the minimum drag the flags add to the ship.