ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2018. The Debut Album

Approach?
Posted by Saurav Kumar 27 Jul 2017 00:07
I want to know how to approach this question in what direction to think so that i can solve it on my own.
Thank you.
Re: Approach?
Posted by Mahilewets 27 Jul 2017 07:54
Problem is tagged with dynamic programming

First,  think about each possible configuration of the current state when you add next song

Second,  think about techniques of DP -  compression
Re: Approach?
Posted by Grandmaster 11 Aug 2017 04:08
well let x[n] be the number of sequences that finish with 1 and y[n] be the number of sequences that finish with 2 of the length n, x[0] = y[0] = 1, x[1] = y[1] = 1, the recurent formula for this is x[n] = y[n - 1] + y[n - 2] + y[n - 3] + .. + y[n - b] and y[n] = x[n - 1] + x[n - 2] + x[n - 3] + .. + x[n - a], basicly for a sequance of n + 1 you must think of the number of ways that the sequance will finish with 1 or with 2

Edited by author 11.08.2017 04:09
Re: Approach?
Posted by Amil Khare 17 Sep 2017 14:33
I am sorry but I still didn't understand, why x is dependent on y. Won't Y[] include cases having consecutive A times 1 and moreover won't Y[] Include duplicate cases ? I am sorry but I am new to this so that's why I am asking.
Re: Approach?
Posted by Grandmaster 30 Sep 2017 02:31
well let's approuch one case where your array is finishing with 1 but no more than "a" times in a row, because the 1 array is dependent from array of 2 and array 2 is alwais finishing with 2 it will look like this 12.... that is y[n] = x[n - 1], than 112... that  is y[n] = x[n - 1] + x[n - 2], than 111...112.... which is y[n] = x[n] + x[n - 1] + x[n - 2] + ... + x[n - a] and is the same in the second case