Hello everyone,

Recently, I was reading about Genetic Algorithms (GA) used in AI training. It sparked an interesting thought: could we apply this concept to Competitive Programming to fish for an AC? I decided to put this to the test on a classic problem: CSES – Elevator Rides.

Problem Summary: There are n people who want to get to the top of a building using a single elevator. You are given the weight of each person and the maximum weight capacity of the elevator. What is the minimum number of elevator rides required? (n <= 16).

With n <= 16, this is obviously a standard Bitmask DP problem. However, just for the sake of experimentation, I decided to solve it using a Genetic Algorithm.

The Core Idea: Permutations as Individuals

Initially, we have n people, where the i-th person has a weight of a[i], and the elevator's capacity is x.

Suppose these n people line up for the elevator in a fixed order (i.e., a permutation P of length n). They enter the elevator strictly in this order. If the next person exceeds the weight limit, they wait for the next ride. We can easily calculate the number of rides for any permutation P using a simple greedy approach:

long long cur = 0, cnt = 1;

for (int i = 1; i <= n; i++) {
    if (cur + a[P[i]] > x) {
        cnt++;       // Overweight, start a new ride
        cur = a[P[i]];  
    } else {
        cur += a[P[i]]; // Add to current ride
    }
}
// 'cnt' is the required number of rides

Our goal is now simplified: Find a permutation P that minimizes cnt.
Generating all permutations is $$$O(n!)$$$ and will definitely result in TLE.

This is where the Genetic Algorithm comes in. Some permutations yield terrible arrangements, while others yield better ones. We can treat each permutation as an "individual" in a population. We will use a fitness function to evaluate how "good" an individual is, select the elite ones, and let them crossover to produce the next generation. We will also introduce random mutations.

Implementation Details

1. Mutation

This is straightforward. I defined a mutation rate X. A permutation P has an X probability of mutating. If it mutates, we randomly select two indices i and j, and simply swap(P[i], P[j]).

2. Crossover

There are many ways to combine two permutations. I used a relatively simple method (similar to Order Crossover):
Assume we want individuals A and B to produce a child C.

• First, randomly select a subarray range [l, r].
• Child C inherits the exact subarray [l, r] from parent A.
• The remaining empty slots in C are filled sequentially using the genes from parent B (skipping elements that are already present in C).

Example:
Crossover A = [5, 4, 3, 2, 1] and B = [1, 2, 3, 4, 5] with range l = 1, r = 3.

• First, C[1..3] = A[1..3], so C = [5, 4, 3, ?, ?].
• We have 2 empty slots left. Iterating through B, the unused numbers are 1 and 2. We place them in the remaining slots.
• The resulting child is C = [5, 4, 3, 1, 2].

3. Fitness Function

This is the most important part. The primary metric is, of course, the number of rides. However, many individuals will require the exact same number of rides, making this metric alone insufficient for natural selection.

To fix this, we need a secondary score: the square of the fill ratio for each elevator ride.
For example, let the capacity be 10. If an individual results in two rides with total weights 10 and 1, the fitness score component would be (10/10)^2 + (1/10)^2.

Why square it? Consider another individual that produces two rides of weights 5 and 6.
If we didn't square the ratios:
(10/10) + (1/10) = (5/10) + (6/10)
The algorithm would treat the [10, 1] arrangement and the [5, 6] arrangement as equally good. But intuitively, [10, 1] is much better because it perfectly packs one ride, leaving more flexible space for the rest. Squaring the ratios heavily rewards rides that are packed to maximum capacity.

Tuning the Parameters

With the logic set, I started submitting and tweaking the hyperparameters:

• Attempt 1: Population = 100, Generations = 500, Mutation Rate = 0.1.
  Result: Not bad for a first try, but Got WA on 4 tests.
• Attempt 2: I realized that instead of hardcoding the number of generations, I should just let it run until it's about to hit the Time Limit. I set it to loop continuously until 0.9s, increased Population to 200, and Mutation Rate to 0.15.
  Result: Improvement, WA on 3 tests.
• Attempt 3: Increased Mutation Rate to 0.4 and Population to 500.
  Result: Only 2 WAs left.
• Attempt 4: I noticed the evaluation and crossover functions are extremely fast. If the population is too small, running too many generations just leads to premature convergence (getting stuck in local optima). I drastically increased the Population to 5000, keeping the 0.9s time limit.
  Result: Accepted!

Conclusion

This was a fun experiment applying randomized heuristics to CP. Obviously, I do not recommend relying on this in strict offline contests where you have no feedback and a single WA can cost you dearly. It took quite a bit of parameter tuning to squeeze out an AC here.

However, when constraints are suddenly bumped up and exact solutions like DP Bitmask TLE, randomized heuristic searches like GA can get some partial points!

The AC code