These are just my personal thoughts on what role a Div2A should play in a contest, based on what I've seen from my own contests and the opinions of my classmates who are newer to Codeforces. Of course, I'm only 1600-rated and haven't written a contest for the larger Codeforces userbase, so my opinion will likely differ from a seasoned GM organizer for Div2s and Div1s. Plus, higher-rated participants probably view A and B problems as less and less interesting, regardless of "quality", due to the (intended) easy difficulty. If you disagree with any of the points I make or have a second opinion, please share them down below!

Most of the points I make don't apply to Educational Round Div2As, since those are specifically tailored to teach concepts important to competitive programming.

Superficially, this just means writing a simple problem, but I also believe that Div2As shouldn't test any algorithmic knowledge beyond what is learned in the standard first-year CS course. (I particularly dislike Div2As that involve XOR or any modular arithmetic beyond simple remainder definitions.)

Regarding the latter point, since Div2As are solved by almost all high-rated participants in a contest (unless your name is rainboy), a Div2A should aim to be "fast" to solve for those who recognize the solution and serve as a momentum and morale booster for the rest of the contest. As silly as it sounds, I believe AC dopamine is a real factor that should be considered by problemsetters — participants undeniably feel much better about a round if they kick things off with a quick 1 minute A solve rather than a tedious "1 minute mental solution + 5 minute coding phase" solve.

As the linked blog post eloquently describes: "Observation means that you stare at some problem for a sufficient amount of time and you are able to reduce it to some easier problem... Despite being rated 3000, the problem is solvable in 30 lines of trivial code." Of course, the above quote describes a much more difficult problem, but the underlying principle applies just as much to Div2As. A good Div2A should require an interesting observation or reduction by the participant, which reduces the problem to a trivial implementation. Note, for example, the highly-regarded 1339A - Filling Diamonds (if you haven't solved it yet — solve it now! It's a Div2A, after all, what are you waiting for?). This problem may appear to be a challenging geometric reasoning task at first — but trace some examples by hand or reason it out mentally, and the clever solution reveals itself as a simple print(input()). I think this is an example of a very good Div2A, and the fact that some people still remember an A problem from a several-year-old contest should speak to its effectiveness.

After all, as with the problem I mentioned at the start of this section, a brute force solution doesn't feel satisfying when it feels like a newbie could have accidentally stumbled on the solution with the simple formula of "if I don't find the answer within the first thousand numbers, it probably doesn't exist." Div2As should be easy, but they shouldn't be free and should involve a bit more thinking on the user's part than a simple "brute force for the first N cases." Of course, this doesn't mean that a brute force should be disallowed; I particularly like problems that involve observations with small constraints, such as 2155A - El fucho, giving the user a sort of "choose your own adventure" solution; try to find the observation that reduces the problem into a trivial implementation, or implement a brute force that will take longer to code but will guarantee the correct answer. (This achieves the dual purpose of avoiding a "roadblock" on a Div2A; if you can't find the observation, you don't have to be frustrated throwing yourself at a wall and instead choose to code the slower but correct brute force to move on.)

Nothing feels worse than a WA that you don't know how to fix — again, an arguably important skill, but a huge morale killer for participants all around. As a contest organizer, I aim to make contests that not only accurately place people based on skill, but also leaves the majority participants feeling satisfied and wanting to participate again, even if they got a bad placement. (In marketing terms — user retention is important!) A Div2A that has the potential to mislead a substantial portion of participants into implementing an incorrect solution is an excellent way to fail that goal.

Amazing
Decent
Average
Bad

Balanced
Too Easy
Too Difficult
Difficulty Spiked Too Much

Balanced
Too Easy
Too Difficult
Difficulty Spiked Too Much

Yes, the suspense is fun
No, transparency is better
No opinion

If PHS sells $$$n$$$ tickets, then they will earn $$$2*n$$$ dollars. So, output $$$2*n$$$.

print(int(input())*2)

Amazing
Decent
Average
Bad
Didn't Solve

If every visitor takes one piece of candy, then $$$a-b=c$$$ must hold. So, output YES if $$$a-b \neq c$$$, and NO otherwise.

a,b,c = map(int, input().split())
if (a-b) == c:
    print("NO")
else:
    print("YES")

Amazing
Decent
Average
Bad
Didn't Solve

Refer to your language's documentation for how to check for the presence of a substring in a string. Note that even though $$$x$$$ is an integer, it is much easier to treat it as a string.

t = int(input())
for _ in range(t):
    num = input()
    print("YES" if "67" in num else "NO")

Amazing
Decent
Average
Bad
Didn't Solve

Note that Polly cannot get more than $$$a+d$$$ Skittles, $$$b+e$$$ Kit Kats, and $$$c+f$$$ Reeses Cups. Additionally, since Polly's candy total cannot change, $$$x$$$ cannot be greater than $$$(a+b+c)/3$$$ floored. So, the answer is the minimum of those four expressions.

t = int(input())
for _ in range(t):
    a,b,c,d,e,f = map(int, input().split())
    print(min((a+b+c)//3, a+d, b+e, c+f))

Amazing
Decent
Average
Bad
Didn't Solve

Note that if $$$n \gt m$$$, it is clearly impossible to give all $$$n$$$ students at least 1 serving of food. Otherwise, it is always possible. One trivial construction is to initially give every student $$$1$$$ serving, and then give all leftover servings to the first student.

t = int(input())
for _ in range(t):
    n,m = map(int, input().split())
    if n > m:
        print(-1)
    else:
        print(m-n+1, end=" ")
        for i in range(1, n):
            print(1, end=" ")
        print()

Amazing
Decent
Average
Bad
Didn't Solve

Assume the starting note is $$$1$$$, and build the song accordingly. Then, find the minimum note frequency in the song, and increase all frequencies in the song by the smallest $$$k$$$ such that the minimum note frequency becomes $$$1$$$.

t = int(input())
for _ in range(t):
    n = int(input())
    a = input()
    b = [1]
    for c in a:
        if c == "0":
            b.append(b[-1]-1)
        else:
            b.append(b[-1]+1)
    
    upshift = 1-min(b)
    for i in range(n+1):
        b[i] += upshift
    
    print(" ".join(map(str, b)))

Amazing
Decent
Average
Bad
Didn't Solve

Note that it is never optimal to move left (except perhaps if all houses are visited and Polly has extra time), since Polly could have just visited the house as she was passing by. So, loop through each house and set it as a "stopping" point, and see how much time Polly has left after moving to that house and visiting that house only. Then, take the maximum-quality houses among the houses Polly passed by (depending on how much time she has left), and add that to her total candy yield.

t = int(input())
for _ in range(t):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))

    best = 0
    for d in range(n):
        time = x - d
        if time <= 0:
            break

        passed = sorted(a[:d+1], reverse=True) # sort houses in range [0, d]
        best = max(best, sum(passed[:min(time, d+1)])) # sum of min(time, d) highest-value houses
    
    print(best)

Amazing
Decent
Average
Bad
Didn't Solve

Note that all nodes are on a distinct "ring" (hexagon), and the only way to move between rings is through one of the six radial lines. So, one way to construct an optimal path is to move onto the right ring, and then choose whichever rotation direction (clockwise or counter-clockwise) reaches the goal node in the shortest time.

Although unintended, building the graph locally and running BFS for each pair is another valid way to solve this problem. (The original harder version of this problem would have had infinitely many hexagons in the spiderweb, but I decided to only use 3 hexagons to simplify the diagram.)

t = int(input())
for _ in range(t):
    a,b = map(int, input().split())

    # Move onto same ring
    path = [a]
    a -= 1
    b -= 1
    if (a//6) != (b//6):
        while (a//6) < (b//6):
            a += 6
            path.append(a+1)
        while (a//6) > (b//6):
            a -= 6
            path.append(a+1)
    
    a += 1
    b += 1

    # Calculate CW and CCW paths
    path1 = path.copy()
    path2 = path.copy()
    temp = a

    while (a % 6) != (b % 6):
        a += 1
        if (a % 6 == 1):
            a -= 6
        path1.append(a)

    a = temp
    while (a % 6) != (b % 6):
        a -= 1
        if (a % 6 == 0):
            a += 6
        path2.append(a)
    
    # Output more optimal path
    if len(path1) < len(path2):
        print(len(path1)-1)
        print(" ".join(map(str, path1)))
    else:
        print(len(path2)-1)
        print(" ".join(map(str, path2)))

Amazing
Decent
Average
Bad
Didn't Solve

How many moves can a game take if played optimally?

Consider proof by induction.

Find a situation where Polly loses on her first turn.

If Polly loses when she increases the strength to 1 on her first turn, then Stanley must win (since Polly can't make any valid starting move that doesn't cause her to lose). Otherwise, Polly can force a win since there must exist an integer $$$X$$$ that Polly can choose to force Stanley to lose on his next turn. (We don't have to find this integer under the constraints of the problem.)

Proof: Since Polly makes a move of $$$X$$$ that doesn't consume all the firewood, then $$$X-1$$$ also does not consume the firewood, and if $$$X$$$ does consume the firewood, then $$$X+1$$$ must also consume the firewood. Let $$$Y$$$ be the first $$$X$$$ where all firewood is consumed on Polly's move. Then, Polly should choose $$$Y-1$$$ as her first move. Then, Stanley will lose on his turn. (If $$$Y$$$ causes a loss, then an increment of $$$Y-1$$$ and then $$$1$$$ will also cause a loss).

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    x = 1
    i = 0
    while i < len(a):
        if x < a[i]:
            break
        x += a[i]
        i += 1
    
    if i == len(a):
        print("Stanley")
    else:
        print("Polly")

Amazing
Decent
Average
Bad
Didn't Solve

For a fixed $$$a+b$$$, which values of $$$a$$$ and $$$b$$$ maximize the score?

What is said maximum score?

0 AND (expr with only ANDs) = 0

If $$$b=0$$$, then the answer is $$$0$$$. If $$$b=1$$$, then the answer is $$$a+b$$$, as we place the OR gate to the left of the last number. (Note that $$$x & y \leq x$$$ for all positive $$$x$$$ and $$$y$$$.)

If $$$b \gt =2$$$, the answer is the smallest number that is one less than a power of two, that is not included in the interval $$$0$$$ to $$$(a+b)$$$. This is trivial to prove for $$$b \gt =3$$$, since we can surround the largest number with a bitstring of all $$$1$$$s and the number directly after it (which contains a $$$1$$$ in the leftmost bit). For $$$b=2$$$, note that we can surround the last occurrence of an all-1 bitstring in the interval with ORs and achieve the same result, since the expression to the right will have a 1 in its leftmost bit.

t = int(input())
for _ in range(t):
    a,b = map(int, input().split())
    n = a+b
    ans = 0

    if b == 0:
        pass
    elif b == 1:
        ans = n
    else:
        ans = 2
        while (ans-1) < n:
            ans*=2
        ans -= 1
        
    print(ans)

Amazing
Decent
Average
Bad
Didn't Solve

When is the answer $$$1$$$?

Imagine a checkerboard.

Note that if the tree is directly adjacent to the starting cell $$$(1, 1)$$$, then the answer is $$$1$$$, since any path longer than $$$1$$$ must exit the starting cell through either $$$(1, 2)$$$ or $$$(2, 1)$$$ and re-enter through the other.

Otherwise, view the plot as an $$$n$$$ by $$$n$$$ checkerboard with the starting cell colored white, and count the number of unoccupied white and black cells. Since any valid path (longer than 1) must visit an equal number of black and white cells, the answer is $$$\min(w, b) * 2$$$.

As a bonus, try to construct such a path. It can be shown that such a path can always be constructed.

t = int(input())
for _ in range(t):
    n,x,y = map(int,input().split())
    if n == 2 or (x == 1 and y == 2) or (x == 2 and y == 1):
        print(1)
    else:
        white = (n*n)//2
        black = white
        if n%2 == 1:
            white += 1
        
        if (x+y)%2 == 0:
            white -= 1
        else:
            black -= 1
        
        print(2*min(white, black))

Amazing
Decent
Average
Bad
Didn't Solve

A continuous segment of symbols of length $$$n$$$ contains $$$(n-2)(n-1)/2$$$ patterns.

We should only flip bits that are at the end of a continuous segment of symbols.

Instead of counting every pattern, note that a continuous segment of symbols of length $$$n$$$ contains $$$(n-2)(n-1)/2$$$ patterns. Patterns cannot contain symbols of different types, so to calculate the base score, it is enough to calculate the score for each continuous segment of symbols.

Also, note that it is always optimal to change bits that are at the "end" of a continuous segment of symbols. (Otherwise, Stanley would be splitting a segment into two segments, which would cause a decrease in his score.)

To efficiently check the score after flipping each endpoint, precompute the score of each segment, and store the base score. Then, for each flipped symbol, calculate the change in the score caused by the flip. (This is efficient because each flip can affect the length at most three continuous segments.)

The final answer is the maximum change across all flips (including no flip, which changes the score by $$$0$$$), added to the base score.

t = int(input())

for _ in range(t):
    n = int(input())
    a = input()

    b = []
    last = a[0]
    count = 0
    for i in range(n):
        if a[i] == last:
            count += 1
        else:
            b.append(count)
            last = a[i]
            count = 1
    b.append(count)

    base = 0
    for i in b:
        if i >= 3:
            base += (i - 2) * (i - 1) // 2

    bestd = 0
    ni = len(b)
    
    for i in range(ni - 1):
        delta = 0
        if b[i + 1] > 1:
            if b[i + 1] >= 3:
                delta -= (b[i + 1] - 2)
            delta += b[i] - 1
        else:
            if i < ni - 2:
                delta -= (b[i] - 2) * (b[i] - 1) // 2
                delta -= (b[i + 2] - 2) * (b[i + 2] - 1) // 2
                delta += (b[i] + b[i + 2] - 1) * (b[i] + b[i + 2]) // 2
            else:
                delta += b[i] - 1
        bestd = max(bestd, delta)

    for i in range(1, ni):
        delta = 0
        if b[i - 1] > 1:
            if b[i - 1] >= 3:
                delta -= (b[i - 1] - 2)
            delta += b[i] - 1
        else:
            if i > 1:
                delta -= (b[i] - 2) * (b[i] - 1) // 2
                delta -= (b[i - 2] - 2) * (b[i - 2] - 1) // 2
                delta += (b[i] + b[i - 2] - 1) * (b[i] + b[i - 2]) // 2
            else:
                delta += b[i] - 1
        bestd = max(bestd, delta)

    print(base+bestd)

Amazing
Decent
Average
Bad
Didn't Solve

What information is preserved?

Solve the problem for a 10-digit combination.

$$$N \lt = 300$$$ is the effective constraint on the intended solution.

We can use the frequency of each digit to encode a digit in the original combination. So, the number of zeros in the encoding is the first digit, the number of ones in the encoding is the second digit, and so on. To deal with the 11th and 12th digits, one way is to multiply their frequencies by 10 and add them to the zero and one counts. For example, if there were 67 zeros in our encoding, we'd interpret that as the first digit being 7 and the eleventh digit being 6.

For 000000000000, to avoid outputting an empty line, instead output an otherwise nonsensical encoding (such as 333 zeroes), and check for that specific case in the decoder.

I actually didn't think of this solution. Such is the beauty of an open-ended interactive problem!

Since $$$16^{10} \gt 10^{12}$$$, we can encrypt the original combination in hexadecimal. Then, our encoding can use the frequencies of each digit to encode a 10-digit hexadecimal number.

def encode(a):
    counts = [0] * 10
    for i in range(12):
        if i >= 10:
            counts[i % 10] += 10 * (int(a[i]) - int('0'))
        else:
            counts[i] = int(a[i]) - int('0')

    if a == "000000000000":
        counts[0] = 100

    for i in range(10):
        for j in range(counts[i]):
            print(i, end="")
    print()

def decode(a):
    counts = [0] * 10
    for c in a:
        counts[int(c)] += 1

    if counts[0] == 100:
        print("000000000000")
        return

    ans = [0] * 12
    for i in range(10):
        ans[i] = counts[i] % 10
    ans[10] = counts[0] // 10
    ans[11] = counts[1] // 10
    for x in ans:
        print(x, end="")
    print()

mode = input()
n = int(input())
for _ in range(n):
    a = input().strip()
    if mode == "encode":
        encode(a)
    elif mode == "decode":
        decode(a)

Amazing
Decent
Average
Bad
Didn't Solve

Given a $$$k$$$, how can we efficiently check if every cell is lit up?

Let $$$f(k)$$$ return whether the grid is lit up for a given $$$k$$$. $$$f(k)$$$ is monotonic.

To find the minimum necessary $$$k$$$, we can binary search for the smallest value that lights up the entire grid. So, now the problem is to efficiently check whether the grid is lit up for a given $$$k$$$, since checking all $$$10^8$$$ cells is too slow.

Well, instead of going cell-by-cell, how about going column-by-column? For column $$$c$$$ and generator strength $$$k$$$, note that a lamp at $$$(x, y)$$$ does not light up any cells in the column if $$$|y-c| \geq k$$$. Otherwise, the lamp must light up all cells $$$(a, c)$$$ in the column where $$$x - (k - |y - c|) \lt a \lt x + (k - |y-c|)$$$. Now, we simply need to check if the intervals covered by each lamp fully light up the column, which can be done in $$$O(m \log m)$$$. This means we can check the entire grid for a given $$$k$$$ in $$$O(nm \log m)$$$. For $$$\log n$$$ queries for $$$k$$$ from binary search, this gives a final time complexity of $$$O(nm \log(n+m))$$$.

A similar approach can be used to check row-by-row instead, with identical time complexity.

Another solution is to binary search for the smallest $$$k$$$ for each column, where the maximum across all columns is the final answer. Code for this solution is given below.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
using pairll = pair<ll, ll>;

#define io_optimize() ios::sync_with_stdio(0); cin.tie(0);

bool islit(ll n, ll m, ll row, ll k, const vector<pairll>& towers) {
    vector<pairll> segs;
    for (pairll t : towers) {
        ll dy = abs(t.second-row);
        if (dy >= k) continue; // out of range
        ll diff = k-dy-1;
        segs.push_back({t.first-diff,t.first+diff});
    }

    if (segs.size() == 0) return false;
    
    sort(segs.begin(), segs.end()); // by left endpoint
    if (segs[0].first > 0) return false; // non-lit at left
    ll r = segs[0].second;
    for (pairll seg : segs) {
        if (seg.first > (r+1)) break; // break on gap
        r = max(r, seg.second);
    }

    if (r >= (n-1)) return true; // lit from 0 to n-1
    return false;
}

int main() {
    io_optimize();
    
    int t;
    cin >> t;
    for (int _ = 0; _ < t; _++) {
        ll n, m;
        cin >> n >> m;
        vector<pairll> towers(m);

        for (ll i = 0; i < m; i++) {
            ll x, y;
            cin >> x >> y;
            x--;
            y--;
            towers[i] = {x, y};
        }

        ll ans = 0;
        for (ll r = 0; r < n; r++) {
            ll lk = 0;
            ll rk = 2*n-1;
            while (lk < rk) {
                ll mk = lk + (rk-lk)/2;
                if (islit(n, m, r, mk, towers)) rk = mk;
                else lk = mk+1;
            }

            ans = max(ans, lk);
        }

        cout << ans << endl;
    }
}

Amazing
Decent
Average
Bad
Didn't Solve

Which ghost should Stanley steal from each turn?

What is the state of Polly's ghosts after she splits and Stanley takes his turn?

When should Polly start choosing pairs of ghosts instead of splitting?

Note that it is always optimal for Polly to split a ghost as evenly as possible, and for Stanley to steal from the ghost with the most spirits. Polly should also avoid choosing a pair of ghosts to add to until she has enough ghosts to win ($$$6*{ghosts} + 5 \geq x$$$), unless she needs a ghost with more than one spirit in order to split.

From there, a recursive implementation will pass under the constraints, keeping track of Stanley's total and the highest-value ghost that Polly has, along with the total number of ghosts. (Note that we don't need to keep track of all ghosts, because all but one of them will be holding $1$s due to Stanley stealing, until Polly decides to start adding pairs.)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define io_optimize() ios::sync_with_stdio(0); cin.tie(0);

void solve(ll ghosts, ll highest, ll stanley, ll goal, ll round) {
    // Assume Calvin has 1,1,1,1,...,1,highest
    // (It can be shown that this is always optimal for Calvin)

    //cerr << ghosts << " " << highest << " " << stanley << " " << goal << " " << round << endl;
    if (stanley >= goal) {
        // Stanley won on his turn last round
        cout << "Stanley " << endl << (round-1) << endl;
    } else if (ghosts == 1) {
        // Stanley cannot win off of Calvin's first move, so no need to check
        solve(ghosts+1, highest/2, stanley + (highest-1)/2, goal, round+1);
    } else if (highest + 10 + ghosts - 1 >= goal) {
        // Calvin can immediately choose a pair and +5 +5 to win
        cout << "Calvin " << endl << round << endl;
    } else {
        if (6*ghosts + 5 >= goal) {
            // if we're here, note that we cannot win from a single +5/+5

            // ignore the base 1s in this calculation (5 10s instead of 6 11s, easier)
            ll needed = goal - ghosts; 
            ll turns = 0;
            ll stanleydelta = 0;

            // who wins first
            if (highest >= 6) {
                // Calvin immediately wins on his final +10, otherwise we net +5 every turn
                // Note that Calvin also starts with +10, since Stanley will spend his turn stealing from highest
                // (This does not win for Stanley, see first comment of parent "if")

                // add 10, stanley takes highest-1
                needed-=10;
                stanleydelta+=(highest-1);

                // inefficient but fine in the slow sol
                while (needed > 10) {
                    needed-=5;
                    stanleydelta+=5;
                    turns++;
                }

                // Calvin wins on this turn
                if (stanley + stanleydelta < goal) {
                    cout << "Calvin" << endl << (round+turns) << endl;
                    return;
                }
            } else {
                // Calvin immediately wins on his final +10, otherwise we net +5 every turn
                // In this case, highest is left alone unless Calvin +5s on it
                
                needed -= (highest-1);
                ll gleft = ghosts-1;
                while (needed > 10) {
                    if (gleft == 1) {
                        // we dont win when +10
                        needed -= 10;
                        needed += (5 + highest - 1);
                        stanleydelta += (5 + highest - 1);
                    } else {
                        needed -= 5;
                        stanleydelta += 5;
                    }
                    gleft--;
                    turns++;
                }

                // Calvin wins on this turn
                if (stanley + stanleydelta < goal) {
                    cout << "Calvin" << endl << (round+turns) << endl;
                    return;
                }
            }

            // If doing so would hand a win to Stanley, then he will delay
            // Note that at this point, it can be shown that it is impossible for Calvin to win
            // So, he will "stall" as long as possible
            if (highest == 1) {
                // O(1) calculation to determine how much Calvin can stall

                // Every 3 turns
                // 1 1 -> 1 6 (+5) -> 1 1 3 (+7) -> 1 1 1 1 (+8)
                ll stanleyleft = goal - stanley;
                ll stall = 3 * (stanleyleft/8);
                stanleyleft %= 8;
                if (stanleyleft > 5) stall+=2;
                else if (stanleyleft != 0) stall += 1;

                cout << "Stanley " << endl << (round+stall-1) << endl;
            } else {
                // Highest/2 with each iteration, so efficient
                solve(ghosts+1, highest/2, stanley + (highest-1)/2, goal, round+1);
            }
        } else {
            if (highest == 1) {
                // Calvin is forced to +5 + 5
                solve(ghosts, 6, stanley+5, goal, round+1);
            } else {
                solve(ghosts+1, highest/2, stanley + (highest-1)/2, goal, round+1);
            } 
        }
    }
}

int main() {
    io_optimize();
    // io_file("input.txt", "output.txt");

    // ----- WRITE CODE HERE ----- //
    int t;
    cin >> t;
    for (int _ = 0; _ < t; _++) {
        ll n, x;
        cin >> n >> x;
        //cerr << "test case " << n << " " << x << endl;
        solve(1, n, 0, x, 1);
    }
}

Amazing
Decent
Average
Bad
Didn't Solve

Treat each encoding as being sorted rather than shuffled.

Besides the digits themselves, there is one more piece of information that is preserved during a shuffle (or sort).

Treat each encoding as being sorted rather than shuffled. We can now assign an ordering number to each sorted arrangement. Note that because we don't need to use all 67 trees, we can encode additional information via the length of our encoding. Via stars-and-bars and combinations, we have enough possible sorted arrangements to assign each an ordering number from 1 to $$$10^{12}$$$. Now, all one needs to do is to write a function that determines what ordering number corresponds to a sorted arrangement. This can be done by going left-to-right through the sorted encoding and using combinations to count how many sorted orderings are lexographically less than the given encoding.

from math import comb

def encode(a):
    assert len(a) == 12

    num = int(a) + 1
    x = 0

    digits = 1
    next_comb = comb(digits + 9, 9)
    while x + next_comb < num:
        digits += 1
        x += next_comb
        next_comb = comb(digits + 9, 9)

    assert digits <= 67

    i = 0
    for d in range(digits, 0, -1):
        next_comb = comb(d - 1 + 9 - i, 9 - i)
        while x + next_comb < num:
            i += 1
            x += next_comb
            next_comb = comb(d - 1 + 9 - i, 9 - i)
        print(i, end='')
    print()

def decode(a):
    a = sorted(a)

    x = 0
    i = 0

    digits = len(a)
    assert digits <= 67
    for d in range(1, digits):
        next_comb = comb(d + 9, 9)
        x += next_comb

    for d in range(digits, 0, -1):
        val = int(a[digits - d])
        while i < val:
            next_comb = comb(d - 1 + 9 - i, 9 - i)
            x += next_comb
            i += 1

    print(f"{x:012}")

mode = input().strip()
n = int(input().strip())
for _ in range(n):
    a = input().strip()
    if mode == "encode":
        encode(a)
    elif mode == "decode":
        decode(a)

Amazing
Decent
Average
Bad
Didn't Solve

Moving left is never optimal.

When should Polly change costumes?

Read the editorial for the Standard Division version of this problem. A similar "stopping point" approach works here, but what does the stopping point signify this time?

Our stopping point is the only house Polly should change costumes at.

The stopping point should be a cumulative maximum of all houses Polly has visited so far.

How should Polly use her leftover time?

Placeholder

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

/* one-indexed */
struct Fenwick {
    vector<ll> bits;
    ll n;

    Fenwick(ll n) { 
        this->n = n;
        bits.assign(n+1, 0);
    }

    void add(ll idx, ll val) {
        for (; idx <= n; idx += idx & -idx) bits[idx] += val;
    }
    
    ll sum(ll idx) {
        ll res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bits[idx];
        return res;
    }

    ll revsum(ll idx) {
        if (idx <= 0) return -1;
        return sum(n) - sum(idx-1);
    }
};

#define io_optimize() ios::sync_with_stdio(0); cin.tie(0);
const ll maxQual = 1e4;

int main() {
    io_optimize();

    int t;
    cin >> t;
    for (int _ = 0; _ < t; _++) {
        ll n, x;
        cin >> n >> x;
        vector<ll> a(n);
        for (ll i = 0; i < n; i++) cin >> a[i];

        Fenwick csum(maxQual);
        Fenwick ccnt(maxQual);

        ll best = 0;
        ll curmax = 0;
        for (ll i = 0; i < n; i++) {
            // optimal solution repeats at a prefix max
            if (a[i] <= curmax) {
                csum.add(a[i], a[i]);
                ccnt.add(a[i], 1);
                continue;
            }
            curmax = a[i];

            // stopping at i
            ll score = 0;
            ll time = 0;
            
            // movement + first claim
            time += (i+1);
            score += a[i];
            ll left = x - time;

            if (left < 0) break;

            ll req = (a[i]/2) + 1; // minimum quality to consider visiting
            ll psum = csum.revsum(req);
            ll pcnt = ccnt.revsum(req);

            if (pcnt > left) {
                // find smallest req (> baseline) such that ccnt.revsum(req) <= left

                ll lo = req;
                ll hi = a[i];

                while (lo < hi) {
                    ll mid = (lo+hi)/2;
                    if (ccnt.revsum(mid) > left) {
                        lo = mid+1;
                    } else if (ccnt.revsum(mid) <= left) {
                        hi = mid;
                    }
                }

                req = lo;
                psum = csum.revsum(req);
                pcnt = ccnt.revsum(req);
                // todo: compensate for partial sum?
            }

            ll margin = left - pcnt;
            if (margin % 2 == 0) {
                // always optimal to choose these, and use remainders to cleanly get repeats
                
                // check if we can partially use the "next highest house"
                // i.e. 5 5 5 5 5 6 with x = 10
                if (req > (a[i]/2 + 1)) {
                    ll cand = req-1;
                    // note that due to how we choose req, we don't have the margin to choose EVERY house with quality cand
                    // instead, we choose as many as we can
                    psum += cand*margin;
                    margin = 0;
                }


                score += psum;
                score += (margin/2)*a[i];
            } else {
                // case 1: visit 1 more house
                // case 2: visit 1 less house, get 1 more repetition
                score += psum;
                score += ((margin-1)/2)*a[i];

                //cout << i << " ";
                //cout << score << " " << margin << endl;

                // case 1
                // binary search for last candidate such that ccnt.revsum(cand) > pcnt; that's the next highest house
                // note that there may be multiple of these! (see the pcnt > left binsearch at the start)
                // however, an optimal solution won't take ALL of these, because we'd either run out of time
                // or at least tie by taking repetitions of stopping point instead
                ll temp1 = score;

                ll lo = 1;
                ll hi = req;
                while (lo < hi) {
                    ll mid = (lo+hi+1)/2;
                    if (ccnt.revsum(mid) > pcnt) {
                        lo = mid;
                    } else if (ccnt.revsum(mid) <= pcnt) {
                        hi = mid-1;
                    }
                }
                ll cand = lo;

                if (ccnt.revsum(cand) > pcnt) {
                    // a "next highest house" exists
                    ll candcnt = ccnt.revsum(cand) - pcnt;
                    temp1 += cand;
                    candcnt--;
                    if (candcnt > 0 && (cand * 2 > a[i])) {
                        ll reps = (margin-1)/2;
                        temp1 -= min(reps, candcnt/2)*a[i];
                        temp1 += min(reps, candcnt/2)*2*cand;
                    }
                } else {
                    // a "next highest house" doesn't exist
                    // case 2 will be better in this case
                    // (unless first element, in which score is the answer)
                }

                // case 2
                // find the smallest candidate such that ccnt.revsum(cand) < pcnt; (cand-1) is the smallest house
                ll temp2 = score;

                lo = req;
                hi = a[i];
                while (lo < hi) {
                    ll mid = (lo+hi)/2;
                    if (ccnt.revsum(mid) >= pcnt) {
                        lo = mid+1;
                    } else if (ccnt.revsum(mid) < pcnt) {
                        hi = mid;
                    }
                }
                cand = lo-1;
                
                if (pcnt == 0) {
                    // we never picked anything in the first place
                    // case 1 will be better in this case
                    // (unless first element, in which score is the answer)
                } else if (ccnt.revsum(cand+1) < pcnt) {
                    // exists
                    temp2 -= cand;
                    temp2 += a[i];
                }
                
                
                score = max(temp1, temp2);
            }

            csum.add(a[i], a[i]);
            ccnt.add(a[i], 1);

            best = max(score, best);
        }
        cout << best << endl;
    }
}

Amazing
Decent
Average
Bad
Didn't Solve