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

why

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!

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.

It wasn't fun at all

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.

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.

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

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

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.

May Luogu provide a English site just like atcoder?

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

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

Fruta Fresca 🍉🍋🍌🍍🍎

JPrime marianoferesin FedeNQ

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

problem C has quite a bit heavy implementation.

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

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?

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

to give div2 people a harder problem to upsolve

It was more like Div. 1.5

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.

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

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

Love the first hint of the problem E

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/القذف-حكمه-أنواعه-وضابط-كل-نوع-وعقوبته

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

I am 25 years old

MikeMirzayanov please make this place out of such things.

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 dont see why they should remove it either, its not like its disallowed

Solution :

My O(max(a) * log(max(a))) submission passes for E, maybe you didn't remove duplicates from the array?

Vladosiya back to CM

I think this is not a place to get political.

One of the ways to fix it is to add the target pragma AFTER the STL includes. This should make your code compile, but a lot of code would simply not be optimized, so use it at your own risk.

It is not necessary to leave the whole STL without optimization, you only need the place where the error occurs to be before any target pragma. If you look closely at the output, you will see that the error occurs at C:/Programs/gcc13-64-winlibs/include/c++/13.2.0/bits/allocator.h:184:7. So you need to add only #include <bits/allocator.h> before the pragmas to make your code compile.

#include <bits/allocator.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

int main() {
    std::vector<int> vec(100);
    return 0;
}

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?

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....

If you seek attention, then twitter is a better place for all these political topics. Leave this platform away from such stuffs. Nothing gonna change by such posts.

Hi! I'm glad you liked the post and hope you learnt something new from it.

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.

BitForces (

BitForces

I have consulted the coordinator for a way to fix this. If I can swap out the model solution to the $$$\mathcal{O}(n {\log_2}^2 n)$$$ tester solution that is guaranteed to work, then at least the problem becomes fine. I am unsure if this is possible however. I will keep you updated.

Strong!

Romania:

• Iulia-Ela Morariu (iulia.ela.morariu) — 1st time, 5 attempts left
• Ana-Maria Petcu (6ana6) — 1st time, 1 attempt left
• Ioana Mihaela Pașca (rockoanna) — 1st time, 1 attempt left
• Elisa Ipate (elisaipate) — 1st time, 1 attempt left

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.

APMO results still aren't out though

For example, consider the sequence [9, -1, -1, -1, -1, -1, -1, 5]. The solution presented in the editorial is to find the unique simple path from 9 to 5 in the binary tree ([9, 4, 2, 5]) and then alternate between 5 and 10, resulting in the sequence [9, 4, 2, 5, 10, 5, 10, 5]. Most of the complicated logic in the solution is for finding this path, and in particular, for finding 2, the LCA of 9 and 5.

My solution is to repeatedly find the largest entry with a missing neighbor and set its missing neighbor(s) to its value divided by two. In this example, 9 is initially the largest such entry, so set its missing neighbor to floor(9/2) = 4. Then, 5 is the largest such entry, so set its missing neighbor to floor(5/2) = 2. If the largest such entry is ever 1, we cannot set its neighbor to floor(1/2) = 0, so set it to 2 instead. Ties are broken arbitrarily. The full sequence of operations in this example is:

9 - - - - - - 5
9 4 - - - - - 5
9 4 - - - - 2 5
9 4 2 - - - 2 5
9 4 2 1 - - 2 5
9 4 2 1 - 1 2 5
9 4 2 1 2 1 2 5

For the last sample input, in the first step, 7 is the largest number, so set its missing neighbors to floor(7/2) = 3. Then, there are four 3's, each of which has at least one missing neighbor, so choose one arbitrarily (here I chose the first one). Then, there are two 1's and three 3's with missing neighbors, so chose one of the 3's arbitrarily (here I chose the last one). This case proceeds as follows:

- - 3 - - - - 7 - - 3 - -
- - 3 - - - 3 7 3 - 3 - -
- 1 3 1 - - 3 7 3 - 3 - -
- 1 3 1 - - 3 7 3 1 3 1 -
- 1 3 1 - 1 3 7 3 1 3 1 -
2 1 3 1 - 1 3 7 3 1 3 1 -
2 1 3 1 2 1 3 7 3 1 3 1 -
2 1 3 1 2 1 3 7 3 1 3 1 2

In the binary tree, this corresponds to choosing a path that gets as close to the root as possible and using the cycle 1 2 1 2 ... to fill any remaining space. This can be implemented easily using a priority queue.

Good job! Trolling cheaters is funny :)

who hates

Yeah. That is the point of ratism

cringe ahh post

Yes, it seem, this tickbird is made for leaving comments only. Here is his alt jinsu

In Div. 3 the most important thing is the number of solved problems. If 2 participants have the same number of problems solved, then a "penalty" is computed for each of them. The penalty is the sum over the solved problems of the number of minutes from the begining of the contest up to the accepted submission (I think that if you send 2 or more accepted submissions then the last one is the penalty giving one).

Penalty can also be accumulated by making wrong submissions, i. e. 10 minutes/penalty points per submission. Thus if you submit 3 wrong submissions and a correct one after 50 minutes from the start of the contest, your penalty will be $$$3 * 10 + 50 = 80$$$ for this problem. Do this calculation for each problem, sum the penalty and you get your total penalty.

It is best to have small penalty (i. e. solve problems fast with less errors).

very correct

For problem $$$C$$$, i found this logic. In order to go from one positive value to next positive value, we find the minimum no. of operations required, then if the required operations is less than given steps and has same parity as required, it is possible to go from one value to next, otherwise just return -1. This we do for all such positive values. Then, for first and last element, we just fill remaining -1s by doing *2, /2 and so on.
HOW TO FIND OPERATIONS EFFECTIVELY?
Let's say for example, we want to make 3 to 9, this can be done in 4 operations but how?
$$$(3)_1$$$$$$_0$$$ $$$=$$$ $$$(11)_2$$$ and $$$(9)_1$$$$$$_0$$$ $$$=$$$ $$$(1001)_2$$$, we just find the common bits from MSB in both, don't change them and first delete the uncommon ones from val1(here 3) and insert uncommon ones from val2(here 9). Here, common bits are only MSB, so operations required will be 1(for deletion from 3) and 3(from addition from 9), so total 4.
During removing, do /2 operation, doing addition and bit is 0, do *2 operation, bit is 1, do *2+1 operation. We do this for all pairs of positive values of a.
Submission Link :- 263497185

It's actually confirmed that they used AI, because if you see their submissions such as https://atcoder.jp/contests/abc355/submissions/54073783 and https://atcoder.jp/contests/abc355/submissions/54073778, it says "Generated by gpt4-o" at the top.

Some local environments, like CodeBlocks, tend to mostly give your program zero-filled memory on allocation. So the bugs like uninitialized variables are less visible then.

It seems that all the people participating in this round but not the next round and getting level upgrade have encountered this problem.

I only hate them who don't hate themselves.

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
ll bucket[200100];
int main()
{
    int z;
    cin >> z;
    while(z--){
		string s;
		cin >> s;
		ll n = s.size(), ans = 0, potential = 0;
		memset(bucket, 0, sizeof(ll) * (n/2 + 5));
		for(ll i=0; i<n; i++) {
			potential += (s[i] == '(' ? 1: -1);
			ans += bucket[potential];
			bucket[potential] ++;
			if(potential & 1ll) bucket[potential/2] = 0;
		}
		cout << ans << '\n';
    }
 	return 0;
}

UPD: I compressed my code further and I'm surprised to find that I now have the shortest correct solution for the problem.

wasa855 LJC00118 xay5421, Asia East, China, Peking University.

it's the penalty for a wrong submission in this round

You can solve all problems here: https://oj.uz/problems/source/652

Did he do it on purpose?

(I think that if you send 2 or more accepted submissions then the last one is the penalty giving one).

Actually, every submission after the first accepted one does not count, so the penalty is (the number of wrong submissions before the first accepted submission) * 10 + (the time in minute the first accepted submission was made). This is why you can freely submit multiple solutions if you have any doubt in your previous accepted solution without worrying about the penalty in Educational / Div. 3&4 rounds (as opposed to normal Div. 1 or 2 rounds where the earlier solutions become WA penalty).

Thanks for reply!
Exactly because of it's almost not a problem for ARC or above, serious competitors are almost not care this situation in the difficult round (and I also don't hope to be do hard banning of AI).
But in ABC, the situation is different. In ABC356, fastest ABCD gets about 1400perf so every green or below coder "shold" use this method. From Japanese community, it seems this strategy problem and "lose to ChatGPT" itself demotivated them and some of community members think this isn't healthy.
In addition, the thing that ABC focuses on education and guideline rather than competition makes this problem more complex, then switch ABC to more competitive (for example, make them more ad-hoc) is not a solution...

I will use the power of induction, going over the number of vertices in the tree.

The base is immediately obvious for n = 1 or n = 2.

Consider a vertex v != root. If we choose some set of leaf nodes L = {l1, l2, ..., lk} in its subtree, how many bridges do we remove? This number equals to the size of the union of edges of all paths from li to v, plus some number C, which does not depend on leaves in L.

Actually, C depends only on other leaf nodes we chosen — the ones not in L. It can be shown that C equals to the number of remaining bridges on the path from v to root after we choose all leaves do not belong L.

This means we can choose some leaf nodes outside of v's subtree, and then optimize leaves in Lindependently from others, if |L| = const(if their number remains constant). By inductive hypothesis for v's subtree, greedy is the optimal way.

Suppose we have some solution which is not greedy. Let's show that there is a vertex v, which subtree solved non-greedy (and we can make it better). Just take 2 leaves: l1, which will be taken in greedy solution, and l2, which was taken instead of l1. Choose v = LCA(l1, l2).

P.S. May be there is some inaccuracy in my proof, such as deg(root) = 1 condition in the problem, but induction does not use it. We need this condition only to find out that we should connect root with 2k-1 leaves, so there is no problem.

C is not a C. D is not a D.

I think CDEF should be DEFG, and insert an easier C.

Firstly, that wouldn't be helping anyone.

I shouldn't even need to add to that, but I will. I am simply against it, as I said in my blog, you are only fooling yourself. And obviously, I do not want to be associated with such a thing. I am a CP enjoyer, CF Master, IOI medalist, problem setter myself, and probably a member of the Serbian committee from next year. I am not going to give all of that up over some small amount of money.

Even when I help people with upsolving problems, I also do not like to give solutions. I prefer to give just hints, as most fun comes from figuring out the problem and enjoying the process of going from reading to AC. Without it, AC doesn't feel special.

I was expecting a problem to minimize the error, but it turned out to be a problem to cancel the error knowing the accurate answer. Still a fun problem, but it seems not as useful in practice as advertised (they said "addressing this challenge", not "a problem inspired by this challenge"). It would be surprising to me if the organizer could use any of the algorithms in this contest on their chips.

:)) In our country the children day it's June 1

maybe its all to get more contributions

Wow it is less than 24 hours?!?

Please come join the contest. Fun guaranteed!

GLHF!

This didn't seem like a Div. 2.

Any smart solution for C? Feels like another boring implementation task that I can't care less debugging. Took a huge L today.

Will the rating changes of this round be calculated on the ratings before the EDU or on the updated ratings of the EDU?

Same

Wait. maspy FSTed on problem F???

A 0-solve D2F??

I think people cheat so that they can show it in their resume that they have such and such rating and title on codeforces. But even that is not very effective as truth will be out when the company interviews you on your coding skills.