Hi everyone,
I was recently working on the Timus problem "The Debut Album". While doing so, I came across something very odd: my nlog(n) algorithm is way too slow! To summarize the problem:
- You must assign n elements either 1 or 2
- There can be no more than "a" 1s in a row or "b" 2s in a row
- How many assignments can we make?
The solution I came up with was DP, where each state = {element number, count of the previous 1s in a row, count of the previous 2s in a row} --> {i, cntA, cntB}. Now, I understand why, in the worst case, this algorithm is ineffective. "n" can grow as large as 50,000, and "a" and "b" can get as large as 300 --> 50000*300*2 states (multiply by 2 because if cntA is positive, cntB must be 0 and vise versa) --> 3*10^7 * log2(3*10^7) is clearly way too much. But even when I reduce "n", "a", and "b" on my own computer to 50000, 30, and 30 respectively, the program still takes upwards of 10 seconds to run, which is ~10 times longer than you would expect (3*10^6 * log2(3*10^6) < 10^8). What's going on here?
Note: I do know the correct solution, I'm just wondering why this implementation takes so long for the future.
