This is a story about HackerRank engaging contests, and about problem solving in extreme conditions (NEVER, NEVER use phone as a replacement for a computer).

You can skip the problem-related lines... and keep only with the story (there is even a pretty girl).

Here is the P-Sequences problem. The official editorial is here

But my story solving this problem is quite "unique", here we go.

Resumed versions: Given N and P, count how many sequences of N non-negative integers, satisfy that for any pair of adjacent elements, its product is <= P.

Constraints: N <= 10^3 and P <= 10^9.

After reading it, the problem seemed hard, almost instantly I got an O(N*P) algorithm, but no clue about how to improve it.

NOTE: HackerRank gave 24 hours to solve the problem.

Next day I woken up at 7am, and the very first thing that came to my mind was that the number of states with "different" values was only O(sqrt(P)) for a given N, eg. dp[N][P/2 + 1 ... P] contains the same value, the same for dp[N][P/3 + 1 ... P/2] and so on, I was enlighten, but have absolutely no idea how to use or implement it efficiently.

That day I was traveling to Bern (I currently live in Lausanne) to solve important affairs. Anticipating a busy day I left my precious laptop, and take only an old notebook(the one made of paper, NOT the electronic device), a pen and the phone (no laptop, only a phone!!!). Even worse, my girlfriend came with me too, hoping to have a nice couple day... so the little free time I was counting on was almost reduced to zero.

In the 1h:45m that takes the train to get to Bern I sketched a recurrence, and defined a state of the DP as follows:

dp[N][i] = number of ways to build a sequence of N elements, with the last element <= i

dpPover[N][i] = number of ways to build a sequence of N elements, with the last element <= (P / i)

The answer would be dpPover[N][1] (the number of sequences of N elements where the last element is something <= (P / 1))

Then we arrived to Bern, and the time to submit was slowly expiring.

While having lunch at McDonald's I spent like 30 minutes coding my solution, ON THE PHONE!!! and I have to say it in capital letters, it was HORRIBLE, phones are evil machines for programmers. Symbols like []{}¦ were 3 keys away on the touch keyboard ... a really painful experience. Sites like ideone.com doesn't work fine in phones, and HackerRank code editor was also useless. I did all using Jota++ Editor, a simple notepad app. No syntax highlighting, no indentation, testing was almost impossible... When leaving McDonald's my program compiled but was still incorrect. My girlfriend insisted that we should walk and take some pictures, visit the most we could (including the Albert Einstein Museum), and enter in all the stores, so I put the phone on my pocket and follow her, trying to find in my mind what was wrong with my code.

Hours later, we arrived to the Cathedral, and found a nice bank, surrounded by kids, with a beautiful view to the river. My girlfriend was exhausted, so she used me as a pillow, so I continue to think, and finally found the bug, YESSSSS!!!!. I fixed my program and hit submit, and got AC with my girlfriend resting in my legs, the adrenaline rush make me feel that I was the smartest person in the world in that moment (but I'm not). I've solved a really challenging problem using a phone and the day was still a success. I wrote this entry after the OFFICIAL testing, but I was quite confident about it. A phone is a terrible tool for programming, but releases the full power of thinking, of crafting an idea in the best possible way. Here is my final solution, which seems a lot simpler than the official one:

#include <iostream>
#include <cmath>
using namespace std;

const int MOD = 1000000007;
const int SQP = (int)sqrt(1000000000) + 100;
int N, P;
int dp[2][SQP];
int dpover[2][SQP];

int main(){

  cin >> N >> P;
 
  int S = (int)sqrt(P);

  for (int i = 1; i <= S; i++) {
    dp[1][i] = i;
    dpover[1][i] = P/i;
  }

  for (int i = 2; i <= N; ++i){

    int cur = i & 1;
    int prev = 1 - cur;

    dp[cur][1] = dpover[prev][1];

    for (int j = 2; j <= S; j++) {
       dp[cur][j] = (dp[cur][j - 1] + dpover[prev][j]) % MOD;
    }

    dpover[cur][S+1] = dp[cur][P/(S+1)];

    for (int j = S; j > 0; j--) {
        dpover[cur][j] = (dpover[cur][j + 1] + (P/j - P/(j+1)) * 1LL * dp[prev][j]) % MOD;
    }
  }
  
  cout << dpover[N&1][1] << endl;

  return 0;
}