Problem description

  • Sample: non-empty sequence of consecutive notes in the piece

  • Good sample: all notes are different in sample.

  • Conditions on a piece:

      1. No pitch higher (>) than m

      2. Has exactly K good samples

    Example: 

       N = 3  (piece has 3 notes)
 M = 2  (notes uses: 1 2)
 K = 5  (piece has exactly 5 good samples

Solution:     1 2 1

Good samples: each single note:  1   2   1
              and:               12  21  121 (bad)

Problem Analysis

  • This is a hard problem because you have to find a trick to construct a piece with exactly K good sample.

  • The find this trick, you need to understand the problem/properties of constructing a piece (= sequence of notes)

  • No amount of knowledge in computer science will help you solve this problem...

    So there is no way I can teach you how to prepare for this kind of problems...

    (This question is more like a logic puzzle than a computer science contest question...)

Problem Analysis

  • I will use examples to illustrate the trick to construct a piece with exactly K good samples: 

     N = 10, M = 3, K = 10

       Answer:      1 1 1 1 1 1 1 1 1 1 
       Good smps:   Each note is a "good sequence" 

 N = 10, M = 3, K = 11

       Answer:      1 2 2 2 2 2 2 2 2 2 
       Good smps:   Each note + 12

 N = 10, M = 3, K = 12

       Answer:      1 2 1 1 1 1 1 1 1 1
       Good smps:   Each note + 12 + 21

 N = 10, M = 3, K = 13

       Answer:      1 2 3 3 3 3 3 3 3 3
       Good smps:   Each note + 12 + 123 + 23

 N = 10, M = 3, K = 14

       Answer:      1 2 3 2 2 2 2 2 2 2 
       Good smps:   Each note + 12 + 123 + 23 + 32

Problem Analysis   how to make a piece with exactly K good samples

  • This is the trick: 

     N = 10, M = 3, K = 12

 Suppose the answer so far is:

    Answer:      1 2 1 _ _ _ _ _ _ _   Unfilled notes     = 7
    Good smps:   Each note + 12 + 21   Total good samples = 5

 Remaining notes:        N' = 7
 Remaining good samples: K' = 12 - 5 = 7

 if ( Remaining notes == Remaining good samples )
    fill the rest of the piece with the last note

 Answer:        1 2 1 1 1 1 1 1 1 1 1

Problem Analysis   how to make a piece with exactly K good samples

  • See how it works for another example: 

     N = 10, M = 3, K = 14

 Suppose the answer so far is:

    Answer:      1 2 3 2  _ _ _ _ _ _   Unfilled notes  = 6
    Good smps:   1 + 2 + 3 + 2 + 12 + 123 + 23 + 32     = 8

 Remaining notes:        N' = 6
 Remaining good samples: K' = 14 - 8 = 6

 if ( Remaining notes == Remaining good samples )
    fill the rest of the piece with the last note

 Answer:        1 2 3 2 2 2 2 2 2 2

Problem Analysis    How to create a piece of music ?

  • Because we have a trick to trottle down the number of good pieces, the strategy to make a piece of music is: 

    
 Piece:
               N-p                  p
      |<-----------------> X | X X X X X X X |
       Maximize the number    
       of good samples
       when constructing
       this part 

  Make sure that:

       <-----------------> X  has exactly K-p  good samples

Problem Analysis    you can create a boring piece of music...

 

  • Unlike good sounding music that have harmonuous notes, all that we care is:

      • No 2 notes in a good sample are equal to each other

  • So instead of making a piece that looks like this: 

        1 7 4 3 2 .....

    we make a piece that looks like this: 

        1 2 3 4 5 .....

Effect of adding a new note (to an unfinished piece)

Effect of adding a new note in the initial M notes of the piece: 

      next note = 4
        |
        V
  1 2 3 
                              
  Good samples:   1   2   3
                  12  23
		  123

  1 2 3 4

  Good samples:   1    2    3   4
                  12   23   34
		  123  234
		  1234



  So:  Adding note k to the initial M notes will increase
       the number of good samples by k

Effect of adding a new note (to an unfinished piece)

Effect of adding a new note in the subsequent M notes of the piece: 

                next note = 4
                      |
             (M)      V
  1 2 3 4 5 6 7 1 2 3 
                              
  Good samples:   { some set }
 
  

  1 2 3 4 5 6 7 1 2 3  4

  New good samples:   4   34   234  1234  71234  671234  5671234



  So:  Adding note k to the piece after M notes will increase
       the number of good samples by M

Effect of adding a new note (to an unfinished piece)

One more trick:   trottle the last new note 

                next note = 3
                      |
             (M)      V
  1 2 3 4 5 6 7 1 2 3                   (last note = 3)
                              
  Good samples:   { some set }
 
  

  1 2 3 4 5 6 7 1 2 3  3

  New good samples:    3 



  So:  Adding  last note to the piece  will increase
       the number of good samples by 1

Effect of adding a new note (to an unfinished piece)

One more trick:   trottle the last new note 

                next note = 2
                      |
             (M)      V
  1 2 3 4 5 6 7 1 2 3                   (last note = 3) 
                              
  Good samples:   { some set }
 
  

  1 2 3 4 5 6 7 1 2 3  2

  New good samples:    2  32 



  So:  Adding  last note - 1 to the piece  will increase
       the number of good samples by 2