Xin chào Codeforces (・ω・)ﾉ
We are pleased to announce the resumption of the Global Rounds. Thanks to XTX Markets for supporting the initiative! In 2024, we will hold 4 such rounds. The series results will take into account the best 3 participations out of 4.
On Apr/06/2024 17:35 (Moscow time) we will host Codeforces Global Round 25. 
Codeforces Global Round 25 marks the first round in the 2024 series of Codeforces Global Rounds. These rounds are open and rated for everyone.
The prizes for this round are as follows:
- The top 30 participants will receive a t-shirt.
- 20 t-shirts will be randomly distributed among participants ranked between 31 and 500, inclusive.
The prizes for the 4-round series in 2024:
- In each round, the top-100 participants get points according to the table.
- A participant's final score will be the sum of the points they earned in their 3 highest-placing rounds.
- The top 20 participants across the series will receive sweatshirts and placement certificates.
We extend our gratitude to XTX Markets for supporting the global rounds initiative in 2024!
The problems were all marinated and cooked by MofK and Kuroni.
Our sincerest gratitudes go to:
- errorgorn for being the 🥶 and 😭 coordinator, and TheScrasse for being the 🧌 coordinator.
- xuanquang1999, gamegame, zeena., lanhf, Sana, TrungNotChung, lmqzzz, Umi, imsuck12, Saacoota, htetgm, kodomo_tachi, shine_, uocgimauxam, Pemguimn, Bananabread, hphuong, DeMen100ns, Kriz_Wu, milind0110, YangJackie, Vladithur, Ann, Endagorion, richzli, BucketPotato, and _FireGhost_ for testing and ensuring the balance of the round.
- Alexdat2000 for translating the statements to Russian.
- And of course, MikeMirzayanov for Codeforces and Polygon.
Round Information:
- Duration: $$$3$$$ hours.
- Number of problems: $$$9$$$ problems.
- Score distribution: $$$500 - 1000 - 1500 - 1750 - 2250 - 2750 - 3250 - 3500 - 4000$$$.
A tiny bit of personal note at the end, this is our first round on Codeforces in 3 years, and it feels a bit nostalgic to be back here again :) We eagerly anticipate your participation and let's all make it an awesome contest together!
UPD: Added score distribution.
UPD: The round has concluded. Congratulations to the winners!
- Geothermal
- ecnerwala
- Um_nik
- maroonrk
- jqdai0815
- Benq
- hos.lyric
- antontrygubO_o
- cmll02
- AlternatingCurrent
Tutorial can be found here, and playlist of songs used in the problem statements can be found here.
GLOBAL ROUND COMEBACK LET'S GOOOO!!1!
omg kuroni round
Guess who's back? Back again? Shady's back, tell a friend
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round orz
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round orz
omg kuroni round
omg kuroni round
omg resumption of global rounds
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
TLE*Segment Fault : Stack Overflow
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
Everyone is copying Asaten.
omg kuroni round
omg kuroni round
omg kuroni round
omg kuroni round
/.
kuroni is an untrusted author
omg kuroni round orz !
omg Kuroni round
As the author of at least 1 problem, hi! (updoot on the right)
imagine if you faced grealish instead of haaland
Forza city
As a tester, I love this contest. And I hope you will too!
Kuroni senpai orz
As a tester, I enjoyed this round and I hope you will too!
da. god
I pray to God that I can solve C this time.
Please marry me
Hi everyone, I have an announcement to make. Ari is no longer my girlfriend.
We're married now.
Before every contest, I habitually review the previous contests of the authors. It dawned on me that you both frequently collaborated on them. However, after stumbling upon this blog, I found myself scrolling through the comments. I noticed people hailing you as a legendary figure returning after a long absence. This sparked my curiosity about you and make me excited about this upcoming round. It's remarkable to learn that the two of you were not only partners in creating Codeforces rounds but also in life, culminating in marriage. I'm genuinely awestruck. Wishing both of you a lifetime of happiness! As they say, "Happy wife, happy life."
real
not true;
mofk -> https://team.vnoi.info/?team=quang-minh-dinh-nguyen
kuroni -> https://www.cs.purdue.edu/news/articles/2020/team-programming-finals.html
is this real?
XD
ok i will
As a tester, meow
As a participant,mooo
MofKuroni orz let's gooooooooooo
As a tester, I hope you guys enjoy this round
I also hope I enjoy this round.
cuteroni
uoooh cuni
As a tester, I need one more rating point but Kuroni say No.
Wait for the rating roll back.
Wow! Everyone is so excited! Which makes me even more excited! Why everyone so excited?
Finally!! Finally it's back!!!
As a tester, I can't speak too much, or Kuroni will send two Bocchi plushies to subdue me
we're watching you
Where BoKita
omg kuroni round vietnam gm orz so cute i love u uwu
My waifu Ikuyo Kita is soooooo cute!
true
Is this from the manga?
Omg global round
Kita wants to let you know something
good luck everyone, hope you all get a higher rank this round!!!
As the 🧌 coordinator, I can't participate :(
Sad:(
FINALLY GLOBAL ROUND ARE BACK!!!
I hope this would be a best Global Round ever!!
Good Luck for every one!!!!!!!
Is it rated ?
kuroni la ai ?
la ai
Is it rated?
Yes.rated for everyone.
Can somebody share the link to the blogpost that explains the legacy of CF global rounds or could just simply explain abt it.I am a bit curious to know abt it.
3 hours 🤢
As a tester, i tested
As a participant, I will participate
I hope it will not be MathForces.
Agreed, math like shjt
4000 score question!
a
I know you are looking for a Vietnamese comment here
How hard are the questions? I mean what div?
most likely div 1 level of problems because its a global round
Bro are u fr , its for all so mp it will have well distributed ques
It is div 1 + 2
Is it rated?
Dad please we need it right now, every single minute waiting is extremely painful
Waiting for so long so much suffering Where are you?
You are completely ignorant, holidays are coming everything is closed there's no food for days, putting someone alone through all of this is simply inhumane
As a participant, I will participate in this round.
Good luck everyone <3
leaving a comment for the culture
.
T made a mistake replacing X(his ex) else it would have been a lot of fun (XXX)
Let's go!!! and defeat all the questions. I can't wait to see the green accepted submission!!!!!!!
I hope I can solve 3 today !!! :(
Is it rating contest?
no, it is rated contest
the blooper gif :skull: :eyes_with_spiral: :sob:
kuroli came back :((((((
It's Kuroni
let's see how rusty i am
AINT NO WAY YOU CAME BACK FOR THIS
WE NEVER SKIP KURONI CONTESTS
I can feel the wa energy
found amogus in Problem D. ඞ
Deez nutz
oh it's in all problems didn't notice that !!
genuine question, is the song for each problem from author's playlist or it's just random bangers from youtube?
We know about these songs beforehand :) but they are random bangers indeed
song for problem I is such a banger. RIP wowaka
You Bad, heat you.
I took a short break from CP, but i am glad, that i came back for this one. I absolutely liked the problems, especially ones i didn't solve. Looking forward to the editorial to up-solve some.
Me spending two hours thinking of C "wait what kind of simulation is needed for this clusterhex?"
Me prepassed C at 2hr: "wtf just greedily sorting?????"
I should catch a break...
that's me
Hell that and an absurdly stupid +4 late on B will cost me my orange for sure...
Terrible day for me T.T
For problem G, OEIS saves my day!
I'm wondering if H is even easier than D/E or just my simple greedy algo passed the pretests?
Okay so H's solution is dead simple but we spend 5 days to solve it correctly with proof. I think it's just hit or miss.
got 13 WA on B
How to solve it??
notice that it's only optimal for you to swap numbers with index smaller than you. It's because it's better for our index to be as small as possible so we can win more matches. Notice again that we're not going to win if an element is bigger than ours but has smaller index. So, when there's a bigger element with smaller index than us, just swap them and then see number of wins. But there is another case. Consider that we don't need to swap anything or there's no element bigger than ours that has smaller index. In that case, swap first element with kth element. It's because we want index as small as possible so we can win more matches :)
I stucked and do not know what to do with 2 test cases
6 5 7 2 727 10 12 13 5 5 386397236 187533184 8314578 802929321 432147499 please explain!
In conclusion we have to check for two cases. Case 1: we swap first element and kth element then find winning matches. This works because. if the elements to the left of us are smaller than its better to switch ours on the left. ex: pretend our element is 5
1 2 4 (5) 3 10 11 -> only win one match
(5) 1 2 4 3 10 11 -> win four matches.
and case 2: if there's a an element bigger than the kth element with smaller index, we swap them then find winning matches. This is because if there's an element that is bigger than us but has smaller index then we cannot win at all:
ex: ours is 5
1 10 3 (5)
match result: 10 10 10 -> we cannot win at all.
swap:
1 (5) 3 10 -> we win twice.
After we find case 1 and case 2, then just take the bigger one.
6 5
7 2 727 10 12 13
case 1: swapping kth element with 1st element
12 2 727 10 7 13
max(12, 2) = 12 (ours win match), max(12, 727) = 727, max (727, 10) = 727, max(727, 7) = 727, max(727, 13) = 727 -> we only win 1 match
case 2: swapping kth element with first element that's bigger than us with smaller index
7 2 12 10 727 13
max(7, 2) = 7, max(7, 12) = 12 (ours win match), max(12, 10) = 12 (ours win match), max(12, 727) = 727, max(727, 13) -> we win 2 matches
result = 2 because we find the max of the two.
note: you don't actually need to swap element in the code if you don't want to (but you could if you prefer to). I just say swap to make it simpler. Hope this helps :)
I think the solution is just: try swapping with the first cow, and see what score you get, try swapping with the first cow that beats you, see what score you get. Take the maximum of these two. You can get both scores in linear time.
The reason this should work is: 1) you should never swap with anything later than the first cow that beats you, because then you will lose all your games 2) all the cows before the first one that beats you, you will beat, so if you swap with anything before the first cow that beats you, you might as well swap with the very first one (then you'll get to play the maximum number of matches before you go up against the first one that beats you).
I don't know though. I have 999 WA on this as well.
b is harder than c for me :(
I literally did this
same
How to solve C using binary search ?
I was also initially doing C through binary search on answer but later figured out that binary search was not needed at all after getting tle on test 5
i solve using heap and some maths , but somewhere i felt it was a typicall binary search question but couldn't figure out till last.
can you explain it ?
sort the days in increasing order of their price and pick the very first ceil(k/m) number of days and buy maximum number of possible tickets on each day. Just dont forget to increment the price of upcoming days ticket by the number of tickets bought on current day [this could be done by just maintaining a varialbe "i named it tax"]
i used max_heap to find the ceil(k/m) number of the smallest element from the cost array rather than sorting. I did come up with a proof , but its long and i am lazy to type , if you really need it do tell me.
thank you brother for the given time
I don't think you need BS. just keep track of how many you've taken so far and any $$$ a_i + soFar $$$ will give you the current price at that index. then you can check if we want to take it or not. Just use sorting for minimizing the total cost you get.
Time Complexity: $$$ O(nlogn) $$$
Geothermal orz, is this your first Div1 win? (assuming no FST)
This was not a div 1 round, it was global round. div 1 + div 2, get it ?
For the top participants (who are in div1), their ranking in a div1 versus their ranking in a div1+div2 will be pretty much identical. Thus, a div1+div2 is functionally a div1 for someone at the top of the leaderboard. They don't need to be categorized separately in this case.
If you knew how codeforces rating system works, you'd know that you're completely wrong.
Again, this was not a Div 1 round and Geothermal is yet to win his first Div 1 round.
I know how the rating system works, and I know that for div1 participants at the top of the leaderboard (like top $$$100$$$ or smth), it doesn't matter if the contest is a pure div1 with ~$$$1000$$$ at least candidate masters, or if there are also $$$10\,000$$$ more lower rated participants in the contest. Someone rated $$$3200$$$ or similar is expected to place higher than someone rated $$$1800$$$ or lower with probability nearly equal to $$$1$$$, and assuming the $$$3200$$$ places high, they will have placed higher than (almost all if not) all $$$\le 1800$$$ participants, so their participation in the contest has no significant effect on the rating change of the $$$3200$$$ participant.
If the $$$3200$$$ participant solves no problems, then they will lose more rating in a div1+div2 than they would in a pure div1. But this is not really a realistic situation, so it doesn't matter in practice.
Technically winning a div1+div2 is more difficult than winning a pure div1, since a div1+div2 has more participants. Also, div1+div2's often might also have more good participants than pure div1's, especially when the rounds have prizes.
Also, why are you so keen on the technical definition of "div1"? It doesn't actually matter how a word is technically defined, what matters is how the word is used in practice. And in practice div1 participants use the word "div1" to refer to a Codeforces contest which is rated for participants with no rating upper bound. Div1+div2 falls into this category, so it is called a div1 contest.
If you reply, I probably won't be replying back anymore. I don't want to engage in arguments with people who are overconfident about things they don't understand correctly.
vgtcross orz, can you please share your thought process and how do you make observation and come up with a solution for problem C it will be helpful for other people also.
Problem E
Yeah and it's pretty easy to google
Can you please tell how do you search such problems , I couldn't find it when i googled.
How can i see the solution here... please help, i am not familiar with this Timus Online Judge website.
Nightwish feat. Jonsu — Erämaan Viimeinen big love.
Rammstein — Ausländer also big love, but sadly didn't manage to solve it.
Solved C without proving
How to solve C?
It is obvious that you have to buy tickets in at least p = (k + m — 1) / m days. So, sort a, and take the first $$$p$$$ $$$a_i$$$ to buy. Then you need to decide which day you will buy the least tickets. And I "feel" that it should be the day with max $$$a_i$$$ among those p days, and the index of that day is the smallest as possible (Here is when I can't prove)
"the day with max $$$a_i$$$ among those p days"
I wrote several cases on paper, and it seems to me, that it doesn't matter, which day to choose for least number of tickets, as long as the multiset of numbers of bought tickets is the same (which is of form $$$x, \dots , x, x - 1, \dots , x - 1$$$).
Glad to hear you say that, as I swear it doesn't work with my random approach :v
i did calculations but i cant prove why the order doesn't matter any idea??
after analyzing the problem, you need to find the minimum sum {v[i] * s[i], 1 <= i <= n} + sum {s[i] * sum {s[j], 1 <= j < i}, 1 <= i <= n} (where v[i] is the initial ticket value and s[i] is how many tickets you buy in day i). the second part of the equation is just sum {s[i] * s[j], 1 <= j < i <= n}, which is equal to ((sum {s[i], 1 <= i <= n}) ^ 2 — sum {s[i] ^ 2}) / 2. But (sum {s[i], 1 <= i <= n}) ^ 2 = k ^ 2, and all you need to now is to minimize the sum {v[i] * s[i], 1 <= i <= n} — sum {s[i] ^ 2 / 2, 1 <= i <= n} = sum {- 1 / 2 * s[i] ^ 2 + v[i] * s[i], 1 <= i <= n}. this is how i proved that the order of the elements doesn't matter. after this, is pretty easy to see why the greedy algorithm works.
You have to buy the maximum tickets on the day it has minimum cost, but wait it's not that simple because what you have bought on previous days ( more like will eventually buy in previous days if necessary ) will change the price in the future (i.e. can change today's price.) but we don't know whether I will or have bought anything previously at the point when I am trying to just find the minimum price day. so we must store the minimum price day's index along with how many we buy that day. later sort them according to the index, i.e. the day number as only the days previous to current can change today's price. and from that get the final answer. check this out. sorry for the template code ignore them. :) 255354516
Same, and it feels tougher than D and E, possibly even F if my approach is correct.
Though to be fair, I feel like most people would have guessed the approach to E as well.
What's the proof for E? I guessed two is always possible, but did not want to submit without proof.
No clue at all, I just guessed that if the answer is YES, its always possible by splitting the string into at most 2 parts. I stress tested against a few million small palindromes to convince myself and then submitted.
Tbh I expected E to be much harder and felt like I'd waste my time coding the hashing solution so I stuck on D (which I also was trying to guess), after throwing a guess on C after being stuck on it for an hour. This contest was a nightmare.
Yeah, I expected I would fail at implementing the hashing approach, so I just copied a Manacher's implenentation from cp-algo.
Came up with the same hypothesis but couldn't implement it in time :/
Disclaimer: A simpler proof may exist.
We will show that every string falls into (at least) one of the following categories:
If $$$s$$$ is not a palindrome, one substring works. Now assume $$$s$$$ is palindromic.
If every character in $$$s$$$ is equal, no solution exists. Now assume $$$s$$$ contains at least two distinct characters.
Let $$$a = s_1 = s_n$$$, i.e. $$$a$$$ denotes the first (and last) character of $$$s$$$.
Let $$$b$$$ be the first non-$$$a$$$ character in the string. Now the string must look something like this:
a...ab?...?a. The prefixa...abis not a palindrome. If the suffix?...?ais not a palindrome, we found a good split. Now assume the suffix is a palindrome.Let the position of $$$b$$$ be $$$k$$$. Now we know that $$$s[1, n]$$$ is a palindrome, and $$$s[k+1, n]$$$ is also a palindrome.
This means that for all $$$1 \le i \le n$$$, $$$s_i = s_{n+1-i}$$$. Also, for all $$$k+1 \le i \le n$$$, $$$s_i = s_{n+k+1-i}$$$.
Now take any $$$1 \le i \le n-k$$$. We know that $$$s_i = s_{n+1-i}$$$.
$$$1 \le i \le n-k$$$
$$$-1 \ge -i \ge k-n$$$
$$$n+1-1 \ge n+1-i \ge k+1$$$
$$$n \ge n+1-i \ge k+1$$$
This means that $$$s_{n+1-i}$$$ is inside the palindrome $$$s[k+1, n]$$$. Thus, $$$s_i = s_{n+1-i} = s_{n+k+1-(n+1-i)} = s_{n+k+1-n-1+i} = s_{k+i}$$$.
$$$s_i = s_{i+k}$$$ for all $$$1 \le i \le n-k$$$. Thus, the string $$$s$$$ is just $$$s[1, k]$$$ repeated until the end.
Since the string is a palindrome, it must look like
aaabaaabaaabaaabaaa.There are a few cases left. Let $$$x$$$ denote the number of $$$a$$$ between every $$$b$$$ ($$$x = 3$$$ in the above string). Let $$$y$$$ denote the number of $$$b$$$ in $$$s$$$ ($$$y = 4$$$ in the above string.)
If $$$x = 1$$$, the string looks like
abababababababa. Any substring of odd length is always a palindrome. Since $$$s$$$ has odd length, a split cannot contain only even length substrings. Thus, no solution exists.If $$$y = 1$$$, the string looks like
aaaaaaabaaaaaaa. As the string is a palindrome, partition with one substring doesn't work. The string contains only one $$$b$$$, which can be contained in only one of the substrings. Any split with more than one substring must have a substring with only $$$a$$$, and thus, be palindrme. No solution exists.Otherwise, we can split $$$s$$$ into $$$s[1, k+1]$$$ and $$$s[k+2, n]$$$: split
aaabaaabaaabaaabaaaintoaaabaandaabaaabaaabaaa.$$$s[1, k+1]$$$ isn't a palindrome since the substring has more than one $$$a$$$ ($$$x > 1$$$), followed by a $$$b$$$, followed by an $$$a$$$.
$$$s[k+2, n]$$$ isn't a palindrome, because the substring has at least one $$$b$$$ ($$$y > 1$$$), its prefix has $$$x-1$$$ $$$a$$$'s before the first $$$b$$$, and its suffix has $$$x$$$ $$$a$$$'s after the last $$$b$$$.
I tried so hard in E with dp: dp[i] describe if we can divide in the first i position such that no partition is palindrome. Then dp[i] |= dp[j — 1] for all s[j...i] is not a palindrome. Do you think it is possible to do like that as I can't optimize
Is $$$O(n \log^2(n))$$$ intended to TLE on F?
Basically, is this intended / close to the intended?
Q and Q.P are linked, so same logic as [problem:https://codeforces.me/contest/1918/problem/B], min inversions for Q = [1, 2, ..., n], max inversions for Q = [n, n — 1, ..., 1]. Additionally, any swap that increases the number of inversions in Q either increases the total number of inversions by 2 or keeps it the same.
Since we only increase by +2, if we increase the number of inversions in Q with a consistent algo, we will eventually reach any combined sum of inversions possible in the range.
So binary search on the number of inversions in Q such that combined sum of inversions $$$\geq k$$$. The inversions of Q can be built in the normal manner (place largest value possible while inversions > 0, then place remaining values in ascending order).
I think this solution is wrong (although I haven’t figured out why yet) since I implemented it as well and got wrong answer test 8
edit; the solution is right I forgot to cast to long long
What a "nice" round. :)
literally spent 2 whole hours on problem B received 14 WA rig myself looking for pref sum, segtree, ternary search, could've solved D if not
I'm going to buy a rope today.
Tell me.... i also want
LOL I looked for the exact same things but for C: pref sum, segtree, ternary search. I even have a O((log n)!) solution :skull:
me today. In the case that K is bigger than the index of the first cow with bigger rating that our cow i didn't contemplate that it could be another cow with bigger rating than K between the first cow with rating bigger and K. it cost me 6-7 WA and ruined my contest... very sadge.
I guess I have been to enter an Educational Round.
Got reality checked so hard, spent too much time on C couldn't think of the others!! anyways will take the L.
I regret registering in this contest Out of my stupidity, I'll find myself a rope.
Damn, spent 2 hours trying to figure out why my code gives wrong answer on pretest 2 for problem D(
They really threw me off with max shops as $$$60$$$ and $$$1e18$$$ in the bounds. I spent >2 hrs on the completely wrong bitmask approach.
Missed D, can't think about "no" case :sob:
Proof of C: Need to minimize the expression $$$\sum_{t=1}^{n} (\sum_{i=1}^{t-1} x_i) \cdot x_t + a_t \cdot x_t$$$ subject to $$$0 \leq x_t \leq m$$$ and $$$\sum_{i=1}^{n} x_t = k$$$. By algebraic manipulation, this can be simplified to $$$\frac{k^2}{2} + \frac{\sum a_i^2}{2} - \frac{1}{2} \sum_{t=1}^{n} (x_t-a_t)^2$$$. Note that $$$(x-1)^2+(y+1)^2 \leq x^2+y^2$$$, for any two distinct integers $$$x>y$$$. Thus greedy solution works. Sort array $$$a$$$ and choose the maximum possible quantity in each step.
I think everybody pretty much did "Proof by AC" for this problem lol.
I did C greedily purely based on intuition and made a implementation error, then spent a hour and made 2 WAs thinking it's a logical error :/
2 solves for Problem I. I believe I was able to derive a solution that would run in O(k*E*log(E)) which would be 2 billion iterations in worse case, so too slow. Really curious what the approach was to that one. If k <= 10^6, it is a much easier problem.
I am so close to solving F. I figured out how to determine YES or NO, but I don't know how to construct the answer in less than $$$\mathcal{O}(n^2)$$$ time. Could someone give me a hint? Thanks.
How do you construct a permutation of size $$$n$$$ with exactly $$$k$$$ inversions? Needed algorithm is very similar
I will try to fill in all integers from $$$1$$$ to $$$n$$$. I will maintain a variable
posstarting from $$$n$$$.If we put the current integer into
posthen the number of inversions will be increased by(pos - 1)since all blanks beforeposwill be filled with integers larger than the current one. If(pos - 1)is too large then just decreaseposand try again.The problem is, in this specific scenario the number of increased inversions is kind of "continuous". You can always find a position to fill in. However in problem F it is not the case.
Ok, thats another way to construct a permutation with exact number of inversions, idk maybe its possible to solve with it too? But what I did: I iterate on positions from $$$1$$$ to $$$n$$$ (not integer) and see what number do I place on this position. It's either minimum available number or maximum available number until you are in a spot when you can construct all remaining suffix easily
Nice set of problems, thanks!
A is harder than D
Summary of the contest
Still love the contest though lol, I think the problems are nice
What is the idea behind D?
If n == k, then you can only have one stall with price = 1, and k > n is trivial.
Now, you can observe that for k <= ceil(n / 2), you can always have two stalls, with the first having price n — k + 1 and the second having price 1. This lets you construct an answer for all k <= ceil(n / 2).
Now, if k doesn't lie in either of the ranges, i.e. k > ceil(n/2) and k != n, then you can't construct an answer. Since you k < n, so you must buy k/x jewels from the first stand, where x >= 2, which leaves you with less than floor(n / 2) coins and at least one jewel and now you can buy at max floor(n/2) jewels, i.e. you have at max floor(n/2) + 1 jewels, but as k > ceil(n/2), you can never reach your goal
Wow! Thanks a lot!
how you are left with n/2 coins if you take amount n and first stand x as 2, coins remaining would be n % 2.. ?
I wrote that x >= 2, and since k < n & k > ceil(n/2), what's the maximum reminder you can get for k in this range upon division by n/x(or k/x since you must buy at least one jewel) for x >= 2? It is floor(n/2) when k = n — 1, and x = ceil(n/2).
Yet another round full of constructive problems. My brain has already crashed.
Nice problems, surely deserves a Global Round!
Though G is somewhat technical (We can use this method for all problems of this kind), I enjoyed an unexpected cubic formula.
Yeah honestly I'm still tripping myself over that comment to this day. What does he mean by "for all problems of this kind"? From my understanding maybe he means if we describe state $$$S$$$ as a sequence $$$(s_{1..n})$$$ then we can just use the potential function trick. But surely there's gotta be some additional conditions on the transitions $$$S \rightarrow S'$$$ right? How can we be sure that solving for potential functions actually gives a solution when there are a lot more equations than variables?
In fact I don't perfectly understand "all problems of this kind", either, but I interpret it as: we should try to construct a potential function when we see a problem with a Markov process whose states are points in high dimensional space but the transitions are "locally". From my experience it is almost(?) always the case that $$$\sum_i s_i$$$ is constant.
Also, there is a Japanese editorial which tries to find a nice sufficient condition for this method to be useful.
My solution for problem E ( But I am not sure whether it'll pass the system tests ):
I had an intuition that if the answer is yes, then you can divide it in one prefix and one suffix. Hence, I picked a random index 60 times, and checked whether a division of a prefix and suffix bordering at that index gives two non-palindromes.
Code
It's actually a Battle Cow. Spend more then 2 hour+.
The greatest contest i have ever participated.The examples are so strong that I could pass examples even when I misread the statements.Really love it!
btw,you see D $$$k<=60$$$,in fact $$$k\le 2$$$; you see E $$$k\le n$$$,in fact $$$k \le 2$$$.So cool,isn't it?
Ough, that's big number of WAs. When I am quite sure that my solution is correct, then after the first WA I write a stress, even for first problems.
So cool, isn't it?— yes, I don't see a problem here.In fact,each time I submit,I found a new problem.Passing examples only meant I wrote a compiled code at that night.That's really an awful experience.
I don't think it's correct to hide the constraints of constructing steps in this way,which makes this problem's discrimination quite randomized. At least I hate it.
Wait till you get to know of the old contests where writing compiled code = passing pretests.
I dont see any issue with weak samples and wish more authors had weak samples. Its upto you to ensure that your code is right, samples imo should only be for verifying that you understood the problem right.
I do make an exception for problems where the implementation might be difficult/tricky however, but most of cf problems arent like that, and you get wa because you are guessed.
Personally, when i guess (and I do occasionally), i dont blame my skill issue on authors. Maybe try proving? I was completely sure of A — E when submitting
Well,I could say that I was not guessing with problem BCE that night(Eventually I passed them).I just wrote,and got WA,and found the examples useless at all.
That's also other reasons:I misread C;I solved E in a very difficult way at first; I thought about problem B with a incorrect proof. But all of these couldn't be checked by examples,and I was not patient enough,finally led to a bad result.Unlucky,but on another hand coz I'm still too weak.I posted this text because I was very unhappy and my head was totally a mess at that time,so maybe it's a bit funny.
IMO,I think examples are used to check our ideas and common situations.If you don't want to give samples make sense,I think giving no samples could be a better choice(show the attitude to the contestants,but Codeforces seems not to allow this)
"IMO,I think examples are used to check our ideas and common situations.If you don't want to give samples make sense,I think giving no samples could be a better choice(show the attitude to the contestants,but Codeforces seems not to allow this)"
no i want samples to be there, but on problems where people will make lots of wrong guesses, i support making them weak on purpose so that guesses can be punished. Not putting any samples is too much and will lead to even more people just misunderstanding the problem.
We actually tried pretty hard to make the samples useful. For example, B's samples highlighted the harder of the two cases in the intended solution, D's samples showed that it is impossible to solve when $$$k > \lceil n / 2 \rceil$$$, and for E we showed that a palindromic string can indeed be partitioned into non-palindromic strings.
I believe luck was just not on your side on that day :( We didn't try to manipulate the samples in any way that obstructs people, but constructing samples that counter misreading is really hard because there are 10 million ways one can misread a problem ...
I could only see that I was very unlucky that night...And all in all,the problems are interesting and thanks for your effort!
Hmm, for last several months this is the third problem which requires checking if substring is a palindrome using hashes.
1951E - No Palindromes
1943B - Non-Palindromic Substring
ABC331F — Palindrome Query
"Requires" is too strong of a word. 1943B - Non-Palindromic Substring can be solved without hashing, and my solution to 1951E - No Palindromes even uses the naive algorithm for checking if a string is a palindrome.
My solution to E today was casework.
I split into segments of consecutive characters. If even number of segments, we can just pair segment[i] to segment[i + 1] and we're done.
Odd number of segments: if there is a position where segment[i] != segment[i + 2], we can make a segment starting from i + 1 and extend it equally as much as possible to both left and right. After that, there might be an even number of segments left which we can pair off just like above.
Now we have alternating segments. We can look for a segment[i] where i is odd (0 indexed). If the length of segment[i] >= 2, we can break into two distinct segments, and then pair up like the even case.
If we still have not found anything, we can look for a segment[i] where i is even and i is not the first or last segment. If the length is >= 2, then we can s into two strings [0, x] and [x + 1, n — 1] where s is somewhere in segment[i] (basically split somwhere in segment[i]).
Now the only thing we should have left is an odd number of alternating segments of length 1. We can prove that this is impossible to split because after splitting, there is guaranteed to be at least one odd length segment but this will always be a palindrome.
Submission: https://codeforces.me/contest/1951/submission/255365657
Unfortunately, I did not finish this during the contest qwq.
Clean code for C:
any proof why greedy works here?
Basically, when you buy x of one ticket all the other tickets prices' will get raised by x. What this means is that you will add this x to your answer, and the order of when you add doesn't matter. So, we can greedily pick from the smallest ones, raise the prices, and continue, and this will yield the same answer as if you picked them in order. I hope that makes sense.
What could be the ratings of C and D??
Finally...finally!!!!!!!!!TAT
congrats GM it is
thx bro good luck :)
CM finally?
A-E probably worst set i've done since traktor round. Maybe it gets better after...
Does anyone know why the first submission for E is skipped?
Because you resubmitted.
But the time of the accepted submission was recorded as 01:04:19. That shouldn't happen, right?
That is intended.
I think if you resubmit a correct solution the latest one is considered
Is there any blog/page on CF that documents all such rules?
The later on counts.
How to D?
here
Is there a solution for D using $$$O(\log V)$$$ stalls? Otherwise what's the purpose for setting the limit to $$$60$$$?
Mainly to subvert guessing, but also
The subversion did worked, to nearly all of the fellows in my dormitory.
The problem would've been way easier with a limit of $$$2$$$ imo.
$$$60$$$ did make me wonder about $$$O(logV)$$$ solutions at first. That confusion was probably intended.
You can see that $$$60$$$ is the maximum number of stalls that can actually be used (by the standard 'mod operator at least halves' argument) so effectively it is setting no limit.
I guess
Probably, these authors wanted to have a hand in creating April Fools Contest too
Thanks for amazing comeback of GR!
How to came up with problem C? It has very cute conclusion though it has very natural settings.
Glad you liked it!
Here's the lore for the problem:
One day I randomly thought about problem A from this legendary TMW video and wondered "how could I make this problem more interesting"? Then I came up with adding the tax (note that the original only has $$$m=1$$$ so adding the tax only increases the answer by $$$\frac{k(k+1)}{2}$$$, the greedy obviously still works). Then I realized allowing to buy $$$m$$$ items per day doesn't change the strategy as well! (I then tried to have different limit for different days but it obviously didn't work)
D felt like an april fools problem, the main difficulty is figuring out which trick the setters are trying to pull (like putting s <= 60 and not putting n = k in the samples)
yeah took me a hour for that
Thanks for the round! Though Im most likely biased I think all problems till F are very nice (and no idea about GHI) :)
May there be no constructive problems in heaven.
yo koruni top 1 sever vn i love u <3
I feel like my experience was quite unfortunate:
I submitted D, thought I had correct proof, WA2'd. Realized my proof was incorrect, so tried to prove for a while. Couldn't come up with a counterexample, so brute forced n and k up to 1000 and that didn't cause a counterexample. Gave up on proving, and realized that my original solution was correct if I printed long longs instead of ints, so wasted like 30mins.
E: Guessing the solution is really obvious, but I also tried to prove. Gave up on proving after a while and AC'd.
F: Really easy and free, since it's a constructive there isn't anything to prove, but wrote a slightly incorrect solution because I wasted too much time trying to prove earlier problems.
C was very cool!
I got TLE #47 on problem E because wanted to make sure that no solution of length 3 exists. My solution did approximately
50Npalindrome checks with hashes and shouldn't fail. CF servers are very bad and it costed me a lot of score :(After the contest I found out that
43Nchecks passed in almost 2 seconds. Codeforces servers are very slow, unfortunately. Where can I found the exact hardware description of CF servers? cc: MikeMirzayanovYour code ran twice as fast on C++20 64-bit 255374818
Replacing
endlwith\nalso make it AC on C++17 32-bit 255375660It's not really the server's fault. The constraints here are $$$10^6$$$ (a bit higher than usual), and you're doing $$$50N$$$ checks with double hashing and checking both sides, with double modulo application for each computation. You're essentially doing $$$400N$$$ mod operations. Now if it were addition or bit operations, expecting $$$4*10^8$$$ operations in 2 seconds is reasonable, but that many MOD operations are quite slow and I'd be surprised if it's much faster for you locally.
After seeing the solutions of top rankers, I wanna kill myself.. Problems were so simple and elegant ,.,..
Auto comment: topic has been updated by Kuroni (previous revision, new revision, compare).
D won with me. GG
Can I ask what were your expectations when you set Problem E at that position? Were you thinking that many people would guess or rather thought, people would not guess since it is E, it can't be that easy. Just curious? (I wish I submitted D:)
First Div. 1 win! The second hour of this contest (solving FGH in a total of an hour after taking 52m to solve A-E) was probably one of my best-ever comebacks, up there with solving CD in the last ten minutes of Round 706 and solving five problems with my team in the fourth hour of NAC22. Very memorable contest; thanks to the authors!
Feedback on the tasks: A: Good enough as the easy problem. Samples are weak and didn't include the exactly two 1's case, which led me to take an unfortunate early penalty.
B: Good problem. It took me a while to really wrap my head around the setup, but once I did the solution works out pretty nicely.
C: Nice problem; the solution isn't immediately obvious but is relatively easy to see once you write out the price function formally.
D: Fine problem. A bit more focus on guessing than I'd like, but in fairnessonce you just try a few cases I think the approach is pretty well motivated.
E: Not my favorite problem, mostly because I suspect from post-contest discussions that most people who implemented the easiest solution (checking if any one-split approach works) didn't prove that their strategy was correct. There's also an alternative casework solution (which I implemented) where validity is easy to prove but implementation is much longer.
F: Nice problem; permutation compositions are always intimidating, but in this case looking at the number of inversions each pair (i, j) will contribute makes it a lot more clear what to do. Figuring out how to construct the permutation took me a few more minutes than I'd have liked, since the ideas I had seemed infeasible without some kind of fancy data structure, but then I realized that the construction always follows a simple pattern, after which the implementation was pretty straightforward (especially because the only data structure required is OST).
G: Very good problem--a bit on the standard end (especially for any contestants preparing for quant trading interviews?), but evidently it wasn't well-known to many participants. I hadn't seen this exact setup before, but I had seen enough very similar problems that I immediately knew how to find the probability that each marble is the last one standing and that I needed to compute the expected time until each marble is the only one left, conditional on that marble being the last one. The idea is nice enough that I really liked the problem, conditional on most contestants not having seen it before.
H: Good problem, but strangely easy for its position imo. I might have gotten a little lucky, but it felt like the first thing I tried basically worked right away. I think this is easier than G (and one could argue that the difference in solve counts is just the leaderboard effect).
F and G were my favorite problems from the round. I had to spend a bit more time on the easy problems than I would have liked due to doing casework on E and taking penalties on A/B (though both were really my fault for some pretty silly implementation errors), but the back half of the contest was very nice. Thanks for the round!
As an aside: after this month I'm starting a new job, and I expect to have significantly less time to train. Given that I've accomplished the bulk of what I've set out to do on CF, I think there's a pretty good chance I retire from rated contests at least for the time being. That being the case, I'm hoping to continue to engage with the community by regularly testing rounds, so if you're an author looking for testers for your upcoming contest, please feel free to DM me!
Geothermal orz
Congratulations! Actual GIGACHAD Geothermal
Nice round. Thanks a lot MofK Kuroni and all testers.
I got so many WA in B.I even use force and try to solve it but in vain.I want to swap(0..n,mycow) and calc how many matches can my cow win, and calc its max, finnaly I swap it again to recover cowList.But I got VERRRRRRRRRY many WA .How can I improve it. :(
I'm very unsatisfied with this "unbelievable" round
3 constructions,2 of them use k < 3 conclusion
guess guess and guess
I can't learn anything except guess from the "global" round
I'll DOWNVOTE it
My thoughts exactly. I guessed C, D and E and didn't get AC on neither D nor E because I was scared to write those guesses. Judging from the comments majority of people who solved them did not even prove their solutions to either of these problems which just makes the contest experience awful.
maybe try proving?
well D is just plain bad even if the guessing is really easy to prove
would be far better if the number of stalls are $$$\leq 2$$$ (although it may not be D anymore)
I mean, we can argue about quailty of problem D, because its plain math, and someone dont like it in CP contests, sure
would be far better if the number of stalls are $$$\leq 2$$$
However, I really dont understand this take. I think problem would be worse? Because with $$$\leq 60$$$ I just solved problem the way it is, in the end just noticed that it takes $$$2$$$ at most, ok fine, go next. Like, I never guessed "hmm maybe $$$2$$$ is always enough?" while solving problem, and I want to believe that most participants didnt too? Because this really seems like a completely desperate out-of-nowhere guess without motivation behind it?
If problem had $$$\leq 2$$$ in statement, that would be very weird constant which would attract attention in the first place and completely changed the line of solving a problem, making it worse
Also $$$60$$$ is a maximum theoretical limit since $$$n \mod x \leq \frac{n}{2}$$$ for all positive $$$n, x$$$, so this exact constraint seems motivated
yeah, i kinda agree with your point. now that i look at it, the $$$\leq 60$$$ constraint is very much reasonable, especially seeing that the actual mechanism of how Alice spend the coins resembles the modulo operation for coins and division operation for jewels. i'm probably just mad about this constraint because of how it deceived me into thinking about bitmasks solution before even realising it's just the nature of modulo itself. still, D is overall very weird in my opinion, probably because the solution involves some guessing.
anyways, good point. upvoted :>
I Just want to share my sadness:
TLE on testcase 46: https://codeforces.me/contest/1951/submission/255345491
AC: https://codeforces.me/contest/1951/submission/255365135
One code IS in C++17, while the other one is in C++20. I would get master with this ac :(
Same here: https://codeforces.me/blog/entry/127943#comment-1137290 But you shared wrong link to the second submission. I think something is wrong with C++17 performance, because my solution (https://codeforces.me/contest/1951/submission/255350123) should barely exceed 1 second, definitely shouldn't even be close to 2 seconds. cc: MikeMirzayanov
If in not mistaken, i think c++20 runs long long int faster than c++17, but idk why the pretests dont have a case that it is a bunch of 'l', but it is what it is
I guess this is due to the difference between 32-bit and 64-bit --
long longis slow on 32-bit architecture.It is slower, but why is it so slow? At least I think there must be hardware description of CF servers somewhere.
A
long longdoes not fit in a machine register, so every operation onlong longs expands to a few machine instructions (where one instruction is enough for 64-bit) -- I think this is the primary reason of slowness. Also IA-32 has very few general purpose registers, which makes values are read from or written to memory more often.Thanks for the round, prove of C is beautiful, and I learn something today :)
Im finally Expert!!! Thank you Codeforces!
I've just upsolved problem E, can't believe it's AC, wow! I have no idea why E seems a lot easier than C and D.
255365140
Thank you guys for an amazing contest!
Got the wrong answer on D because of Python. Python does not divide bigger numbers correctly. :(
from math import ceil from decimal import Decimal
def solve(): n, k = map(int, input().split())
if k > n: print("NO") return elif k == n: print("YES") print(1) print(1) elif k > ceil(Decimal(n / 2)): print("NO") else: print("YES") print(2) print(n - k + 1, 1)for t in range(int(input())): solve()
This is the code on which I got the wrong answer. Dont want anything but wanted to share my misery.
May be ceil function is not working, try by replacing it.
This works
from math import ceil from decimal import Decimal
def solve(): n, k = map(int, input().split())
if k > n: print("NO") return elif k == n: print("YES") print(1) print(1) elif (k > n // 2 and n % 2 == 0) or (k > n // 2 + 1 and n % 2 == 1): print("NO") else: print("YES") print(2) print(n - k + 1, 1)for t in range(int(input())): solve()
So your issue resolved?
yes
Guessforces
Felt the samples very pretty weak. Had wrong attempt in almost every question :(
Really good contest. D was really close to be my first AC D in div1+2. Thanks for the authors! Hope to see other contests of yours
Why everyone finds D ques difficult?
Is the song from Problem D on Spotify? I found this https://open.spotify.com/track/1TVFphEyfjzEIir70656d4?si=68360585a1254339 but this is without Jonsu :/
TaklaOi orz?
Thank you guys for an amazing contest!
intuitionforces
When you thought you could solve the problem F without a stress test :'(
And also in my opinion H was a very easy problem for the position H.
G is absolutely beautiful!
hi everyone, mwah. i love yall. happy contest day! wish you good luck. mwah. (please downvote me)
Food and water is basic right really
"Xin chào" is similar to Chinese pinyin（
haha funny picture
My solution to 3rd one got skipped, but I did not cheat. I do have conclusive evidence, but my source for inspiration was this GFG link(https://www.geeksforgeeks.org/maximize-number-of-elements-from-array-with-sum-at-most-k/)
Hi, even i got the mail but for problem B mentioning the people i don't even know. What should be done in this situation because the logic was quiet very basic.
Please tell something what can be done
Hello everyone, I got a mail saying my solution is copied. Many ids are mentioned which i don't even know. I don't have any idea how it is same because i wrote it myself and also the logic was quiet very basic. I don't know now what to do in such situation please if anyone could help
my solution is skipped because it match with one person 3rd question was very simple so there is possibilities that many people have same approach to solve may be solution is similar pls undersand
Who gets t-shirts?