Hi everyone,↵
↵
I was recently working on the Timus problem "[The Debut Album](https://acm.timus.ru/problem.aspx?space=1&num=2018)". While doing so, I came across something very odd: my nlog(n) algorithm is way too slow! To summarize the problem:↵
↵
1. You must assign n elements either 1 or 2↵
2. There can be no more than "a" 1s in a row or "b" 2s in a row↵
3. 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.↵
↵
Here is my code: https://codeshare.io/loWmNR
↵
I was recently working on the Timus problem "[The Debut Album](https://acm.timus.ru/problem.aspx?space=1&num=2018)". While doing so, I came across something very odd: my nlog(n) algorithm is way too slow! To summarize the problem:↵
↵
1. You must assign n elements either 1 or 2↵
2. There can be no more than "a" 1s in a row or "b" 2s in a row↵
3. 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.↵
↵
Here is my code: https://codeshare.io/loWmNR
