ICPC 2023 Online Spring Challenge powered by Huawei

HybridStrategy.cs

public class HybridStrategy : SingleStrategy
{
    public HybridStrategy(Tenant tenant, int qSize = -1) : base(tenant, qSize) { }
    public override CachingStrategy CloneStrategy(CachingStrategy s)
    {
        CachingStrategy result = new HybridStrategy(s.Tenant);
        result.CopyCache(s, this);
        return result;
    }

    public override void ProtocolAccess(int pageId) => Scores[pageId] = Tenant.PageFreq[pageId] + 3e-3 * Solution.Time;
    public override string GetName() => nameof(HybridStrategy);
}

LeastFrequentStrategy

public class LeastFrequentStrategy : SingleStrategy
{
    public LeastFrequentStrategy(Tenant tenant, int qSize = -1) : base(tenant, qSize) { }
    public override CachingStrategy CloneStrategy(CachingStrategy s)
    {
        CachingStrategy result = new LeastFrequentStrategy(s.Tenant);
        result.CopyCache(s, this);
        return result;
    }

    public override void ProtocolAccess(int pageId) => Scores[pageId] = Tenant.PageFreq[pageId] + 1e-9 * Solution.Time;
    public override string GetName() => nameof(LeastFrequentStrategy);
}

LeastFrequentXStrategy.cs

using System.Collections.Generic;

public class LeastFrequentXStrategy : SingleStrategy
{
    private int factor;
    private int[] FreqX;
    private Queue<int> queue = new();
    public LeastFrequentXStrategy(Tenant tenant, int factor) : base(tenant, -1)
    {
        this.factor = factor;
        FreqX = new int[tenant.DatabaseSize];
    }
    public override CachingStrategy CloneStrategy(CachingStrategy s)
    {
        CachingStrategy result = new LeastFrequentXStrategy(s.Tenant, factor);
        result.CopyCache(s, this);
        return result;
    }

    int lastAccess = -1;
    public override void ProtocolAccess(int pageId)
    {
        if (lastAccess == Solution.Time) return;
        lastAccess = Solution.Time;
        queue.Enqueue(pageId);
        FreqX[pageId]++;
        Scores[pageId] = FreqX[pageId] + 1e-9 * Solution.Time;
        while (queue.Count > QTarget * factor)
        {
            int p = queue.Dequeue();
            FreqX[p]--;
            Scores[p] = FreqX[p] + 1e-9 * Solution.Time;
            if (HasCached(p)) CacheTree.Update(PagePos[p], Scores[p]);
        }
    }

    public override string GetName() => nameof(LeastFrequentXStrategy) + factor;
}

LeastRecentStrategy.cs

public class LeastRecentStrategy : SingleStrategy
{
    public LeastRecentStrategy(Tenant tenant, int qSize = -1) : base(tenant, qSize) { }
    public override CachingStrategy CloneStrategy(CachingStrategy s)
    {
        CachingStrategy result = new LeastRecentStrategy(s.Tenant);
        result.CopyCache(s, this);
        return result;
    }

    public override void ProtocolAccess(int pageId) => Scores[pageId] = Solution.Time;
    public override string GetName() => nameof(LeastRecentStrategy);
}

MinSegmentTree.cs

using System;

// https://cp-algorithms.com/data_structures/segment_tree.html
public class MinSegmentTree
{
    public int Size;
    private (double val, int index)[] Data;

    public MinSegmentTree(int size, double initialValue)
    {
        this.Size = size;
        Data = new (double, int)[4 * size];
        for (int i = 0; i < size; i++) Update(i, initialValue);
    }

    private (double value, int index) Min(int v, int tl, int tr, int l, int r)
    {
        if (l > r) return (1e9, -1);
        if (l == tl && r == tr) return Data[v];
        int tm = (tl + tr) / 2;
        var a = Min(v * 2, tl, tm, l, Math.Min(r, tm));
        var b = Min(v * 2 + 1, tm + 1, tr, Math.Max(l, tm + 1), r);
        if (a.value < b.value) return a;
        return b;
    }

    public (double value, int index) Min() => Min(1, 0, Size - 1, 0, Size - 1);

    private void Update(int v, int tl, int tr, int pos, double newVal)
    {
        if (tl == tr) Data[v] = (newVal, pos);
        else
        {
            int tm = (tl + tr) / 2;
            if (pos <= tm) Update(v * 2, tl, tm, pos, newVal);
            else Update(v * 2 + 1, tm + 1, tr, pos, newVal);
            if (Data[2 * v].val < Data[2 * v + 1].val) Data[v] = Data[2 * v];
            else Data[v] = Data[2 * v + 1];
        }
    }

    public void Update(int pos, double newVal) => Update(1, 0, Size - 1, pos, newVal);
}

MostFrequentStrategy.cs

public class MostFrequentStrategy : SingleStrategy
{
    public MostFrequentStrategy(Tenant tenant, int qSize = -1) : base(tenant, qSize) { }
    public override CachingStrategy CloneStrategy(CachingStrategy s)
    {
        CachingStrategy result = new MostFrequentStrategy(s.Tenant);
        result.CopyCache(s, this);
        return result;
    }

    public override void ProtocolAccess(int pageId) => Scores[pageId] = -Tenant.PageFreq[pageId] - 1e-9 * Solution.Time;
    public override string GetName() => nameof(MostFrequentStrategy);
}

MostRecentStrategy.cs

public class MostRecentStrategy : SingleStrategy
{
    public MostRecentStrategy(Tenant tenant, int qSize = -1) : base(tenant, qSize) { }
    public override CachingStrategy CloneStrategy(CachingStrategy s)
    {
        CachingStrategy result = new MostRecentStrategy(s.Tenant);
        result.CopyCache(s, this);
        return result;
    }

    public override void ProtocolAccess(int pageId) => Scores[pageId] = 1000000 - Solution.Time;
    public override string GetName() => nameof(MostRecentStrategy);
}

Segmented_LRU_LFU_Strategy.cs

using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

public class Segmented_LRU_LFU_Strategy : CachingStrategy
{
    public SingleStrategy[] Segments = new SingleStrategy[2];
    public Segmented_LRU_LFU_Strategy(Tenant t) : base(t)
    {
        Segments[0] = new LeastRecentStrategy(t);
        Segments[1] = new LeastFrequentStrategy(t);
    }

    public override bool HasCached(int pageId) => Segments.Any(s => s.HasCached(pageId));

    public override void ProtocolAccess(int pageId)
    {
        foreach (CachingStrategy s in Segments) s.ProtocolAccess(pageId);
    }

    public override string GetName() => nameof(Segmented_LRU_LFU_Strategy);

    public override bool Update(int pageId)
    {
        ProtocolAccess(pageId);
        if (Segments[0].HasCached(pageId))
        {
            Segments[0].Update(pageId);
            HitsCount++;
            return true;
        }
        if (Segments[1].HasCached(pageId))
        {
            Segments[1].Update(pageId);
            HitsCount++;
            // TODO move back to segments[0]?
            return true;
        }

        if (Segments[0].QCurrent < Segments[0].QTarget) Segments[0].Update(pageId);
        else
        {
            int shift = Segments[0].MinPage();
            Segments[0].Update(pageId);
            if (shift != -1) Segments[1].Update(shift);
        }
        QCurrent = Segments[0].QCurrent + Segments[1].QCurrent;
        return false;
    }

    public override int MinPage() => Segments[1].MinPage();

    public override void Shrink()
    {
        QTarget--;
        if (QCurrent <= QTarget) return;
        if (Segments[0].QCurrent < Segments[0].QTarget) Segments[0].Shrink();
        else if (Segments[1].QCurrent < Segments[1].QTarget) Segments[1].Shrink();
        else if (3 * Segments[0].QTarget > Segments[1].QTarget)
        {
            int shift = Segments[0].MinPage();
            Segments[0].Shrink();
            Segments[1].Update(shift);
        }
        else Segments[1].Shrink();
        QCurrent = Segments[0].QCurrent + Segments[1].QCurrent;
    }

    public override void Grow(int pageId)
    {
        QTarget++;
        if (QTarget <= Q)
        {
            if (3 * Segments[0].QTarget <= Segments[1].QTarget) Segments[0].QTarget++;
            else Segments[1].QTarget++;
        }
        Update(pageId);
    }

    public override CachingStrategy CloneStrategy(CachingStrategy s)
    {
        CachingStrategy result = new Segmented_LRU_LFU_Strategy(s.Tenant);
        result.CopyCache(s, this);
        return result;
    }

    public override void CopyCache(CachingStrategy cache, CachingStrategy winning)
    {
        Segments[0].Scores = Tenant.Strategies.OfType<LeastRecentStrategy>().First().Scores;
        Segments[1].Scores = Tenant.Strategies.OfType<LeastFrequentStrategy>().First().Scores;
        QTarget = cache.QTarget;
        QCurrent = cache.QCurrent;
        List<int> cached = cache.GetCache().OrderByDescending(c => Segments[0].Scores[c]).ToList();
        for (int i = 0; i < (cached.Count + 3) / 4; i++) Segments[0].Grow(cached[i]);
        for (int i = (cached.Count + 3) / 4; i < cached.Count; i++) Segments[1].Grow(cached[i]);
    }
}

SingleStrategy.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;

public abstract class SingleStrategy : CachingStrategy
{
    public MinSegmentTree CacheTree;
    public double[] Scores;
    public int[] PagePos;
    public int[] PagePosReverse;
    public Stack<int> free = new();

    public SingleStrategy(Tenant tenant, int qSize = -1) : base(tenant)
    {
        int q = qSize == -1 ? tenant.QMax : tenant.QBase;
        CacheTree = new MinSegmentTree(q, double.PositiveInfinity);
        Scores = new double[tenant.DatabaseSize];
        PagePos = new int[tenant.DatabaseSize];
        PagePosReverse = new int[tenant.DatabaseSize];
        Array.Fill(PagePos, -1);
        Array.Fill(PagePosReverse, -1);
        for (int i = 0; i < q; i++) free.Push(i);
    }

    public override int MinPage() => PagePosReverse[CacheTree.Min().index];
    public override bool HasCached(int pageId) => PagePos[pageId] != -1;


    protected int Evict()
    {
        QCurrent--;
        var min = CacheTree.Min();
        CacheTree.Update(min.index, double.PositiveInfinity);
        int page = PagePosReverse[min.index];
        PagePos[page] = -1;
        PagePosReverse[min.index] = -1;
        return min.index;
    }

    public void SetValue(int pageId, double value)
    {
        CacheTree.Update(PagePos[pageId], value);
    }

    public void EvictPage(int pageId)
    {
        QCurrent--;
        int pos = PagePos[pageId];
        CacheTree.Update(pos, double.PositiveInfinity);
        free.Push(pos);
        PagePos[pageId] = -1;
        PagePosReverse[pos] = -1;
    }

    public override bool Update(int pageId)
    {
        ProtocolAccess(pageId);
        if (HasCached(pageId))
        {
            HitsCount++;
            CacheTree.Update(PagePos[pageId], Scores[pageId]);
            return true;
        }
        else
        {
            AddPage(pageId);
            return false;
        }
    }

    private void AddPage(int pageId)
    {
        int insertPos = QCurrent < Q ? free.Pop() : Evict();
        QCurrent++;
        CacheTree.Update(insertPos, Scores[pageId]);
        PagePos[pageId] = insertPos;
        PagePosReverse[insertPos] = pageId;
    }

    public override void Shrink()
    {
        QTarget--;
        if (QCurrent > QTarget) free.Push(Evict());
    }

    public override void Grow(int pageId)
    {
        QTarget++;
        Update(pageId);
    }

    public override void CopyCache(CachingStrategy cache, CachingStrategy winning)
    {
        Scores = (winning as SingleStrategy).Scores;
        QTarget = cache.QTarget;
        foreach (int pageId in cache.GetCache()) AddPage(pageId);
    }
}

Solution.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading;

public class Solution
{
    public static Tenant[] Tenants;
    public static int[] PagePos;
    public static int[] PagePosReverse;
    public static int Time;
    public static int QueryCount;
    public static int BufferSize;
    public static Queue<int> FreeCells = new();

    public static void Main(string[] args)
    {
        //Generate();
        Solve();
    }

    private static (int tenant, int page) ParseQuery()
    {
        string line = Console.ReadLine();
        int tenant = 0, page = 0;
        int pos = 0;
        while (line[pos] != ' ') { tenant *= 10; tenant += line[pos] - '0'; pos++; }
        pos++;
        while (pos < line.Length) { page *= 10; page += line[pos] - '0'; pos++; }
        return (tenant - 1, page - 1);
    }

    private static void Solve()
    {
        int[] nums = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int tenantCount = nums[0];
        BufferSize = nums[1];
        QueryCount = nums[2];

        Tenants = Enumerable.Range(0, tenantCount).Select(i => new Tenant(i)).ToArray();
        nums = Console.ReadLine().Split().Select(int.Parse).ToArray();
        for (int i = 0; i < tenantCount; i++) Tenants[i].Priority = nums[i];
        nums = Console.ReadLine().Split().Select(int.Parse).ToArray();
        for (int i = 0; i < tenantCount; i++) Tenants[i].DatabaseSize = nums[i];
        nums = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int offset = 0;
        for (int i = 0; i < tenantCount; i++)
        {
            Tenants[i].QMin = nums[3 * i];
            Tenants[i].QBase = nums[3 * i + 1];
            Tenants[i].QMax = nums[3 * i + 2];
            Tenants[i].Offset = offset;
            offset += Tenants[i].DatabaseSize;
        }
        Validator validator = new();
        double scale = (double)BufferSize / Tenants.Sum(t => t.QBase);
        foreach (Tenant t in Tenants)
        {
            t.QExpected = Math.Max(t.QMin, Math.Min(t.QMax, (int)(t.QMin * scale)));
        }

        PagePos = new int[Tenants.Sum(t => t.DatabaseSize)];
        PagePosReverse = new int[Tenants.Sum(t => t.DatabaseSize)];
        Array.Fill(PagePos, -1);
        Array.Fill(PagePosReverse, -1);
        foreach (Tenant t in Tenants) t.Init();
        for (int i = 0; i < BufferSize; i++) FreeCells.Enqueue(i);

        List<int> logTimes = new();
        for (Time = 1; Time <= QueryCount; Time++)
        {
            (int tenantId, int pageId) = ParseQuery();
            int action = Tenants[tenantId].Store(pageId);
#if DEBUG
            validator.Validate(tenantId, pageId, action);
            if (Time % 100 == 0)
            {
                logTimes.Add(Time);
                foreach (Tenant t in Tenants) t.LogState();
            }
#else
            Console.WriteLine(action + 1);
#endif
        }
#if DEBUG
        validator.ValidateBuffer();
#endif

        Console.Error.WriteLine($"BufferSize:{BufferSize}\tQueries:{QueryCount}\tTenants:{tenantCount}\tPenalty: {Tenants.Sum(t => t.Score())}");
        foreach (Tenant t in Tenants)
        {
            Console.Error.WriteLine(t.GetStats());
        }
#if DEBUG
        PlotStats(logTimes);
#endif
    }

    private static void PlotStats(List<int> times)
    {
        foreach (string key in Tenants[0].History.Keys)
        {
            string name = "img/" + key.Replace(" ", "_");
            string code = "import matplotlib.pyplot as plt\n";
            code += "time = [" + string.Join(",", times) + "]\n";
            foreach (Tenant t in Tenants)
            {
                code += "plt.plot(time, [" + string.Join(",", t.History[key]) + "], label='" + t.ID + "')\n";
            }
            code += "plt.rcParams['figure.dpi'] = 300\n";
            code += "plt.rcParams['savefig.dpi'] = 300\n";
            code += "plt.xlabel('query')\n";
            code += "plt.ylabel('" + key + "')\n";
            code += "plt.legend()\n";
            code += "plt.savefig('" + name + ".png')";
            using (FileStream fs = File.Create(name + ".py"))
            {
                byte[] info = new UTF8Encoding(true).GetBytes(code);
                fs.Write(info, 0, info.Length);
                fs.Close();
            }

            ProcessStartInfo start = new ProcessStartInfo
            {
                FileName = "python3",
                Arguments = name + ".py",
                UseShellExecute = true
            };
            Process.Start(start);
        }
    }

    private static void Generate()
    {
        for (int testId = 1; testId < 100; testId++)
        {
            Random random = new();
            int tenantCount = random.Next(3, 11);
            BufferSize = random.Next(1000, 10000);
            int queryCount = random.Next(100000, 200000);
            Tenants = Enumerable.Range(0, tenantCount).Select(i => new Tenant(i)).ToArray();
            do
            {
                BufferSize++;
                foreach (Tenant t in Tenants)
                {
                    t.QMin = random.Next(100, 1000);
                    t.QBase = random.Next(t.QMin, 5000);
                    t.QMax = random.Next(t.QBase, 10000);
                    t.Priority = random.Next(1, 11);
                    t.DatabaseSize = random.Next(t.QMax, 2 * t.QMax);
                }
            } while (Tenants.Sum(t => t.QMin) >= BufferSize);
            List<string> testcase = new();
            testcase.Add($"{tenantCount} {BufferSize} {3 * queryCount - 200}");
            testcase.Add(string.Join(" ", Tenants.Select(t => t.Priority)));
            testcase.Add(string.Join(" ", Tenants.Select(t => t.DatabaseSize)));
            testcase.Add(string.Join(" ", Tenants.Select(t => $"{t.QMin} {t.QBase} {t.QMax}")));

            List<int>[] freqPerTenants = Tenants.Select(t => new List<int>()).ToArray();
            for (int i = 0; i < tenantCount; i++)
            {
                int freqBias = random.Next(1, 11);
                for (int d = 0; d < Tenants[i].DatabaseSize; d++)
                {
                    for (int j = random.Next(1, freqBias + 1); j > 0; j--) freqPerTenants[i].Add(d);
                }
            }
            List<Tenant> tenantBias = new();
            foreach (Tenant t in Tenants)
            {
                for (int i = random.Next(5); i >= 0; i--) tenantBias.Add(t);
            }

            for (int i = 0; i < queryCount; i++)
            {
                Tenant t = tenantBias[random.Next(tenantBias.Count)];
                testcase.Add((t.ID + 1) + " " + (freqPerTenants[t.ID][random.Next(freqPerTenants[t.ID].Count)] + 1));
                if (i >= 100)
                {
                    testcase.Add(testcase[testcase.Count - random.Next(1, 101)]);
                    testcase.Add(testcase[testcase.Count - random.Next(1, 101)]);
                }
            }
            File.WriteAllLines("inputs/" + testId + ".txt", testcase);
            //File.AppendAllLines("inputs/" + testId + ".txt", testcase);
        }
    }
}

Strategy.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;

public abstract class CachingStrategy
{
    public Tenant Tenant;
    public int HitsCount;
    public int SLA => Tenant.QueryCount - HitsCount;

    public int QTarget;
    public int QCurrent;
    public int QMax = 1000000;
    protected int Q => Math.Min(QMax, QTarget);
    public double Hitrate;

    public CachingStrategy(Tenant tenant)
    {
        this.Tenant = tenant;
    }

    public IEnumerable<int> GetCache()
    {
        for (int i = 0; i < Tenant.DatabaseSize; i++)
        {
            if (HasCached(i)) yield return i;
        }
    }

    private int hitUpdate;
    private int hitsCount;
    public void UpdateHitrate(bool hit)
    {
        hitUpdate++;
        if (hit) hitsCount++;
        Hitrate = (double)hitsCount / hitUpdate;
    }

    public abstract int MinPage();
    public abstract bool HasCached(int pageId);
    public abstract void ProtocolAccess(int pageId);
    public abstract bool Update(int pageId);
    public abstract void Shrink();
    public abstract void Grow(int pageId);
    public abstract CachingStrategy CloneStrategy(CachingStrategy s);
    public abstract void CopyCache(CachingStrategy cache, CachingStrategy winning);
    public abstract string GetName();
}

Tenant.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

public class Tenant
{
    public int ID;
    public int Priority;
    public int DatabaseSize;
    public int QMin, QMax, QBase, QCurrent, QExpected;
    public int[] GlobalCacheLocation;
    public int SLAcurrent;

    public bool CanAdd => QCurrent < QMax;
    public bool CanRemove => QCurrent > QMin;

    public int QueryCount;
    public int[] PageFreq;
    public List<int> Calltimes = new();
    private double qAverage;
    private double qAverageLRU;

    public List<CachingStrategy> Strategies = new();
    public CachingStrategy LeadingStrategy;
    public CachingStrategy ActiveStrategy;
    public LeastRecentStrategy LRUStrategy;

    public Dictionary<string, List<double>> History = new()
    {
        ["Q current"] = new List<double>(),
        ["Q current target"] = new List<double>(),
        ["Penalty"] = new List<double>(),
        ["Penalty predict"] = new List<double>(),
        ["SLAbase predict"] = new List<double>(),
        ["SLAbase current"] = new List<double>(),
        ["SLAreal predict"] = new List<double>(),
        ["SLAreal current"] = new List<double>(),
    };

    public Tenant(int id) => this.ID = id;

    public void Init()
    {
        GlobalCacheLocation = new int[DatabaseSize];
        PageFreq = new int[DatabaseSize];
        Array.Fill(GlobalCacheLocation, -1);

        Strategies.Add(new HybridStrategy(this));
        Strategies.Add(new LeastRecentStrategy(this));
        Strategies.Add(new MostRecentStrategy(this));
        Strategies.Add(new LeastFrequentStrategy(this));
        Strategies.Add(new LeastFrequentXStrategy(this, 3));
        Strategies.Add(new MostFrequentStrategy(this));
        Strategies.Add(new Segmented_LRU_LFU_Strategy(this));
        foreach (CachingStrategy s in Strategies) s.QMax = Math.Max(10, Solution.BufferSize / Solution.Tenants.Length);

        LRUStrategy = new LeastRecentStrategy(this, QBase);
        ActiveStrategy = new HybridStrategy(this);
        LeadingStrategy = Strategies.First(s => s.GetName() == ActiveStrategy.GetName());
    }

    public int Offset;
    public int GlobalPageId(int pageId) => Offset + pageId;

    public int Store(int pageId)
    {
        Calltimes.Add(Solution.Time);
        UpdatePageHit(pageId);
        int globalId = GlobalPageId(pageId);
        CachingStrategy best = Strategies.MaxBy(s => s.HitsCount);
        if (best.HitsCount > LeadingStrategy.HitsCount + 10)
        {
#if DEBUG
            Console.Error.WriteLine($"@{Solution.Time}, {ID}: {ActiveStrategy.GetName()} => {best.GetName()}");
#endif
            LeadingStrategy = best;
            ActiveStrategy = best.CloneStrategy(ActiveStrategy);
            ActiveStrategy.HitsCount = best.HitsCount;
        }

        if (ActiveStrategy.HasCached(pageId))
        {
            ActiveStrategy.Update(pageId);
            foreach (CachingStrategy s in Strategies) s.Update(pageId);
            return GlobalCacheLocation[pageId];
        }

        if (CanAdd && Solution.FreeCells.Count > 0)
        {
            int free = Solution.FreeCells.Dequeue();
            GlobalCacheLocation[pageId] = free;
            Solution.PagePos[free] = globalId;
            ActiveStrategy.Grow(pageId);
            foreach (CachingStrategy s in Strategies) s.Grow(pageId);
            Solution.PagePosReverse[globalId] = free;
            QCurrent++;
            return free;
        }

        double score = 0;
        Tenant other = null;
        bool valid = false;
        // replace from own storage
        if (QCurrent >= QMin)
        {
            score = Score(QCurrent) * AgeFactor();
            if (score < 0) score /= 0.99;
            else score *= 0.99;
            valid = true;
        }

        // extend into other storage
        if (CanAdd)
        {
            foreach (Tenant t in Solution.Tenants)
            {
                if (t == this || !t.CanRemove) continue;
                double tmp = t.Score(t.QCurrent) * t.AgeFactor();
                if (!valid || tmp < score)
                {
                    other = t;
                    score = tmp;
                    valid = true;
                }
            }
        }

        ActiveStrategy.ProtocolAccess(pageId);
        int result = (other ?? this).MinIndex();
        GlobalCacheLocation[pageId] = result;
        Solution.PagePos[result] = globalId;
        Solution.PagePosReverse[globalId] = result;
        if (other != null)
        {
            this.QCurrent++;
            other.QCurrent--;
            other.ActiveStrategy.Shrink();
            foreach (CachingStrategy s in other.Strategies) s.Shrink();
            this.ActiveStrategy.Grow(pageId);
            foreach (CachingStrategy s in Strategies) s.Grow(pageId);
        }
        else
        {
            ActiveStrategy.Update(pageId); // this will update scores, important for LeastFrequentX
            foreach (CachingStrategy s in Strategies) s.Update(pageId);
        }

        return result;
    }

    private double AgeFactor()
        => Math.Min(LRUStrategy.Scores[ActiveStrategy.MinPage()], Calltimes[^QCurrent]) / (Solution.Time + 100);

    private int MinIndex() => Solution.PagePosReverse[GlobalPageId(ActiveStrategy.MinPage())];

    private double Score(int qCurrent)
    {
        double progress = (double)Solution.Time / Solution.QueryCount;
        double slaPlan = PredictSLAreal(qCurrent);
        double slaExpected = PredictSLAbase();
        if (slaPlan >= slaExpected) return Math.Pow((slaPlan - slaExpected) / slaExpected, 2) * Priority / Math.Pow(QBase, 0.9);
        return -1e-9 * Math.Sqrt((slaExpected - slaPlan) / slaExpected);
    }

    private double PredictSLAbase()
    {
        double remainingFactor = ((double)Solution.QueryCount - Solution.Time) / Solution.Time;
        remainingFactor *= 0.1 * Math.Min(1, 5.0 * Solution.Time / Solution.QueryCount);
        double qAvg = 1.2 * qAverageLRU - 0.2 * QBase;
        return LRUStrategy.SLA + LRUStrategy.SLA * remainingFactor * (DatabaseSize - QBase) / (DatabaseSize - qAvg);
    }

    private double PredictSLAreal(double qCurrent)
    {
        //if (Solution.Time > 60000 && ID == 1) Debugger.Break();
        double remainingFactor = ((double)Solution.QueryCount - Solution.Time) / Solution.Time;
        remainingFactor *= 0.1 * Math.Min(1, 5.0 * Solution.Time / Solution.QueryCount);
        double qAvg = 1.2 * qAverage - 0.2 * qCurrent;
        return SLAcurrent + SLAcurrent * remainingFactor * (DatabaseSize - qCurrent) / (DatabaseSize - qAvg);
    }

    public double Score()
    {
        if (SLAcurrent > LRUStrategy.SLA) return Math.Pow((Math.Max(SLAcurrent, LRUStrategy.SLA) - LRUStrategy.SLA) / (double)LRUStrategy.SLA, 2) * Priority;
        return -1e-9 * Math.Sqrt((LRUStrategy.SLA - SLAcurrent) / (double)LRUStrategy.SLA);
    }

    private int QCurrentTarget()
    {
        return 0;
        Tenant[] tenants = Solution.Tenants;
        int[] qs = tenants.Select(t => t.QCurrent).ToArray();
        qs[0] += Solution.FreeCells.Count;
        bool change = true;
        while (change)
        {
            change = false;
            double baseScore = tenants.Sum(t => t.Score(qs[t.ID]));
            for (int from = 0; from < tenants.Length; from++)
            {
                if (qs[from] <= tenants[from].QMin) continue;
                int bestTo = from;
                double score = baseScore;
                for (int to = 0; to < tenants.Length; to++)
                {
                    if (from == to) continue;
                    if (qs[to] >= tenants[to].QMax) continue;
                    double tmp = baseScore + tenants[from].Score(qs[from] - 1) - tenants[from].Score(qs[from]) + tenants[to].Score(qs[to] + 1) - tenants[to].Score(qs[to]);
                    if (tmp < score)
                    {
                        score = tmp;
                        bestTo = to;
                    }
                }
                if (bestTo != from)
                {
                    qs[from]--;
                    qs[bestTo]++;
                    change = true;
                }
            }
        }
        return qs[ID];
    }

    private void UpdatePageHit(int pageId)
    {
        QueryCount++;
        qAverage = (QueryCount - 1.0) / QueryCount * qAverage + 1.0 / QueryCount * QCurrent;
        PageFreq[pageId]++;
        if (!ActiveStrategy.HasCached(pageId)) SLAcurrent++;

        qAverageLRU = (QueryCount - 1.0) / QueryCount * qAverageLRU + 1.0 / QueryCount * LRUStrategy.QCurrent;
        if (LRUStrategy.QCurrent < QBase && !LRUStrategy.HasCached(pageId)) LRUStrategy.Grow(pageId);
        else LRUStrategy.Update(pageId);
    }

    public string GetStats()
        => $"ID: {ID}\tQueries: {QueryCount}\tQmin: {QMin}\tQbase:{QBase}\tQmax:{QMax}\tQcurrent:{QCurrent}\tSLABase:{LRUStrategy.SLA}\tSLAcurrent:{SLAcurrent}\tPriority:{Priority}\tDBSize:{DatabaseSize}\tPenalty:{Score()}\t{string.Join("\t", Strategies.Select(s => s.GetName() + ":" + s.HitsCount))}";

    public void LogState()
    {
        History["Q current"].Add(QCurrent);
        History["Q current target"].Add(QCurrentTarget());
        History["Penalty"].Add(Score());
        History["Penalty predict"].Add(Math.Min(1.5, Score(QCurrent)));
        History["SLAbase predict"].Add(PredictSLAbase());
        History["SLAbase current"].Add(LRUStrategy.SLA);
        History["SLAreal predict"].Add(PredictSLAreal(QCurrent));
        History["SLAreal current"].Add(SLAcurrent);
    }
}

Validator.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

public class Validator
{
    public int[] CachePerTenant;
    (int tenant, int page)[] BufferContent;
    HashSet<(int tenant, int page)> CacheContent = new();
    public Validator()
    {
        CachePerTenant = new int[Solution.Tenants.Length];
        BufferContent = new (int, int)[Solution.BufferSize];
        for (int i = 0; i < BufferContent.Length; i++) BufferContent[i] = (-1, -1);
    }

    public void Validate(int tenant, int page, int action)
    {
        if (BufferContent[action] == (tenant, page)) return;
        Debug.Assert(!CacheContent.Contains((tenant, page)));
        if (CacheContent.Contains((tenant, page))) throw new Exception();
        CacheContent.Remove(BufferContent[action]);
        int oldTenant = BufferContent[action].tenant;
        if (oldTenant != -1 && oldTenant != tenant)
        {
            CachePerTenant[oldTenant]--;
            Debug.Assert(CachePerTenant[oldTenant] >= Solution.Tenants[oldTenant].QMin);
            if (CachePerTenant[oldTenant] < Solution.Tenants[oldTenant].QMin) throw new Exception();
        }
        if (tenant != oldTenant)
        {
            CachePerTenant[tenant]++;
            Debug.Assert(CachePerTenant[tenant] <= Solution.Tenants[tenant].QMax);
            if (CachePerTenant[tenant] > Solution.Tenants[tenant].QMax) throw new Exception();
        }
        BufferContent[action] = (tenant, page);
        CacheContent.Add(BufferContent[action]);
        //ValidateBuffer();
    }

    public void ValidateBuffer()
    {
        foreach (Tenant t in Solution.Tenants)
        {
            int count = 0;
            foreach (int c in t.ActiveStrategy.GetCache())
            {
                count++;
                Debug.Assert(BufferContent[t.GlobalCacheLocation[c]] == (t.ID, c));
                if (BufferContent[t.GlobalCacheLocation[c]] != (t.ID, c)) throw new Exception();
            }
            Debug.Assert(count == CachePerTenant[t.ID]);
            if (count != CachePerTenant[t.ID]) throw new Exception();
        }
    }
}