Stimulated analing 2
IntuitionApproachComplexity
Time complexity: constant time complexity

Space complexity: O(1)
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity: constant time complexity
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(1)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
#include <vector>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <algorithm>
using namespace std;

class Solution {
    // Penalty factor; must be high enough to force duplicates to be rejected.
    const int PENALTY = 10000;
    
    // Return a random double in [0,1)
    double randomDouble() {
        return (double)rand() / (double)RAND_MAX;
    }
    
    // This function performs one run of simulated annealing on grid
    // and returns the sum-of-values (without penalties) of a feasible state.
    int simulatedAnnealing(vector<vector<int>>& grid) {
        int R = grid.size();
        // state[r] is the column index chosen for row r; -1 means “disabled”
        vector<int> state(R, -1);
        // Frequency counts for values in [1,100]
        vector<int> freq(101, 0);
        int enabledCount = 0;    // number of rows with a chosen cell
        int currentSum = 0;      // sum of selected cell values
        int currentPenalty = 0;  // duplicate penalty count
        
        // --- INITIALIZATION ---
        // For each row, randomly decide to pick a column or leave it disabled.
        for (int i = 0; i < R; i++) {
            int cols = grid[i].size();
            if (rand() % 2 == 0) {
                int col = rand() % cols;
                state[i] = col;
                int val = grid[i][col];
                freq[val]++;
                currentSum += val;
                enabledCount++;
            }
        }
        // Ensure at least one row is enabled.
        if (enabledCount == 0) {
            int r = rand() % R;
            int col = rand() % grid[r].size();
            state[r] = col;
            freq[grid[r][col]]++;
            currentSum += grid[r][col];
            enabledCount = 1;
        }
        // Compute initial duplicate penalty.
        for (int v = 1; v <= 100; v++) {
            if (freq[v] > 1)
                currentPenalty += (freq[v] - 1);
        }
        // Our current "energy" (objective) is:
        int currentScore = currentSum - PENALTY * currentPenalty;
        
        // bestScore is recorded only for fully feasible (duplicate–free) states.
        int bestScore = (currentPenalty == 0) ? currentSum : currentScore;
        vector<int> bestState = state;
        
        // --- SIMULATED ANNEALING PARAMETERS ---
        int iterations = 5000;
        double T = 1000.0;
        // Cooling rate chosen so that final temperature is around 1e-6.
        double coolingRate = pow(1e-6 / T, 1.0 / iterations);
        
        // --- MAIN SA LOOP ---
        for (int it = 0; it < iterations; it++) {
            // Pick a random row to modify.
            int r = rand() % R;
            int cols = grid[r].size();
            int oldSel = state[r];
            int newSel;
            // Do not disable if that would leave us with zero enabled rows.
            bool canDisable = true;
            if (oldSel != -1 && enabledCount == 1)
                canDisable = false;
            
            double p = randomDouble();
            if (oldSel != -1) {
                // Row is enabled.
                if (p < 1.0 / cols && canDisable)
                    newSel = -1; // disable this row
                else {
                    // Choose a new column (different from the current one).
                    if (cols == 1) continue; // no alternative exists
                    do {
                        newSel = rand() % cols;
                    } while(newSel == oldSel);
                }
            } else {
                // Row is currently disabled; enable by picking a random column.
                newSel = rand() % cols;
            }
            
            // --- Compute the change (delta) in our state metrics ---
            int deltaSum = 0;
            int deltaPenalty = 0;
            // If the row was enabled, then “removing” its cell:
            if (oldSel != -1) {
                int oldVal = grid[r][oldSel];
                deltaSum -= oldVal;
                // Removing a duplicate: if freq > 1, then removing reduces penalty by 1.
                if (freq[oldVal] > 1)
                    deltaPenalty -= 1;
            }
            // If the row becomes enabled, “adding” its new cell:
            if (newSel != -1) {
                int newVal = grid[r][newSel];
                deltaSum += newVal;
                // If newVal already appears, then adding it increases duplicate count by 1.
                if (freq[newVal] > 0)
                    deltaPenalty += 1;
            }
            
            int deltaScore = deltaSum - PENALTY * deltaPenalty;
            
            // --- Decide whether to accept the move ---
            if (deltaScore >= 0 || exp(deltaScore / T) > randomDouble()) {
                // Apply move: update frequency counts, enabledCount, and state.
                if (oldSel != -1) {
                    int oldVal = grid[r][oldSel];
                    freq[oldVal]--;
                    if (newSel == -1)
                        enabledCount--; // row is now disabled
                }
                if (newSel != -1) {
                    int newVal = grid[r][newSel];
                    freq[newVal]++;
                    if (oldSel == -1)
                        enabledCount++; // row becomes enabled
                }
                state[r] = newSel;
                currentSum += deltaSum;
                currentPenalty += deltaPenalty;
                currentScore += deltaScore;
                
                // If the state is now feasible (no duplicates) and its sum is better, record it.
                if (currentPenalty == 0 && currentSum > bestScore) {
                    bestScore = currentSum;
                    bestState = state;
                }
            }
            
            // Cool down the temperature.
            T *= coolingRate;
        }
        
        // --- Return the final answer ---
        // Since bestState is feasible (each value appears at most once),
        // we simply sum the chosen cells.
        int finalScore = 0;
        for (int i = 0; i < R; i++) {
            if (bestState[i] != -1)
                finalScore += grid[i][bestState[i]];
        }
        return finalScore;
    }
    
public:
    int maxScore(vector<vector<int>>& grid) {
        srand(time(0)); // seed randomness
        
        // Run the simulated annealing several times and record the best result.
        int bestOverallScore = 0;
        int numRuns = 10;  // you can experiment with this value
        for (int run = 0; run < numRuns; run++) {
            int score = simulatedAnnealing(grid);
            bestOverallScore = max(bestOverallScore, score);
        }
        return bestOverallScore;
    }
};

```
['C++']