### BERNARB.01's blog

By BERNARB.01, 6 weeks ago,

This year's Asia-Pacific Informatics Olympiad (APIO) is approaching, it will be open on 28 May for official participants for a 48-hours window, and the mirror will be open for everyone on May 30 for 24 hours.

It is an IOI-Style contest with 3 problems and 5 hours. You can find more information on the official APIO 2022 site apio2022.org.

Let's discuss problems/cutoffs/results here in the comments after the contest (and the mirror) ends.

I wish everyone participating good luck!

UPD: You can find more information about the mirror here.

UPD2: Both the contest and the mirror are now over.

UPD3: The final ranking has been announced, you can find it here.

• +119

 » 6 weeks ago, # |   0 So excited for the contest! Good luck everyone :)
 » 6 weeks ago, # |   -45 Does anyine know whether there ll be a mirror ?
•  » » 6 weeks ago, # ^ |   -41 Probably yes because it had in previous years and it's international
•  » » 6 weeks ago, # ^ |   0
 » 6 weeks ago, # | ← Rev. 2 →   -18 Going to be interestingGood luck ^_^
 » 6 weeks ago, # | ← Rev. 2 →   +29 Good luck to all players
 » 6 weeks ago, # |   0 proud to compete in the name of Botswana i will bring great pride to my nation!
 » 5 weeks ago, # |   0 Contest is now over if I'm not mistaken. Anyone solved C? I would really like to see the full solution, I only got 91 points but I think the idea is beautiful!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +32 First, we need to wait after the contest ends. I will contact my friend generic_placeholder_name to explain it for you Second, we all got 91 points on that problem :)) (except for 1 guy who got 93 and 2 guys who got 100)
•  » » » 5 weeks ago, # ^ |   0 Orz
•  » » » 5 weeks ago, # ^ |   +19 Ops yeah my bad I just checked the official page it says to wait a few days... Ty tho! I would really appreciate it. And also woah I didn't know that few ppl got 100! is there a scoreboard btw?
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I think the scoreboard will be here after the mirror. (The next part was deleted)
•  » » » 5 weeks ago, # ^ |   0 I know another person who participated unofficially and got 94.xx
•  » » » 5 weeks ago, # ^ |   0 there are a lot of people that got 100 i got 91 tho
•  » » 5 weeks ago, # ^ |   +9 I think we shouldn't discuss the contest until the mirror is also over (https://www.timeanddate.com/worldclock/fixedtime.html?iso=20220531T00)
 » 5 weeks ago, # | ← Rev. 2 →   +7 I don't know if it's time to announce it yet, but according to the preliminary results, the cutoffs are If you want to see the cutoffs you can check the previous version. I don't know if it's okay, so I updated my comment. (sorry for the inconvenience)
•  » » 5 weeks ago, # ^ |   0 doesn’t really matter but152.97*
 » 5 weeks ago, # |   +8 Now the open contest is over. Maybe time to discuss problems?Official ranking is shown here.I got 36+30+91.36=157.36pts on the Chinese unofficial group.​
•  » » 5 weeks ago, # ^ |   0 Ops I can't access the link :(, maybe it is my end — ty for sharing tho. Could you share your approach for problem A? I didn't understand the statement during competition lol. I got 0 + 30 + 91.36=121.36 points on the Mexican unofficial group.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Oops it's unavailable now, maybe try again later.For problem A: (36pts solution)Look at the sample below. The top left block stores the info of blocks that have the same color with it. Sample for n=3 My code in the contest#include #include"mars.h" using namespace std; int const N=2333,dx[]={-1,0,0,1},dy[]={0,-1,1,0}; int f[N]; int find(int x){ return f[x]^x?f[x]=find(f[x]):x; } void merge(int x,int y){ int fx=find(x),fy=find(y); if(fx^fy)f[fx]=fy; } int ord(int x,int y,int n){ return x*n+y; } string solve(vector>const&a,int n){ string s=string(N,48); for(int i=0;i<3;i++) for(int j=0;j<3;j++) for(int x=0;x=n||ty<0||ty>=n||s[p1]==48||s[p2]==48)continue; merge(p1,p2); } int cnt=0; for(int i=0;i>=1; return res; } string process(vector>a,int ti,int tj,int k,int n){ string s=string(100,48); if(k==n-1) return solve(a,2*n+1); for(int i=0;i<3;i+=2) for(int j=0;j<3;j+=2) for(int x=0;x<=k;x++) for(int y=0;y<=k;y++) s[ord(x+i/2,y+j/2,k+2)]=a[i][j][ord(x,y,k+1)]; //(x,y) stores the info of (x+2i,y+2j) instead of (x+i,y+j) (i,j\in N) return s; } The count of max string length is $n^2$, so it can pass tests with $n\le 10$.
•  » » 5 weeks ago, # ^ |   0 I can't open official ranking website,anyone saved that?
•  » » » 5 weeks ago, # ^ |   +25 The contest server seems to have been taken offline, but there is a preliminary rankings file with medals: https://docs.google.com/spreadsheets/d/1PR6qtlsXOu39HY1PUdPuUpVDa3G9eLnfwxeOvass4tU/edit?usp=sharing
•  » » » » 5 weeks ago, # ^ |   0 UwU
 » 5 weeks ago, # | ← Rev. 2 →   0 I'm really curious what the solution for problem B is, I thought about memorizing the last node < k visited in the dfs for every node, and updating this value after each query which could potentially lower the complexity of the brute force but the worst case is still quadratic, idk. Anyone got hints for the full solution?
 » 5 weeks ago, # |   0 Bronze medal : hom much score?
•  » » 5 weeks ago, # ^ |   -37 301
 » 5 weeks ago, # |   +64 B (not implemented) SpoilerI assume that you can solve 60 points in $O(k(m + n))$.Build a segment tree (basically, memoized D&C) over range $[1, k]$. Take the middle point $m = (k + 1) / 2$. There is a set of reachable nodes from $m$, and the nodes that can reach $m$. Let them be $L, R$ respectively.If $L \cap R \neq \emptyset$, it means there is a cycle, so terminate.Otherwise, you recurse down. For the left subproblem, you can only consider vertex set $L$, and for the right subproblem, you can only consider vertex set $R$: This means, for each vertices, as long as they are not in any cycle, they belong to at most $\log k$ subproblems.When adding an edge, you can determine the set of vertices that are either appended to $L$ or $R$. If you have to add to both, then you have a cycle. Depending on the position you added, you can determine which direction to recurse down. You may have to add a large set of vertices at once, but the amortized bound still holds.I think it is related to this thing.
•  » » 5 weeks ago, # ^ |   +37 Here's a different point of view which gives an equivalent solution, but may be simpler to implement. SpoilerRecall that the $O(k(m+n))$ solution stores, for each node, the earliest special node you can reach from it, and the latest special node you can reach it from; we'll report a cycle when these values cross. These values get updated only $O(k)$ times per node/edge, so the total runtime is $O(k(m+n))$.We'll start by showing a $O(\sqrt{k}(m+n))$ solution. Instead of storing these reachable special nodes at full precision, let's break the special nodes into $O(b)$ buckets of size $O(k/b)$, and store for each node, the earliest/latest bucket which it can reach/can reach it. Updating this information takes only $O(b(m+n))$ time, since there are only $O(b)$ bucket changes per node.However, this information is not sufficient to check if a node is part of a cycle, since we only know if the earliest/latest special nodes are in the same bucket. To fix this, we'll compute the exact earliest/latest special nodes once we notice that the earliest/latest buckets coincide (we'll say this node falls into this bucket). This computation is efficient because, once this node falls into a bucket, all successor vertices on the path from this node to the bucket also fall into the bucket (since we provide a path from the bucket), and likewise for predecessors. Thus, each node will be updated with exact special nodes only $O(k/b)$ times. By setting $b = \sqrt{k}$, we can get an $O(\sqrt{k} (n+m))$ solution.However, we can take this one step further. Instead of using just 2 levels of precision, we can use $\log(n)$ levels, each with $2$ buckets (this is similar to the segment tree in the above solution). The ideas are quite similar, and the implementation ends up quite simple: each node stores which level/bucket it's currently part of, and when we push a node a level deeper, we just check the predecessor/successor nodes and push them deeper too if necessary. Implementation#include "game.h" #include namespace ecnerwala { namespace { int N; int K; std::vector> outEdges; std::vector> inEdges; std::vector> cur_range; void init(int N_, int K_) { N = N_ + 1; K = K_ + 1; outEdges.resize(N); inEdges.resize(N); cur_range.resize(N); for (int i = 0; i < K; i++) { cur_range[i] = {i, i+1}; } for (int i = K; i < N; i++) { cur_range[i] = {0, K}; } } bool checkVert(int cur); bool checkEdge(int st, int en) { // st must be left-ish of en if (cur_range[st][1] <= cur_range[en][0]) { // always good return false; } // Contradiction! if (cur_range[st][0] >= cur_range[en][1]) { return true; } if (cur_range[st] == cur_range[en]) return false; // st is on top, we need to keep moving it down until en is in the right half if ((cur_range[st][0] + cur_range[st][1]) / 2 >= cur_range[en][1]) { cur_range[st][1] = (cur_range[st][0] + cur_range[st][1]) / 2; return checkVert(st); } else if ((cur_range[en][0] + cur_range[en][1]) / 2 <= cur_range[st][0]) { cur_range[en][0] = (cur_range[en][0] + cur_range[en][1]) / 2; return checkVert(en); } return false; } bool checkVert(int cur) { for (int nxt : inEdges[cur]) { if (checkEdge(nxt, cur)) return true; } for (int nxt : outEdges[cur]) { if (checkEdge(cur, nxt)) return true; } return false; } bool add_teleporter(int u, int v) { u++; v++; if (v < K) v--; outEdges[u].push_back(v); inEdges[v].push_back(u); return checkEdge(u, v); } } } // end namespaces void init(int n, int k) { ecnerwala::init(n, k); } int add_teleporter(int u, int v) { return ecnerwala::add_teleporter(u, v) ? 1 : 0; } 
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +20 For the sqrt solution, can you elaborate on how you would update the vertices that have the same bucket value for L and R?
 » 5 weeks ago, # | ← Rev. 3 →   +28 A (100 points) ideaWhen the grid has size $5 \times 5$, we can store the entire grid directly. Let $h = \lfloor \frac{n}{2} \rfloor$.We store these rows $[0,h),[h, n), [n,n+h),[n+h,2n),[2n,2n]$. We can see that $h \leq 10$ when $n \leq 20$, so are able to directly store the entire grid in this fashion.Now, we want to transfer the $5 \times 5$ grid into $3 \times 3$ grid (Actually I only used $4$ tiles of the $9$ tiles).We want to store each $(n+1) \times (n+1)$ square in a compact way such that we are able to get all the information we need. Let us focus on the top-left region (the one with the red square).We only care about the cells in this yellow band and the connectivity between them. There might be islands that are already formed that do no touch the yellow band. We will count them separately.Now, when $n=20$, we need to use $41$ bits to store the entire state of the yellow band. and there can be up to $100$ islands in the white region that is not connected to the yellow band. So we have already used about $48$ bits.Now, we need to store the connectivity of those lands in the yellow band using the other bits. We can actually do this in $42$ bits only. Firstly, let us focus on the yellow band only. There are at most $21$ connected components. If $2$ lands are adjacent in the yellow region, they belong to the same connected component.The worst case where the number for connected components for $n=3$ is shown here. Now, here is the crucial observation. Let us label the connected components in some order of walking along the line.Suppose $a using namespace std; #define int long long #define ii pair #define fi first #define se second #define puf push_front #define pof pop_front #define pub push_back #define pob pop_back #define lb lower_bound #define ub upper_bound #define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--) #define all(x) (x).begin(),(x).end() #define sz(x) (int) (x).size() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); bool bad(int i,int j){ return i<0 || 10<=i || j<0 || 10<=j; } const int dx[]={0,0,1,-1}; const int dy[]={1,-1,0,0}; bool has[45][45]; int id[45][45]; vector al[45][45]; //extra shit void dfs(int i,int j){ rep(z,0,4){ int i2=i+dx[z],j2=j+dy[z]; if (i2<0 || j2<0) continue; if (has[i2][j2] && id[i2][j2]==-1){ id[i2][j2]=id[i][j]; dfs(i2,j2); } } for (auto [i2,j2]:al[i][j]){ if (has[i2][j2] && id[i2][j2]==-1){ id[i2][j2]=id[i][j]; dfs(i2,j2); } } } int read(string s,int l,int r){ int curr=0; rep(x,r+1,l){ curr<<=1; if (s[x]=='1') curr++; } return curr; } string write(int i,int len){ string s(len,'0'); rep(x,0,min(len,20LL)) if (i&(1<> S, signed i, signed j, signed k, signed m){ rep(x,0,45) rep(y,0,45){ has[x][y]=false; id[x][y]=-1; al[x][y].clear(); } int n=2*m+1; if (m==1){ //pretty retarded case rep(x,0,n) rep(y,0,n) has[x][y]=(S[x][y][0]=='1'); int ans=0; rep(x,0,45) rep(y,0,45) if (has[x][y] && id[x][y]==-1){ id[x][y]=0; //dont care dfs(x,y); ans++; } return write(ans,100); } ii arr[45][45]; ii brr[45][45]; rep(x,0,n) rep(y,0,n) arr[x][y]={min(max(x*m/2,x),x+2*k),min(max(y*m/2,y),y+2*k)}; rep(x,0,n) rep(y,0,n) brr[x][y]={min(max(x*m/2,x),x+2*(k+1)),min(max(y*m/2,y),y+2*(k+1))}; //our goal //( 0,0) ( 0,10) ( 0,20) //(10,0) (10,10) (10,20) //(20,0) (20,10) (20,20) vector imp[4]; rep(x,0,m+1){ imp[0].pub({m,x}); imp[1].pub({m,2*m-x}); imp[2].pub({m,x}); imp[3].pub({m,2*m-x}); } rep(x,m,0){ imp[0].pub({x,m}); imp[1].pub({x,m}); imp[2].pub({2*m-x,m}); imp[3].pub({2*m-x,m}); } if (k==m-2){ //second last step //there are 4 regions we want to care about here if (i%2==1 || j%2==1) return string(100,'0'); //rep(x,0,5){ //rep(y,0,5) cout< head; string mask(41,'0'); rep(x,0,sz(imp[num])){ int a,b; tie(a,b)=imp[num][x]; if (has[a][b]){ mask[x]='1'; if (!pp) head.pub({x,id[a][b]}); pp=true; } else{ pp=false; } } //for (auto [a,b]:head) cout< head; rep(x,0,sz(imp[num])){ int a,b; tie(a,b)=imp[num][x]; if (mask[x]=='1'){ has[a][b]=true; if (pp==ii(-1,-1)) head.pub({a,b}); pp={a,b}; } else{ pp={-1,-1}; } } vector stk; rep(x,0,sz(head)){ int a,b; tie(a,b)=head[x]; if (F[x]=='1'){ stk.pub({a,b}); } else{ int c,d; tie(c,d)=stk.back(); //cout< •  » » 13 days ago, # ^ | 0 For what do you use arrays imp, arr, brr?  » 5 weeks ago, # | ← Rev. 2 → +15 C: 10Since$k \le 90$, a simple construction is$k - 2, k - 3, \dots, 1, 0$. 91.36Observation 1: A permutation$0, 1, \dots, n - 1$, has$2^n$increasing subsequences.After making this observation, it is reasonable now to think about$k$in terms of powers of$2$.We now know how to obtain$k$increasing subsequences in our permutation if$k$is a power of$2$, so let's start with the permutation$0, 1, \dots, \lfloor log_2k \rfloor$, and see how the number of increasing subsequences changes when adding new elements.Assume for now that the length of our current permutation is$n$.Observation 2: Inserting$n$at index$i$adds$2^i$new increasing subsequences to our current permutation.Now it is easy to find a construction after making the second observation. You can see the implementation below for more details. 91.36 (Implementation)vector construct_permutation(long long k) { int z = __lg(k); vector p(z); iota(p.begin(), p.end(), 0); for (int i = z - 1; i >= 0; i--) { if ((k >> i) & 1) { p.insert(p.begin() + i, z++); } } return p; } How to improve this to 100? Or is it a different approach for 100? •  » » 5 weeks ago, # ^ | ← Rev. 6 → 0 NVM, my dumb solution attempt clearly fails •  » » » 5 weeks ago, # ^ | ← Rev. 5 → +3 It seems like you're missing an obvious flaw in your solution. That's OK, things like this can happen to less experienced contestants.If$k$is a prime, your permutation will have the same length as$k$.For example, let$k=1000000007$. Since$1000000007$is a prime, its factorization is just$(1000000007)$. Thus your solution will generate the permutation$[1000000006,1000000005,...,1,0]$, with length$1000000007$. •  » » » » 5 weeks ago, # ^ | 0 Yeah, I get it now, thanks for explaining!And to think I wasted the last 30 minutes of the contest trying to make Pollard rho and Miller Rabin work... :/ •  » » 5 weeks ago, # ^ | ← Rev. 5 → +56 100 ptsFor the sake of simplicity, I will loosely define a permutation as any sequence of pairwise distinct numbers. We can always transform any permutation defined this way into a valid permutation, by replacing each element with the number of elements smaller than it. The bound of$n=90$suggests that we need to encode each bit of$k$in$1.5$elements on average, or$2$bits in$3$elements. So naturally we write$k$in base$4$instead (since$4=2^2$), and we will represent each digit using at most$3$elements.To acheive this, suppose we have a permutation$P$consisting of elements$0,1,...,n-1$that has$x$increasing subsequences. If we can construct permutations with$4x$,$4x+1$,$4x+2$and$4x+3$increasing subsequences from$P$using at most$3$additonal elements, we will have acheived our goal. To assist us in doing so, we will use the following observations:Observation 1: Adding$n$(in other words, an element larger than any element in$P$) to the right of$P$creates a permutation with$2x$increasing subsequences, since there is a one-to-one mapping (bijection) between additional subsequences containing$n$and already-existing subsequences in$P$.Observation 2: Adding$-1$(in other words, an element smaller than any element in$P$) to the right of$P$creates a permutation with$x+1$increasing subsequences, since the only additional subsequence created this way is$[-1]$.With these observations, the cases$4x$,$4x+1$and$4x+2$are solved by adding$[n,n+1]$,$[n,n+1,-1]$and$[n,-1,n+1]$to the right of$P$respectively. For the case$4x+3$, we use the following observation:Observation 3: If the element$1$is positioned to the left of$0$in$P$, adding$1.5$to the right of$P$creates a permutation with$x+3$increasing subsequences. The additional subsequences created this way are$[1.5]$,$[1,1.5]$and$[0,1.5]$.Thus, if$P$contains$1$and$0$in this order, we can solve$4x+3$by adding$[n,n+1,1.5]$to the back of$P$. Otherwise, we add$[n,-1,n+1,-2]$to$P$. This we will call the fallback method (and yes, I know it uses$4$elements, I will get back to it later).Thus, our solution is as follows: The first digit of$x$is constructed using the base cases$x=1$,$x=2$and$x=3$, which we will cover with the permutations$P=[]$,$P=[0]$and$P=[1,0]$. Then, we use one of the four cases ($4x$,$4x+1$,$4x+2$,$4x+3$) to push one of the four digits$0,1,2,3$to the back of$x$'s base-$4$representation. Thus we can make$x$'s base-$4$representation the same as$k$'s representation, meaning$x=k$and the problem is solved.At this point, one question remains: What about the fallback method? If we use the fallback method every iteration, we will end up using 4 elements per digit on average. Fortunately, we can prove that we use the fallback method at most once: the first time we use it, it establishes that$1$(the second smallest element) is to the left of$0$(the smallest element) in$P$, and all the other operations we use during the process maintains this fact, thus we never need to use the fallback method again. This, combined with the fact that the first digit is always constructed using$\le 2$elements, leaving us with$1$to spare, means that we end up using at most$3$elements per digit on average. Since$log_4(1e18) \le 30$, the solution uses at most$3*30=90$elements, scoring the full$100$points. Code (implemented differently, but follows the solution above)#include "perm.h" #include using namespace std; #define int long long #define ii pair #define fi first #define se second #define puf push_front #define pof pop_front #define pub push_back #define pob pop_back #define lb lower_bound #define ub upper_bound #define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--) #define all(x) (x).begin(),(x).end() #define sz(x) (int) (x).size() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); vector construct_permutation(int k){ int bit=64-__builtin_clzll(k); vector ans; //lazy bool flag=false; while (bit>0){ bit-=2; if (bit==-1){ ans.pub(1e9); if (k&1) ans.pub(-1e9); } else{ int val=(k>>bit)&3; if (ans.empty()){ if (val==2) ans={0}; else ans={1,0},flag=true; } else{ if (val==0){ ans.pub(1e9); ans.pub(1e9+1); } else if (val==1){ ans.pub(1e9); ans.pub(1e9+1); ans.pub(-1e9); flag=true; } else if (val==2){ ans.pub(1e9); ans.pub(-1e9); ans.pub(1e9+1); flag=true; } else{ if (!flag){ ans.pub(1e9); ans.pub(-1e9); ans.pub(1e9+1); ans.pub(-1e9-1); flag=true; } else{ ans.pub(1e9); ans.pub(1e9+1); ans.pub(1.5); //should be second guy } } } //cout<<"debug: "< uni(all(ans)); sort(all(uni)); for (auto &it:ans) it=lb(all(uni),it)-uni.begin(); //for (auto it:ans) cout<(all(ans)); } I hope I didn't make any mistakes describing the solution, but if there are any, you're always welcome to point it out so I can fix it promptly.Lots of thanks to errorgorn for sharing me this solution and providing the code. I didn't have a solution that provably worked and instead came up with some other heuristics that I didn't implement in time, causing me to lose gold by <2 points. Feel free to thank him and call me noob in the replies below. •  » » » 5 weeks ago, # ^ | +64 what a noob •  » » » » 5 weeks ago, # ^ | -18 It's nice to see a top gold here! •  » » » » » 5 weeks ago, # ^ | 0 I'm very glad to see two top golds here!!! •  » » 5 weeks ago, # ^ | +69 Meme 100 pointsThis is how I got 100 points in contest:I thought of the problem in terms of reducing$k$as fast as possible. Dividing by$2$is always optimal when$k$is even; otherwise, in the 91 points solution, we subtract$1$then divide by$2$. This is suboptimal; we can instead divide by 3, 5, etc. if possible. Trying this with some small primes gives 100. Code (Big Meme)vi construct_permutation(ll k) { if(k == 1) return {}; if(k == 2) return vi{0}; for(int i: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}) { if(k % i == 0 && k > i) { vi l = construct_permutation(k / i); vi r = construct_permutation(i); for(auto& x: r) x += l.size(); l.insert(l.end(), all(r)); return l; } } vi a = construct_permutation(k / 2); a.pb(a.size()); if(k & 1) a.insert(a.begin(), a.size()); return a; }  •  » » » 5 weeks ago, # ^ | ← Rev. 3 → 0 I may find a hack .... Spoiler2 953883484319907839 824157585052139519   » 5 weeks ago, # | -21 how to get 94.96 on CFor a sequence$X$let$f(X)$denote the number of increasing subsequences that it has. We must construct a sequence small enough$X$with distinct elements (these can be converted into a permutation at the end) such that$f(X) = k$where$k$is the given value. Let's make some observations: If we have a sequence$X$with$f(X) = x$then we can create$X'$with$|X'| = |X|+1$and$f(X') = x+1$by appending a small enough number to$X$. For eg$(5, 4, 2, 1) \to (5, 4, 2, 1, -1)$If we have a sequence$X$with$f(X) = x$then we can create$X'$with$|X'| = |X|+1$and$f(X') = x+2$by decreasing the minimum element of$X$by$1$and appending the original minimum at the end. For eg$(5, 4, 2, 1) \to (5, 4, 2, 0, 1)$If we have a sequence$X$with$f(X) = x$then we can create$X'$with$|X'| = |X|+1$and$f(X') = 2x$by appending a large enough number to$X$. For eg$(5, 4, 2, 1) \to (5, 4, 2, 1, 6)$If we have a sequence$X$with$f(X) = x$then we can create$X'$with$|X'| = |X|+2$and$f(X') = 3x$by appending$M+2, M+1$to the end of$X$where$M$is the original largest element of$X$. For eg$(5, 4, 2, 1) \to (5, 4, 2, 1, 7, 6)$One of the$91.36$solutions is to use steps$1, 3$to reduce the number (the binary solution). Anyone who has gotten the$91.36$solution like this will know that the issue were odd numbers, they required$2$steps to reduce. This is precisely what we fix. Say we have to find$list(k)$for some$k$. If$k = 2$we return$(0)$. If$k = 3$we return$(1, 0)$. If$k$is even, we find$list(k)$recursively from$list(k/2)$by using observation$3$. If$k$is divisibly by$3$we find$list(k)$recursively from$list(k/3)$by using observation$4$. Otherwise we find$list(k)$recursively from$list(k-k \bmod 3)$by using observation 1 or observation 2 (depending on whether$k \bmod 3 = 1$or$2$).Implementing this in the straightforward way will give$94.96$points. hahai now know a crazy randomised solution that passes for$100\$ points but not going to share bcuz am evil
 » 5 weeks ago, # |   +5 Where can i submit apio 2022 questions
 » 5 weeks ago, # |   -65 Very nice contest! Problem C was one of the coolest problems I've seen in a long time.When will the results/editorial be published?
•  » » 5 weeks ago, # ^ |   +70 in my opinion C is trash
•  » » » 5 weeks ago, # ^ |   +54 B was the coolest to me, C was trash
•  » » » » 5 weeks ago, # ^ |   -26 A was coolest imo.
•  » » » » » 5 weeks ago, # ^ |   +38 not imo, it is apio.
 » 5 weeks ago, # |   0 Will we be able to upsolve the problems ?
 » 5 weeks ago, # | ← Rev. 2 →   +14 When will the final results be released?
 » 5 weeks ago, # | ← Rev. 2 →   +19 My simple solution for problem C (99.64 points): SolutionGreedily maintain the permutation and add one element to the right each time, until we have the needed number of increasing subsequences. The value added to the permutation will be the largest possible value such that we do not pass the needed number of increasing subsequences.Note that if we add x to the right, we increase all other values in the permutation that are at least x by 1. For example, adding 3 to the permutation (5, 2, 0, 1, 3, 4) would result in: (6, 2, 0, 1, 4, 5 ,3).This alone gives 91.36. To improve to 99.64, we simply try to extend all initial permutations of length 3 (length 2 gives about 97). Minor improvements to get a 100Unfortunately, my solution during the contest didn’t count the number of increasing subsequences efficiently (didn't have time to remove an O(permutation-length) factor from the complexity), so I could only fix the first 3 values to fit the time limits. Had I maintained the number of increasing subsequences efficiently, my code would have run about 100 times faster, and I would have been able to fix more initial permutations, which I’m convinced would have given a 100.Even not improving the efficiency of the code, but stopping to check all initial permutations if the best permutation so far is already small enough, could be fast enough. My scoreUnfortunately, I did none of these improvements during the contest, and so I got 173.64. The cutoff for silver medal was 174. Just sad.UPD: Applied the minor improvement of stopping when reaching a length that is small enough, and increased initial permutation size to 5. Got a 100. Devastated that this costed me a medal.
 » 5 weeks ago, # |   +10 where can i find the problems?
 » 5 weeks ago, # | ← Rev. 2 →   +16 APIO final ranking released. The cutoffs are:Bronze: 153.66Silver: 174.00Gold: 207.70Congrats to all the winners!btw does the unofficial ranking swap the scores of problem mars and perm?
•  » » 5 weeks ago, # ^ |   +6 they fixed it yesterday, but yeah it was swapped.
 » 5 weeks ago, # |   +23 The test cases have been published on the APIO 2022 website.You can upsolve the problems at https://tlx.toki.id/problems/apio-2022
 » 5 weeks ago, # |   +18 You can solve all problems here; https://oj.uz/problems/source/600