SRM 531: "challenging"

What a match to fail the SRM, I am not even sure my 300 is going to survive.

Div1 500: The one with the matrix product
There is initially one bunny of type 1. Every day all the bunnies die, but when a bunny of a certain type dies, a group of bunnies of different types is created. There are at most 50 types.

According to the statement, two outcomes are possible: Even the number of bunnies will eventually become constant and not change, or the number will grow infinitely. It is impossible to ever have less bunnies.

So, if the number grows infinitely, return -1. Else return the constant number modulo 1000000007.
-----
The easy part is to know that you can simulate the creation of bunnies in logarithmic time by using a linear recurrence. Make sure to read bmerry's article: linear recurrences.

IF you use a high enough number as the number of days to wait before calculating the total number of bunnies, you will be able to get the result.

The problem is how to detect cases that grow infinitely. A lot of 'clever' tricks like the ones I tried during the match (Take some random high exponents and compare). Will fail easily if the challenger is smart enough to make a case in which the result is a multiple of 1000000007. I thought of this during the match, but thought that it was going to be very hard to do it. I guess not. Kudos to ainu7.

I resubmitted once after I found an easy way to break my initial 'clever' try. Still, I failed for the aforementioned multiple of 1000..7 issue...

Div1 300: The one about songs and play lists
A music player generates a playlist of P songs. There are N songs available. A condition: Each of the N songs must play at least once. The number of songs between two equal instances of the same song must be M.

It seems dynamic programming is a clean approach here. The complication is how to deal with M. Well, imagine that you just played a song. You will have to wait M+1 turns to be able to play that song again, right?

Keep in mind, a variable called extra and a variable called mustPlay. At some point of the play list, you have extra songs that have already been played but can be played again and mustPlay songs that haven't been played yet. Let's say you are deciding what song to play at position x. Well, if x is high enough, then it is possible that the song you played M+1 turns ago is now available again (increase extra).

Then it becomes easy: Either play an extra song or a mustPlay song.

A base case for our recurrence is when x is P , which means that we have already decided all positions of the play list. If there are still mustPlay songs, then it is not possible to make a valid play list, else the play list is already valid.

Code:

const int MOD = 1000000007; 
struct NoRepeatPlaylist 
{ 
    int P, M; 
    long long mem[101][101][101]; 
    long long mem2[101][101][101]; 
    bool doit; 
    long long rec(int mustPlay, int x, int extra) 
    { 
        long long & res = mem[mustPlay][x][extra]; 
        if (res == -1) { 
            res = 0; 
            if (x == P) { 
                // No more slots to decide! 
                if (mustPlay == 0) { 
                    // Already valid 
                    res = 1; 
                } else {  
                    // Can't be valid. 
                    res = 0; 
                } 
            } else { 
                // If enough songs were played before, increase extra. 
                // (We can play again the song we played M+1 positions ago). 
                if (x >= M+1) { 
                    extra++; 
                } 
                //use an extra song or a mustPlay song. 
                if (mustPlay > 0) { 
                    // There are mustPlay options to choose from 
                    res += ( mustPlay * rec(mustPlay-1, x+1, extra) ) % MOD; 
                } 
                if (extra > 0) { 
                    // There are extra options to choose from 
                    res += (extra * rec(mustPlay, x+1, extra-1) ) % MOD; 
                } 
                // During the match, I forgot to do this: 
                res %= MOD; 
                // But I didn't resubmit because I did a test for all possible 
                // inputs, and it doesn't affect it. 
                // (Right as I am writing this comment, I figured it out. 
                // extra is always 0 in the first called instance of the recurrence. 
                // So this won't matter. 
            } 
 
             
        } 
        return res; 
    } 
    int numPlaylists(int N, int M, int P) 
    { 
        this->P = P; 
        this->M = M; 
        memset(mem, -1, sizeof(mem)); 
        return rec( N, 0, 0); 
    } 
}; 

Update: Good news everyone, at least one person during the match did a solution for div1 500 that doesn't rely on tricks and actually correctly predicts if the graph will grow infinitely. Take a look to bmerry's solution.