1 hour before the contesst.

Hint: Matrix * Matrix takes O(n^3), but Matrix * Vector only takes O(n^2). (Looks like al13n had the intended algorithm but unfortunately failed by overflow.)

TFW you solve 0 problems and still get +38 rating increase.

I tried to solve like that:

int PowerEquationEasy::count(int n)
{
  for (int m = 2; m * m <= n; m++)
    root[m * m] = m;

  long long total_cnt = n * n;
  for (int m = n; m >= 2; m--)
  {
    cnt[m] += n;
    cnt[root[m]] += cnt[m];
    total_cnt += cnt[m];

    cnt[root[m]] %= mod;
    total_cnt %= mod;
  }

  return total_cnt % mod;
}

But, for some reason it doesn't always work.

Solution to the more general div 1 250: it can be seen from prime factorization that if a^b= c^d, then a= t^x and b= t^y for some t,x,y. Now you can just loop over all t and count the number of possibilities of (x,y). You don't need to consider because then x and y cannot be greater than 1.

Completely agree! I think that should have been scored as 300 but not 250!

I honestly think that 250 scenario is: open and implement, the average score is about 200. Here we have only 3 coders with more than 200 points on it. And having that many people did not open 2nd (or open and had only 10 minutes to read and code it).

I did the math. I count 6 at 9PM and 6 at 5:30AM-11AM. Seems like a fair game to me.

Or maybe you are right, it should be something like:

• 7 PM: 2
• 5 PM: 1
• 10 PM: 3
  
  
• 7 AM: 3
• 11 AM: 2
• 5:30 AM: 1

Or you want less amount of contests in the first group?

Topcoder is the only site that actually rotate the starting time to fit all time zones. Codeforces, Codechef, Hackerrank, Atcoder don't give a shit.

And you know, there's some people living in the Americas and the 9 PM is good for them.

I'm not sure about my approach (couldn't get enough time to implement during contest), but some solutions looked like this:

Start with bitmask dp, dp[1<<n][n] where dp[i][j] is the number of ways to traverse mask i, ending up (last traversal) at j.

Recurrence relation should be dp[i][j]=sum(dp[i&(~(1<<j))][k] if k,j are set in i and it is possible to move from k to j. It is possible iff node x is visited (marked in i) only when complete subtree of x is visited or x lies on path from root to j.

I got AC using the following approach. I use DP with state as (mask, current_vertex). I iterate over the next vertex nxt I will visit. If I do visit some particular vertex nxt, I will always return back to current_vertex only after ALL the vertices reachable from nxt, unvisited as of yet, get visited. So, for each pair (mask, current_vertex) I calculate the mask of all the unvisited-till-now vertices I will visit if I start at current_vertex (I store this in reachable[mask][v] in my code).

So, I go from current_vertex to nxt, I add the product dp(mask|(1<<nxt), nxt)*dp(mask|reachable[mask|(1<<nxt)][nxt], current_vertex) to the answer. The first part of the product calculates the number of ways of dealing with nxt and the latter deals with the number of ways of dealing with the remaining unvisited neighbours of current_vertex.

DP[mask][v] returns the number of permutations possible if I have already visited nodes denoted by mask and am currently at v.

Code