MISMARS - Editorial

Problem Link:
Clash Wildcard 2022

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.

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++)
#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

        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) {

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

    #ifndef ONLINE_JUDGE
        freopen("/home/tarun/Desktop/input.txt", "r", stdin);
    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;

    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;

    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';