Hi Codeforces!
As the Chinese New Year approaches, we are glad to invite you to our Codeforces Round Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2) which will be held on Jan/26/2025 17:35 (Moscow time). You will be presented with $$$8$$$ problems, one of which is divided into two subtasks, and $$$2.5$$$ hours to solve them. This round will be rated for all participants.
This round is the first Div. 1 + Div. 2 round on Codeforces with a four-digit round number, and it is also my first round. We hope you will enjoy this round.
Great thanks to:
- SSerxhs for helping me prepare most problems,
- Yakumo_Ran for providing some problems,
- TheScrasse for good coordination of this round,
- Alexdat2000 for translating all statements to Russian,
- EvenImage, ugly2333, dXqwq, Sugar_fan, propane, LuCpp, triple__a, PinkieRabbit, fallleaves01, thenymphsofdelphi, N_z__, tarjen, tiger2005, golomb, Tobo, add10k, Kieray, meowcneil, huansir, Phantasmagorias, Cai_Guang, fr200110217102, Nanani, shstyle., Theresa_Apocalypse, wjy666, PaperCloud, Kepy, _Sherbiny, nnv-nick, EternalJourney, shendeliliang, Alex2025_qwq, sabino1, larush, Kraska, yorisou, umazing, Enderwitherzjdl for testing our round,
- MikeMirzayanov for the amazing Codeforces and Polygon platforms.
Good luck & Have fun!
upd1: The score distribution is as follows: $$$500 - 1000 - 1000 - 2000 - (1500 + 2500) - 3500 - 4000 - 4500$$$
A few words from our sponsor:
Hello, Codeforces!
We are Ethflow, a proprietary trading fund specializing in cryptocurrency trading, and we’re glad to host our first Codeforces round!
Participants will have a chance to win T-shirts:
- The top 50 ranked competitors.
- 50 random participants who solve at least 3 problems and rank below 50th place.
Our team includes Codeforces grandmasters, IOI/IMO medalists, and ICPC Finals competitors. At Ethflow, we value people and create an environment where you can focus on challenges you enjoy, exploring everything from infrastructure to analytics without toxic practices. To join our team, please fill out the form.
Good luck to all participants!
upd2: Editorial
Congratulations to the winners!
As a writer, it's the second round I put in a lot of effort to. Let's see if jiangly can keep jiangly as he has registered.
Besides, I have prepared another mysterious mission. If anyone solves it, share it!
As a tester...I met StarSilk during the EC-Final and found he is a little white cute cat( = · ω · = ) and I'm very appreciate to the problems in this round created by StarSilk , SSerxhs and Yakumo_Ran.Hope every participant enjoy this round!
As a tester, I recommend to invest bitcoin instead of ethereum :)
As a tester, it's my pleasure to enjoy such miaomiao problems. Hope u enjoy them, too.
Look look miaomiao problems( = · ω · = )
Look look miaomiao problems( = · ω · = )
Hope I will not jiji in the contest.
Hope to meet a perfect game on the 1001st night
As a tester, I think this match is fantastic, and I hope everyone can enjoy these meowmeow questions( = · ω · = ).
As a participant $$$1001$$$ is the first $$$4$$$-digit palindrome.
$$$0000$$$ has 4 digits and is smaller than $$$1001$$$... sir!
0000 is not a four digit palindrome it is a one-digit palindrome
As a participant, I can confirm that $$$1001$$$ is a composite.
As a tester, I confirm that StarSilk is a cat.
as participant i will share you a fact for fun, if you write a number n>=100 and n<=999 and write the same number to it's exactly right, then the new 6 digit number formed will be divisible by 1001.
As a tester, hope every participant enjoy the 'SSSS round' authored by StarSilk,SSerxhs and Yakumo_Ran. :)
Thanks for providing amazing problems for all Codeforcers.
As a participant, i hope i can gain non negative delta
HOPE TO GET POSITIVE DELTA
As a tester, I can finally say that I TESTED. Really good contest, I hope everyone gets positive delta.
As a participant, I can confirm that 1001 is the product of 3 consecutive primes!
Score Distribution.
Score distribution ???
Score distrib => Speedforces?
I hope to become CM in this contest.
Another Speedforces round ! :(
No, C will make me cry..
Uss moment
uss.
there is a problem with rating (1500 + 2000 ) .. I understand that it will have 2 parts , easy version and hard version but is 1500 rating for this problem easier than the problem before that which has rating of 2000
I am asking this because I have seen such difficulty ratings in previous competitions but still solves for that lower rated problem ( which is easier version of some harder problem ) is generally lower than an earlier problem which can be more rated
As far as I know, yes, it will (or should, as the scores are not always accurate) be easier. That's probably because most participants try to solve the problems in order (this also affects the problem difficulty afterwards, which might explain why the difficulties are usually increasing even when the scores are not).
Also note that (since someone always asks this in contest announcements) that the hard version's actual score (its score if it was a single problem without subtasks) is 3500 (1500+2000), not 2000.
thank you for the insight,
this will help me plan how I do the problems. I will peek at that lower-rated problem once before I spend time on an earlier higher-rated one
could you please explain should i attempt the 1500 one before or the 2000 one
Well, the 1500 one is easier. On the other hand, the score of problems worth more points decreases faster that problems worth less.
Personally, I just solve them in order, but that's probably not be the best strategy.
Since speed is the most important thing, you should look at both and solve whichever one you can do faster first (which is what I did, and solved E1 before D).
That might be a good idea (I've planned to do that before, but usually stick to the actual order, though).
Anyway, my advise: always have the number of solves in mind, and, if you can't solve a problem, check the next one.
There are cases of contests where earlier problems worth less points are harder than later ones, and you might waste time on a harder problem if you don't notice the difference in the number of solves. Also, sometimes, a problem that's hard for most people might be easy for you, especially if it's based on a topic you're good at.
Of course, you should also remember that the number of solves might be affected by other things, like in problems with subtasks.
thank you so much for your insights, this will definitely help me.
I think I need to work on my strategy also along with DSA, LOL
To be honest, I don't have a specific strtegy for CF contests, just lessons I learned by participating, like this. Just practice and even if you participate without a specific plan, your rating will grow.
That's also true for OIs, even what I consider my "strategy" isn't something I conciously do, just something I realised I do.
Besides, different strategies work for different people.
yes, I will try to participate and practice more.
glhf xD
As a contestant, I really think StarSilk is a cat
unfortunately jiangly has to lose his title soon
how to do DIV 2D?
Exactly the same way as DIV 1D.
Just go to topmost right corner and right click.
B,C were weird (not in a bad way) but actually really easy if you think simple. I wonder how GPT did on this contest.
how did you solve C? I was searching for my soul while thinking of ways. Also it'd be great if you could explain your thought process leading to any observation
Plain brute Force!
At every step we can have 2 choice, do diff OR do reverse and diff OR (current sum though this doesn't require an extra step). that leads to 2^49 possibilities in BF. So how did you applied BF? I guess it must be some better observation on which you did BF.
at everystep we have 2 choices but we will discard the one with less sum and move on
n<=50 , brute force it first check diffrence sum if you dont reverse the array lets say its X then reverse the array and check diffrence sum Y if X>Y assign cur_array= array wihout reverse else cur_array = diff_array (after reversing) untill array length becomes 1 keep track of ans=max(ans,max(X,Y))
what's the intuition/proof that this works??
think of vector operation
You brute force all possible difference arrays and take the maximum of the absolute value of the sum of each array. It can be shown that the absolute value of the nth difference array is always the same. Code
Here was my thought process:
Started with a naive solution (recursion): At each step, we can do one of three things: - Accept the current sum and stop the process - Reverse the array - Replace the array with its diff (as explained in the problem statement).
This worked, but is super slow, so let's see how we can optimise it.
First observation, since the length of the input array is 50, we can replace the array with its diff at most 49 times (specifically, at most n-1 times), after that, we can no longer make any move.
Second observation, reversing the array twice consecutively is worthless, as it will have no effect on the result.
From these observation we conclude that we are looking for a sequence of operations such that there is never 2 consecutive reversing, and no more than n-1 diff operations. So it should look something like this: [R,D,D,D,R,D,...] (R for reverse, D for diff).
Notice that an R must be followed by a D.
Now notice the following: Say we have an array
[a1, a2, a3, a4], if we do diff directly, we get[a2-a1, a3-a2, a4-a3], if we do reverse followed by diff, we get[a3-a4,a2-a3,a1-a2].What do you notice? We got the same elements, but multiplied by -1.
It means that if doing diff eventually gives us a solution X, then doing reverse then diff should give us a solution -X.
So now we can reduce the recursion complexity a lot, because we only need to discover one of the two branches, the opposite branch is just -1 * the first one.
Thus, we can simply do the following: At each step, check the current sum, then compute the diff and do recursion to get a return R. Finally, return
max(sum, abs(R)).We have tested ChatGPT-o1 and Deepseek-R1 before the contest.
GPT: Solve AB.
DS: Solve A, write a correct but $$$O(n^2)$$$ solution for B.
carrot extension is not working anymore?
so where is the solution?
editorial takes some time, hoping that they upload it fast
My screencast (in Rust) will be available once it ends uploading
Finally got master!
E1 is really nice for both the idea and the implementation(although my one may be complicated).
Guessforces. So helpless when coding.
F is cool
Why guessforces???
This time I really guessed B first before proving it
Why 2.5 hours?
Cuz 2.6 would be kinda awkward
for A and C I couldn't make any observation so for A I just simulated greedily and for C I just assumed that there is no point in reversing twice ( no proof , but my pretests passed )
now I hope for good results
although I later realized that for A you can just count number of 1s .. NOOOOOO !!!
Why do you not use Alice and Bob? If you are going to use dumb names with no relevance that make the problem harder to understand, at least try to not swap the gender in the middle of the statement.
Why there is not hacking phase? I mean after contest there should be 12 hour hacking phase right ?
I think that is only for educational rounds (and for div3 ??).. not for div2 and div1 rounds, you can only hack during contest after locking your problem
if my problem is locked then i can hack on that problem of others?
yes, during the contest, you can lock your problem and hack solutions of other people
Okay Thank you man for helping a newbie :)
A: Answer is simply initial count of '1'
B: Answer is true if and only if a[i]>2*max(i, n-1-i) for all 0<=i<=n-1
C: Do operation 2 and pick the absolute value of sum(a[i]) at this moment, as a candidate answer. Repeat until length of a[i] become 1. The initial sum is also a candidate answer
D: Assume a[i] has been decided, then the answer is sum(max(0, a[u]-a[parent(u)])), where a[parent(u)]=0 when u is the root. Then we can find the answer simply by dp
E1: For any node u, if there's any other node v such that v is not in subtree of u, and w[v]>w[u], we call u "good node". Then any good node with maximum w[u] could be the answer.
F: Sort all pairs such that for all 0<=i<n-1, we have (a[i]-b[i]<a[i+1]-b[i+1]) or (a[i]-b[i]==a[i+1]-b[i+1] and a[i]<=a[i+1]). Then candidate answers will be:
maximum value of b[i]+a[j]+ sum(a[t]+b[t]) (i<j, sum over several t (possibly none) with i<t<j)
maximum value of 2*b[i]+a[j1]+a[j2] + sum(a[t]+b[t]) (i<j1<j2, sum over several t (possibly none) with i<t<j2 and t!=j1)
maximum value of b[i1]+b[i2]+2*a[j] + sum(a[t]+b[t]) (i1<i2<j, sum over several t (possibly none) with i1<t<j and t!=i2)
maximum value of 2*b[i1]+a[j1]+b[i2]+2*a[j2] + sum(a[t]+b[t]) (i1<j1<i2<j2, sum over several t (possibly none) with i1<t<j2 and t!=i2 and t!=j1)
We can find the answer by simple DP.
Please post this editorial every round
What is mathematical proof behind C ?
Also, E2, did you try thinking with PST ( persistent segment tree ? ). I had an approach, but code would be horrible. I don't know if my approach would work or not.
Interesting problem C, enjoyed the contest thoroughly
yea took me a while to understand that reversing only helps in changing sign and doesnot produce new value
C ruined my contest.
thanks for the problems. They were indeed enjoyable.
D absolutely killed me taking > 1 hr on it, but I was fast on F so fortunately my rating is saved at least.
50 random participants who solve at least 3 problems and rank below 50th place.
I should have figured out earlier why the count was set to 3 problems.. The steep rating change between C and D broke my soul !!
Indeed a SPEEDFORCES Round..
What I did in the contest:
Guess A, then passed.
Guess B and passed.
Guess D and get WA.
Guess C and passed.
Guess D for another solution and passed.
Guess E1 and passed.
The contest end.
What a terrible experience!
What did u Guess in C..?
We will only reverse 1 or 0 times.
The proof for C is this: Let $$$r$$$ be reversing, $$$d$$$ be taking difference, and $$$1$$$ be the identity operation. Then it is easy to see $$$rdr = -d$$$ and $$$r^2=1$$$. So any sequence of $$$r$$$ and $$$d$$$ can be converted to a canonical form $$$r^i d^j$$$ where $$$i\in{0,1}$$$.
And for the reverse direction, any $$$d^n$$$ can be converted to $$$-d^n$$$ via either $$$rd^nr$$$ or $$$rd^{n-1}rd$$$, depending on the parity of n.
I did proove for B, rest of it i just guessed too, i dont know if it just me , but it feels annoying to give 2.5hrs and get nothing of it and also its so unsatisfying to guess and pass
This contest is just like my life. Fucked me up. [EDIT: Removed an asked question.]
That won't run in time since each node has a range of starting values instead of a specific value. You can't brute force all possible combinations of starting values.
Thanks.
PS: I am under water.
Just get grammarly!
nice one !!!!!
Great contest!
Loved the problem statements and the ideas.
Nice!
For E1, I used Euler Tour and Segment Tree, and it took a little over 1 second. I heard that the intended solution needs to be in half the time limit, so 4 seconds works. 2 seconds would make intended solutions TLE I believe.
Did anyone else not realize that you needed
longs for problem C?I changed it at the last minute before submitting
I stress tested some random testcases and noticed that they looked a bit weird
Some realized that it avoids a lot of problems to allways use 64 bit since it costs like nothing.
i use java and in java indexs can not be long and i am lazy....
Java is the new Cobol ;)
I did not use long for C: https://mirror.codeforces.com/contest/2062/submission/303063303
it passed main tests
You are using 64 bit integers everywhere.
You’re right; unfortunately I can’t delete my comment now :(
Wtf, I just realized I used long long; must have been some god’s enlightment or something like that
I am still unable to understand why do we need long long in this problem. How can the sum go beyond 32-bit ?
Take 1000, -1000, 1000, -1000, … And see what happens when you keep taking the diff between two consecutive values.
The differences can go up to $$$2^n\cdot max(a_i)$$$. For example -1000,1000,-1000,...
guessforces!
D why
anyone solved E1 using small to large ?
Explain the solution pls
I sorted by weights large to small and used binary lifting, did you do it the other way around?
I did, but during contest, most of my time was wasted in researching about how to find "number of elements larger than x" and figured that PBDS would do the job but implementing that also took a lot of time. Not knowing standard stuff hurts. Anyways, my swap function was not O(1) which I figured after the contest.
AC submission (after contest): https://mirror.codeforces.com/contest/2062/submission/303136352
thankss
Hey I also had similar code as urs , Can u tell how swap is not taking O(1) time and how u changed that
my submission: 303167462 people can take a look
This problems are so bad
A terrible round, thank you
probably just me, but why did D and E both have to be tree problems
Literally me, but just change 12 to 22
same experience
Actually, I proved C also by using some tree construction
E1 was doable.
Treeforces (and I liked it)
Treeforces (and I didn't like it)
please dont make monkey problems like A
D was very challenging for me can someone explain the main idea in very few words please
Don't know if it is theoretically correct but passed the test. So record all the leaf nodes (in a queue). Notice that a leaf node can always increment itself, so if its parent node can have a higher value (i.e. upper bound of the parent is bigger than the lower bound of the leaf), then no need to worry (we can remove that leaf). Otherwise, the remaining tree (the whole tree except the leaf) must be incremented to match that leaf. However, no need to go and increment each node by a value, because the difference between each node in the remaining tree stays the same. Just increment that offset in an external variable. Then delete that node from the leaf queue. Once a nonleaf node becomes a leaf, push it into the queue. Repeat until only 1 node is left.
Of course, the bond needs to be adjusted. i.e. the parent's lower bound shouldn't be smaller than the leaf's lower bound in case 1. In case 2, the parent's lower bound should be set to the highest it can be(match the upper bound of itself).
hmm interesting approach, thank you ! I was thinking of all sort of weird stuff but couldnt find anything that could even pass the first pretest !
Thanks for the nice contest! I definitely had a good start, and I think mainly due to a fast start I got my LGM! Then I got stuck on the other problems, but they were fun to think about. My experience with the problems:
Considering the fact that I've lost 9,6% of my rating, I don't think this round was that good for me xd
Once a grandmaster, always a grandmaster
can someone provide some hint for problem D or from where did you start building your solution
I am stuck at how to view the operation even if i fis all the values at all the nodes.
The idea is to always operate on adjacent nodes. If you operate of non-adjacent (u, v) with u -> x -> v (vals = [10, 15, 20]). Now, if you operate on (u, v), you would have left out x with vals = [20, 15, 20]. Now, you would need to increase x anyhow. Operating (u, x) would give vals = [20, 20, 25]. Now, another operation with (x, v) is required with final vals = [25, 25, 25]. Now, this could have been avoided if we had operated on (u, x) first and then with (x, v), giving us final vals = [20, 20, 20].
Operating on adjacent nodes minimises the cost as we are maintaining the relative differences of other node values and any two adjacent nodes have to be operated separately if they are different (otherwise, the relative difference can never change).
The key hint here is to fix the root of the tree and try making all the values equal to the root's value.
Operating on two nodes
(u, v)where u isparent[v]increases the root's value bymax(0, val[v] - val[u]). If the child's value is smaller, then only the child subtree values are increased to match it to the parent's. Otherwise, we need to increase the value of all the nodes except subtree(v) which includes the root.The operation which increases the parent's values does not change the relative difference for any node that is not part of subtree(v). This means increasing the val[u] does not change its difference with val[parent[u]]. Thus, no matter what the actual value of 'u' is, after operating on it's subtree, increasing the value of parent[u] would still be increasing the root's value by
max(0, val[v] - val[u])consideringval[v]andval[u]to be the initial values assigned to the nodes.PS: Sorry for the such a long answer, such details might be trivial and repetitive but this helped me understanding my solution better (as I did not really thought of rigorous proofs). Also, try to prove why fixing any root would give the same answer.
Thanks for the explanation. I will try builiding the solution on it
Nice round! (The people in comment section seems to have mythical observability, I failed to guess anything useful lol)
I think all problems are very good (at least until F), but putting them together in a single match is somewhat strange.
The Gap between C, D/E1, and E2/F are all too big (the number of accepted participants differs by almost 10 times). I was lucky enough to notice the key to E2 immediately after solving E1 and ended up in a good position. Though many participants got stuck in a single problem (C,D,E2,F are all problems where one could easily go wrong and never come back again), which led to disastrous results.
It would be better to have an easier D and an easier F. In this case the round would be more balanced and a small mistake wouldn't cause too much damage for a single participant.
G and H are also great!
D is tough but I loved it. Thought I was having a chance but I was way off from the solution.
Read the editorial and upsolved, thanks for the contest.
only i solved E2 first then realise the solution of E1 ??
Submission Can anyone tell why this code is for E1 is giving TLE I wanted to find for each node number of values greater than it in its subtree . I used pbds to store all the values in its subtree
Change this
swap(vec[it],vec[node])tovec[it].swap(vec[node])EXTREME huge gap between D/E1 and E2/F.
100 points and 200 points
After upsolving E2, G (read editorial), H, I am yet again surprised by exactly how good the problems are of this round.
I was asked sometime ago about a contest where I like all problems, and it was surprisingly hard for me to find one (nearly all contests have at least 2 problems I don't like). This was a surprising exception, and from the start to end excellent, even ABC were interesting.
Thanks to the authors yet again.
hey there , my account got banned for the using of AI, i didnt have a clue regarding the rule, ill follow it from now on, is there anyway i can get my account activated again??
the username was Moayad999
As a tester,I think that the test is various
Why can't I vp the contest :(
It showed
You are not authorized to fill out this formwhen I click theStart virtual contestbutton.MikeMirzayanov please fix it
Congratulations to t-shirts winners! You will be contacted via private messages with instructions to receive your prize.
Thanks for the gift! Really glad to be on this list
Honoured to be the last name on this list lmao!
Excited!
thanks for the gift
Oh no. I'm busy preparing for the College Examination Exam at that time and this is probably my final contest at that time. So the prize claim expired... oof
As a tester, I have a proof that upvoting this comment will lead to positive delta. But the proof is too long to fit the margin.
Can Someone please help me with the Question E1,
For below test case
My code is printing 7, and according to me, it can be a possible answer. But the actual answer is only 5. Please help me if I am somewhere wrong.
Una_Shem when will I get my prize