Very nice round!

IOI 2024 Team Russia

• Daria Grekova (arbuzick) — 1st time at IOI, 1 attempt left

• Ivan Piskarev (Qwerty1232) — 2nd time at IOI (IOI 23 Gold), 0 attempts left

• Gimran Abdullin (bashkort) — 2nd time at IOI (IOI 23 Gold), 1 attempt left

• Petr Losev (green_gold_dog) — 1st time at IOI, 1 attempt left

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

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.

Japan's team:

• Shogo Amacho (PCTprobability) — 2nd time at IOI, 0 attempts left
• Katsuki Ohta (shiomusubi496) — 1st time at IOI, 1 attempts left
• Ryotaro Hayashi (Forested) — 1st time at IOI, 0 attempts left
• Yuya Hirasawa (hirayuu_cf) — 1st time at IOI, 3 attempts left

Now PinkieRabbit was skipped and got a -220 rating. Glad to see that.

Guess why

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

as a not-so-high-rated div1 user, i cant seem to agree. Basically, as in any high-level competition, standard problems are not recommended: they aren't gonna distinguish anything other than whether you know the algorithm and its standard applications well enough. This isn't algorithmic thinking.

I agree with your opinion on div4 and div3, but cannot agree on div2. as some famous lgm said, "there shouldn't be standard problems in div1s." div2s problems are usually standard to some extent, so maybe they won't be a good fit for a div1 contest. Of course, exceptions can be made, but i wanna hear the community's opinion on this too:)

Taiwan's team:

• Chen Po-Kai (becaido) — 2nd time at IOI, 0 attempts left.

• Chang Ping-Chung (PCC) — 1st time at IOI, 0 attempts left.

• Chao Yi-Yu (zacharychao) — 1st time at IOI, 0 attempts left.

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

Vietnam's team:

• Nguyen Huu Tuan (ahihi1234) — 1st time, 2 attempts left
• Pham Cong Minh (socpite) — 1st time, 0 attempts left
• Pham Ngoc Trung (hotboy2703) — 1st time, 0 attempts left
• Hoang Xuan Bach (bachbeo2007) — 1st time, 1 attempt left

Ukraine's team:

• Andrii Smutchak(xGaz_) — 2nd time at IOI(IOI 23 Silver), 0 attempts left
• Ihnat Zharikhin(Ignut) — 1st time at IOI, 0 attempts left
• Denys Tereshchenko(TheQuantiX) — 1st time at IOI, 0 attempts left
• Permiakov Illia(160cm) — 1st time at IOI, 0 attempts left

This has been talked about before and the general consensus seems to be that while these last problems of Div. 2 contests may be hard, they are also too standard to be suitable for a Div. 1 contest.

the hero we do not deserve

I think probably the problem setters want these rounds to be “educative”. For example, I participated all the 3 rounds you mentioned in your post, and I learned a lot from them like 2-sat and using exgcd to solve Diophantine equations.

Perhaps different people have different standards to measure if one problem or round is “interesting”. I agree with that rating plays an important role in CP, but IMO seeing much harder things is also a must since it stimulates us to keep learning and practicing.

And also, beside these hardest problems in the rounds, the difficulty of other problems seems normal to the participants from respective divisions. So they can enjoy the contests while learning new stuff.

IMO you should not stop giving div2’s altogether. It’s better to have a lower true rating than a higher fake rating. Plus, the only way to get better at solving div2C’s in contest is to attempt doing so.

Well, it's added.

As I said in my original comment, I just want him to say that what he did was wrong, and that he will never do it again, and return the 2 TON he got from cheating. Is it really that hard?

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

D is created only to give pain and trauma :skull:

For me personally, the latest div3 tasks were very useful when I was a specialist/expert. And I think that only by solving them, I was able to quickly improve from 1500 to 1900 (you can look at the graph and make sure).

Therefore, I think that it is necessary to look for such tasks where it will be possible to pump your skills quickly with a minimum of effort. And one of these tasks for beginners is div3/div4, just get out of your comfort zone.

Umanity will win EJOI 2024

I think this was recently skipped too. He was mentioned as master in the round announcement.

#include <iostream>
#include <stack>


using namespace std;

// Calculate the fp32 sum sequence like {s:1,2,3}
double calculateFp32(stack<double>& nums) {
    float currResultSingle = 0;
    while (!nums.empty()) {
        currResultSingle += static_cast<float>(nums.top());
        nums.pop();
    }
    return static_cast<double>(currResultSingle);
}

int main() {
    stack<double> s({1.0e-10, 1.0e-10, 1.0e0});
    double answer = calculateFp32(s);
    printf("%.20lf\n", answer);
}

This code prints 1.00000000020000001655 under "GNU G++17 7.3.0", and prints 1.00000000000000000000 under "GNU G++20 13.2". In addition to that, if we add a printf like printf("value: %.20lf\n", nums.top()); currResultSingle += static_cast<float>(nums.top());, the result changes to 1.00000000000000000000 under "GNU G++17 7.3.0".

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

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

How is your IOI?

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

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

A little difficult, but absolutely a nice contest and high quality problems.

Three LGMs in china's team is crazy...

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

FREE TwentyOneHundredOrBust!!!!

MikeMirzayanov

The 4th participant has not been determined yet.

Please write suffix array template and never submit hashing solution again

Some may be standard for IGMs and LGMs, but I don't think it holds true for most Masters and low reds. Many, not all, Div 2 rounds are definitely suitable for a "Div 1.5" and the coordinator should be able to decide this.

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.

Finally i have reached master

bump

← Anonymous Tester

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

In some cases, this actually seems useful for finding a balance between time and memory. For example, it seems that it is better to use flat_map when storing edges at the node of a trie.

As far as I understand this is just an implementation like vector<pair<Key, Value>> with sorted Keys. And it works great with cache.

no it is created by Sergey Kolodyazhnyy

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.

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

Is there going to be a mirror?

Deducing this, std::flat_map, std::print

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.

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

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

Great problems!

Cheating report comments are also getting banned, even tho they do not violate cf rules

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.

As a tester, I

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?

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

I have some trouble understanding the given proof for the $$$O(1)$$$ solution for Problem A. I'll explain how I got that solution. Let us take an optimal solution (i.e., a solution with the max possible number of draws that corresponds to the given values of $$$p_1$$$, $$$p_2$$$, and $$$p_3$$$). The total number of games played is $$$\frac{p_1 + p_2 + p_3}{2}$$$. Let $$$a$$$, $$$b$$$, and $$$c$$$ denote the number of draws in the $$$A_1$$$ vs. $$$A_2$$$, $$$A_2$$$ vs. $$$A_3$$$, and $$$A_1$$$ vs. $$$A_3$$$ matches respectively, where the names of the players are $$$A_1$$$, $$$A_2$$$, and $$$A_3$$$. Since this is an optimal solution, the correct answer to the problem is $$$a+b+c$$$. Now, if it so happens that more than one of these players had wins (say, $$$A_1$$$ and $$$A_2$$$ both had nonzero wins — say, $$$k_1$$$ and $$$k_2$$$) — then, we could have repurposed them as $$$\min(k_1,k_2)$$$ more draws in $$$A_1$$$ vs. $$$A_2$$$ games, and one of them having $$$\mid k_2 - k_1 \mid$$$ wins instead, contradicting the optimality of our solution. Therefore, we may assume that only one of these players had wins (if any), say $$$w$$$ of them, in our optimal solution.

Suppose $$$A_3$$$ is the player who had all $$$w$$$ wins ($$$w \geq 0$$$) in our optimal solution. Then, $$$p_1 = a + c$$$, $$$p_2 = a + b$$$, and $$$p_3 = b + c + 2w$$$. Solving for $$$a$$$, $$$b$$$, and $$$c$$$, we get $$$a = \frac{p_1 + p_2 - p_3 + 2w}{2}$$$, $$$b = \frac{p_2 + p_3 - p_1 - 2w}{2}$$$, and $$$c = \frac{p_1 + p_3 - p_2 - 2w}{2}$$$. Verify that these values for $$$a$$$, $$$b$$$, and $$$c$$$ will be the same even if you assume $$$A_1$$$ or $$$A_2$$$ won all $$$w$$$ games! Note that we get integral solutions for $$$a$$$, $$$b$$$, and $$$c$$$, iff the number of odd numbers in $$${p_1, p_2, p_3}$$$ is even. If this is not the case, we output $$$-1$$$, and finish.

Now, thanks to $$$p_1 \leq p_2 \leq p_3$$$, $$$w = 0$$$ (i.e., all games are draws) leads to a valid (i.e., nonnegative integer) solution for $$$b$$$ and $$$c$$$, and a valid solution for $$$a$$$ only if $$$p_1 + p_2 \geq p_3$$$. That is, if $$$p_1 + p_2 \geq p_3$$$, the answer we must output is $$$\frac{p_1 + p_2 + p_3}{2}$$$. The case left to deal with is when $$$p_1 + p_2 < p_3$$$. To make the value of $$$a$$$ nonnegative, the minimal value of $$$w$$$ to be set (we want a minimal value for $$$w$$$ as we want maximum draws) is $$$\frac{p_3 - p_1 - p_2}{2}$$$. With this setting of $$$w$$$, we get a valid solution $$$a = 0$$$, $$$b = p_2$$$, and $$$c = p_1$$$, so that the answer is $$$a + b + c = p_1 + p_2$$$. I wrote this solution (sadly, after the contest) and it was accepted.

Regardless of the high or low, I think rating after solving 4 or more tasks is more true than solving 2 or less. The latter tends to be more easily fluctuated by luck than the former.

According to regulation schedule, the contest window is over. But is it truly over? Are there anyone who didn't participate?

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

No one need disjoint set union solution!! put like to get

can't accept that mike neglects cheating behavior of an lgm for so long

My post contest discussion stream

Also, can someone hack my solution for G?
Gentle ping maroonrk because of this

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.

Same lol, I used Sparse Table and Binary Search. Ig I really over killed it.

The checker seems deterministic, why would the order of operations change?

Could you share this situation or describe how to reproduce it? I don't think it should be legal in this code in standard C++, at least with IEEE 754-compliant FP arithmetic.

Could you share this test? float->double->float roundtrip should be lossless.

Edit: The example yosupo provided answers all my questions; "GNU G++17 7.3.0" doesn't strictly adhere to IEEE 754.

Interesting. I was aware of this issue a while ago, but lately couldn't reproduce it so discarded the knowledge as no longer relevant in practice. Thank you!

I thought that was the point of educational rounds, to learn to be able to use techniques and algs that you wouldn't be able to use on problems like game theory.

the current format is more educational than competitive which i like for lower divisions and when u get to div 1 where competition starts then its fair for everybody i think divisions which target lower rated participants should focus more on the educational side than the competition side

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

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.

my hardest div.2 till now

Why do you think so?

Yes of course if the blog have +50 likes

don't waste time or energy learning advanced stuff, just focus on simple 9th grade math, logic and thinking. after u got better at that(rating around 1000), learn prefix sums, sets, lower/upper bound

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 : )

I have another solution for F, which run in 796ms, but I don't know the time complexity for it
https://codeforces.com/contest/1973/submission/261433060
Idea: - Calculate least common multiple (lcm) for each pair a,b
- Calculate lcmv = gcd of all lcms
- Reduce a,b of each pair to gcd(lcmv, a), gcd(lcmv, b)
- Add cost of all elements with the same new a,b (From the observation that for any i,j, if ai == aj and bi==bj then we must either swap i,j or not swap any)
- Sort all triple (a,b,c) by a ascending, b ascending
- For each item, maintain a map of (a,b) => minc; with a,b is the current gcd of sequence a,b; c is minimum possible cost
- After that, we create the array of [(sum gcd value), (min cost)] ascending for both elements, and do binary search for each query

Youtube channel won't help you grow dude, Problemset will.

Separate things properly. If PinkieRabbit really is a cheater, he should be punished accordingly. And that doesn't invalidate the good deeds he had done, if any. Those two are completely independent topics, and none would outshadow the other.

You can't use your good past as an excuse for your present wrongdoing. And vice versa, your present good deeds might earn people's respect, but they don't fully delete any sins in your past — at least their marks for remembrance and atonement will always stand.

Wansur will win EJOI2024

Thank you!

When will every country participated and I can discuss problems?

Yeah, so lets take an example, lets say the array is this -

idx: 1 2 3 4 5 6
-----------------
  p: 5 1 6 2 4 3
  q: 2 6 1 5 3 4
-----------------
     7 7 7 7 7 7

Here $$$p[2] = 1$$$, so we try to make values at odd indices local maximums.

The values at odd indices are $$${5, 6, 4}$$$.

Since we are going to iterate over increasing values, we go in the order $$$4 \rightarrow 5 \rightarrow 6$$$.

So we first swap(q[pos[1]], q[pos[4]]) to get -

idx: 1 2 3 4 5 6
-----------------
  p: 5 1 6 2 4 3
  q: 2 3 1 5 6 4
-----------------
     7 4 7 7 10 7

Then we perform swap(q[pos[1]], q[pos[5]]) to get -

idx: 1 2 3 4 5 6
-----------------
  p: 5 1 6 2 4 3
  q: 3 2 1 5 6 4
-----------------
     8 3 7 7 10 7

Then we finally perform swap(q[pos[1]], q[pos[6]]) to get -

idx: 1 2 3 4 5 6
-----------------
  p: 5 1 6 2 4 3
  q: 3 1 2 5 6 4
-----------------
     8 2 8 7 10 7

And we are done!

in C 2nd hint

n/2 -1 not +1

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