### E869120's blog

By E869120, 4 weeks ago,

Hello everyone!

JOI Open Contest 2024 will be held from Sunday, June 16, 04:00 UTC to Monday, June 17, 04:00 UTC.

The duration of the contest is 5 hours, but you can start any time in the 24-hour window. Note that if you start competing after 23:00 UTC, the contest automatically ends at 04:00 UTC and you cannot compete 5 full hours. For example, if you start competing at 03:45 UTC, the contest will be shortened to 15 minutes.

The contest information is as follows. Details are available in contest page.

• Max Score for Each task: 100pts
• Style: IOI Style (There may be some partial scores)
• Problem Statement: Japanese & English

Note that from this year, you can submit with C++20.

The registration page will be announced 30 minutes before the contest starting time. Good luck and have fun!

UPD1: The contest will start in 24 hours.
UPD2: Now the contest is started, so good luck and have fun. Note that you can start any time in 24-hour window.
UPD3: The contest is ended. Thank you for your participation.

• +172

 » 4 weeks ago, # |   +17 Saturday is June 15th, right? The link says so, indicating the start day is actually Sunday.
•  » » 4 weeks ago, # ^ |   +36 Revised.
 » 4 weeks ago, # |   +16 HYPE!
 » 4 weeks ago, # |   -41 i think will be hard contest because its 3 tasks on 5 hours
•  » » 4 weeks ago, # ^ |   +21 3 tasks on 5 hours it's standard for IOI like contests
 » 4 weeks ago, # |   0 Wait, didn't it say the contest was on Saturday?
 » 4 weeks ago, # |   0 Thanks for a great contest!How to solve the third problem ?
•  » » 4 weeks ago, # ^ |   +10 You can find the solutions to all the problems at the contest page
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +15 It seems they have a deterministic solution. I, however, have a non-deterministic solution which I still find interesting and would like to share: RandomThe query answers the number of cycles of the given p composed with the inverse of the answer.Generate random permutations until you get one that has like $2$ cycles. Futher swap random values until you obtain a single cycle. We now strive to break the cycle in unitary pieces, which actually means we found the permutation. For that, we can take another random pair and swap them, meaning we are breaking the current cycle into two pieces. We now have to identify those pieces, so a scan among the elements of the cycle is necessary.This is very similar (if not identical) to the quicksort procedure. Given the (I assume) not adaptive manner of the grader, this has around $O(n*logn)$ queries. Problem is, given $log$, for a random pair, has its base equal more towards $3/2$ rather that $2$. This will not pass.The trick is as follows: take $~6$ elements. Perform swaps among them until they are all in separate cycles. We now have the liberty to rearrange cycles in a manner that is beneficial to us, i.e., if we chain these cycles back together, taking the representative of the $1$-st cycle and the $4$-th cycle, we now have a random pair that divides the cycle more closely to two halves. This fixes the constant enough to pass (Locally, my code takes around $4800$ queries on average to solve).
•  » » » 4 weeks ago, # ^ |   0 why
•  » » » » 4 weeks ago, # ^ |   0 I forgot the intended solution.
•  » » 4 weeks ago, # ^ |   0 bound of 5000 queries kindly suggests some O(N log N) queries solutions. Let's think of one suchFirst thought is binary search, but it's not clear how to apply it here, so we'll return to it later.Recall what is the smallest number of swapt to "sort" the permutation? It is equal to N - number of components in graph (i -> p[i]). We don't have to sort the permutation, but we can actually create a permutation of indices and sort it, so the problem stays same. Described above is called decomposing permutation in cycles, and it has the next property: if we swap two elements that belong to same component, number of components increases by 1; otherwise it decreases by 1. Respectively after any swap we can track whether those two elements belonged to same component (and respectively this "swap" should be kept) or not.O(n^2) queries solution would be: for each j from 2 to N, try to swap it with each 1<=i
 » 4 weeks ago, # |   +46 Its funny to see you guys are still "upset" regarding the venue choices :P. Story of P2, I mean
 » 4 weeks ago, # |   0 This is my code for 2nd subtask in problem A: Spoiler#include #define F first #define S second #define pb push_back #define ppb pop_back #define ep insert #define endl '\n' #define elif else if #define pow pwr #define sqrt sqrtt #define int long long #define ll long long #define y1 YONE typedef unsigned long long ull; using namespace std; const int N=1e6+5; int n,q,b[N],c[N]; char a[N]; bool f(int l,int r){ //cout<l;i--){ x+=p*(a[i]-'0'); p*=10; } return b[1]>=x; } // if a[l...r] is of form (f): if (a[l]=='(' && c[l]==r){ return f(l+1,r-1); } // if a[l...r] is of form !!!!x: if (a[l]=='!' && c[l]==r) return !f(l+1,r); bool x=0,y=0,z=0; for (int i=l;i<=r && !x;i++){ if (a[i]=='(') {i=c[i];continue;} x|=(a[i]=='|'); y|=(a[i]=='^'); z|=(a[i]=='&'); } if (x){ for (int i=l;i<=r;i++){ if (a[i]=='(') {i=c[i];continue;} if (a[i]!='|') continue; return f(l,i-1)|f(i+1,r); } } if (y){ for (int i=l;i<=r;i++){ if (a[i]=='(') {i=c[i];continue;} if (a[i]!='^') continue; return f(l,i-1)^f(i+1,r); } } if (z){ for (int i=l;i<=r;i++){ if (a[i]=='(') {i=c[i];continue;} if (a[i]!='&') continue; return f(l,i-1)&f(i+1,r); } } return f(0,0); } int32_t main(){ //ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); cin>>n>>q; for (int i=1;i<=n;i++) cin>>a[i]; for (int i=1;i<=q;i++) cin>>b[i]; stack s; for (int i=1;i<=n;i++){ if (a[i]=='(') s.push(i); elif (a[i]==')'){ c[s.top()]=i; c[i]=s.top(); s.pop(); } } for (int i=1;i<=n;i++){ if (a[i]=='[') s.push(i); elif (a[i]==']'){ c[s.top()]=i; c[i]=s.top(); s.pop(); } } for (int i=1;i<=n;i++){ if (a[i]!='!') continue; int r=i; for (int j=i;j;j++){ if (a[j]=='!') r=j; else break; } for (int j=i;j<=r;j++) c[j]=c[r+1]; i=r; } if (f(1,n)) cout<<"True"<
•  » » 4 weeks ago, # ^ |   0 It fails on [2]^[2]^....[2] (repeated 250000 times)
 » 4 weeks ago, # |   0 pretty sus how library appeared on POI 3 months ago with the exact same constraints...
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +2
 » 10 days ago, # |   +5 oj.uz when will the tasks be uploaded to oj.uz?
•  » » 10 days ago, # ^ |   -8 next monday