#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
static constexpr int LANGS = 56;
// More bins reduces collisions (big deal above ~0.85).
// 2^18 => per table: 262144 * 56 * 2 bytes ≈ 28.1 MiB
static constexpr int BINS_POW = 18;
static constexpr int BINS = 1 << BINS_POW;
static constexpr uint32_t MASK = BINS - 1;
// Gram weights (tune here). You said weight on 1,2,4; keep those strong,
// but enabling 3 & 5 usually boosts from ~0.86 -> ~0.91+.
static constexpr int W1 = 1;
static constexpr int W2 = 3;
static constexpr int W3 = 5;
static constexpr int W4 = 7;
static constexpr int W5 = 6;
// Unigram frequency clip: counts above this are capped.
static constexpr int UNI_CLIP = 3;
// Small bias toward seen languages (helps early); keep small.
static constexpr int BIAS_W = 1;
// If prediction is correct but margin is small, still do a tiny update vs runner-up.
static constexpr int MARGIN_SHARPEN = 30; // try 20..80
static constexpr int SHARPEN_STEP = 1; // keep small
static vector<int16_t> tab1, tab2, tab3, tab4, tab5;
static int seen_cnt[LANGS];
static int total_seen = 0;
static inline uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
// Signed feature hashing: store key = (bin<<1) | negBit
static inline uint32_t hash_to_key(uint64_t raw) {
uint64_t h = splitmix64(raw);
uint32_t bin = (uint32_t)(h & MASK);
uint32_t neg = (uint32_t)((h >> 63) & 1ULL); // top bit as sign
return (bin << 1) | neg;
}
static inline int key_sign(uint32_t key) {
return (key & 1U) ? -1 : +1;
}
static inline uint32_t key_bin(uint32_t key) {
return key >> 1;
}
static inline void sat_inc(vector<int16_t>& tab, uint32_t bin, int lang, int delta) {
int idx = (int)bin * LANGS + lang;
int v = (int)tab[idx] + delta;
if (v > 32767) v = 32767;
if (v < -32768) v = -32768;
tab[idx] = (int16_t)v;
}
// ---------- feature builders ----------
// 1-gram: keep clipped counts (frequency)
static inline void make_features_1(const int E[100], vector<pair<uint32_t,uint8_t>>& out) {
static vector<uint32_t> tmp;
tmp.clear();
tmp.reserve(100);
for (int i = 0; i < 100; i++) {
// mix symbol with a salt so different n-grams don't collide identically
uint64_t raw = (uint64_t)(uint32_t)E[i] ^ 0x123456789ABCDEF0ULL;
tmp.push_back(hash_to_key(raw));
}
sort(tmp.begin(), tmp.end());
out.clear();
out.reserve(64);
for (int i = 0; i < (int)tmp.size();) {
int j = i + 1;
while (j < (int)tmp.size() && tmp[j] == tmp[i]) j++;
int c = j - i;
if (c > UNI_CLIP) c = UNI_CLIP;
out.push_back({tmp[i], (uint8_t)c});
i = j;
}
}
// 2..5-gram: presence (unique)
template<int N>
static inline void make_features_ngram(const int E[100], vector<uint32_t>& out, uint64_t salt) {
static_assert(N >= 2 && N <= 5, "N must be 2..5");
out.clear();
out.reserve(100);
for (int i = 0; i + (N - 1) < 100; i++) {
// pack up to 5 symbols (each <= 65535) into 64-bit by mixing, not direct packing (packing 5*16=80 bits).
uint64_t x = salt;
for (int k = 0; k < N; k++) {
x ^= (uint64_t)(uint32_t)E[i + k] + 0x9e3779b97f4a7c15ULL + (x << 6) + (x >> 2);
}
out.push_back(hash_to_key(x));
}
sort(out.begin(), out.end());
out.erase(unique(out.begin(), out.end()), out.end());
}
// ---------- predict & update ----------
struct PredResult {
int best, second;
int32_t bestScore, secondScore;
};
static inline PredResult predict_lang(const vector<pair<uint32_t,uint8_t>>& f1,
const vector<uint32_t>& f2,
const vector<uint32_t>& f3,
const vector<uint32_t>& f4,
const vector<uint32_t>& f5) {
int32_t score[LANGS];
for (int l = 0; l < LANGS; l++) score[l] = (int32_t)seen_cnt[l] * BIAS_W;
// 1-gram with counts
for (auto [key, cnt] : f1) {
uint32_t bin = key_bin(key);
int sgn = key_sign(key);
int base = (int)bin * LANGS;
int mult = sgn * (int)cnt * W1;
for (int l = 0; l < LANGS; l++) score[l] += (int32_t)tab1[base + l] * mult;
}
// 2-gram
for (uint32_t key : f2) {
uint32_t bin = key_bin(key);
int sgn = key_sign(key);
int base = (int)bin * LANGS;
int mult = sgn * W2;
for (int l = 0; l < LANGS; l++) score[l] += (int32_t)tab2[base + l] * mult;
}
// 3-gram
for (uint32_t key : f3) {
uint32_t bin = key_bin(key);
int sgn = key_sign(key);
int base = (int)bin * LANGS;
int mult = sgn * W3;
for (int l = 0; l < LANGS; l++) score[l] += (int32_t)tab3[base + l] * mult;
}
// 4-gram
for (uint32_t key : f4) {
uint32_t bin = key_bin(key);
int sgn = key_sign(key);
int base = (int)bin * LANGS;
int mult = sgn * W4;
for (int l = 0; l < LANGS; l++) score[l] += (int32_t)tab4[base + l] * mult;
}
// 5-gram
for (uint32_t key : f5) {
uint32_t bin = key_bin(key);
int sgn = key_sign(key);
int base = (int)bin * LANGS;
int mult = sgn * W5;
for (int l = 0; l < LANGS; l++) score[l] += (int32_t)tab5[base + l] * mult;
}
int best = 0, second = 1;
if (score[second] > score[best]) swap(best, second);
for (int l = 2; l < LANGS; l++) {
if (score[l] > score[best]) { second = best; best = l; }
else if (score[l] > score[second]) { second = l; }
}
// tie-break toward less seen (gentle exploration)
if (score[second] == score[best] && seen_cnt[second] < seen_cnt[best]) swap(best, second);
return {best, second, score[best], score[second]};
}
static inline void update_model(int trueL, int predL,
const vector<pair<uint32_t,uint8_t>>& f1,
const vector<uint32_t>& f2,
const vector<uint32_t>& f3,
const vector<uint32_t>& f4,
const vector<uint32_t>& f5,
int step_true = 1,
int step_pred = 1) {
// 1-gram
for (auto [key, cnt] : f1) {
uint32_t bin = key_bin(key);
int sgn = key_sign(key);
int d = sgn * (int)cnt;
sat_inc(tab1, bin, trueL, +d * step_true);
if (predL != trueL) sat_inc(tab1, bin, predL, -d * step_pred);
}
// 2-gram
for (uint32_t key : f2) {
uint32_t bin = key_bin(key);
int sgn = key_sign(key);
sat_inc(tab2, bin, trueL, +sgn * step_true);
if (predL != trueL) sat_inc(tab2, bin, predL, -sgn * step_pred);
}
// 3-gram
for (uint32_t key : f3) {
uint32_t bin = key_bin(key);
int sgn = key_sign(key);
sat_inc(tab3, bin, trueL, +sgn * step_true);
if (predL != trueL) sat_inc(tab3, bin, predL, -sgn * step_pred);
}
// 4-gram
for (uint32_t key : f4) {
uint32_t bin = key_bin(key);
int sgn = key_sign(key);
sat_inc(tab4, bin, trueL, +sgn * step_true);
if (predL != trueL) sat_inc(tab4, bin, predL, -sgn * step_pred);
}
// 5-gram
for (uint32_t key : f5) {
uint32_t bin = key_bin(key);
int sgn = key_sign(key);
sat_inc(tab5, bin, trueL, +sgn * step_true);
if (predL != trueL) sat_inc(tab5, bin, predL, -sgn * step_pred);
}
seen_cnt[trueL]++;
total_seen++;
}
void excerpt(int E[100]) {
static bool inited = false;
if (!inited) {
tab1.assign((size_t)BINS * LANGS, 0);
tab2.assign((size_t)BINS * LANGS, 0);
tab3.assign((size_t)BINS * LANGS, 0);
tab4.assign((size_t)BINS * LANGS, 0);
tab5.assign((size_t)BINS * LANGS, 0);
memset(seen_cnt, 0, sizeof(seen_cnt));
inited = true;
}
vector<pair<uint32_t,uint8_t>> f1;
vector<uint32_t> f2, f3, f4, f5;
make_features_1(E, f1);
make_features_ngram<2>(E, f2, 0xA5A5A5A5A5A5A5A5ULL);
make_features_ngram<3>(E, f3, 0xC3C3C3C3C3C3C3C3ULL);
make_features_ngram<4>(E, f4, 0x5F5F5F5F5F5F5F5FULL);
make_features_ngram<5>(E, f5, 0x9B9B9B9B9B9B9B9BULL);
PredResult pr = predict_lang(f1, f2, f3, f4, f5);
int guess = pr.best;
int correct = language(guess);
if (correct != guess) {
// Standard perceptron correction
update_model(correct, guess, f1, f2, f3, f4, f5, /*step_true=*/1, /*step_pred=*/1);
} else {
// If it's correct but margin is tiny, sharpen vs runner-up (reduces future flips)
int32_t margin = pr.bestScore - pr.secondScore;
if (margin < MARGIN_SHARPEN) {
update_model(correct, pr.second, f1, f2, f3, f4, f5,
/*step_true=*/SHARPEN_STEP, /*step_pred=*/SHARPEN_STEP);
} else {
// still count it as seen
seen_cnt[correct]++;
total_seen++;
}
}
}
