"You are braver than you believe, stronger than you seem, and smarter than you think." — A.A. Milne
Hello Codeforces!
I have the pleasure of inviting you to participate in Codeforces Round 930 (Div. 1) and Codeforces Round 930 (Div. 2), which will start on Feb/29/2024 17:35 (Moscow time).
You will be given 6 problems and 2 hours to solve them in both divisions.
One of the problems may be interactive. So, please refer to the guide on interactive problems if you are unfamiliar with them.
The problems were prepared and authored by wuhudsm, chromate00, Psychotic_D and MagicalFlower.
We would like to thank :
- irkstepanov for coordinating the round;
- BurnedChicken for the only LGM testing;
- amenotiomoi,siganai, vgtcross, amethyst0, dognotlike, alireza_kaviani, and dorijanlendvaj for GM and IGM testing;
- aryanc403, k1r1t0, Little_Sheep_Yawn, Amir_Parsa, blxst, pavlekn, Error_Yuan, IceKnight1093, aufannn, Mingyu331, Akulyat, Arpa, and mhtkrag for M and IM testing;
- O--O, Abhishek_Srivastava, MrDelrus, htetgm, Silver_Fox, dhyang24, and milind0110 for CM testing;
- brave-kid, WrongAnswerOnTest3, vikram108, mafailure, AnanasClassic, Think_Only_Once, go_onin, lemoncookie, and flakes24 for Expert testing;
- Banis, stepan.karpov, FiniteMoves, and fintai for Specialist testing;
- HexShift for the only Pupil testing;
- JaberSH1 for the Newbie testing;
- tibinyte2006 for the Illegal newbie lying face testing;
- MikeMirzayanov for the great Codeforces and Polygon platforms;
- And at last but not least, You for participating in the round!
Good luck, and may the code be with you!
UPD: Score distribution:
Div.1: $$$500 - 1000 - 1500 - 2000 - 2500 - 2750$$$
Div.2: $$$500 - 1000 - 1500 - 2000 - 2500 - 3250$$$
UPD2: Let's continue the streak of announcements with photos of the authors and coordinator.
UPD3: Editorial is out.
UPD4: Top Performers
Div.1
| Rank | Name |
|---|---|
| 1 | Radewoosh |
| 2 | zhoukangyang |
| 3 | ugly2333 |
| 4 | tourist |
| 5 | 998batrr |
Div.2
| Rank | Name |
|---|---|
| 1 | JiaY19 |
| 2 | kizaru |
| 3 | Midnights |
| 4 | SATSKYnerfed |
| 5 | VTloBong |
Yet another TheForces official round!
Be sure to take part in this round, the authors have put a lot of efforts to prepare the round as balance as possible ;)
As a problemsetter, I hope everyone will enjoy the contest. May the $$$\Delta$$$ be with you!
I think the score distribution for Div.1 and Div.2 need to be reversed.
done 🙏
Mathforces ? Just a prediction.
As a brave tester I can assure that problems are very good
First time testing an official round! Hope the problems will be interesting for all of you!
As a tester, I assure that your Leap Day is going to be fun!
Finally, $$$6$$$ months have passed since the last official round of TheForces community, another official round! I hope you enjoy this round :)
As a tester, problems are really nice. Please do participate and get high ∆
As a tester, may positive delta be with you.
as a tester i can assure that problems are very nice
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
haha broke your silly chain
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round
OMG! Another Psychotic_D round!
OMG Other Psychotic_D round
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
OMG! Another Psychotic_D round!
YEAH! Another Psychotic_D round!
OMG! Another Psychotic_D round!
so many testers !
Adding tibinyte2006 as newbie tester should be illegal 🤥
Adding tibinyte2006 as newbie tester should be illegal :lying_face:
Adding tibinyte2006 as newbie tester should be illegal :lying_face:
All this testers!. i think the contest is going to be great.
As a Sigma tester, I did fintai during testing this round, because problems are great.
Agree
Yay finally a div1 that takes place when I'm actually available.
Are you winning son?
OMG! k1r1t0 is tester!
Yes
I want to become CM for the first time. I am so excited!!!
I hope to welcome you to cyan!
Thank you so much my friend. Its good to know that I am always loved no matter where I am or what my color is. I hope to see you green after this contest!
As a tester, this is definitely one of the rounds of all time
No. This is two of the rounds of all time.
As a tester, problems are nice, recommend everyone to participate!
amenotiomoi orz tester <3
vikram108 sir orzzzzz
As a tester, problems are interesting, hope your delta be >0, and have fun when solving the problems, especially the interactive one(if there's one in your division)!
So many testers that only the "As a tester" comments would make the normal comments count. XD
As a green tester, the text inside the problems are not green. It's black.
But still, very clear statements all around and hope y'all enjoy the rounds!
Once in FOUR years
.
Problem solved!
zzoxaz stoled MKasirloo's meme!
Problem solved
Illegal newbie lying face testing xD... Real Psychotic :p
The interactive problem is for div1 or for both division?
It may be only in Div1 or Div2 or in both Div1 and Div2, you will see it after the round starts:)
How so pro Psychotic_D ser?
How so pro Psychotic_D ser?
Please not again ;)
How so pro Psychotic_D ser?
It'd be good if you continue the streak of announcements with photos of the authors :)
Will do for sure.
Uploaded
Damn, I thought chromate was bot.
One problem will be based on Leap day or Leap year I guess
Thanks for continuing streak of putting authors pictures on the contest blog
grecozo will win the round, pin this.
*gets a negative delta and again "sadness,boredom,depression,loneliness,social-anxiety"
and the loop continues..
It's too early for that.
As a parcipicant, this round will happen again in 4 years
And also Good luck for everyone!
Abhishek_Srivastava , the tester , orz
Is there a photo of MagicalFlower?
Orz chromate00 for being a problemsetter.
never get bored of this meme
deleted
I'm sorry about that
memes are called memes because many people share them. If you are against this, go to a platform where you can hold copyrights. Let us have fun as the codeforces community.
I loved the way you thanked the participants.
Goodbye, cyan ;(
Hope I will reach to 1400+
Is MagicalFlower the up right one on the photo?
no, that's irkstepanov, the coordinator. (sorry for the ping, mr coordinator)
No offence to anyone.
HAPPY LEAP DAY 2024 ROUND.
dark theme looks so good awwwwwwwww,how did you get that!!
There is an extension for chrome, dark reader.
chromate00 be like :)
Downforces incoming
Psychotic_D We would have been more happy if today's contest named was Happy Leap DAY 2024
Absolutely love the quotes that they have started putting at the start of these announcements.
Back after long time hope to solve 2-3 problems.
looking forward to photo of MagicalFlower. very handsome
indeed
B is bad
whats wrong with this round??
hardforces
try something other than creating contests
Shout-out to all my div1 homies who submit a problem when they know for sure that they will lose rating if they become a participant after making a submission
lmao
Binaryforces.
Maybe I have forgotten how to make correct submissions to problems
For div1, it is so painful to get -50 for each dirt, since the total score is not very high. rk30 ~ rk60 only has a score difference around 100, but the ranking doubled.
Nice problem C
how to solve B, i only got the lexicographically smallest string but could not figure out how to get no.of ways
The key observation is: If you go down at some point, then you have to go to the right for the rest of the operations.
So the way I handle is to build an array b, which indicates that for a position i, if I go down, can I get the lexicographically smallest string? Then, for each position i, you have two choices: go to the right or go down. If you go down, check if b[i] = 1, then you can increase your result. If you go to the right, you have to make sure the current string you got is matching with the lexicographically smallest one.
Submission
Too Hard.
observation force
why so hard b
The first three problems were one of the best in a while, especially problem C, but the last three were too hard.
Div1B — ImplementationForces
Div1C — StandardForces, if you put it at Div1B it would easily have 500-600 solves.
I spent like 10 mins combined to think of the solutions and around an hour to implement them :).
Div1A legitimately required more thinking than Div1B and Div1C combined (and was actually a pretty cool problem).
What to do in problem C? I have no idea.
Sort values of each attribute in non-decreasing order and add edges between adjacent attribute values "nodes" to make a line graph of their values. Going "up" in value costs 0, going "down" costs the change in value. This corresponds to the "increase power" operation. This uses $$$2 \cdot (n - 1)$$$ edges per attribute, or $$$2 \cdot (n - 1) \cdot m$$$ edges in total.
Then add edges between attribute value nodes and pokemon nodes. The edge to the pokemon corresponds to summoning them and has a cost of $$$c_{\text{pokemon_idx}}$$$ while the edge the other way has no cost. This uses $$$2 \cdot m$$$ edges per pokemon, or $$$2 \cdot n \cdot m$$$ in total.
Then you can just dijkstra from pokemon $$$1$$$ and find the min cost to reach pokemon $$$n$$$ in $$$O(n \cdot m \log(n \cdot m))$$$ time.
how to implement B
My solution at least is painfully long, so just going to roughly describe each step:
Calculate the number of '>' to the left and '<' to the right of each pos. These represent positions where we might turn around during this operation.
Based on these counts and $$$s_i$$$, we can figure out how many values we'll bounce off to the left and right. It will be either min of the count of the above two values, possibly 1 lower. We can also figure out which direction we'll leave the grid in, I just add that time to my answer here since its convinent.
Now, we can keep track of prefix / suffix sums of these (one at a time) as we iterate. Then if we known we will make $$$x$$$ bounces to the left, we want the sum of distances to the last $$$x$$$ bounces. This can be represented as $$$(i \cdot x) - (\text{position_prefix_sum}_{end} - \text{position_prefix_sum}_{end - x})$$$. Don't forget to multiply this two since we bounce and come back to the center.
Code — 248943453
How to modify the Dijkstra for Div1C? I couldn't figure out how to quickly calculate if a pokemon would beat the other one where one is modified for in its attribute.
Hint / Short answer — Try to split the edges into two types, corresponding to the two types of operation. Then the graph for dijkstra becomes much easier to formulate.
See https://codeforces.me/blog/entry/126416?#comment-1123291 for a more detailed explanation.
Actually there exist easier way to solve B, my submission only takes < 30 lines
submit C in last 10 second phew~
Can someone explain why this wouldn't work for problem C ?? 248966532
if n = 12, then it would be optimal to chose 11 and 4
Actually, 11 and 4 (you cannot use 12)
ez minus delta
DeflationForces
Why is there a 20-minute penalty for every wrong submission, when it's only two hours of competition.QAQ
wtf bruh :(, never seen this hard Div2.B, all aside but I enjoyed the contest. Thanks
The problems are really good, but they felt a bit harder for their position.
We felt they are easier.
Sorry for it.
1B = https://codeforces.me/contest/733/problem/E?
It is exact the same. I modified my code for 1B, turnning 'U' into '>' and 'D' into '<' and it just passed 733E here.
Can someone please explain the flaw in my logic for C?
ah no way I didn't even think about oring them with each other. I think the flaw is that or includes duplicate bits and so it would make for a suboptimal XOR.
for 0,1,2,3 3 will give maximum or with all 4 index, how'll you handle it?
You have to handle the case when the ORs are the same, then take the smaller element. For example, n = 8, 7|6 == 7|0, your solution would return the positions of 7 and 6.
Note that the solution requires the maximum XOR. So there are multiple indexes that give the best results with OR with the maximum element, but only one of them gives the best result when XORed with the maximum, which we output as solution.
There are potentially multiple indices i such that max value OR i yields the maximum answer. Think about which of these indices will yield the maximum answer for XOR.
The smallest "candidate" value
Can someone pls explain an approach to Div 2 C?
The answer is x and y.
That is pretty clever, I didn't even consider oring the same element lol. Thanks
can you share the intuition behind this
1.We can use n-1 to find max value
2.how do you handle for multiple ORs when they are equal a[x]|a[y]
3.why do we need x&y where a[y] is smallest
W can have max ans as $$${2^{(msb+1)}-1}$$$
For example a[x] = 1001. Then there are only two a[y]: 0110, 0111. As you can see, those a[y] | a[x] produce the same result (which is 1111) but we choose the smallest ay as the answer because it has the SMALLEST NUMBER OF SET BIT. This is important because we could prevent 1 XOR 1 in some positions.
I guess since we know all values (permutation 0..n-1) we can find the max xor, and then find values which give that target xor.
The thing is, if you look at binary presentation of (n-1), and !(n-1) easy (not during the contest) to see, that !(n-1)<n-1 (we dont look at the bits greater than greatest bit of n-1), so if !(n-1) !(n-1) exist in permutation. Also easy to see that (n-1)^(!(n-1)) is the maximal xor we can get, and all what we must do it find n-1 and such index that (n-1)^p[index] maximal, we proved that p[index] = !(n-1). I think so
Nice problem Div2C/Div1A. Got the solution with 2 minutes remaining :(
Solved Div1B in last 10 seconds. How can I improve my implementation?
Ok simple question for PROBLEM-B
if I had 2 paths previously and 3 NEW paths were found, what is the total no of possibilities?
A) 2+3=5
B) 2*3=6
C) 2^idk
D) Think outside the box
Testcase -
7
1111111
1101110
Ans is 11101110 probably, please HELP
My code Thanks!!
once you go down a thing you can do is go right
This idea is genius!!
Find Lex string and for each index
check if top left+bottom right==lex string
Implemented its code and it's working perfectly. Too bad I can't submit to check it.
Thanks a lot, I can sleep peacefully now.
I'm pretty sure that idea of string comparison for each index will give you TLE though...
1B=https://codeforces.me/problemset/problem/733/E
It's NOT Div2, it's Div 1.5
So I guess Blogewoosh #5 (+ golden search to squeeze it) isn't intended for F?
No, it isn't :(
Terrible contest.I don't think this kind of competition is very interesting, even if the question setter feels that they have come up with something interesting.
Why??
The problems are good, but I'm totally confused about what happend with cin in code 248946386, which I got TLE. When I replace cin with handwrite fast io in code 248950473 my program just run 249ms.
Is it possible to solve Div2B with dp?
can someone please check my code, gives error on pretest 2 248969661
if it helps, loop1 : i i j j to search a[ i ] = n-1; loop2: query (i j i cc) to find j such that (i or j is max) and a[j] in minimum among all such j
D1A/D2C: First query for the largest element, let it's index be i0, then query for indexes j such that (a[i0]|a[j]) is the maximum, finally in these j we find j0 such that a[j0] is the minimum, then (i0, j0) is the answer.
D1B/D2D: WLOG assume s[i]='<', then we do something like this: go left find the first '>' --> go right find the first '<' --> and so on... So if cnt1= the number of '>' to the left of i, cnt2= the number of '<' to the right of i, then if cnt1<=cnt2, we will turn back at all positions of '>' to the left and first cnt1 positions of '<' to the right, if cnt1>cnt2, we will turn back at all positions of '<' to the right, and first cnt2+1 positions of '>' to the left. Then we can calculate the answer by the sum of positions of points we turn back. (The contribution factor of points we turn back at left is -2, points we turn back at right is +2, and the start point is +1, the end point is +1 (if end at right border) or -1 (if end at left border))
D1C/D2E: Build a graph of n*(m+1) nodes with index (i, j) (1<=i<=n, 0<=j<=m). Then for all 1<=i<=n, 1<=j<=m, we add edges (i, 0) --> (i, j) with cost 0, (i, j) --> (i, 0) with cost c[i]. For each 1<=j<=m, we sort [1, n] by the value of a[i][j], and for adjacent (i1, i2) in the sorted array, we add edges (i1, j) --> (i2, j) with cost 0, (i2, j) --> (i1, j) with cost a[i2][j]-a[i1][j]. (So distance from (u, j) to (v, j) is the cost to let pokemon v to win pokemon u by attribute j) Therefore, go along the path (u, 0) -> (u, j) -> (v, j) -> (v, 0) means we let pokemon v beat pokemon u, then the answer is the distance from (1, 0) to (n, 0).
D1D/D2F: This uses segment tree idea described here. The idea is that there are only $$$O(\log A)$$$ number of distinct prefix ORs/suffix ORs. so we will all of the possible suffix and prefix ors, along with the maximum of the other array in those positions (which corresponds to maximum of the shortest prefix/suffix with equal or). We can merge nodes suffix and prefix while keeping them distinct, and update the answer for node with brute force in $$$O(\log^2 A)$$$ resulting in $$$O(q \log n \log^2 A)$$$ but if we use two pointers to update the answer, the overall complexity will be $$$O(q \log n \log A)$$$ and this is fast enough to pass. Beware that creating too many
vector<pair<int,int>>s could be too slow, that's why it's better to usebasic_string(I described this here).Does this contest allow hacking?
You can only hack during contest time in div. 2 if it is not educational round
(The problem) is very well done, don't do it next time.
at least write your real opinions about the problems instead of taunting the authors :/
I was only joking, and if this offended you, I sincerely apologize. Additionally, it's just a humble opinion of mine that if a competition were to rank based on the speed of solving easy problems, due to the presence of highly difficult problems acting as a divide, it might be considered somewhat biased.
Actually you're right, we received feedbacks from the testers that the problemset is even easier than usual CF rounds, and we never expected this level of difficulty for the participants ...
I'm sorry but is Div.1 B similar to contest 733 problem E?(✺ω✺)
would have been great to have subtask for Div1B which allows n^2 solution. then participants can decide whether they spend time implementing full solution on not. being forced to implement this is not great experience... (yeah yeah i know im bad in implementation, but IMO this change would have improved contest experience for a lot of participants)
tourist might come back to top 10 rated today :) :)
Div2 is so difficult. I dont like it.
what is the best way to test my interactive problem's code.
make a function to calculate the responses for your queries and then comment the function while submitting.
Answer your own queries
DuongNeverAlone Bro if i want to reach expert in 6-8 months! What should be my strategy? how many questions per day i have to solve? (i started c++ last year) I'm ok-ok at implementation, basic maths, and techniques like pfsum, sliding window etc
It's not really important how many problems you solve per day. I mean, it is still good if you manage to solve such huge problems in a day, but it is more crucial to concentrate on problems which are higher than your current level, then you can study more topics from those. Otherwise, solving easy problems literally give you nothing much.
By the way, if you want to give you an exact numbers, I think 5 to 6 problems should be fine.
Make a template with something like
Example in rust.
Can div2B be solved with DP to find the path's string?
My trial: Submission Div2B
Bro Don't make this problem complicated. Think in some simple way. My Submission: 248641114
Is the problem solvable by doing just simple dfs?Just expanding the path if it is giving lexicographically smaller ?
Bro, I didn't even know dfs so i can't tell you if it is possible or not
Any idea why this fails for Div2 C? 248972248
wait...so div1B/div2D and CF733E are completely equal?
exactly, just change "U" with ">" and D with "<"
The experience was not good. :(
Within a few minutes after the end of this round , I saw many people saying that they are identical problems.
Wanted to thank all the authors for coming up with a very nice problem set. Especially problem C, which helped me realize that similar to MinMaxFlow, Dijkstra too is quite powerful when combined with carefully constructed graphs. Thank you for taking time to produce these problems. :)
Can the System Testing be resumed?
I am really curious how bad my F code would fail.
They are preparing tests to kill unintended solutions :(
Issue from the CF server, I guess.
Something seems to have broke, Mike is on it right now.
Why did the system test STOP
Are Mike playing Genshin Impact ???
I think he is not playing genshin impact, but maybe he is playing Honkai: Star Rail right now!
mihoyo leads
I want to upsolve
For F you can binary search and check nonemptiness of disks intersection. How to do this in the simplest possible way? You recall the simplest possible algorithm to nonemptiness of halfplanes intersection https://blog.mitrichev.ch/2016/07/a-half-plane-week.html?m=1 and generalize it to circles. That is, take random order of circles and maintain the rightmost point of their intersection. If a new circle contains it, then we are good. If not, then this point is on this circle and we intersect it with all previous ones in O(i) time (where we are considering i-th circle right now). Amounts to O(n) time, so with binary search on top O(n log n) for the full problem
And of course such problem had to be on a round in which I wanted to participate, but forgot >.<
Skill issue, bro
actually we had that in one of our tester's solutions, it gets WA due to not sufficient precision and/or bad epsilon evil laugh
No one told me that it will be Div 1.25 ;/
Why does this give tle for problem B is it O(n^2) because of the iterators? 248960076
Can somebody provide insights? Thanks
string addition is O(n)
Funny how i misread C's statement and solved it for increasing jumps and still got AC
Nice contest and Nice problem C.
screwed up too badly on b, spend an hour and half on hashing string & bitset & dp shit. endup +6 wrong submission until finally realize [spoiler] and receive 300/1000pt. 🙃
was a similar problem to div2d on IMO?
It's a nice Div.499122177
Wonderful round!I became master!
Solved ABC. Thanks a lot for the round wuhudsm chromate00 Psychotic_D MagicalFlower and all testers!
$$$O(n)$$$ two pointer simple solution for D1B/D2D. https://codeforces.me/contest/1937/submission/249021364
In this contest https://codeforces.me/contest/1936/problem/B and https://codeforces.me/problemset/problem/733/E are a question.
Nice Round..
LOL