Hello, Codeforces!
We (KDOI Team) are glad to invite you to take part in Refact.ai Match 1 (Codeforces Round 985), which is the 8th CP contest held by us! You can view the previous rounds by us here.
- Number of problems: $$$9$$$ ($$$0$$$ interactive);
- Start time: Nov/09/2024 17:35 (Moscow time);
- Contest duration: $$$180$$$ minutes;
- Score distribution: $$$750-1250-1750-2250-2500-3000-3500-5000-5500$$$.
The problems were authored and prepared by Error_Yuan, _istil, Otomachi_Una and me sszcdjr.
A few words from our sponsor:
We’re Refact.ai, an open-source AI Coding Assistant, and on November 9th, we’ll be hosting our first round on Codeforces! Winners will receive valuable prizes, and all participants will have a chance to get some exclusive merch from us.
Refact.ai is pushing AI beyond simple code completion. Soon, we’ll launch the Autonomous AI Agent—a developer’s buddy that handles real engineering tasks end-to-end, from planning and coding to testing and deployment. You can read more about us in this announcement.
If you're excited about AI in software development and want to build the future instead of focusing on the trivial, join Refact.ai, founded by a former OpenAI researcher. We’re looking for talented Researchers and Backend developers to join our team.
Prizes:
- 1st place: 500 USDT
- 2nd place: 300 USDT
- 3rd place: 200 USDT
- 4-5th place: 100 USDT
- Top 50 participants will get T-Shirts
- Additionally, 50 random participants from the top 51-500 will receive a T-shirt
Good luck in the contest!
On the right, badges of the authors. From top to bottom, left to right are Error_Yuan, Otomachi_Una, sszcdjr and _istil respectively.
We would like to thank:
- Vladithur for his wonderful coordination.
- Again, Vladithur for the Russian translation.
- programpiggy for providing a few unused problems.
- gyh20, dXqwq, Sugar_fan, 275307894a, Kubic, PEIMUDA, A_zjzj, LMydd0225, abc864197532, N_z__, rui_er, ProjectCF, chenyifanlx, ling_luo, wsc2008qwq, EasonLiang, Caylex, Hanghang007, SpadeA261, IwannaEATaCUTEcaca-qwq, OctoberEstuary, MrPython, gza, chromate00, mathtsai, Codula, tibinyte2006 for testing and giving useful feedbacks.
- You, for participating and getting positive delta.
- Last but not least, MikeMirzayanov for great Polygon and Codeforces platforms.
Good Luck & Have Fun!
UPD1. The Editorial was published.
UPD2. Congratulations to the winners!
As an author, I can confirm that no problems are authored by AI!
As another author, I can confirm that as I authored at least one problem, I'm not AI!
I think you are a bot as I don't know how your mind works.
I think you are a bot as I don't know how your mind works.
I think I`m a bot
As a tester, I can confirm that the authors are all bots.
As a tester, I can confirm that a lot of people think I am AI!
...which really kinda shows from the downvotes, I told you 😂
I think you are a bot as I don't know how your mind works.
As a bot, I can't participate in this contest.
As a bot, my existence has violated CF in-contest rules.
Hi there
As a tester, I was really looking forward to participating in this sponsored contest, only to realize that I had already tested it.
As the boyfriend of the girlfriend of the tester Caylex, may you good luck & have fun!
Didn't think that relationship is commutative, until I saw the same name. Well played!
oh！you are such a cute nailong.
Philosophy
The round's number "985" is special for chinese, especially for our students.
Hope you all can perform well in the "special" round.
why
Because 985 mean a group of good colleges in China.
Project 985 refers to the drive by Chinese government (announced in May '98) to push the best Chinese universities (original list had about 9) to be among the world's best.
Heartbreakingly, my university is still 983 steps away from being a 985.
As a newbie, I hope that I learn more in this contest.
The score distribution is scaring. I hope I can reach master in the contest.
yeah, it feels like questions are gonna be on harder side
congrats!
As a tester, I might lose a T-Shirt.
I wonder what the tourist will choose: the chance to win money with the risk of losing their rating, or doing nothing at all?
If you just think that he could ever think in the 2nd choice (losing the rating), then you don't know him.
As an author, I prepared $$$998244353$$$ problems and wrote $$$998244353$$$ pieces of editorial in all (modulo $$$998244353$$$).
Love the score distribution, 750 for A problem means 1 WA only cost ~ 7% score...
It'll be less painful for stupidity submission sometimes.
As a tester, there will be 0.3 problems about penguins.
24 points to expert ! lesss gooooooooo
Bruh C is worth 1750!!! Thats actually too much. I'm assuming it'll be wayy more difficult than usual.
points are relative to that contest problems.
As I said earlier..
Thanks for all the downvotes though.
As a tester,I'm a bot.
As a tester, I really like some of these problems.
For Chinese high school students, "985" is a special number. Wish everyone to get into the university of their dreams!
what's the coloration
a kind of Chinese university, they are usually the best in China
As a tester and the friend of the author sszcdjr, I can confirm that the authors are all not AI, because I can't solve any of their problems! GL&HF!
sszcdjr is male.
Just out of curiosity, what is the relationship between the score of a question in a contest and its difficulty in the problem set (https://mirror.codeforces.com/problemset). I know higher score questions are more challenging, but after noticing 2 questions with score ≥ 5000 and no questions in the problem set with this difficulty it made me realize its not a identity mapping between the two (that is difficulty(score) != score)
Is there Chinese statement?
No.
thx
Finally got the Tourist title :)
Congrats!
How come the badges of the authors are not related to their PFP I thought in CF badges come from your CF PFP.
It mainly comes from their luogu PFP.
Please reschedule, it's my birthday
Please reschedule, it overlaps with COCI Contest #2
Want to see tourist's rating change!
_istil What's the behind your badage ?
light ray ? physics ?
btw like it
geometrical optics, it's a convex lens and the object is positioned b/w the pole and focus hence a virtual image is formed.
In fact, it is the badge of sszcdjr)
Good luck!
rainboy vs 5500 points problem
Smashed it LOL
this contest is rated? ;-;
From the post we can see, YES
Hope to reach CM in this contest!
So this contest is rated?
Why you think it's unrated?
It's rated for sure.
I think it clashes with COCI :(
Nope, it seems that COCI starts 25min after the CF round ends.
Loved the '0' interactive phrase .
Good luck for everyone!
I think, contest will be interesting without interactive problems, (because I can't really solve it)
The contest is about to start in an hour, but only 17000 people registered!? Is this a special feature of Div1+2?
Last Div2 30000+ people registered, and this one is a Div1+2, shouldn't there be more people?
As i see in previous rounds,it's probable due to length of the round,many people skip the 3 hr contests.
As a tester,Hanghang007 hanghanghanghanged
this is the hardest div
i need mom <_>
rainboy being RAINBOY !!
As a participant, I read all the comments!
c any hints??
edit : got it thanks
DP
can you elaborate
dp with 3 states — in interval, before interval, after interval
Me personally, I did a Binary Search on answer but I'm expecting an FST lol
can you explain
So... Let x be the final rating i can achieve. Here's how u verify if there's a possible answer. So u start from 0 and reach i with rating say a. Now the final rating is x so u can trace it back and check what the possible rating could have been at every index j from back.
Now for any index i, U can remove the subarray [i,j] if i can achieve the rating x from j. And this is something that we have already precomputed from the back.
Will share the sub after system testing
how did you calculate the achievable rating from back
I just simulated the process in the backward direction.
Here's the sub: https://mirror.codeforces.com/contest/2029/submission/290731708
I also cam up with same idea but while simulating backward I couldn't get it right as in case when my current rating after ith x and ai is also x so previous possible rating would be either x-1 or x this divergent thing makes it tedious and branching outwards for implementation, could you explain how u came up with computing from the back.
Yeah i faced the same problem. So the trick is to always consider it to be x-1 and not x. This is because u wanna consider the minimum possible rating at index j with which u can achieve the final rating x. So its always optimal to take x-1 instead of x when ever u have a choice.
Another way of thinking would be that the rating is always continuous. So if i got some y<x (final rating) I would have always got all ratings between y and x included.
ohh nice, missed it there
thanks.
Note that at each index $$$i$$$ (right of the interval), you need to maximize the current rating at $$$i$$$ to reach the global maximum. It is not easy to note this.
Binary search
I spent 2 hours on C, yet did not solve it.
me neither
leetcode buy and sell stock came in clutch
same
Prolbem E. Why this is WA21? (I can't resubmit now, and in submission there is junk code.)
Where is
primedefined?It's
bool prime[N];, accidentally erase hereNote that if you have a prime like 1021, then you can't reach 2077, and 2077 is not prime
2 67 143
2
401 817
1 2 431 869
wtf C, I'm so broken mentally, been doing cp for nearly 2 year still cannot solve C confidently, how this is even possible. god abandoned me
Why such a small number of participants? Only 7k+ solved A.
Edit: contest without subtasks feels so good.
A must have scared them away
participating div1+2 is generally harmful for div2
How to do C?
you can use dp
Damn got cooked... someone explain C please?
Really enjoyed the problems. Great work authors!
Seems like some $$$O(3^n)$$$ passed H.Is it intended?
Looks like skipping C worked well for me, I solved A, B, D, E, F and then failed to solve C for about an hour lol
Any hints for F?
Things I could observe:
If all edges have same colour, answer is clearly yes.
If both $$$RR$$$ and $$$BB$$$ appear the answer is clearly no since there is at least one pair $$$(i, j)$$$ where all paths start with $$$R$$$ and end with $$$B$$$ and can thus never be palindrome.
For simple alternating colours ($$$RBRBRB\ldots$$$), the answer is yes for odd $$$n$$$ and no for even $$$n$$$.
The answer is no if an even length blocks of a colour appear more than once since there will be paths which are forced to start with $$$BB$$$ or $$$RR$$$ but can only have an odd number of the same colour at the end (example graph).
But I still have no clue how to generalize this to a solution.
Consider the sample RBRBRB.
The answer is no in the samples which matches my statement?
Oh my bad, I misinterpreted your statement. Honestly you are very close to the solution, consider the case where there are only odd length blocks.
You just have to add
And it's "YES" in all other cases. You can remove (3) since it's a corollary of the rest.
One more edge case: the answer is yes if there are no blocks of even length, but there are only $$$2$$$ blocks and one of them has length $$$1$$$ (because both vertices always start in the same big block).
You can't have alternating colours with odd $$$n$$$, the array is cyclic. RBRBR is the same input as RRBRB, which isn't alternating.
I was trying to hack this solution during the contest — https://mirror.codeforces.com/contest/2029/submission/290747953
Can anyone tell me why this is not giving TLE for the case tc = 1e4, l = 1, r = 1e9, k = 1 sszcdjr
The compiler is probably smart enough to optimize loops like this:
Ohh!! thanks.
rainboy orz
C>E
C>D>E
A construction similar to the one from problem D appeared at IMO 2019, problem 3. (But of course, it is a completely different problem.)
broken link
thanks
My solution for C:
dp[i][0] = the maximum answer up until i given that you haven't skipped any elements so far
dp[i][1] = the maximum answer up until i given that you are currently skipping elements
dp[i][2] = the maximum answer up until i given that you skipped some elements and are now back to not skipping elements
Transitions are annoying but its pretty much just casework. The final answer is max(dp[n][1],dp[n][2])
and how to track how many you have skipped? I thought similar but gave up when I thought I also need to track how many we are skipping.
you don't need to track that
but then what will we compare a[i] against?
dp[i-1]
shit ofcourse
How to solve D?
You can decrease number of edges by atleast 1 in each operation until every vertex has degree<=1
The decreased number of edges is 1 or 3.
Got it, it is like a destruction and after a reconstruction to obtain a tree, in case when all degree can't be zero, isn't it?
simple code for C : 290735677
Why does this WA on D? I thought you just needed to get rid of cycles then it was easy
Can someone tell me how to solve B? I think I almost get it, yet I can't arrive at a full-fledged reasoning.
replacing with a 1 doesnt change the count of 1s in s, but replacing with a 0 decreases the 1s. So if the count of 0s in r and 1s in s is same, the final bit in s (which is actually last element of r) should be 0. one more case is if count of 1s in s is just one more than the count of 0s in r, then the final element should be 1 (i.e r.back()) also as long as both zeros and 1s are there there will be atleast one adjacent different pair so we can ignore where to replace ezactly
Note: there exists a $$$01$$$ or $$$10$$$ if and only if the binary string contains both $$$1$$$ and $$$0$$$.
C is like 4500 rated problem... I almost gave up on it at some point :)
Pretty sure you've overkilled it
Undoubtedly!
Skipped it, solved DE, and then while looking at it somehow thought "wait, this is obvious dp"
every overkill solution solves something more than necessary, so i am curious, can your solution solve for a variation of this problem where instead of k increasing by 1, k increasing += b[i] where b is an array of points you get for each time your x > a[j] and j is the i'th contest you measure against? In the original problem you can think of b as an array on only 1s.
Argh, I read B's statement wrong (thought that you to replace $$$s_ks_{k + 1}$$$ with $$$r_k$$$. That makes the problem waaay more difficult :(
me fr wasted 40 mins on that
Same as you. When I realize that 30mins went.
so i'm not alone
Just saw some mf sharing solutions in contest time on YouTube
I still haven't understood why people think videos are a reasonable way to share content that consists almost entirely of text.
Are the downvoters cheating, or did I write something incorrect?
Generally, it is not a good idea to share links to such channels. You will probably do more harm than good by giving potential cheaters an explicit location that they could look out for next time.
However, I'm not sure where one is supposed to report such occurrences; Mike and round authors come to mind, but I don't think they can actually do anything to take channels/videos down on youtube? idk
Oh shouldn't have shared that my bad
Seems like people are quite confused about C while it has a relatively straightforward solution:
Binary search the result x, and check if you can construct a solution whose score is x.
A solution needs some prefix + some suffix. You can calculate $$$prefix[i]$$$ = score as you get to position i, $$$suffix[i]$$$ = minimum score needed, starting from i, so that the score is x. Then you can calculate $$$min_suffix[i] = min(suffix[j], j \ge i)$$$.
The answer is valid if there exists i such that $$$min_suffix[i + 2] \le init[i]$$$: e.g. we take a prefix up to i, skip some elements, then take on a suffix that brings your final score to be x.
Of course you also need to handle the edge cases where the prefix or suffix is empty.
There is an even simpler solution:
A higher score is clearly always better, so I store $$$dp[pos][0 / 1]$$$ = max score after the first pos contests with 0 / 1 indicating whether we've skipped a segment.
The regular (non-skipping) transition is a typical $$$dp[i + 1][j] = dp[i][j] + \text{(score change for current rating = dp[i][j] and performance = a[i])}$$$.
For skipping a range, its just $$$dp[i + 1][1] = \text{best prefix value of } dp[i][0]$$$ :)
Code — 290717116
I'm actually surprised so many people bricked on this problem, to me it feels like an extremely standard problem I'd expect to see in an Atcoder Beginner contest D or E.
Wtf is E? Something to do with least primes?
You're on the right track.
$$$x = 2$$$ clearly works for all even numbers, but what about odd?
For a non-prime value $$$v = p \cdot q$$$ where ($$$p,q \gt 1$$$), whats the largest even value that can reach it by performing the operation once?
Can we ever reach a prime with some other values?
What if the smallest value is prime and the others values aren't?
Use the same logic in hint 2.
Code — 290740094
Check out neal's solution to problem C, you won't believe how simple it is.
C can be solved with 3 priority queues, without dp or binary search.
explain please
We have 3 states: before interval, in interval, after interval.
Loop over the array with maintaining 3 max PQ (one for each state),
in each iteration we do the following:
1) update the top of the after interval PQ. (interval has been closed)
2) push the top of the before interval PQ to the in interval PQ. (open an interval)
3) update the top of the before interval PQ. (interval has not been opened yet)
4) push the top of the in interval PQ to the after interval PQ. (close an interval)
Finally, the answer is the top of the after interval PQ.
Your solution is exactly the same as dp from editorial. Priority queues are not needed, you can simply store value of each state in variables.
Anyone knows what's special about problem D test case 21?
I'm getting TLE and cannot reproduce it on my pc by generating random test cases
From what I can see in the partial input data, I guess that it's a huge star-shaped graph centered on vertex $$$30954$$$, that is, its edges are denoted as: $$$E = \{ (30954, i); 1 \le i \le 100000, i \ne 30954 \}$$$.
holy cow, thanks a lot
Glad to win one ninth of a T-shirt!
Salamancas are even in the cp business now 😱 No one is safe
for F, let $$$s$$$ be the parity of the lengths of the runs of the color which doesn't appear in only groups of $$$1$$$ (WLOG, suppose it is red). I deluded myself into thinking about the problem as if every time you cross a blue, you always start at the left end of the corresponding red segment, for which I think the answer to the problem depends on whether $$$s$$$ equals any of its cyclic shifts
why am I regarded 🤣
i reached candidate master at this round ,finally div1
can anyone explain dp implementation of C. thankyou in advance .
i did not understand f(a,x) it should return a + (a>x) — (a<x) can someone help
That code uses some little-known feature of Python that
boolis a subclass ofint-- you can seeisinstance(True, int)returnsTrue. As a corollary to it, when aboolvalue is used in an arithmetic expression,Trueis converted to1, andFalseis converted to0. For example,5 + Trueis6(!).variable names are reversed here compared to the problem statement. Swap
aandxin the function f and it should make sense.Thank you very much for the contest.
will i be contacted from recraftai if i had filled the form before the round and have got +79 rating points at the round?
Is the red text in I a correction of a constraint that was originally written higher or just emphasis?
Emphasis. :)
Edit: Well, why is this comment getting downvoted?
Isn't this promoting cheating in a way?