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,
- jqdai0815, ugly2333, dXqwq, Sugar_fan, propane, LuCpp, triple__a, PinkieRabbit, fallleaves01, thenymphsofdelphi, N_z__, tarjen, tiger2005, golomb, Tobo, add10k, Kieray, meowcneil, huansir, interlude, Cai_Guang, fr200110217102, nanani, Retired_shstyle, Theresa_Apocalypse, wjy666, PaperCloud, Kepy, _Sherbiny, nnv-nick, EternalJourney, shendeliliang, Teatify, sabino1, larush, Kraska, MeIoN_is_UMP45, weebyes, 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.
really wanted a downvote?
wow! -120
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
i want tourist became again tourist
As a tester, I can finally say that I TESTED. Really good contest, I hope everyone gets positive delta.
Wishing everyone +Δ on Round 7*11*13! :)
As a participant, I can confirm that 1001 is the product of 3 consecutive primes!
as a green green plant, give me rating!
Score Distribution.
Those who surpass 4000 will be awarded a badge with their name???
Wishing everyone a Positive Delta <3
Hope i Get to Pupil this time.
A better Score Distribution needed :p
you too brother...
Score distribution ???
palindrome round )
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.
Guess who is ready to paint its name for a new look(hopefully non-green).
As a participant, 1001 is a symbol of New beginnings and Self growth;
glhf xD
As a contestant, I really think StarSilk is a cat
I am unable to register in some contests including this one. What is the problem
I forgot to register sadly and i had to start 10 minutes lates and then i totally overcomplicated B. Maybe today was not my day.
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.
by mistake
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.
use map() as dp
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??
we can also write a recursive function and everytime make two list first containing diff list of the origal list in accending order and another considering it decending and just call the fuction again and again....
at last use hashset to avoid precomputations also every time we need to conside the the current sum as well.
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
For the current vector a, you could choose replace the sequence with its difference sequence OR reverse it before replacing. However, the result in those 2 cases is just opposite signs, ans1 = -ans2 Therefore, just take care of replacing the sequence by using backtracking
There are at most 2(n-1) operations you can meaningfully do, so if you found a strategy to optimally choose one or two operations at each step without backtracking, in O(n) time, the problem would admit an O(n^2) solution which passes given the lax input constraints. Since reversing more than once doesn't make sense, the sequence of operations boils down to an sequence of operation (2) with at most one reversal operation between each op 2. Reversing at the end doesn't make sense because it doesn't change the sum. Anyway, I solved it greedily by checking if reversing then differentiating is better than just differentiating, and leaving the sequence that got you the larger sum on each step. In the end, you output the largest sum you got at any point.
Note: this can obviously be optimized taking the nature of the operations themselves into account, but you don't have to optimize anything to get AC.
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)).I have done the same thing why this not work? code__
Try
accumulate(v.begin(),v.end(),(long long)0).Thanks I got it
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.
Sir , Can we do D with binary search ?
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.
Yes , E1 is a very beautiful implementation of ETT 2 and segment tree
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
its me.
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://codeforces.net/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.
there is a pattern in the problem. if you find the final number (when the size of array is 1): if n == 3 ---> -1 2 -1 (these are coefficients to be multiplied to the array elements) if n == 4 ----> -1 3 -3 1 if n == 5 ----> -1 4 -6 4 -1 and so on
so this can blow up for n == 50 where there will be a term 50C25(binomial).
The differences can go up to $$$2^n\cdot max(a_i)$$$. For example -1000,1000,-1000,...
guessforces!
really want an upovte? and please editorial??
D why
I have complited A,B,C in 40 min but i again submited C after 2hours (using different lang) which of my solution will be considered for evalution and which time of submittion will be taken 1st or 2nd
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://codeforces.net/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.
Could you go on YouTube and create a video explaining the logic behind your solutions, especially B and C?
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 !
Where editorial?
Can't figure out C then guess it in same way like many others have done.... Still get wrong ans on test case 2 ... Can anyone tell me why this fail.... Same logic many other have passed it
My soln
You shouldn't do tem.pop_back();
jiangly may lose his title due to this contest
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
In part C, I notice that if I keep the array a unchanged and perform subtraction, then create a reversed array of a as b and perform subtraction, all the values in b will be exactly a * (-1). So you dont really have to create b at all. Here is my submission ^-^ https://codeforces.net/contest/2062/submission/303144045
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)
Congratulations on hitting red.
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])please i need like!!!
EXTREME huge gap between D/E1 and E2/F.
100 points and 200 points