### antontrygubO_o's blog

By antontrygubO_o, 16 months ago, translation,

This summer, me and 244mhq held a contest in Petrozavodsk Programming Camp. $1$ problem was provided by gepardo, and we are very thankful for that, and other problems were created by us, 244mhq and antontrygubO_o. This contest will be held as an OpenCup contest on September 19, 11:00 UTC+3.

I and 244mhq are friends for long time, since our years of participation at IMO, and it's 244mhq who introduced me to competitive programming. Therefore, we decided to call this contest GP of IMO.

I will publish the editorial here soon after the contest ends.

Good luck and have fun!

UPD1: Shame on me, I forgot to thank testers of this contest: gamegame, Geothermal, nitrousoxide.

UPD2: Editorial

• +256

| Write comment?
 » 16 months ago, # | ← Rev. 2 →   +8 How to solve problem Q(Delete Files) from Div2 ? Is it greedy or DP ?
•  » » 16 months ago, # ^ |   +8 I tried to implement various greedy algorithms, but they don't work.
•  » » » 16 months ago, # ^ |   +36 Greedy method actually works. Let's iterate through each file from top to bottom. When we reach a file $i$ that does not need to be deleted, we need to delete all files less than $L_i$ that we have already visited. To do this, for each file, we would maintain the length of its filename(denote as $l_i$), and the length of the longest filename of all undeleted files after it(denote as $r_i$). Then, for each deletion, we need to make sure that the horizontal coordinates of the rectangle are in $[l_i,r_i]$. So we can sort all the files by $l_i$, and delete them greedily. Code#include using namespace std; int main() { int n, ans = 0; vector > A, B; cin >> n; auto del = [&](int L) { sort(A.begin(), A.end()); int R = 0; B.clear(); for (auto p : A) { if (p.second >= R) { if (p.first > L) { B.emplace_back(p.first, max(p.second, L)); } else { ans++; R = p.first; } } } A = B; }; for (int i = 0; i < n; ++i) { char d; int L; cin >> d >> L; if (d == 'n') { del(L); } else { A.emplace_back(L, 0); } } del(1e9); cout << ans; } 
•  » » » » 16 months ago, # ^ |   0 Thank you Qingyu! Nice observation ! We misled some points in our approach.
•  » » 16 months ago, # ^ |   +8 There is another greedy approach for Q. SolutionProcess in order from the shortest length. When processing, you should check how much you can delete the files before it and the files after it. It is a greedy algorithm. Intuitively it is obvious that we will delete the much as possible and also we will not delete the needed files as we delete from the shortest file and when we checking we will stop when we achieved the needed which is equal more than the length we want delete. Code: here
 » 16 months ago, # | ← Rev. 2 →   +59 Problem H can be solved by implementing an $O(n^3*2^n)$ checker and randomly generating some undirected graphs. Code#include using namespace std; mt19937 s(233); int n=12,G[25][25],fa[25]; bool f[13][1<<12]; int find(int x){ while (x!=fa[x])x=fa[x]=fa[fa[x]]; return x; } void gen(){ for (int i=1;i<=n;++i)fa[i]=i; int c=n; for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j){ if (find(i)==find(j)){ if (s()%20<=6){ G[i][j]=G[j][i]=1; if(find(i)!=find(j))fa[find(i)]=find(j),--c; }else G[i][j]=G[j][i]=0; } else{ if (s()%4==0){ G[i][j]=G[j][i]=1; if(find(i)!=find(j))fa[find(i)]=find(j),--c; }else G[i][j]=G[j][i]=0; } } if (c!=1)gen(); } void genb(){ for (int i=1;i<=n;++i)fa[i]=i; int c=n; for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j){ if (find(i)==find(j)){ if (s()%20<=9){ G[i][j]=G[j][i]=1; if(find(i)!=find(j))fa[find(i)]=find(j),--c; }else G[i][j]=G[j][i]=0; } else{ if (s()%4==0){ G[i][j]=G[j][i]=1; if(find(i)!=find(j))fa[find(i)]=find(j),--c; }else G[i][j]=G[j][i]=0; } } if (c!=1)gen(); } void genbb(){ for (int i=1;i<=n;++i)fa[i]=i; int c=n; for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j){ if (find(i)==find(j)){ if (s()%40<=21){ G[i][j]=G[j][i]=1; if(find(i)!=find(j))fa[find(i)]=find(j),--c; }else G[i][j]=G[j][i]=0; } else{ if (s()%16<=4){ G[i][j]=G[j][i]=1; if(find(i)!=find(j))fa[find(i)]=find(j),--c; }else G[i][j]=G[j][i]=0; } } if (c!=1)gen(); } int work(){ int ans=0; for(int x=1;x<=n;++x) { memset(f,0,sizeof f); f[x][1<>i&1)&&f[i+1][S]){ for(int j=0;j>j&1) && G[i+1][j+1]) f[j+1][S|(1<> e; for(int i=1;i<=n;++i) for(int j=1;j>K; if(K==1){ printf("2 1\n1 2"); return 0; } else if(K==2){ printf("4 4\n1 2\n1 3\n2 3\n3 4"); return 0; } if(K<=20){ printf("%d %d\n",K,K); for(int i=1;i<=K;++i) printf("%d %d\n",i,i%K+1); return 0; } while(1){ if(K<=40) n=10,gen(); else if (K<=50)n=11,genb(); else if (K<=55) genb(); else genbb(); if(work()==K) { output(); break; } } } 
 » 16 months ago, # |   +37 By the way, it seems that the language of this post is set to Russian, which is not visible in Recent Action for English users.
•  » » 16 months ago, # ^ |   +106 You are right, corrected
 » 16 months ago, # |   +41 G can be solved by calculating random things in hope that everything cancels out: https://pastebin.com/b3GNafWD
•  » » 4 months ago, # ^ |   0 Sorry for being scratchy (We drew it during VP), here is a note.The code calculates $\mathit{cnt}_{\mathit{left}}$ by iterating $BC$ and count $\mathit{cnt}_{BA = BD = CA = CD \neq BC}$, and calculates $\mathit{cnt}_{\mathit{right}}$ by iterating $AB$ similarly. Then we get $\mathit{cnt}_{\mathit{left}} - \mathit{cnt}_{\mathit{right}}$ as answer because lower left part and upper right part cancel out.I think this solution is easier than Editorial.
 » 16 months ago, # |   -40 Is there any other approach for A exempt the editorial's version ? Maybe,it is possible to construct the answer in other way.
 » 16 months ago, # |   -41 Is there any other approach for E exempt the editorial's version ? Maybe, it is possible to find the answer with other strategy.
 » 16 months ago, # |   0 How to solve Div.2 O and P?
•  » » 16 months ago, # ^ |   0 Div2 O: Let's just simply check all permutations of digits (0, 1, 2, 3, 4 , 5, 6, 7, 8 , 9) and find the permutation, when it is possible to obtain the maximum value. CodeDiv2 P: Obviously we want to delete as much as possible. For this case let's observe what will be if we achieved to the panel '<' and our direction at that time is going right, so it will turn our direction to the left. If we will not have '>' we will exit from game and we will not be able to delete as much as possible. So obviously our answer will be the panels which have pairs(means that each '>' has his '<' from the right, one '>' can have 2 '<' and vice versa) and some part if there is, from where our player will run out. By some observation it will be seen that mostly center will have pairs and some parts from right or left may have panels which don't have pairs. So we will choose the maximum part (the left or right), actually we will choose the maximum count from where we will exit if such parts exists. Code
•  » » » 16 months ago, # ^ |   +10 Thanks for your solution, I get it now.
•  » » » » 16 months ago, # ^ |   0 You are welcome !
 » 16 months ago, # |   0 how to get a login for opencup?
•  » » 16 months ago, # ^ |   0 Better to ask here site-register@opencup.org. Cordinator of your region must register you.