Hello! Codeforces Round 954 (Div. 3) will start at Jun/23/2024 17:50 (Moscow time). You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.
You will be given 7 problems and 2 hours and 15 minutes to solve them.
Note that the penalty for the wrong submission in this round is 10 minutes.
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 point of 1900 or higher in the rating.
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.
The tasks were created and prepared by 74TrAkToR. I would like to thank everyone who helped me a lot with round preparation.
- Coordinator Vladosiya for excellent communication and brilliant coordination of the round!
- Testers veleboks, iNNNo, Mox_Taest3r, shqrky, Noobish_Monk, meowcneil, Matrosk1n, sumit_kk10, _supersonic_, FelixArg, KirillKhalin, viteli, zwezdinv, EJIC_B_KEDAX, NicoRobin, detective...dots, Leeda, windreaper for high-quality testing and valuable advices!
- MikeMirzayanov for amazing Codeforces and Polygon platforms!
Good luck!
UPD: Editorial
UPD: Video Editorial
OMG 74TrAkToR!!!!
orz 74TrAkToR
Are you sure this is Codeforces?
It might be:
Mathforces
Algoforces
Codeforces
Interactiveforces
The question asks you to upvote and answer :D
Queueforces
include cheatforces too
5) speedforces
Bruteforces
Education-forces (Problem F)
Classicforces be like
Why everyone disrespects him, everyone made mistakes before. Just enjoy round!
Because he has made more than one mistakes.
Because he made mistakes more than others
Div.3 begin, 74TrAkToR's back, enjoy the trip.
:)
OMG! Another 74TrAkToR Round ..
I feel this blog will be the most downvoted blog in codeforces history.
No this blog will not be most downvoted blog.But i can't say the same to your comment so.
Can you (or anyone for that matter) explain why 74TrAkToR is getting so much hate. I am new here, so don't know much about the previous contests......
https://codeforces.me/blog/entry/124060
The most downvoted blog is 74TrAkToR's appeal
74TrAkToR has to increase his contribution. Good luck !!!
Did you mean contribution??
Looking at your contribution value, I don't want this round.
It is not for you anyway.
Sorry Guys
Competition will return
Marzipan got wronged, ngl.
rated div-3 after 255 days)
Nice progress
I hope you have a wonderful round
I believe 74TrAkToR will bring us a wonderful Div3 this time.
YES, it will be a wonderful round.
true bro
As a tester, I tested :)
What's up with div1 + div2? I can't help, but notice that for some reason low-rated users participate in these contests less eagerly than in div3/div4/even div2
As a CM, I can say that there is a notable difference in difficulty and performance between div2 and div 1+2. This would further exasperated if I could do rated Div3 and Div 4 like pupil/newbie. They just want to do the easier problemsets.
int count = div_3_every_month;
if(count>=3) { cout<<" Helpful for Newbies , Pupils and specialist "<<endl; } else { cout<<"As it is now"<<endl; }
what do you think?
bro you must have some mental disorder
Good Bye 2023!!
This is going to be the one for the books
I think 74TrAkToR is one of the geniuses He is very good at writing problems and is very popular on this site
Have the ratings of previous rounds been re-judged? I don't know how my rating got decreased by 18 suddenly.
Yes, my rating also decreased by 30. Maybe there will be roll back again to distribute the real rating!
Hope to solve A
are there any hacking points for this contest?
No, there are no points for hacking in contests with open hacks phase (usually educational, div 3, and div 4) as someone might create multiple accounts to hack themselves and gain points for this, but if you find a test case that can be used to hack a lot of solutions you can get a better place in the standings by hacking people above you.
Finally I can write this.
as a tester, I can confirm that this contest will be a div 3
on the edge of being specialist
trust in 74TrAkToR round
hope to reach candidate master
bro isnt even close
I will do it soon isa :)
isa?
it means God willing but in Arabic we say In shaa allah
I am still waiting
it was very close :)
I think we should let the bullets fly for a while, at least until we see the problems of this one :D
My cf id is not opening and handle is kxhitz. I had given last contest on 16th June 2024. Please check it out. Solve this issue as soon as possible so that i can continue my practice and participate in contests.
Looks like it has been banned after the recent rollback, if you can prove that the solutions were your original ones and not cheated with anyone, then you can message the Coordinator of the last round to remove the ban otherwise it is gone forever.
thanx for reply. I have messaged the coordinator of that round. Sir, how much time this would take as I have never copied anyone's code in any contest I had given till now.
Is there anything else I should do ??
Quit cf, you cheated in 6 almost consecutive rounds
as div3 enjoyer, i hope it will be a great round!
Dreaming to achieve contribution as 74TrAkToR
Who's going to try to OEIS G tomorrow?
damn i thought 74 is all history
Hope pref 2000+ Although 74 round
i have high respect for low contribution authors
Hope today is not speedforces.
Delayforces...
Hey，but why？
Because its div3
?
Bro it's delayed!
what should we do in delayed time?
just play chess
74TrAkToR is late...
Delayed cause everyone's watching F1
CF>F1
nahh
mAXX won, orz.
Delayed
delayed :)
This is a delay in second 74TrAkToR's contest in a row
if you mean as a coordinator — third
Delayforces :(
Is there ever going to be a div 3 round without delay?
when you become a problemsetter, make an on time cf round
The TrAkToR is going slowly so we have a delay.
thanks I just finished a heavy plate of pasta and I needed that 15 minutes
Everyone will try to become a pupil or specialist. I will try to submit before the cheaters
Problem A Solution
YOU ARE THE CHEATER
Please, don't worry about delay, Mike asked for it to increase testing speed a little.
Traktor king lets go
What happened? why so much people know about the writer?
because of Good Bye 2023.
I thought that I missed the round start by one minute. But, it turned out that I have to wait for more than 10 minutes for the round start now!
Good luck to all, compete fairly and enjoy competitive computer programming.
Hope Goodbye 2024 will be super hard for B and above problems and only A is very easy if 74TraKtor Coordinates again.
good round, solved A,B,C
I don't understand the author's intention to split $$$G$$$ into two tasks and not able to think of a specific algorithm to solve $$$G_1$$$.
Lol, many people submitted G1 but not G2. Or submitted G2 much later.
I believe both $$$O(n*sqrt(n))$$$ or $$$O(nlog(n))$$$, anyway $$$O(n*log^2(n))$$$ could pass. Can anyone share the algo of $$$G_1$$$
not-balanced round
Does D use meet-in-the-middle to solve? It seemed so easy but I couldn't solve it...
it's just brute force on brute force
first solve the following question: given an array of numbers, what is the minimum value of their expression?
this is easy enough: multiply ones and zeroes, sum everything else.
after solving this problem all you have to do is try it for all possible lists of numbers. notice that there are only $$$n - 1$$$ such lists
the final complexity is $$$O(n^2)$$$
I was thinking that approach, but it seems there are lots of cases to handle. For example, assume the digit is "abc0def". How do you decide whether to multiply c x 0, bc x 0, 0 x d, 0 x de, ..? We need exactly N-2 symbol. Probably 0xde leads to the most optimal one instead of 0xd.
At the end I use DP.
in this case you multiply everything by the zero, for example:
$$$ab * c * 0 * d * e * f$$$
Handle the edge case where result is 0. Which is pretty simple.
Since you always have (n-2) signs, therefore theres always a 2 digit number(including 01-09) present in your calculation.
The problem reduces to finding this 2 digit number then applying the following algorithm:
Let i be the starting position of the 2 digit number. For each character from 0..i-1 and i+2..n, add if digit is not 1 otherwise multiply it and finally add the 2 digit number.
Now to find that 2 digit number: You can iterate through all possible 2 digit numbers and add them to vector and sort it.
Then among lowest 2 digit numbers that have the same digit in 1's place, pick the one that gives you the lowest result.
You need to do this because sometimes picking the minimal number is not optimal, like 22 gives better result than 21 in one of the test cases.
I couldn't come up with a better method to pick the minimum number so I kinda brute forced it. The time complexity is O(nlogn). (Picking optimal 2 digit number through sorting)
Sorry if my description is kinda convoluted I am still learning
Actually, you can brute force the element that will be combined with the right one and then try this: When there is 1 you multiply it, otherwise you sum it and write corner cases with zero, because you can multiply everything and make ans 0, but not in 101 and etc.
Really nice problems!
I found a bug in my bridges code due to problem F, thanks to problem authors!
You must think you're humorous by choosing these questions. :D
bye bye rating 💩
problem b were bit hard for it's position (second div3 problem), waste 30min to implement without ChagGPT, rating completely ruined
Thanks for the amazing contest 74TrAkToR !!! Finally a Div 3 contest that felt like a proper, balanced Div 3 contest <3
if you solve 5 tasks first time it doesn't mean that contest is balanced (((
What was intended for G2? I used (almost) the same $$$O(n\sqrt{n}\log(n))$$$ code for G2 as G1 which doesn't seem like it should pass G2.
I solved it in $$$O(nlogn + n*maxdivs(A))$$$ which $$$maxdivs(A)$$$ about $$$300$$$ i guess. The problem becomes for 2 simplified fractions, count the number of pairs of fractions $$$(x1/y1), (x2/y2)$$$ multiplied together to produce an integer. When fixing the denominator of the first fraction ($$$y1$$$) => the numerator of the second fraction must be divisible by the fixed denominator ($$$x2$$$ divisible by $$$y1$$$). => count the number of fractions with numerators $$$x2$$$ and $$$x1$$$ divisible by $$$y2$$$. Just brute all $$$y2$$$, processing $$$x1$$$ can be done before.
D and E are too much implementation heavy...
what is the correct idea of E? I thought of try pairing every two elements from A so every element we can write it as follow : a[i]=x*k + a[j] for j != i
but I didn't implement it
is it correct?
Let $$$x + kn = y$$$ ($$$n$$$ operations on $$$x$$$). This implies $$$y - x = kn$$$. This difference is divisible by $$$k$$$. Thus, two elements can only be made equal if they give the same remainder when divided by $$$k$$$ (if they don't, their difference is not a multiple of $$$k$$$).
So we group elements with the same remainder modulo $$$k$$$.
If there are $$$\geq 2$$$ groups with odd number of elements, it is impossible to construct a palindromic array.
So, we move on to the case where you can apply operations.
For each group, let its sorted list of elements be $$$a_1, a_2, \cdots, a_n$$$.
For an even-sized group, $$$(\lvert a_2 - a_1 \rvert + \lvert a_4 - a_3 \rvert + \cdots + \lvert a_n - a_{n-1} \rvert )/k$$$ is the minimum score needed for that group.
For an odd-sized group it's similar but a little bit more complicated. You will pair $$$2k_1$$$ elements in the front and add their score using the even group method. Then, an element will be left out to be the middle element of the palindrome. After that, the score for the remaining $$$2k_2$$$ elements will be added. The optimal left out element can be calculated using prefix sums.
So you have the total score for each group, and you sum it over all the groups to get the final answer
How can the optimal left-out element be calculated using prefix sums? What's the implementation idea
You can look at my code if it is of any help
This problem from AtCoder is the same, you can read the editorial on there
First time get MLE in div3 round
For E, I wasted a lot of time on prefix/suffix sums to find the optimal element in the odd length array to put in the middle. Then, I realized I could use DP to do it without much thinking.
same bro realised it later and wasted a lot of time on prefix sums, also I did another blunder, by asking this from gpt-4 and claude 3.5 sonnet. they weren't able to code correctly this simple task of prefix sum.
Solution which uses prefix/suffix sums.
https://codeforces.me/contest/1986/submission/267058869
you could also do it using prefix and suffix sum. see
Lol me too,but int the end i just ended up doing it with single variable :) or ig :(
Interesting. I found Greedy with prefix sum easier.
How does the DP work in detail? I don't really understand the transitional relationship.
Nice approach . I was not able to think about this and solves using prefix and suffix sum of two pairs. It was very heavy implementation for me
(recent) parameter in your dp function is not necessary.
solved F 3 minutes after contest finished...... :(
I would die rather than to attempts traktors mathy and implementation heavy rounds
L round
wrote recursive function to verify my observations in D and I found out that I can memoise my recursion function and convert it into dp.
It is just a lot of bruteforce
yep
You can do D with (heavy amount of) casework and greedy ig
Skipping traktor's rounds from now on.
who let him cook a template bridge problem???
lol
For this kind of a standard problem there are not that many solves tho
Although it does scream bridges the moment you look at it
what is template bridge problem? easy to solve with concept from classical/standard problem?
Take a look at this
Additionally in today's problem you also have to come up with a way to calculate sizes of components after you remove a bridge (which is not too difficult)
I copied the bridge search algorithm from an Internet site (the algorithm was published long before the start of the round) without rewriting it by hand and made some changes. I read the competition rules on the codeforces platform and still didn't understand if I could do this. I hope this question will be clarified to me.
I pasted the statement into GPT4 and it gave a slow python DFS solution, then with one prompt I managed to get it to provide a correct solution (only had to fix an overflow bug).
use c++, and do it in O(n) by storing subtree sizes and a bridge finding methodwas the prompt that allowed it to solve the problem!I thought what could possibly change by just increasing the constraint by a mere 5 times in problem G, but it effectively thwarted my square root decomposition solution from G1, and I ended up having many MLE/TLEs :( .
div 2.74 (74 from 74TrAkToR)
why carrot giving error?
as it is stuck in traktor
good round, thanks for the problems.
Task F can be said to be a learning task for finding bridges in a graph. I copied the bridge search algorithm from an Internet site (the algorithm was published long before the start of the round) without rewriting it by hand and made some changes. I read the competition rules on the codeforces platform and still didn't understand if I could do this. I hope this question will be clarified to me.
You could.
According to third-party code rules you should be fine, although I don't know if a copy pasted solution from a public source can get flagged for plagiarism
I'm not able to guess the complexity for my solution of G2, someone hack it. 267078205
Decent round tbh. Better than previous round by 74TrAkToR. Skill issued on implementing, but so did everyone else, I guess.
Here is my DP solution for D.
267043778
You can check my video editorials of D, E and F if you have any doubts
Silly mistake cost me E :(
Okay I'm fairly new to Codeforces, so I have no idea what hacking is. I had successfully solved A and B. But now sometime later after the round has ended, I open up the round page, B is highlighted in red, and after checking submissions I see that the verdict for B has changed to "Hacked"..... what.... why.......
It means that your submitted solution isn't fully correct
How not correct, like to what extent?
It means that someone has found a testcase in which your solution is giving wrong answer. So he basically hacked your code....
.....wow okay
In this particular case your solution can't fit in given time constraints, so it fails. You need to find a more optimized one.
I have a new version of c can anyone help me in that.
Update in 1986C - Update Queries, what if t was not allowed to sort the string c then how will approach. any suggestions.
Here's what i thought about this:
First lets store the distinct occurences of indices in increasing order along with its count. Now for an index $$$i$$$ in this array, we will try to place the smallest available character in $$$ith$$$ pos of $$$s$$$. The position of the chosen character in string $$$c$$$ should be such that we can place all other occurences of $$$i$$$ before it (since it only matter what we place last for an index $$$i$$$). For each character the best chance to be able to choose it would be if we choose the last available occurence of that character.
So now what remains is how do we choose which characters would correspond to the leftover occurences ? It would be best to strike off the maximum characters to the left of the last occurance of the chosen character. We can simulate that using a segment tree.
I was thinking of the same approach but the main difficulty I faced was like suppose for index 1 we have count of 4 and for index 2 we have count of 3.
So, we have sorted t array something like this: 1 1 1 1 2 2 2 .........
Now have to assign best character to last 1 such that there are at least 3 characters before it so that we can assign them to preceding 1. Now for 2 we need to remove max 3 characters that were assigned to 1 and the smallest characters then again go with 2.
Can you tell how you will tackle this, if possible, provide the pseudo code and expected Time complexity.
I don't know why some people complains so much about this Round, it doesn't matter if it's all implementation or math, after all is a problem u need to solve, there are no excuses in real life problems, good Round admins!
Contest was great,but cloudfare spoil it for me
Any reason we are using memory limit 128M instead of the default 256M for G?
I didn't see any reasons to reject solutions on the memory constant factor.
MLEFORCES
Can anyone explain why unordered_map solution is giving TLE, while map is working fine?
unordered map
map
You should read this: https://codeforces.me/blog/entry/62393
It is interesting that the post was made 6 years ago, yet lots of people (me including) dont know. Shouldnt they patch and prevent people using bugged version? Even though perfect implementation is crucial in CP, one shouldnt penalized due to buga from the compiler.
This isn't a bug of the library or the compiler. C++ specification clearly states that
unordered_map<K,V>::insert()'s time complexity is worst case O(N) (cppreference).If you are curious about how this happens, study the data structure of hash tables.
can someone explain why this fail for problem B https://codeforces.me/contest/1986/submission/267043411
Your code fails if n=1 or m=1:
You look at positions (i,j+1) and (i+1,j) without checking if they exist. I don't recomend to write so many if-statements, because then it's very easy to make small mistakes like this. Example of my code without so many if-statements: 266984242.
Turns out test 43 is the first test where $$$n = 500000$$$, which is odd.
Stress tests should be among the initial tests. Otherwise, it takes too long to get the verdict during a contest.
Can someone please explain that in E — Beautiful Array, for the input
13 3 2 3 9 14 17 10 22 20 18 30 1 4 28
How is the output 14? I re -checked multiple times and found it to be 15.
Please reply ASAP
for your remainder equal to 1 the sequence is {1,4,10,22,28} in this you should remove 10 and pair 1 with 4 and 22 with 28.
sorry for bad English.
Can someone explain why this solution failed as TLE?267007171 .I expected the Time complexity as O(nlogn+mlogm).
I'm pretty sure that you are making it O(n^2) through string concatenation (basically, appending a char to a string of length n has time complexity of O(n) because strings in python are fixed-sized unlike C++ where they are almost a glorified vector)
Thanks for your reply and pointing out the mistake, i think it would be a lot helpful to me in the future. Really appreciate it But still i got a question — why does this same code passes with Python3- 267178416 whereas the same code gets a TLE with PyPy3- 267007171
I am not Python expert, I mostly do C++ and some Rust but my guess is that Python3 interpreter recognizes that you are building a string char by char and does some clever optimization on this code which allows it to avoid the O(n^2) pitfall somehow
I have sacrificed 'D' to score 'E'! It was a little heavy implementation (E).
unrated
Unlikely, It's just that tests took quite a lot of time because there were a lot of hacks and that's the reason the whole thing kinda got shifted to later
unrated???
It is not unrated. It seems like rating has not been updated yet.
Is the round going to be unrated??? The ratings aren't updated after system testing
It's not unrated. Ratings are yet to be updated, they will be updated soon.
Are you sure
It's not the first time that ratings have not been updated even after 24 hours to the start of the contest. Besides, there is no reason for the contest to be unrated.
It is showing unrated brother..
It will move to the list of rated contests after rating change. It's just temporarily listed as an unrated contest.
it always shows unrated before ratings are in
see the contribution of the author now..
why did this happen though
That's because of Good Bye 2023, nothing to with this round
the author replied. the round is rated guys, just wait
where did he reply ?
i texted personally, he replied "rating round". that means it's rated if I know english
Can you send a screenshot of your chat with 74TrAkToR?
don't know how to share image here, it just asks to enter a url
You can just upload an image to some cloud service (like google drive) and then put a link.
https://drive.google.com/file/d/1D4LXvsF7kiMMFbxIXGw9bTSNcJNLSHKT/view?usp=drivesdk
this means the round is rated right
unrated :(
why unrated
unrated for me too
Until a contest is rated it will be displayed as unrated. Sometimes it can take more than 24hours to roll out ratings and sometimes they rerate contests too. Nothing to worry ratings will be out maximum by tomorrow. (P.S Don't mind if there are any spelling or grammatical errors)
Changing map to a sorted vector of elements + binary search works in G2, the time complexity is the same but i can't figure out why it removes the MLE i get with map, since intuitively, i am storing count in map and elements in vector, the storage in map is more sparse, is this happening because in testcase 43 the array values are such that, it leads to lower count values in map and thus, reducing the advantage of sparseness?
Map submission
Vector submission
So why does this code: link return a result of Runtime error? I was able to compile the sample locally.
i'm kinda new to contests in codeforces so i dont know if this was a hard contest or the other div 3 contests where too easy. i normally solve around 2 or 3 problems in div 3 contests but i could only solve problem A in this one.is that just a me problem ?
Was there some changes in the rating updation?
I had gotten +39 now I have +51 in this contest.
jiangly Can you please explain your solution for G1 and G2?
Good contest
.