Salam, Codeforces!
After many years, we are excited and pleased to announce that Codeforces Global Round 31 (Div. 1 + Div. 2) will be held on Dec/19/2025 17:35 (Moscow time). Thanks to XTX Markets for supporting the initiative! In 2025, we held 3 such rounds, and the series results will take into account the best 2 participations out of 3. 
Codeforces Global Round 31 marks the third round in the 2025 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 3-round series in 2025:
- 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 2 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 2025!
The problems for this round were prepared by MohammadParsaElahimanesh, Shayan, and me.
We would like to express our sincere thanks to:
- Akulyat for coordinating the round and providing valuable feedback throughout the process;
- the testers: N_z__, A_G, YuukiS, amirhoseinfar1385, ArshiaDadras, Millad, EyadBT, aimoon, michao, JeffreyLC, s.seraj.shafie, AminAnv1, abramazani, MRasool, Radman_, Hooded_Hood, tilnoene, PMiguelez, chromate00, M.H.N, CLown1331, and dina_saba for their time and effort in testing the problems;
- MikeMirzayanov and KAN for creating and maintaining the great platforms Codeforces and Polygon.
The round will feature 8 + 2 problems, and you will have 2.5 hours to solve them.
Score Distribution: $$$500 - 750 - 1500 - 1750 - 2000 - (2500 - 750) - 2750 - (3000 + 3000)$$$
Good Luck & Have Fun!
Editorial is out.
Congratulations to the winners!
As an author, I’m happy to have another global round. Hope you have fun and enjoy it!
Problem C was a nightmare for me
Problem C was too good man!
problem c surely have a lot to teach ...lovely problem.
show some mercy on us bro, problem 'C' was Litttt!!
ofc you are happy watching me being tortured by Problem C.
Frrr
Lol
we both stuck after solving 2. Lolll
yeah, these XOR problems are kinda difficult
i couldn't even solve 2.
you are right
real.
Are you a time traveler from the future? My stress tester for C is literally screaming, and I still have no clue what’s wrong.
I just posted it for fun but I didn't thought that gonna happen real lol.
Bro's AprilFoolsClairvoyant in disguise
True, dude
Best of luck ppl! hope we all do well
Hope to increase my rating, and become expert.
Congratulations
Thanks
We are gonna have an excellent experience, In Sha Allah
I think it is also going to be Round 1 for Pakistan IOI 2026 Team Selection.
Indeed
Why tf was an OI selection round a speedforces round especially when Shayan teaches Pakistani IOI team members.
Please have the visualizer. It helped me solve A and B in Global Round 29.
I won't be participating as I am just a beginner but good luck to all the participants. Hope I become good enough to participate someday.
I can solve problems A and B, but it takes a lot of time. How can I solve them faster?
It is easy; just solve more problems around your rating, and your mind will work faster to solve the problems.
Yet another Persian contest ;) The authors are super strong =)
Thanks a lot <3 I hope we meet your expectations …
I’m happy to have another global round. Hope you have fun and enjoy it!
Silence cheater!
In this blog what is meant by +2 in (8+2) problems can anyone tell? will they be unlocked for those who will solve all 8 problems
8 problems, 2 subtasks
ChatGPT says 8+2 = 9, that means there'll be 9 problems.
Hmmm... That's why ChatGPT has a gold-medal level performance in IMO.
Hoping to get Specialist in this round.
damn congratulations man , you solved D !!!
Thanks bro
Hope to increase my rating, and stay pupil.
i will try my best to participate , busy nowadays because of my college exams !!
8+2 problem so 15 min for every problem , need to unlock ultra instinct for that..
So when can we get the score distribution?
hoping all of us get good score, insha allah
I think duration of the contest must be increased to 3 hours because there are 10 problems.
Previously 9 problems contest were 3 hours long.
My opinion: Duration should be increased.
UPD : My new opinion after problem C :This contest must be of 1.5 hour.
i hope next time will be div4
First time i am gonna give a contest authored by Shayan, big fan of him. Super Excited and i must say contests written by Iranian authors are really nice.
As a tester, I'm happy to be a tester for the first time!
Same here!
Shayan ,my favourite.
first content after a long break,let's go!!!! edit:Taking break was a bad idea :((
good luck
queue feels a bit slow for me!!!
I don't like this round!!!!
what was C problem
How the hell did D get bombed late
26
26
26
26
26
Problem C
Wrong answer on pretest 2
wrong answer on C pretest 2..
The ratio of the number of accepted solutions to the number of submissions in C is insane
Reads A: Ez
Reads B: Ez
Reads C: Ez
Wrong answer on pretest 2
(Thinks for a while)
Wrong answer on pretest 2
Wrong answer on pretest 2
Wrong answer on pretest 2
Wrong answer on pretest 2
Rage quit
Same yaar I mean wth
same, I'm going crazy
same!
REAL. I spoke too soon with my friends went broke. Btw can anyone tell me what is wrong in C: My submission: 354177141
for odd number it is not optimal to include 1 and n^1 because we can have maximum sum by having like this
lets say i have a number in bit
11000100111
now if k is odd we can print n k times
or else
for k-2 numbers are n and then the last two will be a and b where the n*(k-2) + a + b should be maximum so my idea is to set the 2 MSB to 0 in the n and then set all the bits before the 2 MSB so the a will be
a = 10111111111 now to xor the a to get n we have b like this
b = 01111011000
so finally we have to do like this but still i got wrong on pretest 2
mine was super similar to ; 1st msb or 1 to a ; and for second msb 1 ; set 1 to b ; after that for every 1 assign it to a ; and for every 0 assign 1 to both ?? why did it fail i am crashing out it was supposed to be my first "c" i made it till that in first 30 min then i literally couldnt think what was going wrong
Same literally same
i crashed out fr
A good thing to do after you get WA, is to stresstest: - make a (python) script that generates very small testcases - make the dumbest possible brute force - make a script that generates the test cases, runs the brute force and your code, and then compares the outputs
the 3rd point you can already do before the contest. This saves a lot of time usually, although it is a bit tricky to find a good testcase for problem C. Once you have a small testcase where your solution does not work, it is easy to see why it does not work. That way, you don't get more than 1 WA on a problem
To be fair, most bruteforce implementations for this problem would be very slow (I mean, I was too lazy to think of anything smarter than O(n^{k — 1}) [actually, I was sooo lazy, that I made an O(n^k) bruteforce instead)) and, interestingly enough, there are a quite a bit of small cases that pass using even greedy solutions. So, because of the first point I decided to not write a generator and just test by hand (as the number of small cases is, well, small) and because of point 2 I got more and more convinced that maybe it was some kind of strange edge case that rarely every appeared or an implementation detail. Luckily, I found a simple case with just n=86 and k=4 after some trial and error...
This is what I did during the contest after getting one WA.
Runs in about 1 second on my pypy jupyter notebook.
wth I think I got the optimal strategy for c but it stills fails at pretest 2...Can anybody tell me what's wrong here : submission
When $$$n=30, k=4$$$, you code outputs
30 30 15 17which sums to 92. But the solution15 23 27 29exists which sums to 94.My most terrifying dreams are far more friendly than this round. Maybe next time I should just go sleeping.
you passed 2nd test.
Absolutely cucked by $$$C$$$ and $$$D$$$.
Third one cooked me
C cooked
F is somehow boring and takes much time to implement. Also, given that F1 and F2 are relatively independent, is the score for F2 a bit low?
Where is the edition?
Wow , what a contest
can someone help me with the issue in this code for C. my code submission
any hint for c
I wasn't sure at first and failed quite a few times. But after checking the submissions and noticing that the memory usage for AC code was relatively high, I realized I should go with DP instead of a space O(1) greedy approach. T-T
Bro can someone pls explain C to me, wtf happened?
I think odd case was self explanatory. In even case we basically have to divide n into a and b such that a&b is maximized, a<=n, b<=n and a^b = n. My strategy was to make a as (1<<secondsetbit+1) — 1 and b as n^a. I thought I was right but it still failed...
Tried the same
So, for k=odd case, we just set all values to n, which is the maximum possible sum we can get. k=even is the tricky part and from here on, we will talk about just that.
One case that i was continuously trying was to set (k-2) elements to n and choose the remaining two elements (say a and b) such that a^b=n and a+b is maximum. What we can observe is , say n is 1010011 (in binary), Now we need to construct a and b. The bits which are set in n will obviously be set in only one of those. Now what we can do is we can set the msb in a and the next 1 which comes in b. So currently both a and b have missed a large bit and thus from here on whenever a bit=0 comes, we can just set that bit to be 1 in both a and b. For ex, for the above mentioned n a=1001100 and b=0011111. after the second set bit, you can set each 1 in any one of a or b.
But this was not working (Test 2 (the goat)). Then what i saw was we can extend the same idea to all the numbers in pairs. See here after we get 2 set bits, we can just set all 0's to be 1 in two numbers so they can cancel out. Similarly when we have got 4 set bits, we can do the same for 4 different numbers and so on..
You can refer to my code i feel like that would make it much clearer and try trp pen down what we did for 2 numbers and you would observe it once you write 354210416
this c made me wanna harm myself ;
what the fk is wrong in my code to fail pt 2 ;
no please don't harm urself.. this is the time to become keyboard warrior !!
got cooked by C a bit but finally got it !! ...
please tell idea for D .. so many people solved it
for C actually I wrote slow brute force to find failing cases and then observed what is actually happening and then tried to code it.. saved by the fact that
pretest = final test... hope editorial have some elegant solution.I found D much easier then C, you pretty much just greedily merge the points asap, when you can you store minimum and maximum point the Cycle can be, this allows to check the next one too and so on.
ok thanks... I was thinking something greedy but didn't think about that min max thing .. nice !! will try to upsolve
what case u found first ? just interested to know ..
n=46 k=4... code for my brute force is at the bottom 354191460
I don't think it is wise to make a div2C sample super weak....
What was that $$$C$$$ :(
Here are my observations, I don't know why it didn't work in the end, can anyone help?
firstly, I thought of making every element equals to $$$n$$$ if $$$k$$$ is odd (obviously)
for the case of $$$k$$$ is even, I thought first of making all the elements equals to $$$n$$$ except the last one equals to $$$0$$$
then, I found that I can change the last two number from $$$n$$$ and $$$0$$$ to another two numbers $$$x$$$ and $$$y$$$ where $$$x + y \ge n$$$ and $$$x \oplus y = n$$$
what is wrong with this idea :(
30 4 Can be a counterexample because the maximum sum is 29, 27, 23, 15 :(
damn
Consider the case where n = 21 and k = 6. According to your solution, the sum is 105, but the sum 109 is achievable when the array a = {21, 21, 21, 21, 18, 7}.
I had the exact same reasoning sequence, implemented it twice and still WA on 2, no idea. Can any bright mind pleeeease enlighten us
can someone explain ... how the heck this "C" will be solved ?
too weak sample
Why my C submission fails ? https://mirror.codeforces.com/contest/2180/submission/354216942
If k is odd, then it is trivial to print n (k times)
if k is even, then you find the pair with max sum and xor equal to n, and the rest of (k-2) elements is n
for n = 92, k = 4, the optimal solution should be [91 ,31,79,87] , not [92 ,92, X,X]
My worst performance in contest ever. I submited B and queue was taking so long that I was just trying to solve and didn't see that my B didn't passed. After stress testing still have no clue what is wrong with my C solution tho
Literally same happened to me
D + E + F <<< C
small hint for E please ! .. although I couldn't attempt it.. but question was cool
The problem C has a big big trap, which trap me for over an hour. when k is even, you cannot just modify the last two numbers and keep the others as n.
Counter example: n = 92, k = 4, the optimal solution should be [31,79,87,91]
bruhhh, then what was i supposed to do? kms??
How would it be solved then?
what did the pretest 2 for b include that even though the edge cases were giving correct answers but that particular pretest doesnt smh
what was wrong on pretest 2 for q3 https://mirror.codeforces.com/contest/2180/submission/354216827
How to fix second number in c, first number we could have brute forced all powers 2 till 1e9 but what about other number,how could we find that optimal pair from all possibilities
What the fuck is C
No tester considers C is adhoc???
We hate the Wrong answer on pretest 2 we met in C. (n=30, k=4 answer is 29 27 23 15)
Problem itselves are good, but this problemset with 2.5h is too hardcore (even 3h is short for me)...
Here is a counter-example for problem B, if you compared the current word to the answer you're building: ans="ab", s="aba". You would set the current answer to "ababa" since "ab" < "aba", but "abaab" is smaller than "ababa".
Thanks!
can anyone explain C , what is the solution if k is even
If k=4 and n=30, the answer is 15 23 27 29, not 9 23 30 30. From there you can find out how to solve it (hint: when n & (1 << i) is 0, you can set the bit to 1 for pairs, instead of 0).
so we should have known that for specific even k, only in this case simple logic for even k fails?
K=4, N = 30, 46, 54, 58, 60, 61, 62... is so many Counter-example. The key is that [n]*(k-2)+[a,b] may not be the maximum.
No, it's not a specific n or k, this is just the shortest even k > 2 for which modifying only two numbers doesn't work. The larger the number of bits set to 1 for n, the more numbers will be modified in the answer.
Honestly I did a local bruteforce to find it out.
For problem C, in case of even k, I tried to maximize a&b for a and b where a⊕b = n, relying on identity a+b = a⊕b + 2(a&b), and construced a by setting second significant bit of n to 0, and all consqeuent to 1. What is the flaw of my logic?
[submission:https://mirror.codeforces.com/contest/2180/submission/354171451]
ask chatgpt, but i dont guarantee he will answer you, cause the problem is trash
maximizing a1 + a2 + ... an is not the same as maximizing an-1 + an by setting the rest to n. Counter example is 30(29 27 23 15 is better than 30 30 _ _)
Thanks, it was helpful.
10 min solved E 2h did not solve C ^_^
Same struggle here.
please give hint for E
Hint 1: Focus on the Most Significant Different Bit (The Split) Hint 2: The Interval is Forced to Split Hint 3: When the k-th bit of x is 0 (Internal Permutation) Hint 4: When the k-th bit of x is 1 (Global Swap)
ok, thanks a lot !!!
What are the cycle lengths in the permutation you create with any $$$X$$$? What sort of cycles appear in this permutation?
Poor samples on CDE is wild! Also why does greedy work in D?
I guess that even if the current circle is invalid, it would only make the answer smaller by 1. If we adjust the previous circles, it would at most increase the answer by 1, but it would also reduce the range of the current circle. Therefore, the greedy approach is correct
So it's just a boring greedy problem and the only difficult part is to not mess up the signs and stuff... I guess I should've implemented the greedy earlier instead of trying to find some beautiful patters
I know that it's unpleasant and etc., etc. But samples are not supposed to be really good? I can understand similar issue with pretests, but blaming the samples is a bit over the top.
I'm not blaming the samples, I'm blaming the inconsistency of them being either really good or super non-informative. It's common practise nowadays to make them good, and then suddenly on a div 1 they're bad. That's what I didn't like
im done with my life
Why give strong samples when participants can make their own through a visualizer :D
You completely ruined C, a genuinely good problem, by making horrible samples that try to trick you.
Otherwise C would have been a genuinely good problem, satisfying to solve, and even with REAL SAMPLES would not have given away too much.
Do better.
if anyone is wondering solution is this
If odd, ofc its just k n's
If even, note firstly that it is optimal to have k-1 bits on for each on bit, with one off
ok then what? well once a bit in a number is off, lets call it free, because any combination of lower bits wont > n
if we free some indices, then on lower bits off in n, for these indices, we can do whatever with the bits, so if at this index there is some number >=2, we can set its bits on for the largest even prefix such that those indices have been freed
legend c TAT
I'm getting this warning when compiling my code for F1:
The warning disappears when I compile with sanitisers. Both are
-O2, GCC 15.2.1, standard C++17, no other special flags aside from enabling many warnings; the only difference is flags-fsanitize=address -fsanitize=undefined -g3 -fverbose-asm. It doesn't seem to affect anything, compiler bug causing it to be emitted?(Also fun fact: I almost couldn't make my last minute submit for this problem because train net is train net.)
The quality of the contest although it's a global round is insane
so weak example
For me C is 2 hard especially compared to E.
I must be so noob that print (k-2) n...
C is tricky, F is boring, bad luck in this round :(
placing top 1500 for fast AB (high expert), placing 10,000th (newbie) for slow AB.
Stupid as hell
too weak sample in this round :(
I think that:
A is too boring
B is awesome
C is tricky in a cool way!
D is average
E is cool
F1 and F2 are bad because the solution is trivial, and you just have to spend a long time implementing it
But in general there is nothing super wrong with the round so idk why so many downvotes. Thank you for the problems!
Greedies in C and D aren't the most obvious ones and many people tried the most obvious ones. As many people do proof by intuition+samples and are usually rewarded for that, this threw many people off. Also the queue problem in the beginning which added a lot of extra time because you saw that you need to get back to the problem after 5 minutes.
Personally I just didn't believe in greedy in D because after solving C it can't be that easy, right? Also E < C and D. I solved it in longer time because once again bad samples and I had a bug in bit count function.
There's nothing wrong with bad testcases if they were always bad, but that's like the most uninformative samples in a long while
I don't understand what's the problem with that.
Regarding D, I have a dp, so I don't know what is the greedy solution.
When I participate, say, in a div 2 contest, after I get some intuitive solution which I find correct, I implement it, check with the sample, submit and go on. In like 99% of times I get accepted and focus on the next problem.
This time however I first wait for 5 minutes to know if the problem got accepted, while reading the next problem. Then I see that I got wa2 and now I need to get back, this usually slows my thinking a lot (when people fail they are stressed and when people are stressed they fail more, vicious cycle).
That's my usual behaviour and I think that many follow similar patterns. By doing many rounds on CF people form certain strategies which work most of the times. This time it didn't.
i got the same situation in this problem. but isn't it nice that this problem caught us and forced us to actually prove our solution instead of guessing?
I enjoyed proving C but the same effect could be achieved with the good samples.
but this way the problem punished people who don't prove their solutions. i think that's fair.
Only very slightly. 50 points for checking if the solution is really that trivial is a penalty I comfortably took at minute 10. Presystests do the job of punishing people who can't find the right solution, useless sample is just a silly illusion (because local stresstest is a no-effort good idea anyway) of artificial difficulty.
if you have the test, you need less brain power to think of the solution kinda? like you already know what is wrong, and you just need to hunt down the exact problem. but otherwise you need to think and do more stuff.
The first tests that showed the trivial solution failing to me didn't reveal why at all... I had to deeply think about what's actually happening and then about how to make a set of rules that'll help me find a solution.
Just imagine an extra $$$N=12$$$, $$$K=2$$$. The optimal solution is
11 7but this is so limited that all it tells you is why the trivial solution is wrong: sometimes turning a 1 into 0 allows you to benefit from turning less significant bits into 1s. That's literally just an inverse of (false) reasoning for why only 0s and $$$N$$$s should be used. However, which less significant bits? When should 1 be turned into 0? Should it be done multiple times? (This is important, $$$K=2$$$ tells you absolutely nothing about it.) If yes, multiple times for the same bit? What upper bound can we find? And finally how to make a solution that makes sense of these rules to reach a tight upper bound?A proof outline isn't something a better sample, even a very strong sample, can help you with. Of course you don't exactly need to make a proof, but can instead form tested conjectures — and that's also not something a sample can help you with if it's reasonably small. Make a bruteforce, stresstest, find out what doesn't work and what conjectures seem to fit. You need to have many tests and it's quite easy to have them.
More to my point, if you don't have the test, you can make any number of tests you want with little effort and bruteforce answers for them with some effort (DP), thus changing the situation from the default one we had in contest to the one you would've preferred to be in.
C wasn't overkill due to the sample. It's actually legit quite tough and (looking back) was misplaced difficulty-wise. I thought "wow this is tough, I'm such a pleb" when I solved it 1 hour in but if many people got delayed on it, it's because of how hard the solution is to properly figure out.
i actually had an even deeper problem :) i figured that we should put $$$n-2$$$ values $$$n$$$ and then do some smarter stuff with the remaining two. and this worked up to $$$n=30$$$. i was so mad :) i had no idea what's going on. and then i had to actually sit and try to come up with a real solution.
idk... samples are cool but for example in math olympiads there are no samples. and it's your job to both figure out the exact general solution and all the corner cases.
When I saw that the C on the standings was just a bunch of -1s, I decided to write a dfs to verify my correctness. Although writing brute-force code would take some time, it was far better than quickly submitting and getting a
Wrong answer.What's truly terrifying are those problems that are difficult to write brute-force code to verify correctness. In such cases, you can only leave it to fate.
Greedy for D is simply trying to let a maximum number of prefix circles [1...i] to tangent (while they are tangent, i and (i+1) cannot tangent, then we stop, and regard i+1 as a new first circle, the only difference is circle i+1 is also constrained by circle i). It can be proved this strategy is optimal.
Also what's the dp solution for D?
we can do "dp" with an infinite second dimension: $$$dp[i][r]$$$ — how many things touch up to $$$i$$$ if $$$r_i=r$$$. then we can note that $$$dp[i][\_]$$$ behaves in a predictable manner. say, $$$X_i=max_r dp[i][r]$$$. then one can prove by induction on $$$i$$$ that there is some interval $$$(l_i, r_i)$$$ such that in this interval the value of $$$dp[i][\_]$$$ is $$$X_i$$$, and outside of this interval the value is $$$X_i-1$$$. now we can just maintain $$$X_i$$$, $$$l_i$$$, and $$$r_i$$$ instead of the whole "infinite dp table".
"Slope trick in a greedy problem" ahh vibes
But in all seriousness, I love these kinds of solutions, thanks. They seem like overkill but at least the proof is solid
I agree that the difficulty of C and D are reversed, and this causes confusion for contestants. Also, the sample of C can't even hack the most trivial greedy solution, and I think this is a fatal problem.
how did this post went from +250 to -170 in 3 hrs . what happened was the contest hard?
can anyone help me understand why my code is wrong for problem C :354194938
can anyone tell me whats wrong with this idea for c
My submission
so when its odd we print k*n ; when its even a,b and (k-2)*n ; for a , b ; for the msb 1 we assign that bit as 1 in a and for second most significant 1 we assign that bit as 1 in b ; and after that for every 0 we assign 1 to both and for every 1 we assign 1 to a ?? this made me hallucinate stupid things please guide me where i went wrong
Try
n=30, k=4. Using two30here is suboptimal compared to15 23 27 29F1 N=5000, are you serious?
Probably to let the naive O(NM) DP with prefix-sum optimization pass (like me—I only had time to get that far qwq).
This contest MUST be unrated!!!
For anyone who is confused by C. There are two common issues for even $$$k$$$
If you are spamming $$$n$$$ and then calculate the last two values. This won't work. Try
30 4and you'd likely get a XOR factorization summing up to 92 (like15 17 30 30) when it actually can reach 94 with15 23 27 29(only click if you have resolved issue #1)
If you resolved that and did not pass. It might be because one of the two following pitfalls
One is that the zero bits might accidentally appears an odd number of times. Check with the case
28 4and see if the xor is correct.One is that you might miss some one bits when $$$popcount(n) \gt k$$$. Check with the case
31 4and see if the xor is correct.I think this is a bit too many possible pitfalls for a thought-heavy task with high chance of fakesolve in the first attempt. Might be my skill issue though.
for k = even case
0,n,n,n.. (our initial intuitive solution, which is wrong)
claim:instead of removing set bits from one n its optimal to remove from multiple different n's
in general when bit is 0 in n that means we could use 1's in their position(as xor of them is still 0, as our solution looks like ,,n,n,,) but that could increase the current ai value greater than n if we add more 1's .
so in our first solution
we say 0 n n n instead of removing all bits from first position, we can distribute the 1's removal from different n's, so that the value of n decreases, hence we can use our claim, here to add those extra 1's
implementation is tricky, which i couldn't :(
C stands for Cooked
you know you can't solve it when tourist gets 3 WAs
problem -C ~~~~~ //void solve() { ll n,k; cin >> n>>k; vll ans; if(k&1){ for(ll i=0;i<k;i++){ ans.pb(n); } } else{ for(ll i=0;i<k-2;i++){ ans.pb(n); } ll maxSum = -1; ll aAns = 0, bAns = 0; for (ll a = 0; a <= n; a++) { ll b = a ^ n; if (b <= n) { if (a + b > maxSum) { maxSum = a + b; aAns = a; bAns = b; } } } ans.pb(aAns); ans.pb(bAns); } sort(all(ans)); printv(ans); }// ~~~~~ why this code is wrong for probelm C
For problem C , here is counter test case to everyones even set solution
n=30 k=4 , as per my code , we expect 30,30,15,17 as answer
but there is one more which yields better sum
15 23 27 29 ( so jo odd m we print n times same wont wor for jk-2 times always in even case )
my submissions for the first two problems were in queue for long time, specially for problem B it took around 13 minutes, I corrected it after that, but after damaging my rating
Great contest! It was a little unbalanced but the problems A-D were very fun
The C is too hard for me. I think the situation when k is even is similiar to the situation when k is even. But it is prove that my greedy strategy is false.QAQ It's too hard for me to prove the strategy is true.
update: fixed
c is so hardđ
Personally, while C did have weak samples and I got a couple of WAs, I felt it was a really fun question! And it forces you to use your brain to think of corner cases. So, good contest in my opinion.
D, I was surprised because I thought the solution was too obvious, so I hesitated to submit (feeling a bit scarred by what happened in C). ;-;
Problem C was a disaster.
In problem D，pretest is weak，why not open hack？
torture
I regret signing up for this competition.
submissions after first AC shouldn't be counted right? i did 2 submissions on A because while first one was in queue i thought something i forgot might give WA and resubmitted but both were AC however i got like -50 points on its score and after system tests it shows that first submission was skipped which threw me like 2k ranks below </3
why there is -330 votes ?
certainly bad round...
C was hard
Solid round, gg guys! No idea why we all got stuck on C :))
I thought contest was for 3 hrs, cuz it was a global round, my solution for C just passed :(.
I decided to post my thoughts about C, I found it to be a very nice problem, which looks like it has a straightforward solution, but it was very difficult to find a counterexample for the solution. Here's my solution:
If k is odd, the solution is trivial, just print n, k times.
Otherwise, let's make some observations
Observation-1 Let us consider a bit at position i of n which is 1. Now consider the jth element of array whose all bits to the left of position i match n. If we set the ith bit of the jth element to 0, the jth element will always be less than n, no matter what the bits to the right of the ith position are set to.
Observation-2: If the ith bit of n is 1, it is optimal to set the ith bit of k-1 numbers to 1 and one of them to 0. Notice that it doesn't matter which number's ith bit is set to 0.
Observation-3: If the ith bit of n is 0, we would want to set the ith bit of as many numbers as possible to 1, in order to maximize the sum.
Observation-4 If we have 2 positions i and j such that the ith and jth bit of n are both 1, it is optimal to set the ith and jth bit of two different numbers in the array to 0(from observation 1). This is intuitive.
From the above observations, We iterate through the bits of n from MSB to LSB. Initialize all the elements of the array to 0. We will maintain a pointer j initially placed at the 0th index of the array.
If the ith bit of n is 1, add (1<<i) to all elements except the jth element and increment j. If j exceeds the length of the array, we add (1<<i) to all elements except the last element of the array.
If the ith bit of n is 0, if j exceeds the length of the array, we can add (1<<i) to all elements of the array, since k is even. Otherwise, we add (1<<i) to just the first 2*floor(j/2) elements due to observation-2 and the fact that an even number of ith bits of the array need to be set to 1. This can be understood from observation-1 and also ensures what observation-3 claims.
The pointer j enforces observation-4.
Apologies for the bad editing.
exact same solution brother I don't know why people are hating this problem it was a good problem.
Really nice solution. I had been on the right track but instead of looking at finding out the values of all indices using this way, I thought that the first k-2 had to be n, and applied this logic only for the last two elements. The crucial point I missed was that if there is a set bit in n, that means ANY index can have that particular bit unset, without having any affect to the answer. For some reason I thought that it is going to decrease the sum.
Good learning experience, again thanks for the really clear explanation!
I would like to share my insight on bitwise XOR question, and this works well (for context it worked today too) try to think for each bit, don't try to see the number as whole if you try to see each bit you will understand I am attaching my solution hope it helps: https://mirror.codeforces.com/contest/2180/submission/354181688
Contrary to the popular opinion, I think problem C is good.
...
However, the queue was very slow. It took like 20 minutes for me to find out that my first submit was WA.
Problem C was insane, can't imagine someone not rage quiting and solving it
This C is absolutely the best, I spent over 1.5h! I love C. C is the best.
Ain't no way this contest is real. Everyone can speedrun A and B in this contest and then Failed on Pre-test 2 C and D entered
F is absolutely boring.
for even case in c, I assign (k — 2) to n, and the other two numbers tried to insert bits that does not exist in n as much as possible what is wrong with that ? so if n = 20, k = 2, then basic assignment will be 16 and 4 and then I will add 1 and 2 in each of them so I have 19 and 7 ? why this is not optimal ?
for n=30 and k=4 , it fails.. answer should be 29 27 23 15
Thank you so much
People downvoting were clearly unaware of this meme before signing up for a global round. :)
The worst performance should happen in div1 only round.
This meme is mostly for people who don't qualify for Div 1. :)
I would say this would be one of the best contest as problem C was one of the mind boggling problem as the most common logic that most of us would come up with is wrong(maximizing only 2 numbers and keep rest numbers as n is wrong) and authors utilised this very well to prepare this problem.
Why I am not able to open any question on past contests?
..
Please tell me in detail what I learned.
I loved problem D, didn't solve it lol but had fun regardless trying to solve it thanks for the contest also C was giving me hard time but learned new things.
260
what was C problem
Here is my approach for C
for odd k , just print n 'k' times
for even k ,
My idea was to try to bring in as much numbers(out of those k) in that category 'which will have 1 at the bit when n has a 0 at that bit' and as soon as possible .
starting from the highest set bit in n, let the bit be 'b': if b is 1 : we need to have odd number of 1's (in those k numbers combined) at the b th bit , and so obviously to maximise the sum, we would want k-1 numbers to be set 1 at this bit. so make the 1st number of the list have a 0 bit here and rest all 1 bit. Next time we encounter a 1 in n , we make the second number of the list 0 here at this bit and rest all 1 . So after encountering 'k' 1's in n , we would have tried out all k numbers. Now , all the k numbers have been made < n .and in future whenever we encounter a 1 in n , doesn't matter you can make any of the k numbers 0 randomly .
And meanwhile in this process, whenever we encounter a 0 in n , we make the first 2*(num/2) numbers of the list to be 1 here. (Where num is the count of numbers which have been made < n so far) . Once num hits k , we can make all the numbers to be 1 here without violating [0,n] condition.
whats wrong with problem c is wa on test 2
We have been approaching C with the wrong, mindset need to give a second thought on how we used to approach a particular problem with a proof.
why don't C give a strong sample like n=30,k=4?
Because the question setter doesn't want you to pass easily.
C is really the charm to me. Enjoy it so much, even though with 3WAs and eventually a negative delta. Isn't is the fun of greedy thinking: wrong greedy ideas which cannot be proved, gradually mature to a final one with solid proof!
Why so many down votes? That baffles me way more then C.
Problem C bruhhh. I wish I had skipped to D tbh
Thank you to the problem setters, testers, and organizers for putting together Codeforces Global Round 31. Special thanks to XTX Markets for supporting the series. The problems were interesting, and the editorial was very helpful. Good luck to all participants!
f bangladeshi mf
Combination of C and D crushed like everyone in this contest
I don't think this contest should be getting too many down votes only due to ques C.
C is fine. The dislikes feel more like post-WA therapy than actual feedback. according to me C was really beautiful and well made question.
wish i had skipped c and solved d
Problem C was so good!! It taught me alot. Thank you team.
Please continue with such.... (I have no clue why it is so highly downvoted)
When will cheater removal occur for this round? I’m at place 670, the same as when the contest ended.
Thanks mods for removing some people. Someone should look into Axoryn. He has very suspicious behavior on LeetCode where he's clearly using an autotyper to type in his solutions. His submission pattern in this contest is also very suspicious. Submit D and E one minute apart, understands the math for E, yet is completely fooled by C even at the 2:29 hour:minute mark.
If you want concrete evidence, see his Q4 video (rank 2) in this link: https://leetcode.com/contest/weekly-contest-472/ranking/?region=global_v2
Hello, I acknowledge the notification regarding similarity in my submission for problem 2180B. The similarity was unintentional. During the contest, I used an AI tool only to help format my code by mistake because it was in my text editor extension so it auto formatted it., and I now understand that this can still result in unintended structural similarity and is against the contest rules. I sincerely apologize for this mistake. I fully respect Codeforces rules and will ensure that I write and submit solutions entirely on my own in future contests without using any external tools. Thank you for your time and consideration
You follow up your apology with cheating in the most recent Div 3?
This was your first submit on H, which was six minutes after your submission on B.
https://mirror.codeforces.com/contest/2179/submission/354773964
Impressive note deletion for your final submit on H.
https://mirror.codeforces.com/contest/2179/submission/354815060
Congratulations to T-shirts winners! In a few weeks you will be contacted via private messages with instructions to receive your prize.
As usual, we used the following two scripts for generating random winners, seed is the score of the winner.
Bro left after seeing that amount of downvotes. TOP1 Negative Contributor