MISMARS - Editorial

Problem Link:
Clash Wildcard 2022
Practice

Problem:
Help Tom and Jerry kill a bunch of aliens with cheese ball. They can kill all aliens except the ones at both the ends. You are given the healths of each alien.
Each cheese ball does A damage to the alien it hits, and B damage to the adjacent aliens. An alien dies when it’s health is less than 0. Find minimum number of cheese balls required to kill all aliens.

Explanation:
Let’s assume that the aliens are numbered starting from 0.
Let me first introduce a simplification. The problem says to make the health of the alien < 0. Let us assume that we have to make the health of the alien <= 0. To achieve this transition and obtain the same number of minimum moves as the case with < 0, we increment health of each alien by 1.
The only way to kill the 0th and the (n-1)^{th} alien is to shoot a cheese ball directly at the 1^{st} and the (n-2)^{th} aliens respectively. Note that 1^{st} and the (n-2)^{th} aliens may be the same. So, at first we kill the 0th and the (n-1)^{th} aliens via this process.

Now, we are left with aliens from 1 … (n-2). We’ll use DP to solve the problem. Let’s process the aliens in sequence. When we are at the 1^{st} alien, we may either kill it directly by shooting appropriate number of cheese balls on it, or we may leave some of its health which will ultimately be made 0 by the direct shots that we make at the alien 2.
When we are at the 2^{nd} alien, the above said things for the 1^{st} alien hold true for it as well. However, note here that the health of the 2^{nd} alien must have been reduced indirectly already due to the direct attacks that we made to the 1^{st} alien, and again we may or may not completely kill it and the remaining damage will be incurred to it by the next alien (3^{rd} alien).

These observations tell us while we are at a particular alien, our state is dependent on:

  • The index of the alien that we are at.
  • The health of the previous alien remaining. (This will ensure that we shoot at least as many cheese balls on the current alien so that the previous alien gets killed / his health becomes \leq 0).
  • The no. of direct attacks made on the previous alien. (this can reduce the health of the current alien).
    Another observation: Since we only have to make the health \leq 0, we can take any health < 0 to be 0. This will help us in avoiding negative indexing for the 2^{nd} state variable mentioned above.

So, that’s it. We can use a 3 state DP: dp[i][j][k]: where dp[i][j][k]= Minimum number of shots to kill the aliens starting from the i^{th} alien when the previous alien still has j health points left and the number of direct shots at the previous aliens were k.

Setter's Solution (C++)
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define repi(i, a, b) for(int i=(a); i>(b); i--)
#define db(x) (cerr << #x << ": " << (x) << '\n')
#define sync ios_base::sync_with_stdio(false), cin.tie(NULL)
#define tests(t) int t; cin >> t; while(t--)
#define iceil(n, x) (((n) + (x) - 1) / (x))
#define ll long long
#define gcd __gcd
#define mp make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define sz size()
#define all(v) (v).begin(), (v).end()
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define pqueue priority_queue
#define si(a) scanf("%d", &a)
#define sll(a) scanf("%lld", &a)
#define bitcount(x) __builtin_popcount(x)
#define cps CLOCKS_PER_SEC
#define PI acos(-1.0)
#define EPS 1e-9
#define mod 1000000007
#define MOD 1000000007
#define N 20
using namespace std;
 
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
 
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
 
template<typename T>
using maxpq = priority_queue<T>;
 
//All indexing is 0-based
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update> ordered_set;
//methods: find_by_order(k); & order_of_key(k);
//To make it an ordered_multiset, use pairs of (value, time_of_insertion)
//to distinguish values which are similar.
 

//a and b are assumed to be taken modulo p
inline int add(int a, int b, int p = mod){ int c = a + b; if(c >= p) c -= p; return c;}
inline int sub(int a, int b, int p = mod){ int c = a - b; if(c < 0) c += p; return c;}
inline int mul(int a, int b, int p = mod){ return (a * 1ll * b) % p;}

const int inf = 1e7;

int dp[N][N][N];
//dp[i][j][k]: Min. no. of shots to kill the alien starting from the ith alien
//when the previous alien still has j health points left
//and the no. of direct shots at the previous aliens were k

int num[N][N][N];
//num[i][j][k]: No. of direct attacks on ith aliens
//that leads to the min. total no. of cheese balls
//needed to kill aliens starting from the ith alien
//in the state dp[i][j][k]

int hlth[N][N][N];
//hlth[i][j][k]: The remaining health of the ith alien after
//considering direct attacks on it
//and the direct attacks on the alien to its left
//that leads to the optimal answer(min. no. of total arrows)
//from the state dp[i][j][k]

int h[N], n, a, b;
vector<int> result; //The result

//Assume that the alien no. 0 and n-1 have already been killed,
//so we are only left with the aliens from 1 .. n-2

int rec(int i, int j, int k) {
    if(i == n-1) {
        //Reached the last alien
        //If prev. alien is still healthy, it's no longer
        //possible to kill him
        if(j > 0) {
            return inf;
        }
        else {
            return 0;
        }
    }

    int &ans = dp[i][j][k];
    if(ans != -1) return ans;

    ans = inf;

    int hh = h[i] - k*b; //New Health of the current alien after considering the damage incurred
                         //from the direct attacks on the previous alien
    for(int x = 0; x <= 16; x++) {

        if(x * b < j) {
            //If x direct cheese balls on the current alien
            //are not enough to kill the previous alien
            continue;
        }

        int nh = max(0, hh - x*a); //New health of current alien after considering direct attacks
        int kk = rec(i+1, nh, x) + x;
        if(kk < ans) {
            ans = kk;
            num[i][j][k] = x;
            hlth[i][j][k] = nh;
        }
    } 
    //trace(i, j, k, h[i], ans);
    return ans;
}

void compute_result(int i, int j, int k) {
    if(i == n-1) {
        return;
    }

    int m = num[i][j][k]; //No. of cheese balls directly at the ith aliens
    while(m--) {
        result.pb(i);
    }
    compute_result(i+1, hlth[i][j][k], num[i][j][k]);
}

main()
{   
    #ifndef ONLINE_JUDGE
        freopen("/home/tarun/Desktop/input.txt", "r", stdin);
    #endif
    sync;
    clock_t clk = clock();
    cerr << "I will return...\n";
    
    cin >> n >> a >> b;
    rep(i, 0, n) {
        cin >> h[i]; h[i]++;
    }

    memset(dp, -1, sizeof dp);
    while(h[0] > 0) {
        //Make direct shots at alien 1
        h[0] -= b;
        h[1] -= a;
        h[2] -= b;
        result.pb(1);
        //db(1);
    }

    h[0] = max(0, h[0]);
    h[1] = max(0, h[1]);
    h[2] = max(0, h[2]);

    while(h[n-1] > 0) {
        //Make direct cheese ball shots at alien (n-2)
        h[n-1] -= b;
        h[n-2] -= a;
        h[n-3] -= b;
        result.pb(n-2);
        //db(2);
    }

    h[n-1] = max(0, h[n-1]);
    h[n-2] = max(0, h[n-2]);
    h[n-3] = max(0, h[n-3]);

    rec(1, h[0], 0);

    compute_result(1, h[0], 0);

    cout << result.size() << '\n';
    for(int i : result) cout << i+1 << ' '; cout << '\n';
    
    cerr << "...don't you ever hang your head.\n";
    cerr << "Time (in ms): " << double(clock() - clk) * 1000.0 / cps << '\n';
}