{"id":531,"date":"2020-08-24T23:28:16","date_gmt":"2020-08-24T15:28:16","guid":{"rendered":"http:\/\/nocriz.com\/?p=531"},"modified":"2021-09-08T20:20:06","modified_gmt":"2021-09-08T12:20:06","slug":"ptz-a2-abstract-circular-cover","status":"publish","type":"post","link":"https:\/\/nocriz.com\/?p=531","title":{"rendered":"Ptz A2: Abstract Circular Cover"},"content":{"rendered":"\n

\u8fd9\u662fPtz\u4e2d\u7684\u4e00\u9053\u9898\u76ee\u3002\u6211\u5e94\u8be5\u8865\u66f4\u591a\u7684\u9898\uff01Orz um_nik, Orz SpbSU<\/p>\n\n\n\n

\u8b66\u544a\uff1a\u8fd9\u573a\u6bd4\u8d5b\u53ef\u80fd\u4f1a\u53d8\u6210\u672a\u6765\u7684OpenCup\u6216\u8005\u5728\u67d0\u4e9b\u5730\u65b9\u91cd\u73b0\uff0c\u5982\u679c\u4f60\u611f\u5174\u8da3\u5728\u67d0\u4e9b\u673a\u4f1a\u4e2d\u6253\u8fd9\u4e2a\u6bd4\u8d5b\uff0c\u8bf7\u522b\u770b\u8fd9\u4e2ablog\u2026\u2026<\/p>\n\n\n\n

\u9898\u76ee\uff1a\u6709\u4e00\u4e2an\u4e2a\u70b9\u7684\u73af\uff0c\u4f60\u9700\u8981\u5c06\u6bcf\u4e00\u4e2a\u70b9\u6070\u597d\u8986\u76d6\u4e00\u6b21\u3002\u6709n*n\u79cd\u73af\u4e0a\u533a\u95f4\uff0c\u957f\u5ea6\u662f\u4ece0\u5230n-1\uff0c\u8986\u76d6\u7684\u70b9\u7684\u4e2a\u6570\u662f\u4ece1\u5230n\uff08\u8986\u76d6\u4e00\u4e2a\u70b9\u53ea\u9700\u89810\u7684\u957f\u5ea6\uff09\u3002\u533a\u95f4\u7684\u8d39\u7528\u662f\u7ed9\u51fa\u7684\uff0c\u4f60\u9700\u8981\u8f93\u51fa\u5bf9\u4e8e\u6bcf\u4e2ak\uff0c\u4f7f\u7528\u6070\u597dk\u4e2a\u533a\u95f4\u8986\u76d6\u6240\u6709n\u4e2a\u70b9\u3001\u6bcf\u4e2a\u70b9\u53ea\u88ab\u8986\u76d6\u4e00\u6b21\u7684\u6700\u5c0f\u4ee3\u4ef7\u3002<\/p>\n\n\n\n\n\n\n\n

\u9898\u89e3\u5982\u4e0b(OCR\u592a\u597d\u7528\u4e86)<\/p>\n\n\n\n

Let’s firstly solve the problem for one given \"k\".
In fact, our problem is to find \"k\" points at which we split our cycle onto circular segments. This problem would be much simpler if we had a line instead of a circle. So, let’s guess one of the points at random. If we guess one point correctly, it would suffice to run dynamic programming on a line in \"O\left(n^{2} k\right) .\" The answer contains \"k\" distinct points, so we guess one of them with probability \"\frac{k}{n} .\" That’s it, in order to get error probability \"2^{-\varepsilon},\" we have to repeat the process \"O\left(\frac{n}{k} \log \frac{1}{\varepsilon}\right)\" times, achieving the total complexity of \"O\left(n^{3} \log \frac{1}{\varepsilon}\right)\"
Now back to our problem. Note that dp for \"k\" segments also compute answers for every number of segments smaller than \"k .\" Then, in order to achieve probability \"2^{-\varepsilon} \cdot n\" (note additional \"n\" factor \"),\" we have to repeat the process only \"O\left(\left(\frac{n}{k}-\frac{n}{k+1}\right) \log \frac{1}{\varepsilon}\right)\" times for each \"k\"

  <\/span>   <\/span>\"\[\sum_{k}\left(\frac{n}{k}-\frac{n}{k+1}\right) n^{2} k \log \frac{1}{\varepsilon}=O\left(n^{3} \log n \log \frac{1}{\varepsilon}\right)\]\"<\/p>
Therefore, the total complexity is \"O\left(n^{3} \log ^{2} n \log \frac{1}{\varepsilon}\right)\"
Note that it is only the upper bound, and in practice, the probability of error is smaller giving the total complexity about \"O\left(n^{3} \log n \log \frac{1}{\varepsilon}\right)\"<\/p>\n\n\n\n

um_nik\u63d0\u4f9b\u4e86\u786e\u5b9a\u6027\u505a\u6cd5\uff0c\u4ed6\u7684\u505a\u6cd5\u662f\u5148\u6c42\u51fak=1,2,3,…30\u548ck = 30,60,90,…,840\u7684\u7b54\u6848\uff0c\u7136\u540e\u8fdb\u884c\u7b54\u6848\u5408\u5e76\u3002\u6211\u5b9e\u73b0\u4e86um_nik\u7684\u505a\u6cd5<\/p>\n\n\n\n

\u9700\u8981\u8865\u66f4\u591a\u9898\uff01\u660e\u5929\u5f00\u59cb\u7684\u4e09\u5929\u662f\u6700\u540e\u4e09\u573a\u6bd4\u8d5b\u3002\u3002\u597d\u597d\u6253\uff01\u8865\u66f4\u591a\u9898\uff01\u66f4\u8ba4\u771f\u7684\u5b66\u4e60\u3002\u3002<\/p>\n\n\n\n

\u9700\u8981\u5f00\u4e2a\u535a\u5ba2\u8bb0\u5f55\u6211\u8865\u9898\/\u7406\u89e3\u9898\u76ee\u89e3\u6cd5\u8fdb\u5ea6\u5417\uff1f\u6216\u8bb8\u3002<\/p>\n\n\n\n

\u7136\u540e\u53ef\u80fd\u53bb\u4e0a\u6d77\u65c5\u6e38\u4e86\u3002<\/p>\n\n\n\n

#pragma GCC optimize(\"Ofast\")\n#pragma GCC optimize(\"unroll-loops\")\n#include <bits\/stdc++.h>\nusing namespace std;\n\n#define set0(x) memset(x,0,sizeof(x))\n#define F first\n#define S second\n#define PB push_back\n#define MP make_pair\n#define rep(i, a, b) for(int i = a; i < (b); ++i)\n#define trav(a, x) for(auto& a : x)\n#define all(x) x.begin(), x.end()\n#define sz(x) (int)(x).size()\n\ntypedef long long ll;\ntypedef pair<int,int> pii;\ntypedef pair<ll,ll> pll;\ntemplate<typename T> void read(T &x){\n    x = 0;char ch = getchar();ll f = 1;\n    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}\n    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;\n}\ntemplate<typename T, typename... Args> void read(T &first, Args& ... args) {\n    read(first);\n    read(args...);\n}\n\nconst int N = 855,inf = 1e9+10;\n\nint n,C[N][N],dp[N][31][N],dp2[N][31][N],dp3[N][31][N];\n\nint main() {\n    read(n);\n    memset(dp2,63,sizeof(dp2));\n    memset(dp,63,sizeof(dp));\n    for(int i=0;i<n;i++){\n        for(int j=0;j<n;j++){\n            read(C[i][(i+j)%n]);\n        }\n    }\n    for(int i=0;i<n;i++){\n        for(int j=0;j<n;j++){\n            int c = (i+j)%n,c1 = (c+1)%n;\n            dp[i][1][c] = C[i][c];\n            for(int k=1;k<30;k++){\n                if(dp[i][k][c]>inf)continue;\n                for(int l=j+1;l<n-i;l++){\n                    int d = i+l;\n                    dp[i][k+1][d] = min(dp[i][k+1][d],dp[i][k][c]+C[c1][d]);\n                }\n                for(int l=max(j+1,n-i);l<n;l++){\n                    int d = i+l-n;\n                    dp[i][k+1][d] = min(dp[i][k+1][d],dp[i][k][c]+C[c1][d]);\n                }\n            }\n        }\n    }\n    \n    for(int i=0;i<n;i++)\n        for(int j=0;j<n;j++)C[i][j] = dp[i][30][j];\n    for(int i=0;i<n;i++){\n        for(int j=0;j<n;j++){\n            int c = (i+j)%n,c1 = (c+1)%n;\n            dp2[i][1][c] = C[i][c];\n            for(int k=1;k<30;k++){\n                if(dp2[i][k][c]>inf)continue;\n                for(int l=j+1;l<n-i;l++){\n                    int d = i+l;\n                    dp2[i][k+1][d] = min(dp2[i][k+1][d],dp2[i][k][c]+C[c1][d]);\n                }\n                for(int l=max(j+1,n-i);l<n;l++){\n                    int d = i+l-n;\n                    dp2[i][k+1][d] = min(dp2[i][k+1][d],dp2[i][k][c]+C[c1][d]);\n                }\n            }\n        }\n    }\n    for(int i=0;i<n;i++){\n        for(int j=0;j<31;j++){\n            for(int k=0;k<n;k++){\n                dp3[k][j][i] = dp[i][j][k];\n            }\n        }\n    }\n    for(int i=1;i<=n;i++){\n        int a = i\/30,b = i%30,ans = inf;\n        for(int l=0;l<n;l++){\n            if(a == 0){\n                ans = min(ans,dp[l][b][(l+n-1)%n]);\n            }else{\n                if(b == 0){\n                    ans = min(ans,dp2[l][a][(l+n-1)%n]);\n                }else{\n                    int C =(l+n-1)%n;\n                    for(int r = 0;r+1<n;r++){\n                        ans = min(ans,dp2[l][a][(l+r)%n]+dp3[C][b][(l+r+1)%n]);\n                    }\n                }\n            }\n        }\n        cout<<ans<<\" \\n\"[i == n];\n    }\n    return 0;\n}\n<\/code><\/pre>\n ","protected":false},"excerpt":{"rendered":"
\u8fd9\u662fPtz\u4e2d\u7684\u4e00\u9053\u9898\u76ee\u3002\u6211\u5e94\u8be5\u8865\u66f4\u591a\u7684\u9898\uff01Orz um_nik, Orz SpbSU \u8b66\u544a\uff1a\u8fd9\u573a\u6bd4\u8d5b\u53ef\u80fd\u4f1a\u53d8\u6210 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/531"}],"collection":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=531"}],"version-history":[{"count":6,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/531\/revisions"}],"predecessor-version":[{"id":537,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/531\/revisions\/537"}],"wp:attachment":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=531"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=531"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=531"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}