New fear unlocked

Come on... releasing the checker and some tests after 10 days of the competition? +Extension

I did most of the work in the first week, and planned to do very little this week. Good luck with that plan now, right?

Almost toughest Div2. BCD are too hard for their positions and D is the strangest problem of my CP journey...

meanwhile you are just a troll with no life

They brought guns to a fist fight.

It was the most fun Div.2 ever, thank you!

Guess why

Very nice round!

Stop replying with your alts then we can talk

This is a huge insult. I'm sure I'm not the only one who agrees with.

I don't know if I'm qualified to say this, but can't you be kind to other? Can't you at least be kind enough to not be sarcastic or insult someone who has nothing to do with you and has raised a legitimate issue?

United Kingdom's team:

• Hanks Chong (Hanksburger) — 3rd time, 1 attempt left
• Samuel Trajtenberg (sammyuri) — 2nd time, 0 attempts left
• Adavya Goyal (Boomyday12343) — 1st time, 2 attempts left
• Anango Prabhat (anango) — 1st time, 2 attempts left

Duke is overACer kadasix izhang

Is the checker numerically stable? Will it always add the same numbers to the same value?

I locally got a situation where printing extra stuff in the checker changes the sum that it computes. Maybe that's allowed in C++.

I also created a test where s{a,b,c} != s{s{a,b},c}, but I don't understand float->double->float casting enough to say if this is incorrect.

as another participant I don't think this is a wise decision. If you don't attempt harder interactive problems you will not improve at them.

Glad the guy finally got served. Never have anything nice to say, just stupid insults and 4chan rhetorics

Why?
"Next, we calculate the expected sum as precisely as we can"
"//'Exact' answer based on Kahan summation"
Or, the Kahan is shown but the expected sum is really exact while testing?
Hope it is.

at uni

Spain's IOI team is:

• Alejandro Vivero Puga (Esomer) — 2nd time at IOI, 0 attempts left

• Javier Badesa Pérez (Dalek_of_Rivia) — 1st time at IOI, 0 attempts left

• Daniel Nieto Pérez (danx) — 1st time at IOI, 0 attempts left

• Héctor Verdeal Rodríguez (Hectorungo_18) — 1st time at IOI, 1 attempt left

Dyslexic Sparse University of Tartaria

Here is the brazilian team:

• Pedro Suyama Leston Rey (_rey)
• Arthur Lobo Leite Lopes (LoboLobo)
• Filipe de Souza Lalic (Lalic)
• Maria Clara Fontes Silva (clarinha)
• Pedro Henrique Assunção (hyakup)
• Caique Paiva (Pagode_Paiva)
• Carlos Cabral de Menezes Filho (Cabralbonzao)
• Leandro Marcos Checchio de Souza (leanchec)
• Fernando Graminholi Gonçalves (DereFer)
• Enzo Dantas de Britto Monte Araujo (Enzinho)

Good luck guys :D

Happy birthday! I hope you will enjoy the round :D

wait your legendary Aidar Munduzbaev has no attemts left? Sad that he couldnt get gold

Orz!

It seems that people use the rolling hash formula $$$\sum_{j = 0}^{n - 1} q^{n - 1 - j} s_j$$$ more frequently than $$$\sum_{j = 0}^{n - 1} q^{j} s_j$$$. Probably it would be better to have an "reverse the result" option.

thank you blog that man good put like for him

My idea for C is slightly different and imo cleaner. Its also much easier to prove why my idea actually works.

Here's my code: 261430375

swap(q[pos[x]], q[pos[1]]);

Incase I explained something poorly, please let me know! And I'll try to help if I can. :D

Italy:

• Luca Baglietto (BestCrazyNoob) — 2419.0 points (at the team selection tests), 2nd time, 1 attempt left
• Francesco Vercellesi (franv) — 2349.6 points, 2nd time, 0 attempts left
• James Bamber (jamesbamber) — 2303.6 points, 1st time, 0 attempts left
• Alessandro Lombardo (AlesL0) — 2257.0 points, 2nd time, 0 attempts left

Well, it's added.

• Codeforces Round 941 (Div. 1)
• Codeforces Round 942 (Div. 2)
• Codeforces Round 943 (Div. 3)
• Codeforces Round 944 (Div. 4)
• Any guesses?

Expected sum is not always exact. It is calculated by Kahan summation as in the published checker implementation.

Lol I thought I was the only one thinking B was odd. Counting prefixes bit-by-bit should be C at least.

I messed up guys. It was 7 and I wasn't been able to sleep yet. I decided to go to uni right away. Next frame, it was 12! I have no idea what happened since I even had my alarms on for 8.

I hope we'll have a chance to do this another time.

Feel free to downvote this comment. I messed up and deserve that.

Plz.start on 17:05(UTC+08) :<

what is dsu

We have only 11 grades in Kyrgyzstan and I went to school one year early. So yeah, last year was my last chance, despite me being 17 right now. However, this year I will hopefully be in Kyrgyz IOI delegation and help out guys to get the first gold for Kyrgyzstan. Good luck to contestants from all countries.

Receiving clarifications for A about 7-9 mins into the contest after 1 failed attempt to answer the "original" problem is pretty underwhelming.

Bonus points for MASSIVE confusion after the first submission failed on pretest 1.

This never happens again. But, definitely, I will share the channel with them.

Congratulations prvocislo, looking forward to your round :D

Out of curiosity, what makes D so strange in your opinion?

It feels fairly normal for a CF interactive problem to me.

Finally i have reached master

I tried my best to divide the solution into reasonable parts, hopefully it'd be helpful.

P.S: It appears that there are some similarities between my sol and the sol above, which wasn't there when I started writing the comment.

I don't know man, telling someone is right after he called you effeminate is just a little weird

It was very easy to implement, the observation was the difficult part imo.

Find the maximum element $$$mx$$$ in $$$a$$$ by making queries $$$(1,n*n), (1,n*(n-1)),\dots$$$. If you get $$$r=n$$$ on query $$$(1,n*b)$$$ then $$$mx=b$$$.

Now since this maximum element is present in at least one of the $$$k$$$ subarrays, $$$mx$$$ must divide $$$m$$$. Also, if $$$m=b*mx$$$, every subarray must have length at least $$$b$$$. So we only need to check multiples of $$$mx$$$ upto $$$\frac{n}{k}mx$$$. In each candidate for $$$m$$$, just query $$$k$$$ segments starting from position $$$1$$$ and check if these segments cover the array.

This takes $$$n$$$ queries to find $$$mx$$$ and another $$$n$$$ queries to check all values of $$$m$$$.

prvocislo orz <3

Please no GOD no please. I won't play Genshin any more. Please don't hack my Hash.

← Anonymous Tester

no it is created by Sergey Kolodyazhnyy

shayan is awol lol

How can I murder someone as inconspicuously as possible

Honestly, it doesn't matter. There is simply no reason why you should defend the guy.

Anyone proved the validity of C?

I thought of a greedy solution, check if it's possible to maximize at indices $$$(3, 5, \dots, n-1)$$$ or $$$(2, 4, \dots, n-2)$$$, then take the case with better score.

The interaction and the output format is very weird. What I expected: I can ask $$$l, r$$$ and the answer will be $$$f(l, r)$$$. (I know that's not interesting because $$$f(l, l)=$$$ $$$a_l$$$) And the output should be the array or some natural proterty of that.

By the way nice problem.

I appreciate it broski but I have also done a lot of leetcode so, between the two platforms, it is normal growth. I think that leetcode is better than codeforces when you are beginning 100%.

Wow rating changes and editorial were kinda fast... speedforces

Marinush His comments are more useful for the community than your retarded post and comments. It is you who needs to chill.

Also, you don't need to write your username in your every fucking comment. We can see your username with our own eyes. We are not blind either

I'll win.

Diagnostics detected issues [cpp.clang++-c++20-diagnose]: p71.cpp:67:34: runtime error: passing zero to clz(), which is not a valid argument
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:67:34 in

In my opinion, leetcode is the best way to start competitive programming because it introduces the most common competitive programming concepts (greedy, binary search, dp, graphs/trees, etc etc) through more or less straightforward problems. The good thing about this is that you aren't gonna have to do some weird math things while solving leetcode dp problems, for example. You can just focus on learning dp. Another benefit of leetcode is that it has a much bigger community than cf. If you get stuck on a problem, you will have much more than just a single editorial to read. There are videos, writeups, and there is even a solutions tab that you can use to understand the problem.

If I were you, I'd go to https://neetcode.io/roadmap and just start working through that list. NeetCode, the guy who made that website, has great explanations for each problem. Once you finish that list, start doing random mediums, and when you feel comfortable with those, start trying some hards. When I was grinding out mediums, I'd try to limit myself to 45 minutes and then I'd look at the solution.

Make sure you're doing the weekly and biweekly contests while you're practicing. Once you reach a 2000+ rating, I'd say that you should start practicing on some more serious competitive programming websites. 2000 rating should get you to specialist on codeforces at least.

My clar few days ago:
Q. In scoring, "Next, we calculate the expected sum S_e as precisely as we can" Is this mean S_e is the exact sum (after converting the inputs into binary64)?
A. The intent is that it is the closest possible binary64 value to the actual (infinite precision) sum.

... then, finding the exact sum with Kahan's algorithm is contradict with this answer, but will the checker fixed?

Proud of myself by solving C with proving its validity, not by guessing

Solving a 1600 rated problem in your first contest is considered division 5?

any random things like selling solutions can happen. We shouldn't presume guilt, but he had already cheated.

TimDee has neither silver medal nor girlfriend

wasn't eolymp created by medv?

First, we can make $$$4$$$ arrays $$$gr, gl, sr, sl$$$ which stores for index $$$i$$$, what's the nearest greater value to the right, to left and smaller value to left and to right. This can be done using stack in $$$O(n)$$$. Now, let's consider the edges (there is an edge between $$$(i, j)$$$ if we can go from $$$i$$$ to $$$j$$$ in $$$1$$$ move i.e all elements in between are between $$$a_i$$$, $$$a_j$$$). Important thing to notice is that, we will take the edge which brings us closest to $$$r$$$ (considering the query $$$(l, r)$$$). Also, another observation is that it is easily determinable that whether $$$a_i$$$ is a min-point or max-point. We can just check that whether $$$a_{i + 1}$$$ is less or greater than $$$a_i$$$ and then we can't have $$$a_i$$$ as min if $$$a_{i + 1}$$$ is less than it (similar for other case).

Assume that $$$a_i < a_{i + 1}$$$ since other case is similar. Now, $$$a_i$$$ is min and we want the max points. Note that the edges from $$$i$$$ are going to the changes in the max as we go towards right from $$$i$$$. Now, where will the last edge be? It will be to the maximum in the valid range. What is a valid range? the range will be valid such that the min point $$$i$$$ does not change. So, beyond $$$sr_i$$$ (the first index to the right of $$$i$$$ which have smaller value than $$$a_i$$$)we don't have any edge outgoing from $$$i$$$. So, we just get the max in the range $$$[i, sr_i)$$$. Now, we have $$$O(n)$$$ edges added in $$$O(n \space lg(n))$$$.

We can also do binary lifting and store where do I land when I take $$$2^x$$$ edges.

Now, when the query comes, we just go to the rightmost point we can from $$$l$$$ which is $$$\leq r$$$. What to do after that? We can now just do the same things we did for going in the right direction, for the left direction. Now, we starting going left from $$$r$$$ (using binary lifting). And we want the minimum jumps needed to get $$$r \leq l$$$. Now, we add both of the steps and we are done.

Proofs of the observations are not hard, I believe that you should try them.

#include <bits/stdc++.h>
// #include "stub.cpp"
using namespace std;

const int N = 3e5 + 10, LG = 19;
int n, sr[N], gr[N], sl[N], gl[N], pos[N];
int jump_right[N][LG], jump_left[N][LG], MAX[N][LG], MIN[N][LG];

vector<int> a;

int get_max(int l, int r){
    int lg = 31 - __builtin_clz(r - l);
    return max(MAX[l][lg], MAX[r - (1 << lg)][lg]);
}

int get_min(int l, int r){
    int lg = 31 - __builtin_clz(r - l);
    return min(MIN[l][lg], MIN[r - (1 << lg)][lg]);
}

void init_permutation(int N, vector<int> A){
    n = N, a = A;
    for (int i = 0; i < n; i ++)
        pos[a[i]] = i;

    stack<int> st;
    for (int i = 0; i < n; i ++){
        sl[i] = i;
        while (st.size() and a[st.top()] > a[i])
            st.pop();

        if (st.size())
            sl[i] = st.top();
        st.push(i);
    }

    while (st.size()) st.pop();

    for (int i = 0; i < n; i ++){
        gl[i] = i;
        while (st.size() and a[st.top()] < a[i])
            st.pop();

        if (st.size())
            gl[i] = st.top();
        st.push(i);
    }

    while (st.size()) st.pop();

    for (int i = n - 1; i >= 0; i --){
        sr[i] = i;
        while (st.size() and a[st.top()] > a[i])
            st.pop();

        if (st.size())
            sr[i] = st.top();
        st.push(i);
    }

    while (st.size()) st.pop();

    for (int i = n - 1; i >= 0; i --){
        gr[i] = i;
        while (st.size() and a[st.top()] < a[i])
            st.pop();

        if (st.size())
            gr[i] = st.top();
        st.push(i);
    }

    while (st.size()) st.pop();

    for (int i = n - 1; i >= 0; i --){
        MIN[i][0] = MAX[i][0] = a[i];
        for (int step = 1; step < LG && i + (1 << step) <= n; step ++){
            MIN[i][step] = min(MIN[i][step - 1], MIN[i + (1 << (step - 1))][step - 1]);
            MAX[i][step] = max(MAX[i][step - 1], MAX[i + (1 << (step - 1))][step - 1]);
        }
    }

    for (int i = n - 2; i >= 0; i --){
        if (a[i + 1] < a[i]){
            if (gr[i] != i)
                jump_right[i][0] = pos[get_min(i, gr[i])];
            else
                jump_right[i][0] = pos[get_min(i, n)];
        }
        else{
            if (sr[i] != i)
                jump_right[i][0] = pos[get_max(i, sr[i])];
            else
                jump_right[i][0] = pos[get_max(i, n)];
        }

        for (int j = 1; j < LG; j ++)
            jump_right[i][j] = jump_right[jump_right[i][j - 1]][j - 1];
    }


    for (int i = 1; i < n; i ++){
        if (a[i - 1] < a[i]){
            if (gl[i] != i)
                jump_left[i][0] = pos[get_min(gl[i], i + 1)];
            else
                jump_left[i][0] = pos[get_min(0, i + 1)];
        }
        else{
            if (sl[i] != i)
                jump_left[i][0] = pos[get_max(sl[i], i + 1)];
            else
                jump_left[i][0] = pos[get_max(0, i + 1)];
        }


        for (int j = 1; j < LG; j ++)
            jump_left[i][j] = jump_left[jump_left[i][j - 1]][j - 1];
    }
}

int calc_f(int l, int r){
    int ope = 0;
    for (int i = LG - 1; i >= 0; i --){
        if (jump_right[l][i] <= r and jump_right[l][i] > l){
            l = jump_right[l][i];
            ope += (1 << i);
        }
    }

    for (int i = LG - 1; i >= 0; i --){
        if (jump_left[r][i] > l and jump_left[r][i] < r){
            r = jump_left[r][i];
            ope += (1 << i);
        }
    }

    return ope + (l < r);
}

thanks for the great contest! i really liked problem H.

It’s down now. What happened?

can you do a blog edu about binary tree on segment search in O(nlog) compilation time ?

sorry I meant binary search on tree segment

r/wooosh

If I was there, I would surely ask Bill why they allow for such discrimination in ACPC. Can someone please do it for me?

As long as $$$1$$$ is not one of the chosen elements to be local maximums, then such construction will lead to values $$$\geq n+2$$$ for local maximums and $$$\leq n+1$$$ for other values.

A: I guessed we should greedily remove (1, 1) from 2 highest score until there is 0/1 positive score left.

B: I guessed it's binary searchable.

C: I guessed only considering position 2 and 3 is sufficient.

D: What should I guess? XD

Thank's! will see the hint after AC :)

Is it just me who solve A with a naive dp? Can't even come up with any solutions now xD

This blog became more of an orz warks profile review than AMA!

Nummer_64 will win IOI2024!!

And PieArmy will win EJOI2024!!!!

When you die, would you rather not exist at all or have a 99% chance of going to heaven and a 1% chance of going to hell for eternity?

I ended up coming up with the editorial solution and another in the contest, so I'll describe them both:

Editorial Intuition We suppose $$$n$$$ has odd index and then try to make all odd elements into peaks. Is it possible? The worst case might be when $$$1, 2, 3 ... n/2-1, n$$$ are the elements in the odd positions and $$$n/2, n/2+1, ... n-1$$$ are the elements in the even positions. We can even go further and assume $$$n-1$$$ is next to $$$1$$$ and $$$2$$$, and $$$n-2$$$ next to $$$2$$$ and $$$3$$$ and so on.

Obviously let's assign smaller labels to the ones in the even position and larger labels to the ones in the odd positions. Well $$$n-1$$$ gets the label $$$1$$$, so $$$1$$$ and $$$2$$$ need the labels $$$n$$$ and $$$n-1$$$ respectively, and then continuing in this way we can make the observation that you call counter-intuitive.

My Intuition We can construct $$$q$$$ so that all the $$$a_i$$$ are equal (make $$$q_i + p_i = n+1$$$).

Now we want to reorder some elements of $$$q$$$ such that all the odd/even elements become peaks. Since all elements of $$$a_i$$$ are equal at this point, we just need to reorder the elements of $$$q$$$ so that the ones in odd indices increase, and the ones in even indices decrease (or vice versa).

There's a lot of ways to do this, the first one that came to my mind is just suppose that $$$n$$$ appears at an even index $$$2k$$$ and sort the odd indices in increasing order of value.

Then do $$$q_{o_1} \rightarrow q_{o_2} \rightarrow q_{o_3} \dots \rightarrow q_{2k} \rightarrow q_{o_1}$$$.

i.e. the smallest odd index gets value of the next larger odd index, etc. and the largest odd index gets the value of n.

I hacked it with the obvious test case. You got lucky with weak system tests.

You can write contest from only one account and you can only have 1 account.

You create a vector of size 1e6 every test case. Since the number of the test cases may be up to 1e4, your code leads to TLE.

interesting bro. ples publish mor content

So you are proud of being a troll with no life?

As a contestant, qwerasdfzxcl is handsome

I believe priority queue is better as it uses heap instead of a balanced BST, which makes it better in terms of time complexity(better as avl rotations have higher constant factor than extract max of heap) and space complexity(no need of pointer to left and right child as would have been needed in balanced tree for set).

Fuck it, it is 5:30 over here, we have to start in 3 hours and I couldn't sleep yet. I don't understand what is going on. I hope you haven't poisoned me guys.

Ice_man2.0 will win EJOI

I found the problem. It was on the 48-th line, because $$$j$$$ could be negative, which led to negative indexing.

In my humble opinion, these recent announcements are not entirely fair to those individuals in top positions, as they were clever enough to unravel the hidden aspects of the contest unaided. Now, they may face additional competition for the top spots. While such adjustments might be acceptable in a 'just for fun' contest, they seem unjustified here, especially considering the significant monetary stakes involved.

Fear not, top performers! I pose no threat to you! I currently reside at the bottom of the leaderboard and intend to stay there for the duration of the competition. :)

Good luck!

idk it sounds cool

Pretty much. You do the round before it is held and give feedback to problem authors. You can also upsolve and give suggestions and feedback to authors even after testing. Basically helping with problems as it's much easier to make good problems when you have opinion from a lot of people.

Why do you think so?

I think for Problem C hint 2 should be n/2-1.

prvocislo

A bit tougher than usual Div2, but the problems were amazing.

I felt B > C, especially proving that binary search works in B has taken a lot of time.

The fact that n is even should signal that maybe you can somehow split numbers into two groups.

Secondly, it'd fairly common to sort permutations in opposite directions (ascending/descending) and match them greedily.

Also worth noting, it's very easy to get sums of all elements of final array to be equal to (1+n), by matching $$$p_i$$$ with (1+n-$$$p_i$$$).

This was my thought process during the contest, it's really just 3 standards ideas combined together. If you write all these out at some point you'll notice that you can ensure (n+2) is reachable in n/2 points so ot suffices to make the others no greater than n+1, which like we said has an easy construction.

great explanation sir : )

Hey! Check out my video solutions for the contest. I've covered Problem A-D here: https://youtu.be/owawrSp2ywU