This problem is from [Halim et al.] CP book section on complete search: Attach between 1 and h stamps to a letter to obtain a value. Determine k distinct denominations of stamps, s.t. contiguous sequence of obtainable values starting at 1 is longest (if tie pick smaller denominations).
Complete problem statement: https://onlinejudge.org/external/1/165.pdf
I think I understand the intuition solution, but I wanted to ask for help with implementation.
My approach: we are looking to create a subsequence starting at one. We will include 1 in the state.
Since the denominations are distinct we initialize:
state = {1, 2, 3, ..., k}
I am not sure of a way to quickly compute the value: we can repeatedly insert into a set. Say the value of the state (i.e. sequence length) is m. We can try replacing one of denoms in the current state with each from \{1,2,\dots,m\} to try to increase obtained value.
If at some point the obtained value is smaller than its parent, we will not explore further since it will be impossible to patch the gaps by further increasing a value.
I tried and implemented several approaches and each had flaws (WA every time); that is why I am asking for help.