**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:

constintMOD=1000000007;structNoRepeatPlaylist{

intP,M;

longlongmem[101][101][101];

longlongmem2[101][101][101];

booldoit;

longlongrec(intmustPlay,intx,intextra)

{

longlong&res=mem[mustPlay][x][extra];

if(res==-1){

res=0;

if(x==P){

//Nomoreslotstodecide!

if(mustPlay==0){

//Alreadyvalid

res=1;

}else{

//Can'tbevalid.

res=0;

}

}else{

//Ifenoughsongswereplayedbefore,increaseextra.

//(WecanplayagainthesongweplayedM+1positionsago).

if(x>=M+1){

extra++;

}

//useanextrasongoramustPlaysong.

if(mustPlay>0){

//TherearemustPlayoptionstochoosefrom

res+=(mustPlay*rec(mustPlay-1,x+1,extra))%MOD;

}

if(extra>0){

//Thereareextraoptionstochoosefrom

res+=(extra*rec(mustPlay,x+1,extra-1))%MOD;

}

//Duringthematch,Iforgottodothis:

res%=MOD;

//ButIdidn'tresubmitbecauseIdidatestforallpossible

//inputs,anditdoesn'taffectit.

//(RightasIamwritingthiscomment,Ifigureditout.

//extraisalways0inthefirstcalledinstanceoftherecurrence.

//Sothiswon'tmatter.

}

}

returnres;

}

intnumPlaylists(intN,intM,intP)

{

this->P=P;

this->M=M;

memset(mem,-1,sizeof(mem));

returnrec(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.

## No comments :

Post a Comment