IOI selection has not concluded yet please don’t spread misinformation.

This statement is.

Fun fact: the setter has solved 4000+ problems on codeforces and 10k+ problems on a Chinese online judge(which provide the remote judge service of codeforces and atcoder). I'm so shocked by his hard work.

This statement is true.

This statement is false

Thank god I'm unrated

All of these statements are false

Upvoted both the blog and this comment. Luckily no one hate CMs.

why

I am a CP enjoyer, CF Master, IOI medalist, problem setter myself, and probably a member of the Serbian committee from next year

This statement is false

I proved that the required upper bound is $$$O(N / \log N)$$$, but because creating a test case that achieves that upper bound also seemed non-trivial, I didn't seriously consider the constant factor. I ended up submitting with a slightly conservative estimate, taking into account the possibility of tight TL or ML. (Also, since the pretest succeeded with a limit of 1K, I submitted with a limit of 2K.)

While it might have been better to have some cases in the pretests closer to optimality, I think it's great that there were test cases in the system tests that required quite large upper bounds. Thanks for preparing a good contest!

wtf is this comment spam??

sto bnxe orz

An even number of the above statements are true iff the next statement is true.

I will elaborate on that.

You're right, it wasn't expected and that's mostly my fault -- I was able to come up with $$$O(n^2)$$$ solution pretty easily and thought that a lot of people will think about solution $$$O(n \cdot bound)$$$ after some time. In general, I don't want for last problem to be that hard and I will try to listen to feedback of other people more carefully. I still hope that people had fun thinking about this problem (and others problem of the round).

And one more point -- we intentionally didn't put in pretests tests where you need to use very big value of bound (maximum one that zltzlt was able to construct was around 3k and you can pass pretests with around 1k). I also want to elaborate on that. In general, I would vote for pretests to be as strong as possible, but here it was kinda special -- we didn't want people to try to squeeze solutions just with pure guessing (and since I've underestimated the problem, I thought that a lot of people will try to do so), that's why I agreed to not use such tests into pretests. In retrospect, I would insist on putting them (because problem already turned out to be too hard), and I fell sorry for maspy, congratulations on the win though!

IOI selection has not concluded yet please don’t spread misinformation.

The statement is undecidable.

sto bnxe orz

sto bnxe orz

sto bnxe orz

sto bnxe orz

It seems people will make accusations. I purposely avoided making any as I don't have evidence. I encourage others to not make potentially slanderous accusations without proper evidence.

For each of the statements above, either they are true or they are false.

sto bnxe orz

It wasn't fun at all

IOI selection has concluded already; please don’t spread misinformation.

sto bnxe orz

Bruv, the "just give me your codeforces password" part was smart, it would've been over for them.

C has a significantly simpler $$$\mathcal O\left(n \log\left(n\right)\right)$$$ solution. Notice that instead of stopping at the LCA, if the path has missing entries, it is valid to continue farther up the tree. The path only has to stop when it runs out of missing entries or it reaches the root. Therefore, assuming at least one entry is not missing, a simple solution is to repeatedly choose the largest entry $$$x$$$ with missing neighbors and replace those missing neighbors with $$$\left\lfloor\frac x2\right\rfloor$$$ (or $$$2$$$ if $$$x = 1$$$). This can be implemented in about 20 lines with a priority queue:

int n;
cin >> n;
vector<int> A(n);
for (int &a : A)
	cin >> a;
if (*max_element(begin(A), end(A)) < 0)
	A[0] = 1;

priority_queue<pair<int, int>> Q;
for (int i = 0; i < n; i++)
	if (A[i] >= 0)
		Q.emplace(A[i], i);
while (!Q.empty())
{
	auto [a, i] = Q.top();
	Q.pop();
	if (i > 0 && A[i - 1] < 0)
		Q.emplace(A[i - 1] = a == 1 ? 2 : a / 2, i - 1);
	if (i < n - 1 && A[i + 1] < 0)
		Q.emplace(A[i + 1] = a == 1 ? 2 : a / 2, i + 1);
}

for (int i = 1; i < (int)size(A); i++)
	if (A[i] / 2 != A[i - 1] && A[i - 1] / 2 != A[i])
		A = {-1};
for (int a : A)
	cout << a << ' ';
cout << '\n';

Clearly, you are the second type of person.

most intelligent grey

I love the $$$O(\frac{n^2}{\ln n})$$$ solution of problem F, however I spent my whole time in $$$O(n\log n)$$$ overcomplicated segment tree merging solution and mixed indices like tr[x<<1](should be tr[tr[x].ls]) then finally finished 10 minutes after the contest...

edit: I got the first blood!! so funny XD

There are 10 types of people: 1. Those who like bit manipulation. 2. Those who don’t like it.

I hate haters

Stucked on C for $$$45$$$ minutes and finally got 1 place lower than sevlll777, who solved 1 problem less than me. The slowest episode ever.

The long wait is over, and the ranking has been released.

May Luogu provide a English site just like atcoder?

purple sus

What the fuck of the C???????????

problem C has quite a bit heavy implementation.

Latin America, Argentina, Universidad Tecnológica Nacional — FRSF

Fruta Fresca 🍉🍋🍌🍍🍎

JPrime marianoferesin FedeNQ

I like when FBI tests the round ! I feel more secure

He is spamming long texts in this thread, so that people loose interest while scrolling through this blog. He is probably among those cheaters.

It's called qq because when you try to register you cry

Use the among us trick to find the real IOI team

OMG, jiangly's stream!

It was more like Div. 1.5

C's editorial is not friendly as a regular C. LCA is not something that most people thinking about in this position. There's still a solution without using such advanced topic, but why the author didn't do that?

I don't think ratism really a big thing, I think it's just the massive amount of glazing this community does for CMs, Masters, and Grand Masters.

Easy problems in abc are designed to require no algorithm but programming language.

AI masters programming languages very well and also know a little about algorithms.

It's normal for AI to solve these problems, or AI would be too weak.

to give div2 people a harder problem to upsolve

Why is today's G only worth 575 points? I think it is as hard as last round's G, which is 650 points. (and the statistics agrees with me too!)

Why i am still blue even my max rating has been changed to candidate master?

Tough contest. We weren't given enough time.

Auto comment: topic has been updated by zltzlt (previous revision, new revision, compare).

when will the rating be updated ?

https://www.islamweb.net/ar/fatwa/211225/القذف-حكمه-أنواعه-وضابط-كل-نوع-وعقوبته

I am 25 years old

Uzbekistan's team:

• Asilbek Sunnatov (Sunnatov) — 2nd time at IOI, 1 attempt left

• Husanboy Mansuraliev (Husanboy) — 2nd time at IOI, 0 attempts left

• Ulugbek Rahmatullaev (heaven2808h) — 1st time at IOI, 2 attempts left

• Mardon Hazratov (MardonbekHazratov) — 1st time at IOI, 0 attempts left

Nice investigation!

A possible explanation:

Intelligence and having a girlfriend is perhaps positively correlated in the general population, but this doesn't mean that every subgroup of intelligent people have a lot of girlfriends.For instance, the subgroup of intelligent 7 year old boys. Very few of them have girlfriends compared to the subgroup of intelligent 25 year olds. Here age is positively or negatively correlated with having a girlfriend. So it always depends on the characteristics of the subgroup you are looking at.

At CodeForces, there is an obvious other correlate at play, namely nerdiness (basically, are you more interested in objects or people). Nerdy people tend to have fewer girlfriends in most cultures, at least until the age where they begin to make bank. And, among intelligent people, nerds will be more likely to end up at codeforces, because codeforces attract exactly the people who are interested in numbers and objects. (Saying this, this doesn't mean that nerds don't want social interactions, it's all relative.)

With regard to the correlation between intelligence and beauty, there is another explanation in addition to yours: That posive traits like height, beauty and intelligence are all possitively correlated with each other because they are all caused by the same thing, namely good health. Good health here especially means good nutrition in early childhood and no unfavorable genetic combinations. If this condition of "no malnutrition and no genetic defects" is satisfied, people will on average be more intelligent, more beautiful and taller than those people who grew up with malnutrition and genetic defects (genetic defects can manifest themselves in many ways, so they are likely to affect both facial symmetry and development as well as height and brain development).

Will queue issues appear in contest because of EDU 166 system testing?

Will there be delays due to an overlap with yesterday's Educational round's System Testing?

I'm officially having skill issue with constructive problems (again) :D

look at the tester predictions, it is hard to be very accurate in predicting difficulties. F isnt very relevant for div2'ers anyways (only about 10 solve an average F?) that numbeer only decreased by 10.

Good luck to Mongolia's team!

I feel scared that AI will be stronger than many people.

if he is not lying about he's rating, then most probably he's account is funnylmao123, because there are only 13 1880 rated accounts on codeforces and it's the most suspicious one. I checked the contests of this account and most of A's was solved too late and it's the sign of that the person sends him ac code and he "modifys" it and it takes time, only a few time A was solved fast and these problems were too easy it means maybe he solved it in his own.

sto bnxe orz

If misinformation spreads this behavior, please cease you immediately.

The problems are quite suitable for Educational Round,I like this style.

Contest submissions should be prioritized over system tests.

Solution :

Alternative DP solution to F:

The problem choose the largest connected set of edges that has exactly $$$k$$$ leaves and contains the root can be solved with DP. Let $$$\mathrm{dp}_{i, j}$$$ be the answer for the subtree rooted at $$$i$$$, when taking exactly $$$j$$$ leaves. The transitions are straightforward — same as in knapsack. This gives us a $$$\mathcal{O}(n^2)$$$ solution.

Notice that the sequence $$$(\mathrm{dp}_{i, 0}, \mathrm{dp}_{i, 1}, \dots)$$$ is always concave for a fixed $$$i$$$. This can be easily proven with induction — the sequence in leaves is concave, and the max-plus convolution of two concave sequences is also concave. This gives us a faster solution. Instead of storing the DP directly, store the adjacent differences (they will always be sorted in non-increasing order). Then, we can use small-to-large merging, which gives us $$$\mathcal{O}(n \log^2 n)$$$ complexity.

More about max-plus convolution

Submission

"to beat a friend, makes it more interesting" — This is the most satisfying thing ^_____^

If people can reach candidate master and master with cheating than what's the point of anything.

Sure, it is probably demotivating to know that cheaters are reaching high ranks without putting in the hard work themselves. But reaching CM/M is not going to benefit these people at all.

Reaching a rank feels amazing when you do it through your own efforts, but doing it through cheating is basically pointless. Nobody hires based on CF rating, and people respect others not necessarily for their rank, but more for what they contribute to the community for others or for their results in official competitions where it's pretty much impossible to cheat.

While I agree that cheating negatively impacts people who 'play' by the rules, and sometimes (or perhaps more than sometimes) they may not be caught and take prize money, why not twist it into a source of motivation for you? It will feel even better when you overtake them because they didn't work hard and you did.

Look at the standings. It seems your F is too hard for a div2 so it works like a 5-problem round. Is that good?

Mongolia's team:

• Irmuun Chinbat (Irmuun.Ch) — 1st time at IOI, 1 attempt left

• Onolt Khurtsbilguun (Onolt_kh) — 2nd time at IOI, 0 attempt left

• Tamir Jamiyangarav (tamir1) — 1st time at IOI, 0 attempt left

• Erkhem Ganzorig (ezzzay) — 1st time at IOI, 2 attempt left

It could be that the cheater is actually out to "expose" high-rated users who sell out easily. OP made the right call here.

Using QQ is a terrible suggestion to someone who doesn't live in PRC and doesn't know Chinese. QQ-international is abandoned by tencent long ago and is not even supported on my device. When I tried to register in Play Store app, I got the following error message:

I tried to go here to register on a website, and it told me:

Your mobile phone number XXXXXXXXX is a security risk, please go to mobile QQ to register. If you haven't downloaded mobile QQ, scan the QR code below to download mobile QQ and register.

Then I had to download the app from https://im.qq.com/, because of course the version in Play store is outdated. Well, and after jumping all these hoops (and also passing Chinese CAPTCHA) I end up having this:

Meaning that they will not let me register with non-Chinese phone number no matter what, because I got the same error message on like 10 different days I tried to register over the last year. If you really want foreigners to get into Chinese IMs, at least suggest WeChat, it's somewhat possible to register and it actually has an English interface...

It's quite fun seeing I am blue with the rating of 2007 :)

but I believe it will update soon.

Managing different account.

well, well....

MikeMirzayanov please make this place out of such things.

Woohooo, let's go! Onsites are back!

same

It might be better to swap the D and E.

I could not understand your solution very well. It sounds like a great idea. Can you please explain in more detail (possibly with your thinking approach). Thank you

Someone will never think such complex solution in problem C!

I solved C with Two Pointers method, just filling the -1 gaps in the array!

My solution: 263542553

Time Complexity: O(n)

Uphacks are welcome!

Maybe you should ping the author chromate00 to check this.

No because $$$3500-2500\ne2500-2000$$$ :)

BitForces (

BitForces

Well there is an implementation which doesnt have such complications. One thing to notice is that there are only two types of distribution of workers. n + 1 programmers and m testers and n programmers m + 1 testers. For each i, if a[i] > b[i] remove it from the net sum of the n + 1 configuration, otherwise remove it from the net sum of the m + 1 configuration.

Dude actually requested MOD as a price xd, great blog btw

In the last contest EDU 166, it's pretty evident that tons of people have cheated in C, anyone can easily identify that by just looking at the code, these people have destroyed every platform wherever they go, whether it be Codechef or LeetCode. Codeforces need to develop some kind off mechanism to check otherwise it's going the same way as of LC & CC.

Adhoc dominates codeforces nowadays a lot.

This is something i have though about it lots of times and i think i have an accurate answer.

First of all, let $$$A$$$ being attractive, $$$B$$$ being social and $$$C$$$ going out, partying or any social activity, and $$$D$$$ doing math, CP or any intelectual acitivity.

It is pretty obvious that $$$A \implies B$$$, whether we like it or not, people that have A are more accepted by the society and that causes that they talk to more people, make more friends, etc. Im not saying that $$$\neg A \implies \neg B$$$, just saying that A makes it easy to go to B.

Also $$$B \implies C$$$ because if you have many fried groups, you will do activities with them probably.

Finally $$$B \implies \neg D$$$ most of the times because if you spend your time in social activities you have less time for intelectual activities.

So we get that $$$A \implies \neg D$$$ in most of the cases.

Love the first hint of the problem E