SPOJ QTREE2

I'm back after a long break; longer than I anticipated. I was reading a Topcoder tutorial on Range Minimum Query (RMQ) and Lowest Common Ancestor (LCA) problems. Here's a comparison table of the algorithms presented in the tutorial -

Break

I'm taking another break for 3 days; currently overloaded with project works; need to reduce the workload to a maintainable amount.

SPOJ MMOD29

Problem Link : http://www.spoj.pl/problems/MMOD29/en/

I was searching some problems that would require modular inverse / Chinese remainder theorem / Extended Euclidean algorithm. This problem requires the simplest case of modular inverse when the numbers in question are co-prime.

The problem in short

Find the sum of divisors of the number 2004^X mod 29 [1<=X<=10000000].

So, first we need to find the sum of divisors of an arbitrary number N. Let prime factorization of N is -

TopCoder SRM 489 Div 1 Medium (Dice Rotation)

Another bad SRM for me :( I couldn't even submit any problem although I was just 1 click away from solving the medium problem with 30 seconds to go when the network router decided to go offline. My only achievement in this SRM was one successful challenge.

I'm going to explain how I approached the dice rotation problem. In this problem you have to move a standard dice placed at (0,0) cell of an infinite Cartesian plane to (goalx, goaly) by rotating it to right or up. The top of the dice have to show '1' when it starts its journey at (0,0) and also when it ends its journey at (goalx,goaly) and it cannot be on top in any intermediate cell. goalx and goaly can be as high as 10^9.