### ipaljak's blog

By ipaljak, history, 8 months ago,

Hi all,

The Central European Olympiad in Informatics (CEOI) 2022 is starting on Sunday and we'd like to invite you to participate in two online mirror contests that will feature the same problems as the two competition days.

The day 1 mirror will take place on Tuesday, July 26th, 10:00 CEST, and day 2 mirror will take place on Thursday, July 28th, 10:00 CEST. Both contests will last for 5 hours, contain 3 IOI-style problems, and have full-feedback.

In order to participate in the CEOI 2022 Online Mirror contests, you'll need an account on evaluator.hsin.hr. After logging in, you can register for the Mirror contests on the "Events" page.

Hope you'll enjoy the contests.

• +165

 » 8 months ago, # |   +35 Btw, evaluator.hsin.hr is amazing online judge.
 » 8 months ago, # | ← Rev. 2 →   +9 EDIT: The starting time of the mirror was wrong. The mirror starts at 10 am local time. Sorry for the inconvenience. Auto comment: topic has been updated by ipaljak (previous revision, new revision, compare).
 » 8 months ago, # |   +37 Is there any way to register late for the mirror?
•  » » 8 months ago, # ^ |   +31 We've increased the registration period. You can register up to 14 CEST.
 » 8 months ago, # |   +8 Is Abracadabra just Spoilersimulation using treap?
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 un/fortunately yes (or maybe not lol)
•  » » » 8 months ago, # ^ |   0 Yes
•  » » 8 months ago, # ^ |   +4 You can do it using only segment tree
•  » » » 8 months ago, # ^ |   0 wtf how
•  » » » » 8 months ago, # ^ |   +10 You can recover the permutation if you know the prefix maximums.I used a segtree,a Sparse Table and a set. code#include #define re register using namespace std; inline int read(){ re int t=0;re char v=getchar(); while(v<'0')v=getchar(); while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar(); return t; } int n,m,a[200002],tg[200002],Mx,mx[22][200002],L[200002],sum[800002],pos,X,ans[1000002],pp[200002]; setS;set::iterator it; inline int ask(re int l,re int r){ re int tmp=L[r-l+1]; return a[mx[tmp][l]]>a[mx[tmp][r-(1<>1; if(x<=mid)add(p<<1,l,mid,x,y); else add(p<<1|1,mid+1,r,x,y); } inline void Ins(re int x){ it=S.lower_bound(x); re int len=*it-x; if(it!=S.begin())--it,add(1,1,n,a[*it],-len); add(1,1,n,a[x],len),S.insert(x); } inline void Get(re int l,re int r){ re int pos=r; while(pos^l)pos=ask(l,pos-1),Ins(pos); } inline int Find(re int p,re int l,re int r,re int x){ if(l==r){X=sum[p]-x;return l;} re int mid=l+r>>1; if(sum[p<<1]>=x)return Find(p<<1,l,mid,x); return Find(p<<1|1,mid+1,r,x-sum[p<<1]); } struct node{int x,y,id;bool operator<(const node A)const{return x>1]+1; for(re int i=1;i<=n;++i)a[i]=read(),pp[a[i]]=i,mx[0][i]=i;S.insert(n+1); for(re int i=1;i<=20;++i) for(re int j=1;j+(1<a[mx[i-1][j+(1<>1)]; if(X)o=*S.upper_bound(o),Get(o-X,o); ++pos; } re int o=pp[Find(1,1,n,p[i].y)];ans[p[i].id]=a[(*S.upper_bound(o))-X-1]; }for(re int i=1;i<=m;++i)printf("%d\n",ans[i]); } ...
•  » » » » » 8 months ago, # ^ |   +3 Why are u using register so much?
•  » » » » » » 8 months ago, # ^ |   +13 I found someone else using register when I started learing and I kept using it until now even when I know it is useless, it's hard to change.
•  » » » » » 8 months ago, # ^ |   0 Can you explain a bit?
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 You can do it using only BIT. Code/* start thinking: BULB: result of thinking: Pure. start coding: AC: */ #include #define mp make_pair #define mt make_tuple using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ldouble; typedef pair P; typedef pair Pll; const int inf = 0x3f3f3f3f; const ll infll = 0x3f3f3f3f3f3f3f3f; template bool chmin(T1 &x, const T2 &y) { return x > y ? (x = y, true) : false; } template bool chmax(T1 &x, const T2 &y) { return x < y ? (x = y, true) : false; } bool Mbe; #define maxn 200005 #define maxq 1000005 int n, q, a[maxn], nxt[maxn], stk[maxn], tp, ans[maxq], pos[maxn]; vector

qs[maxn]; // (pos, id) int bit[maxn]; void add(int p, int x) { for (int i = p; i <= n; i += i & -i) bit[i] += x; } int qsum(int p) { int res = 0; for (int i = p; i; i -= i & -i) res += bit[i]; return res; } int kth(int &k) { int res = 0; for (int i = 17; i >= 0; i--) { if ((res + (1 << i)) <= n && bit[res + (1 << i)] < k) { res += 1 << i; k -= bit[res]; } } return res + 1; } bool Med; int main() { fprintf(stderr, "%.2fMB\n", (&Mbe - &Med) / 1048576.); scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) { scanf("%d", a + i); pos[a[i]] = i; } for (int i = 1; i <= q; i++) { int t, j; scanf("%d%d", &t, &j); qs[min(t, n)].emplace_back(j, i); } for (int i = n; i >= 1; i--) { while (tp && a[i] > a[stk[tp]]) tp--; if (!tp) nxt[i] = n + 1; else nxt[i] = stk[tp]; stk[++tp] = i; } for (int i = 1; i <= n; i = nxt[i]) add(a[i], nxt[i] - i); for (int i = 0; i <= n; i++) { for (auto j : qs[i]) { int foo = kth(j.first); ans[j.second] = a[pos[foo] + j.first - 1]; } int mid = n / 2 + 1; int foo = kth(mid); if (mid == 1) continue; int fooLen = qsum(foo) - qsum(foo - 1), ed = pos[foo] + fooLen; add(foo, mid - 1 - fooLen); for (int j = pos[foo] + mid - 1; j < ed; j = nxt[j]) { add(a[j], min(ed, nxt[j]) - j); } } for (int i = 1; i <= q; i++) { printf("%d\n", ans[i]); } cerr << "time: " << clock() << "ms" << endl; return 0; } 

 » 8 months ago, # |   +19 really liked the part of the contest where i got to implement the problems
 » 8 months ago, # |   0 Is it possible to get a full score with sqrt-decomposition in Abracadabra?
 » 8 months ago, # | ← Rev. 2 →   +54 Was the mirror same as the real contest in terms of time limits and the judging machines? I struggled a lot with Time Limit in "P3. Prize". My time complexity is $O(N + (K + T) \cdot \log N)$ and only got 19/100 points.Could it matter that I answered queries immediately instead of all at once? I didn't flush the output each time so it should be ok, right?
•  » » 8 months ago, # ^ |   +24 Me the same. I struggled with (19/100) TLE for a really long time!!Then I accidentally changed my way of answering queries and passed!!I used to answer queries one by one, flushing my output every time I read a new one.Then I changed to reading all the queries at once and it passed. I really don't know why..
•  » » » 8 months ago, # ^ |   +16 flushing is expensive
•  » » 8 months ago, # ^ |   +3 I tried out locally (on prize.in.1a) your last submission that scored 19 pts, and it didn't finish under 20 seconds (then I killed it).Didn't analyze the code, but it doesn't look like it's due to the way you answer queries.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +19 Was it some special test? I tried chain, star, random tree — each type was below 1s locally.EDIT: I've just downloaded that test from the system. I get 0.15s locally, strange. Maybe there is UB, I will try to figure it out.
•  » » » 8 months ago, # ^ | ← Rev. 2 →   0 Where can i upsolve this contest?
•  » » 8 months ago, # ^ | ← Rev. 3 →   +13 the same happened to me in the real contest :( , it’s most probably from the way queries are answered…
•  » » 8 months ago, # ^ |   +20 Yes, I am 99,9% sure that was the problem. I've spent more than 2 hours optimizing everything in my code, but still got 19/100. I started reading queries first, and only than answering. Got 100 immediately. And yeah,I didn't flush either and was sure it should be fine. Very frustrating...What's worse, there are official contestants who got 19 points on this problem. Likely those were the absolutely correct solutions, cause solving only sub task K<=200 is almost impossible(at least I think so).
 » 8 months ago, # |   +8 When will CEOI day1 results be published?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +18
 » 8 months ago, # |   +8 I think B is similar to this CF problem.
 » 8 months ago, # |   +49 I don't understand the point of such tight limits in an interactive problem.N<=2000 would have been completely fine as well.The only additional thing required for higher N is how find distance between 2 nodes in O(logn) which is well-know and doesn't serve any purpose
•  » » 8 months ago, # ^ | ← Rev. 2 →   -18 The main point of large N was to differentiate between subtasks 3 and 4 (gauss vs erdos). This also influenced some of the decisions regarding time limits.Our solutions and all of the testers that solved the problem fit it comfortably under 3.5 seconds (2-2.5 seconds usually), and we didn't feel it would cause many problems in the contest.
•  » » » 8 months ago, # ^ |   +59 comfortably under 3.5 seconds2-2.5 seconds usually pick one
•  » » » 8 months ago, # ^ |   0 maybe the high constraints on N and T wouldn’t have caused any problems if the interactor wasn’t so janky
 » 8 months ago, # |   +67 How to upsolve problems?
 » 8 months ago, # |   0 Can someone explain how to solve Abracadabra and Prize?
•  » » 8 months ago, # ^ |   +11 AbracadabraMain idea: greedily divide the permutation into disjoint ranges, so that the first element in each range is greater than the rest of the elements (call such ranges valid). For example, with the sample we have $7\text{ }5\text{ }2\text{ }9\text{ }10\text{ }8\text{ }4\text{ }3\text{ }6\text{ }1 \implies (7\text{ }5\text{ }2)\text{ }(9)\text{ }(10\text{ }8\text{ }4\text{ }3\text{ }6\text{ }1)$Note that the first elements of the ranges must be sorted in increasing order. Then, in each move: If the two middle elements are in different ranges, nothing will happen, and the permutation will stay the same. Otherwise, we cut the range in the space between these two elements. The left portion is still valid, while the right portion might not be - we divide this range greedily into smaller valid ranges. Because the ranges in both the left half and right half are now sorted by the first element, the deck after the riffle shuffle will have all ranges sorted by first element. If we maintain the set of integers that are the first elements of a range, along with the range sizes, it's possible to get the kth element in the permutation in $O(\log n)$ with something like a Fenwick tree. This allows us to both get the $(\frac{n}{2} + 1)^\text{th}$ element (necessary for splitting the ranges) and answer the queries.
•  » » » 8 months ago, # ^ |   0 Thanks for the detailed explanation!
•  » » 8 months ago, # ^ |   +23 PrizeSingle tree, $Q = K - 1$: choose any $K$ nodes, sort them by preorder, then ask queries about consecutive pairs (v1, v2), (v2, v3), (v3, v4), ..., (v[k-1], v[k]). You should also find lca(v1, v2), lca(v2, v3), lca(v3, v4), and so on. All of that is enough to know all the distances that you need.Two trees, $Q = K - 1$: greedily choose the first $K$ nodes encountered by DFS in the first tree. Then focus on the second tree and apply the logic from before. The answers that you get turn out to be enough in the first tree too — because your nodes form a connected component including the root, and any LCA is one of the chosen nodes too.
•  » » » 8 months ago, # ^ |   0 Thanks — a very elegant idea!
•  » » » 8 months ago, # ^ |   +68 Alternatively: Prizeif you have a set of nodes where the lca of every pair is also in the set, you can simply ask K-1 queries of a constant node with every other node.the cool thing is, you can always find a a set like that for both trees simultaneously, by starting with the full trees, and deleting nodes which have one or less children in both trees. for each node you delete you only need to update their parent and child, so the complexity for the process is O(N).There's always a node to delete because the amount of nodes with degree 2 or less in a tree is strictly bigger than the amount of nodes with degree bigger than 2 (pretty easy to prove), so the two such sets for both trees have at least one common node at any given point
 » 8 months ago, # | ← Rev. 4 →   0 Did anyone mange to get $O(n^2)$ complexity to get the $n=10^4$ subtask on A? I think calling atan2 $10^8$ times probably made it TLE. I changed it to dot product but now it WAs for some weird reason
 » 8 months ago, # |   +10 I wonder whether making tests for these problems is harder than the problems themselves
 » 8 months ago, # |   +8 Is there a way to submit? I'm still struggling with C. I found it difficult to implent, is there a good way to do it?
•  » » 8 months ago, # ^ |   +8 I lost all my time trying to debug it. on the one hand I want to find the bug now and finally get ac, but on the other hand I don't want to see that problem ever again :'D
 » 8 months ago, # |   0 I have a though about Drawing, but i am not sure that isn't it is the correct solution.Because the node can adjacent to more than three other nodes in this solution. DrawingWe can just take the point which is the highest (the highest y-axis) as the root, let call it $R$ .Than we can find a straight line through R that separate the remaining point to some parts.So,if the root $R$ have $cnt$ subtree, we can separate the remaining point with $cnt$ part. And do it do it recursively.And how to proof that the edge will not intersect?Let us suppose that the edge in each subtree will not intersect first. And can proof that the edge of different subtree will not intersect too, because they are separated into two part, and there are no any edge between them (they are in different subtree).So we can draw it and no any edge intersect.And that is all my though, I am not sure it is correct or not. Maybe some some statements are not accurate because my english is bad.Also, I didn't how to implement this idea in $O(NlogN)$, or we need to use the condition that "each node is adjacent to at most three other nodes"? I hope that someone can help me about this problem, Thanks!
•  » » 8 months ago, # ^ |   -8 i only see a long one.
 » 8 months ago, # |   +13 All accepted solutions of CEOI 2022(Warning: my solution to drawing is garbage.)
•  » » 8 months ago, # ^ |   +14 Can you explain how to solve drawing?
•  » » » 8 months ago, # ^ |   +34 SpoilerIt is known that the decremental convex hull problem can be solved in $O(n \log n)$ time. I copypasted it from here. I don't think this is implementable in the usual OI environment.Given the solution to the decremental convex hull problem, we can simulate the process efficiently. Take the rightmost point of the hull, and repeatedly remove its adjacent point. If you repeat this $k$ time, you can obtain the first $k$ points from the angular order of the rightmost point. For the smaller subtree, initiate a new decremental CH and recurse. For the largest subtree, remove the points from the smaller subtree and recurse.The time complexity is $O(n \log^2 n)$. I needed a little bit of constant optimization.I think this paper contains an $O(n \log n)$ solution. It could be slightly more implementable from scratch. I don't think it's really interesting though.