Day 2, Task 1: Operations

Solution

BFS on the State Space

This is a shortest-path problem in an unweighted graph where states are integers and transitions are the four operations. BFS finds the minimum number of steps.

The key question is bounding the search range. For the operation set $\{+1, -1, \times 2, \div 2\}$:

Lemma.

An optimal path from $s$ to $t$ only visits values in $[\min(s,t) - 2,\; 2 \cdot \max(s,t) + 2]$.

This bound is loose but sufficient; the actual BFS terminates quickly because doubling shrinks the gap fast.

Alternative: Working Backwards

A cleaner approach works backwards from the target:

• If $t > s$ and $t$ is even, halve $t$ (inverse of $\times 2$).

• If $t > s$ and $t$ is odd, add 1 to $t$ first, then halve (inverse of $-1$ then $\times 2$).

• If $t \le s$, the answer is $s - t$ steps of $-1$.

• This greedy backward approach gives $O(\log t)$ steps. However, it does not always produce the optimal sequence for the full 4-operation set (the BFS approach is exact).

Complexity Analysis

• BFS: $O(|V| + |E|)$ where $|V|$ is bounded by the search range, typically $O(\max(s,t))$.

• Backward greedy: $O(\log t)$ time.

Implementation: BFS

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int start, target;
    cin >> start >> target;

    if (start == target) {
        cout << 0 << endl;
        return 0;
    }

    unordered_map<int, int> dist;
    unordered_map<int, int> parent;
    unordered_map<int, string> op;

    queue<int> q;
    q.push(start);
    dist[start] = 0;

    int lo = min(start, target) - 2;
    int hi = max(start, target) * 2 + 2;

    while (!q.empty()) {
        int cur = q.front(); q.pop();

        struct Move { int nxt; string name; };
        Move moves[] = {
            {cur + 1, "+1"},
            {cur - 1, "-1"},
            {cur * 2, "*2"},
            {cur / 2, "/2"}
        };

        for (auto& [nxt, name] : moves) {
            if (nxt < lo || nxt > hi) continue;
            if (dist.count(nxt)) continue;

            dist[nxt] = dist[cur] + 1;
            parent[nxt] = cur;
            op[nxt] = name;

            if (nxt == target) {
                cout << dist[nxt] << endl;
                vector<string> path;
                int x = target;
                while (x != start) {
                    path.push_back(op[x]);
                    x = parent[x];
                }
                reverse(path.begin(), path.end());
                for (auto& s : path)
                    cout << s << " ";
                cout << endl;
                return 0;
            }
            q.push(nxt);
        }
    }

    cout << -1 << endl; // unreachable (should not happen)
    return 0;
}

Implementation: Backward Greedy

This approach works backwards from the target and produces the forward operation sequence. It is optimal for the operation set $\{+1, -1, \times 2\}$ but may not be optimal when $\div 2$ is also available.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int start, target;
    cin >> start >> target;

    vector<string> revOps; // operations in reverse order
    int cur = target;

    while (cur > start) {
        if (cur % 2 == 0) {
            cur /= 2;
            revOps.push_back("*2");
        } else {
            cur++;
            revOps.push_back("-1");
        }
    }

    // Now cur <= start; need (start - cur) subtract-1 operations
    for (int i = 0; i < start - cur; i++)
        revOps.push_back("-1");

    reverse(revOps.begin(), revOps.end());

    cout << revOps.size() << endl;
    for (auto& s : revOps)
        cout << s << " ";
    cout << endl;

    return 0;
}

Notes

• The BFS approach guarantees optimality for any operation set.

• The backward greedy approach is simpler and runs in $O(\log t)$ time, but is only provably optimal for $\{+1, -1, \times 2\}$.

• For the original IOI constraints, BFS within a bounded range is sufficient.