أهلاً, Codeforces!
cry, Intellegent, and I are really excited to invite you to participate in Codeforces Round 1029 (Div. 3), which will take place on Jun/08/2025 17:35 (Moscow time). You will be given $$$2$$$ hours and $$$15$$$ minutes to solve $$$8$$$ problems.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, all solutions will be judged on preliminary tests during the round, and after the round, there will be a 12-hour phase of open hacks. After the open hack phase, all accepted solutions will be rejudged on successful hacks. Also, note that there is no score distribution but the usual penalty of 10 minutes for each wrong submission, following the rules of educational rounds.
Note that the penalty for each wrong submission in this round is 10 minutes. Also, note the rule restricting AI use. If you are caught using AI in an unorthodox manner, you will be sent to cry's basement. You don't want that to happen.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:
- take part in at least five rated rounds (and solve at least one problem in each of them)
- do not have a rating of 1900 or higher at any moment in time.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you (unless you register unrated).
I would like to thank the following people for making this round possible:
- cry for being an amazing coordinator and being even more amazing to add a problem to the set, and Intellegent for adding a wowee problem to the set.
- Dominater069 for red testing.
- Proof_by_QED, __baozii__, AksLolCoding, amoeba4, catgirl, efishel, -firefly-, Edeeva, 18o3 for orange testing.
- reirugan, Friedrich, wuhudsm, rewhile, IceWolf898 for purple testing.
- macaquedev, beaten_by_ai, SpyrosAliv, chromate00, Non-origination, expertaq, DivinePunishment for blue testing.
- Borhom, _Rawan_, ETL for cyan testing.
- hotfog12 for grey testing.
- rlin61 for unrated testing.
- Vladosiya for statement translation and testing as well.
- MikeMirzayanov for developing Codeforces and Polygon.
Good luck, and most importantly, have fun!
As a tester, the problems are good. I recommend participating.
wowee
As a tester, -firefly- tested.
As a tester, yse held me at gunpoint to test this round.
As a tester, I tested voluntarily :)
As a tester, I contributed an initial AC solution that was later hacked.
as a participant, I hope it's all sunshine and rainbow down cry's basement :D
I've snuck into cry's basement before, here's a list of items I saw:
Farmer Nhoj, holding a pitchfork.
A big bucket of lactase, which he feeds to his test cases to stop them from getting cheesed.
A computer simulating two copies of cry's basement.
A stack of problem proposals — one of which reads "It's Mooin' Time IV"
A group of people lying on the floor with their limbs spread out, one person standing and putting their arms above their head, to create a triangle pointing to the sky.
A chicken jockey.
Have you seen my flying pig down there?
Incidentally, I can confirm that the group of people lying on the floor are the same people who have tested some of cry's rounds in the past (such as the one by SpyrosAliv). Unfortunately, they have since escaped cry's basement and will not be testing rounds anymore.
AI users will not be treated as well, though... (don't cheat, lest you discover the true horrors of cry's basement.)
I was one of the first to escape along with cowthecow :)
Yummy!
As a tester, CHICKEN JOCKEY MENTIONED 🍿🍿🍿🍿🍿🍿🍿🎉🎉🎉🎉🎉🎉🎉🎉🍿🎉🍿🎉🍿🎉🍿🎉🎉🎉🍿🎉🍿🎉🍿🎉🍿
cry is a girl? right?
yes
yes
akasakaR is a GPT cheater? right?
hi
Where is cry's basement?
expertaq orz
if only i had gone down by 7 more rating :(
I hope.
"note the rule restricting AI use. If you are caught using AI in an unorthodox manner, you will be sent to cry's basement. You don't want that to happen."
The FBI is here to search cry's basement.
amazing ^_^ yeah yse and yeah Borhom
2 problems at least this time
I did it
Ok but what if I want to be sent to cry's basement???????
As a participant, I hope to reach expert
Good luck
congratulation!
Thank you
The king in this world joo
Hope get Specialist.
Hope to become a pupil. I am literally on the edge.
stop edging
يا هلا
As a tester
As a participant I hope the problemset is amazing , and I reach pupil ^_^
My turn
why there is a red dot
oh shoot forgot to do my contribution farming out of competition post
If you are caught using AI in an unorthodox manner, you will be sent to cry's basement.Could you please elaborate on the specifics of this? Will I be sent via plane, train, or car? If it's a plane or train, will my ticket be paid for? If it's a car, will one be provided or would I have to provide one, in which case would my gas be comped?
Thank you.
You'll get on a transportation called
Skipped. And you don't need to provide a car, but you'll lost contributions.As a first-time tester, this is the best round I have ever tested.
As a first time tester, this is also the best and worst round I have ever tested.
As a participant, I wish you all a "failed system test" and "hacked" free contest
How to apply for the post of torturer at the cry's basement
As a basement, you don't want to use AI then end up in cry's tester.
As a tester, I can confirm cry is a Honkai: Star Rail enthusiast and his basement aims to produce free Stellar Jade.
Why Sunday but not Saturday?
why not tommorow
As a person, it would be an Intellegent move to participate in this contest.
Hoping that problems will not be hard
as a participant, I want to see cry's basement so add another way than cheating plz :/
First out of competition div3!!!
Wish everyone enjoys an exciting match:)
Eid Mubarak :)
Eid mobarak
i have a doubt why i dont see manypeople coding in java? it seems theres enough time given in questions to code in java but alot of people dont do it
Java is a ~4-5 times slow than cpp , so most people prefer cpp over it in cp
C++ is the most popular because it's (one of) the fastest languages, which can be particularly helpful when avoid TLE (time limit exceeded). Python is also decently popular, mainly for beginners, because it's easy to learn. Java's in the middle ground, and while a jack of all trades can be popular in some cases, generally its not used as much (though it's not unused, I do think its still decently popular, but not as much as C++ and python)
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.
I am a counterexample
as a tester, i tested late so i will miss out on all the contribution :C
این دنیا دیگه به درد نمیخوره
:*)
cry and Intellegent have never disappointed us.
Are we are not going to get the problem rating breakdown as in div 2
in div2 announcements the breakdown isnt rating, but rather the point value of the problems. in div3 rounds all problems are worth 1 point
Be careful in this case, the output may be yse.
Eid Mubaraak !
excited for the only thing that makes me happy, good luck to all
good luck
I hope you achieve the best results and wish success to everyone.
gl hf
my current rating is 1599. finger crossed :3
not happening bro
yeah sadlife..In E, used i>0 instead of i>=0 and life fu*ked up man
Make sure you done end up in his basement
Nice contest. Had fun solving them. Thanks !
m2.codeforces.com down for anyone else? for me only question heading were visible but on clicking them the statements were empty.
PS: It was a refreshing contest, as the problems weren't overly ad hoc, unlike the recent trend. I couldn’t figure out the relation for F, but G was easy, standard i will say.
C made me cry a lot.
I took way longer than necessary on D. Spending the rest of the time on E and probably overcomplicated it as well. Solid problems I suppose though.
the time took for me to solve D is longer than the combine of A, B, C, and E. and 5 WA only on D.
how do you solve E?
for each index i for array a check if some a[i] exists in odd position relative to i in a OR some a[i] exists at even position relative to i in b,also we need to check for indices greater than.Same for array b.if its true for any array ans is atleast i+1.We can implement it using multiset
What is the idea on problem D? I'm sure its something easy, I just can't solve it (even though I've solved E and F...)
System of equations in 2 variables. So solve it for a[0] and a[1], (ensuring the sol is non-negative integers), then test that sol on all the rest.
Assume there are x first operations and y second operations, then you get two equations:
a[i] — a[i-1] = x — y (1) a[0] — x — ny = 0 — (2).
Solve these two equations and check x >= 0 and y >= 0, also check x — y = a[i] — a[i-1] is same for all i.
I first tried to imagine it as a linear equation. And instead of trying to reach 0 from z, I tried to reach z from x and y. Let
We want: a * x[i] + b * y[i] = z[i] To solve it, I used z[0] and z[1] to form two equations and eliminate a, which gives a unique formula for b = (2*z[0] — z[1]) / (n + 1). Once b is known, a = z[0] — b * n. Then just check if all values satisfy the equation
very nice contest!!!
How to solve C
Idea : The first segment contains only the first element. After that, you continue building segments greedily, breaking a segment whenever it includes all the elements from the previous segment.
Code : https://codeforces.me/contest/2117/submission/323459167
The rated top 5 are all cheaters? Mike, check and delete cheaters from the score board. And, we need roll back. Codeforces don't need any cheaters.
To cheaters: is using LLMs so interesting? You can't learn any thing from an AC and a good rank. your same large camel code stile and super long AI names are strange!
Great Round. Esp for me , C and E.
Any hints for F?
one leaf or 2 leaves
the tree will be always of the form o-o-o-o..-o and then two children emerging out of last o.Else answer will be 0.In simple term there are atmost 2 leaf nodes .Finf their lca and give 1 leaf node value 1 and other 2 and vice versa then construction is trivial
Tree must have not more than 2 leafs. If it has one leaf, it is just 2^n. If two leafs, compute the only point with 2 children (let it be point A), lengths of paths from this point to leafs. Path from root to A can be arbitrary, then you need to be careful to compute variants of paths from leaves to A
I don't understand how any author would find it an achievement to write a problem like E. It's so boring and seems to just be a time-waster problem. You could have just left it at no deletions, but you decided to make it cringe. There is also like nothing to learn from it
Personally disagree, the deletions added an interesting part to it (also simplified my solution, though I feel like I'm the only one that applies to).
How to solve H?
Some ideas for problem G? I tried the following but it gets WA on test 2, don't know why yet:
Insert the edges one by one using the Kruskal/DSU algorithm for MST, but stops immediately when 1 and N gets in the same set. Then, find the mininum and maximum edge in their connected component, and output their difference.
that doesn't work because you could get a better combination later (like a way smaller minnimum and just slightly bigger maximum). But if you just do that procedure for all the edges then it works
Ohhh I see, you are right! Thanks for the insight!
did u submit it? i have the same logic but still getting WA on 2
D is hard to implement for me ... and I think C and E have similar ideas and difficulties (maybe E even easier?)
D is just solving x+ny=a0 and 2x+(n-1)y=a1 . y = (2*a0-a1)/(n+1), x = a0-ny
What is the solution to F, I have no observation but the tree is a binary tree if ans > 0.
The tree need not be binary instead it can have atmost 2 leaves.
After this, you can start checking for number of possibilities from the leaves and you will find a way to solve it.
Is H based on sqrt decomposition? Here is what I had in mind:
If f(i) denotes the frequency of an element at index i, we need to maximize difference on function: 2*f(i) — i.
We can store maximum answer for each distinct value over queries.
To make an update (addition/removal), we maintain blocks of size sqrt(N/logN) over each distinct value. This way when an update happens, we can update all the elements of the block of that value to recompute minimum and maximum: 2*f(i) — i. Also we can keep a lazy offset to compute the changes in answer for each of the other blocks. Once we manage to update each block, we can recompute the distinct value iteratively and update it inside the global maxima set of answers.
Is my idea sane enough?
Can someone explain how rankings work in rounds were there is no score distribution ? Is it solely based on problems solved independently of their difficulty ?
Yes ranks are on the basis of number of problems solved
to settle ties, they are then ranked by penalty(sum of time taken to solve each problem, with +10 for each incorrect submission)
Really enjoyed this contest! Thank you :)
Why does the author think that 100 line of if else is cool for E, or my implemention is just dumb.
Maybe you overkilled it, just like I overkilled while thinking about the solution.323533480
i thought the same as a tester, but there are a lot of very neat solutions which arent casework bash
Hello , I am actually a newbie to codeforces and was not very much aware of the system , i did registered as rated contest and even solved three problems in the contest ,but it is now showing as unrated for me , can anyone help me and is there anything which i can do to get my rating increased ?? ...
If possible , do consider helping my submission id's are
https://codeforces.me/contest/2117/submission/323499358
https://codeforces.me/contest/2117/submission/323470875
https://codeforces.me/contest/2117/submission/323448302
Ratings will update after system testing in a few hours.
brother it is still showing as unrated , is it normal ,like yours is still unrated ?? or just mine
It's normal dw.
I tried to solve D, using the fact that when a[n-1] = 2*a[n], I will do operations only of type 2, and the conditions, a[n-i] = (n-i+1)*a[n] should hold for all i, so first I calculated how many operations of first type are required to get a[n-1] = 2* a[n], apply that much operations of 1st type to the entire array, and then check the condition which I told. But I am getting wrong answer on test 3, can somebody please look into my submission and tell the probable error, https://codeforces.me/contest/2117/submission/323482331
n=2,a={47,226}
you output yes, when the answer is no
Yes, thank you very much I have found the error, I was not checking for negative case
Omg graph! I am also a Chinese problem author, and i can't believe that one day the Codeforces div3 will be exactly the same as my idea. https://codeforces.me/contest/2117/submission/323561607
https://ac.nowcoder.com/acm/contest/103864/G This is a problem I prepared about six months ago, it was used for a programming competition for a Chinese university student called the Chuanzhi Cup.
Dramatically, I didn't attend last night's Div3 because I had to review for the final exam. And I have always participated in Div3 from the second to last problem, which was the problem G for last night. It's obvious that I lost the opportunity to get first blood on this problem.
Anyway, I am honored to have the same problem as Codeforces. :)
orz
Can we solve D with Binary Search?
Why do you want to use Binary Search, if you can solve it easily using Linear equations with two variables.
And still if you want to use BS, I would like to know your approach.
why i ac D yesterday, but today i saw D is still in queue?
System Testing is going on which means, now your code is getting rejudged again on all test cases.
where is my rating, I'm starving. /cry
Hello,
I participated in Codeforces Round 1029 (Div. 3) with a rating of 368. I made submissions during the contest and my handle appears in the official standings, but my rating hasn't been updated while others have received theirs.
Could you please check if there was an issue with my rating update?
Thank you.
maybe you participated unrated.
As a tester, Help me figure out why this CPP solution works but not the same python one. CPP: https://codeforces.me/contest/2117/submission/323463628
Python: https://codeforces.me/contest/2117/submission/323479416
Wrong links?
My bad, fixed now
You are getting TLE because you are using hash set which can be hacked, Someone can generate a test that forces it to O(n) per insertion.
A solution for this is to hash the values to other random values
I tried applying this to your solution and it passed 323782302
Another solution is to use a sorted set which isn't built-in in python, but you can copy an already implemented one
I used Pyrival's implementation to sorted list, which is equivalent to a multiset in C++ and your solution passed using it: 323784215
Can someone check why my F solution is giving TLE on Testcase-3, I don't know why it is doing like this. Even some Time-complexity calc showing its O(n). Please help me.
The function is solve6() for F part.(You have to scroll a bit) 323699490
You pass the adjacency list
vby value in thecalc()function, which creates a new copy each time you call the function. Pass it by reference and it should pass.Questions were interesting and was fun to solve
I just tried the virtual contest today, these problem were so fun! Really regret forgetting to join the actual contest yesterday :')
.
Hi Codeforces team,
I’m very sorry for the trouble my submission 323500727 caused. I honestly didn’t know that using a small helper tool could make my code look identical to someone else’s.
The core idea of the solution was my own. Because it was already late and I was very tired, I let a tool generate some quick boilerplate code and then completed the rest myself. I never copied anyone’s contest code and never shared mine. It seems the same boilerplate appeared in other submissions, so the checker flagged us as similar.
I no longer have the local files (I cleaned my workspace after the contest), but I can explain every step of my solution if needed.
I guarantee this will never happen again. I respect Codeforces and will make sure I do not compromise the fairness and integrity of any future contest, and I am willing to accept any penalty you consider appropriate.
Thank you for understanding.
— MNTEEOKK