I'm currently thinking of a new way to solve the twin prime conjecture - but it seems I'm stuck with the equation. Since

for x ¡Ý 55 , we can define the inequality (2x+1)/(log(2x+1) - 4) - (2x-1)/(log(2x-1) + 2) > 1. If this inequality is true for infinitely number of times, then that means there are infinite twin primes. However, the opposite (2x-1)/(log(2x-1) - 4) - (2x+1)/(log(2x+1) + 2) < 1 must also be proved so as to complete the proof using this method. However, I am inclined to believe this approach does not work as I am stuck after just a few steps of expansion. On the other hand, it does not mean that approaches of this kind whereby the prime counting function is directly used to ascertain the twin prime conjecture is totally unfruitful.

I was quite amazed to see a competition for programs to play scissors paper stone... It's called RoShamBo... and it seems there's a very good algo for playing that game... it's the winning program called iocaine powder...

It seems to work by guessing the algorithm of the other program based on previous games... pretty clever and it's amazing that it can be coded! wow...

I realised TopCoder has a lot of resources for learning algorithms. The match editorials themselves provide a great source for learning to solve new problems.

I am almost bored of reading the Div II questions... but the Div I questions can be very challenging... only that some of them are very advance and difficult to solve.

I'm quite amazed how sometimes people can solve those type of problems within one hour... they must be supercoders... but anyway now I have no time to participate in the round matches or even practice in the practice rooms...

I recently read about a simple way to find the maximum number of cliques in a graph :

maximum unweighted bipartite matching - can be solved by network flow - this is what almost every single website will say as an example for transforming a problem into a network flow problem

Well, I learnt a different technique last year. It was based on alternating paths - let us consider matching a's to b's. Start with an arbitrary but correct matching. Then starting with an unmatched a, use unmatched edges to try matching to the b's. Then, from b's back to a's using matched edges, and so continue, by alternating between matched edges and unmatched edges each time, until an unmatched b is found. By flipping the edges (matched->unmatched, unmatched-> matched), we can increase the matching by one (as both the start and end are unmatched edges). I believe this is a special case of network flow.

So I tried coding this out exactly - to just BFS every single possible alternating path. But I realised there can be so many paths that the queue would run out of memory and it was totally disastrous.

But nobody ever said that if a node on side b is visited in a queue, it doesn't have to be visited again - just store where it came from. Then the complexity of coding this BFS is much simpler and can be solved very quickly! To trace back the alternating path, just use the stored values and the matched edges.

But finally, I understood how to code this algo...

I think weighted matching can be similarly solved, each time replacing the cost difference between the matched and unmatched nodes at side b. Not much difference, but a bit more complicated that's all.

I think sometimes it's just hard that there are no simple sample code to look at when learning new algorithms.

Sometimes the implementation of a certain algo is tricky and difficult, though the idea may be simple.

It's just like last time during a test I tried coding a maximum bipartite matching question, but eventually it was full of bugs, when coding for the first time. And I took 2 hrs, which left no time for other questions.

Perhaps the hard way is just to code it when under no pressure...

Dp algos, once understood, are usually easy to debug and code, but more complicated ones like network flow, bipartite matching, minimum spanning tree may be harder to code on the spot. It sometimes may be just the choice of data structure representation that's hard to choose, which affects how the rest of the coding is done.

Wow... amazing... went for Mr Leong's lesson today...

I think his method of taking examples, careful definition, clear representation, extensive elaboration might all work when we are practising...

In actual competition we would need to think a lot faster, sometimes visualisation and clearer definition helps... of course the most needed is a clear mind...

And I finally got the hint that he was making... It about the NOI problem Q3 at http://www.comp.nus.edu.sg/~noi/tasks2004.html 

I thought the best algo was DP... a O(4*k) algo... by considering all the possible permutations of how the previous row of 4 can be filled. Each square is either filled or unfilled, so a dp table of size 2^4 * k is needed, and relations between the previous state and the next state is required.

Eventually I figured out that for this case of 4 * k, only 5 out of the 16 are useful. In fact, 4 of the 16 are really neccessary. The 5 are 0011, 1100, 1001, 0110, and 1111. Since 1111 can be calculated from states 0011, 1100, 1001 from the previous row, 1111 is not really needed.

This optimisation can lead to a slightly better runtime I believe.

Just tried solving some bignum problems on acm...

Realised that there are some little funny tricks to improve runtime, for bignum questions...

Following that thought of using a 10000 base, I thought : since I'm using long instead of int, for fibonacci freeze (495) I could have a 1^9 base bignum... and implementated just that on my solution, resubmitted, and my runtime improved from 1.5s to 0.4s, then following that thought I realised I could even use base 1^18, by using long long, and by doing that the runtime improved to .36 eventually...

Quite stupid right? Just using the same algo but different implementation changes runtime so much...
Anyway it has made my number of accepted solutions increase but not the number of problems solved... so I shan't really concentrate on these small little implementation details... sometimes they do matter - like in bignum, the rest of the times they don't really matter that much...

There's a good website recommended by my friend : http://www.harvestsoft.net/rank.php
It finds the next 20 probably easiest problems for those solving problems from http://acm.uva.es/p
Just realised that, due to rejudging many of those problems which I've solved before appeared on that list of 20 problems...
Some problems have input size increased, some submissions got TLE, some solutions were slightly wrong that didn't take care of extreme cases...
Well so now I'm solving those problems again...
Good thing I still have the solutions which I coded last time...
Daniel's suggestion of using base 10000 for bignum actually works a lot faster than usual string manipulation... tried that for 324 (factorial frequencies)... got quite a good runtime... but not the best though...
Yesterday coded the wrap-around segment sweeping method for 10667(as suggested by Junbin, my RI senior)... well was coding for like 10hrs... with breaks of course... before it was totally correct... it is faster than the usual n^3 method for finding maximum area, but only if given the areas blocked (overlaps don't matter - taken care of).
If given the map of the area instead,  it is still possible to convert to blocks in O(n^2), so overall complexity is still the same, but maybe would take more time to run...
It is possible to convert 10043 to 10667, but I think it would be very inefficient if the same algo is used... how to convert : just treat the trees as a block, and on each row and column the next row or column would be used to contain just the trees, then the next row or column is just a whole empty line... so effectively the input size is 2*n instead of n as the trees take up the other half...
So eventually I modified the code for 10667 for 10043, then got 3.6s runtime, using similar algo but with much shorter code... but the runtime is still far from the best...
Still thinking of an n^3 algo for 10043 like taking 2 points as the endpoints of a rectangle and finding whether another point is in that rectangle... if the points are sorted then it might be even easier... but haven't tried yet... not sure whether it's faster...
Now thinking of solving 495... got TLE after rejuding... can't really remember the last runtime... maybe like 29.5s???

Well, seems that I've learnt a very useful method to find anything that can be expressed in the form of Xn=a1Xn-1+a2Xn-1...akXn-k, where k is a constant...
A simple matix method of the following:

(a1 a2 a3 ... ak) (1 0 0 ... 0) (0 1 0 ... 0) ... (0 0 ... 1 0)

X

(Xn) (Xn-1) (Xn-2) ... (Xn-k)

=

(Xn+1) (Xn) (Xn-1) ... (Xn-k+1)

Let the first matrix on the left be M, the middle one be W, and the resultant be R.
Then by matrix multiplication, M(M(M...(MW)))... = Rn, where M is multiplied n-1 times,
and by a certain matrix property, that is equal to M^n-1*W=Rn, in which M^n-1 can be evaluated in logn time by repeated squaring.
This works for any sequence in which the nth term is the sum of some multiple of each of the previous k terms (i.e the matrix contains only constants, and is of constant size)... and can be found in logn time! Quite interesting right?