CF #637D

D. Nastya and Scoreboard

Problem Statement: here

Solution

This question is a classic example of the knapsack problem, where you need to choose exactly k number of items. So, we can say it as a derived knapsack problem. 

We will solve it using 2d DP.

dp[i][j] -> where it means using the last i positions and j sticks in total, can we get a solution, if yes then it should be as large number as possible.

The dp transition  will be :

You loop through the last position to first position:

Inside this loop, you loop for the possible value of sticks used from 0 to k, 

Inside this loop, you loop from digit 9 to 0.

we can create a function separately, which can return us the total number of sticks i can use to convert the ith string into given digit. If the function results -1, then we cannot convert it and we simply continue. Also, if the cost exceeds the possible value of sticks I am using (by variable j in my code), even then I continue, because it is not possible to construct the number. 

On the other hand, if I get a valid cost  which is less than or equal to the current sticks I have in hand,

I need to check, if I use this much of sticks, was it possible to construct the solution from next up index to last index using the remaining sticks (remember I was looping from behind). 

So, my dp transition in this case becomes : dp[i][j] = digit, only if dp[i+1][j-cost] is not equal to -1, means I have a digit stored at it,  means It is possible to construct the solution. Once, I get a possible digit, I will break the loop, because I need to place maximum possible digit each time, so I don't need to check for each and every digit. 

Once this dp table is filled. 

If my value of dp[1][k] is not -1 then solution exist. 

Why dp[1][k], because I was looping backwards and from n to 1, If i can use exactly k sticks then there must be a digit at dp[1][k], which will tell me that I am the maximum possible digit you can use to construct your solution, so if it exist, i use it and then using the cost to convert a[1] to that digit, I can determine my next digit, simply by doing dp[i+1][k] where I update my k with k -= cost of conversion. 

So, at the end, it makes sense to loop backwards, because I want to place the maximum digit at first place,So I need to know if while doing so, is it possible to construct solution from remaining sticks and next position. 

Nice question on the derived knapsack.

Implementation:

vector<string> digits = { "1110111", "0010010", "1011101",
"1011011", "0111010", "1101011", "1101111", "1010010",
"1111111", "1111011" };

ll check(string d1, string d2){
    ll cost = 0;
    rep(i,0,7){
        if (d1[i] == '1' and d2[i] == '0'){
            return -1;
        }
        cost += (d1[i] != d2[i]);
    }
    return cost;
}

void solve(){ ll n,k; cin >> n >> k; string a[n+1]; rep(i,1,n+1) cin >> a[i]; int dp[n+5][k+5]; clr(dp,-1); dp[n+1][0] = 0; repp(i,n+1,1){ rep(j,0,k+1){ repp(d,10,0){ ll cost = check(a[i],digits[d]); if (cost == -1 || cost > j){ continue; } else{ if (dp[i+1][j-cost] != -1){ dp[i][j] = d; break; } } } } } if (dp[1][k] == -1){ cout << -1 << endl; return; } string ans; rep(i,1,n+1){ int dig = dp[i][k]; ans += to_string(dig); k -= check(a[i],digits[dig]); } cout << ans << endl; }