Hello, Codeforces Addicts!
On Sep/30/2022 17:35 (Moscow time) we will host Codeforces Global Round 22. 
Codeforces Global Round 22 is the $$${\textbf{2}} \cdot {\textbf{2}} = 4$$$-th round of a 2022 series of Codeforces Global Rounds. The rounds are open and rated for everybody.
The prizes for this round:
- 30 best participants get a t-shirt.
- 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.
The prizes for the 6-round series in 2022:
- In each round top-100 participants get points according to the table.
- The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
- The best 20 participants over all series get sweatshirts and place certificates.
Thanks to XTX, which in 2022 supported the global rounds initiative!
The problems were written and prepared by antontrygubO_o, Milesian and me.
We are extremely grateful to the following people who made this round possible:
- Aleks5d as well as KAN for great coordination.
- lucifer1004 for discussion and being the first tester as this round grows.
- 4qqqq, Akulyat, alexX512, arvindf232, BucketPotato, BurnedChicken, choutii, FairyWinx, Sugar_fan, lucifer1004, lyuankai, mejiamejia, nnv-nick, okwedook, p_b_p_b, Potassium, TomiokapEace, Um_nik, yyt16384, and zjq2863974342 for testing the round and their feedback.
- MikeMirzayanov for creating great platforms Codeforces and Polygon.
Round Information:
- Duration: 2 hours and 30 minutes
- Number of problems: $$${\textbf{2}} \cdot {\textbf{2}} \cdot {\textbf{2}} = 8$$$
- Score distribution: 500 — 1000 — 1500 — 2000 — 2500 — 2750 — 3000 — 4000
Kind Tips:
- Always get ready for interactive problems no matter whether they will exist or not, please see the guide of interactive problems if you are not familiar with it.
We are looking forward to your participation!
UPD. Editorial
Congratulations to the winners!
And for the winner of each problem:
A. tourist
B. tourist
C. wind_cross
D. tourist
E. tourist
F. 300iq
G. ksun48
H. rainboy
I don't know how I should feel about this bug...
funny how I guessed you were going to be here before opening the blog, lol.
funny how I guessed you were going to be here before opening the blog, lol.
funny how I didn't guess you were going to be here before opening the blog, lol.
funny how you didn't guess i'm marinush, lol.
Good luck & have fun & Orz !
2022 = 2222 - 222 + 22 = 22(22) * 22(22) - 22(22) * 2 - 2 !
$$$2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2}}}}}}}}}}}}}}}}}}$$$
So why not $$$2022=2+2+2+\cdots+2$$$ ($$$1011$$$ twos in total)?
Because no one was able to make such a difficult observation
As a tester I
<strong></strong>..ly encourage us to participate?
i just strongYepbut why isn't global on weekend? ):
The weekend is most commonly considered the period between Friday evening and the end of Sunday.
So, maybe Codeforces consider Friday as weekend, emmmm, half-weekend at least.
It's indeed on Friday but it's not in the evening for probably one half of the earth due to timezones.
Any time is not evening for more than half of timezones...
Maybe it's because .... 2 days before the week...end?
Can we please make the contest 8 minutes shorter for the memes?
If the system had allowed it, it'd be good to make problem D or E worth 2222 points as well, but sadly we can't
isn't 2250 points possible though?
Great idea! Can't agree more!
But it seems we cannot do that. What a pity
222 + 2*2*2
150 minutes shorter might have been better I think
As a tester, I'm glad that a bad problem was removed from this contest.
Is that so?
Yes, I bet.
Yeah? Why?
Maybe bad problem is bad.
You did the best. It would be better if my account were liouzhou_202.
The emphasis on 2 is hinting at WA on pretest 2
You can also WA on pretest 22.
Please tell me we won't FST on System test 222
The 2-nd problem.
Is this just a coincidence?
The prerequisite of that is passing pretest 2 first .....
2 much 2 in 2morrow's contest
As a tester, this contest has a couple of nice problems, but the overall quality is worse than average.
Lol
As a participant, I am surprised to see a useful tester comment.
Very interesting, also as a tester, the first time I saw a tester say that the problem is not good, generally speaking, as a tester, no matter what the problem is, I will praise the problem, if the problem is good, I would rate it higher, but I like your personality.
no matter what the problem is, I will praise the problemWhy?
Because every tester does this.
But it's stupid and makes tester comments meaningless.
If most testers think like this then that explains a lot...
Thank you for your honesty. Your suggestions will make our rounds better in the future.
Anyway, wish everyone will find something interesting in this round.
But why didn't their suggestions make your current round better?
From where do you see that their suggestions did not make our round better?
As a tester, I second this.
Tired to see testers just praise every contest...
I should have trusted you:)
I don't like testers giving any information on the contest before the round. You felt entitled to do it and the community heavily upvoted you, but such a behavior is outside the scopes and the rights of the tester.
The usual "Best contest ever" comments by testers are childish and annoying, but they are empty. Your comment is actually giving information. If I were the author I would be very pissed as you have likely reduced the number of participants.
I didn't give any information that can be used to get a better result, did I? I don't think that providing such kind of information is worse than providing the names of the authors, which CF does every time.
What do you mean "empty"? What's the difference between saying "the contest is good" and "the contest is bad" from the perspective of providing information? It seems to me like you are applying some imaginary rules. It's like you must answer "I'm good, thanks" to "How are you?". I don't do small talk.
I couldn't care less.
True, but it's not the point.
Possibly true, but it's not the point. Codeforces, being the organizing platform, is entitled to do whatever it wants. A tester should respect the not-imaginary-but-implicit-and-useful rule: if someone is given a private information for a specific purpose, he cannot share the information.
I don't deduce anything on a round when a random tester says that the contest is wonderful. It's exactly as saying "I am fine, thank you" when asked "How are you?" as you mentioned. On the other hand, when you write what you wrote, I deduce information about the round (and in fact, a posteriori, I think that your comment is correct). It's because writing "The problems are amazing" is a trend among testers, it's also because I know that you are more reliable than a random tester.
I assure you that didn't happen. For example, I participated from alt account
As a comedian Codeforces Global Round 10110
Fun. Why not "200 t-shirts are randomly distributed among those with ranks between 31 and 5000, inclusive". Then I wish to win a t-shirt with probability 200*1/4970
Does it rated?
Fun fact about the number 22 I just found out:
It is $$$\mathbf{211}$$$ in ternary and $$$\mathbf{112}$$$ in quaternary. Also it is $$$\mathbf{16}$$$ in hexadecimal!
The BPM of Freedom Dive by xi is 222.22.
I was waiting for this joke since 33 hours ago
While the BPM of GOODRAGE by EBIMAYO is 222.
Good luck and have fun! Hope it won't be unrated :D. I have been waiting for a great global round for a long time ^_^.
is this round rated
Yes.
You people are too obsessed with 22 number.
Grow up kids
22-year-old kids
no need for factorial at the end of the equation)
Hope it won't be unrated!
Hoping for lesser cheating
Tons of cheating on C
Hope Pretest 2 would be strong enough!
I wasn't :)
Yeah! you could be strong.. so many B and C were Hacked/FSTed :(
B could contain the edge case
k = 1in either samples or pretests, sadly I got FST too :(hoping for +ve delta
I hope there are no copied problems this time.
i need dalex to butthurt about how statements are hard to understand
I retired from everything related to CP
C is the worst problem I've seen.
Stop taking these Chinese style shit problem into cf.
edit: Sorry D is worse
edit: Sorry E is worse
edit: Sorry H is worse
edit: Statements are too long. I think authors could use spoiler to fold some definition. F is great. Gaps are too small.
i guess you are the only one who is worse and ugly here LOL : (
if it is worse who said you to do it
dont do it if you dont like it
Because I love both rating and joy of solving problems you such sore loser ^_^
Red is much more beautiful than grey I think.
If you can't say which problem is good and which is worse then u are a loser.
Can't agree more
Weak pretest on B and C ... That's even worse when I get FST on C :(
([hit_call]dx[hit_call])
ReadingForces
Why is this contest so hard? :(
Worse than just that, the difficulty distribution is very flat. I felt like all problems among BCDEF had pretty much the same difficulty, instead of seeing gradually harder problems.
Is this WA on pretest 2 contest !? o((⊙﹏⊙))o
I think all will get negative delta after this round!!
This contest is only good for those with high IQ or great observation skills. Banging my head smh.
C is about as standard as it's possible to be, with no observation skills required.
I apologize, I didn't see the constraints. I was thinking of standard even-odd formula.
why does C give negative elements (sweat)?
Did you mean B? In C, all that matters is whether elements are even or odd, so negative elements should not be an issue.
Negative elements in B were a bit annoying though.
EDIT: nvm, I forgot that a negative odd number mod 2 produces -1 in C++ (and probably some other languages too). I actually dodged a bullet by checking for evens instead of odds (which were covered by the else).
LOL.That's pretty annoying.
wrong-answer-on-pretest2-forces
Really difficult contest TAT.
I guess, no more
The problems were written and prepared by antontrygubO_orounds for me. Worst contest ever...idk
How to solve E?
I mean come on, samples for E were just evil. I think it would have been better ff samples would have been a bit stronger,
How to solve Q2....
WA 17 times...
Thanks to Codeforces Global Round 22 and Educational Codeforces Round 136 I will return back to specialist.
very bad contests just constructive problems depends only on mentality skills!!!
Same thing but with green and gray
The only constructive problems are F and G, and even then it is a stretch to call them constructive.
D >>>>>> A > E > F > B > C. Change my mind. I have no idea how E&F have 4 times less solves when D is legendary hard.
I don't think problems are bad but I somehow performed really bad :(
Great problems! I especially enjoyed C!
I couldn't manage to solve D tho :(
Thank you!
Problem H is straightforward and tedious application of eertree with ridiculous constraints that won't allow $$$O(n \log^2 n)$$$ solutions to pass. Otherwise, the main idea (at least the one that I have used) almost completely repeats this and this problems.
I bet you will be surprised when seeing the intended time complexity.
Why linear when you can do it polylog way more easily :(
Indeed, I don't want to make only $$$O(n)$$$ pass. Just allow some $$$O(n \log n)$$$ to pass.
I passed pretests with $$$O(n \log n)$$$, but the experience is soul-crushing, as I couldn't just submit $$$O(n \log^2 n)$$$ solution that I had from some earlier problems and it ultimately consumed too much time for any meaningful recovery on other problems after passing it :(
Is F easier than E? I found there are many participants who solved F much faster than E.
The logic for F is easy compared to E. It's just that people have hard time understanding interactive problems
I would say the opposite. The logic of E seems much easier than F, but the implementation is kind of a pain and at least in my implementation there was a special case that I missed (I kind of convinced myself that the logic for
0 0 0and1 0 0 0 1is the same, but it's not). Meanwhile, F was actually kind of clean for an interactive problem.Is AGC easier than some large-coded data structures like 917E - Upside Down?
got hacked on B yesterday and today as well, I would have reached pupil otherwise, any suggestions to avoid hacks?
Well, check the constraints before submitting and think of corner cases as well.
Hello there srikaran_p
Hello Taha_adeel!
Is there any simple solution for A?
i just feel c samples would have been better i feel its just useless why didn't it cover more scenarios?
Errrrrrrrrr... Not bad
How to solve H:
How could I have remembered that while I was not feecle6418. :(
I bet you will be surprised when seeing the intended time complexity.
I know that in some year's (edit:2017) Chinese IOI Training Essays, there exists a paper that claims "PAM can support arbitary pushfront pushback popfront popback operations in complexity same with only pushfront pushback". (However I have never seen an implementation of it) So I guess it indeed can be solved in less complexity.
The thing that surprised me the most is that the alphabet size is larger than logn.
Never mind. I just don't want $$$O(n \log n)$$$ to fail.
How to solve H:
Edit:
Some of my friends complained that if you find the solution of BZOJ version you might get TLE.
However this situation should be checked before the contest, authors and testers should ensure that there is no googleable problem.
Got it! Next time I will let all non $$$O(n)$$$ solution fail. Then, it's not googleable at all. Do you like it?
Could you point to the problem? Intended solution to this one is $$$O(n \log^2 n)$$$ and it gets TL.
I actually copypasted main ptz solution to BOJ 19026 (fearful is my alt), then opened the fastest solution by cyanic and constant-optimized it a bit.
road to pupil
Sad. The thinking was somehow enjoyable though.
Glad to see you enjoy it.
The first great-positive-delta contest recently for me xD
Congrats!
D had so much reading comprehension, the solution ended up being kinda nice but not worth the like 1 hour of just brute forcing patterns.
C was literally you know DP or you don't, unless there's a greedy solution?
A and B were kinda insane for A's and B's
I saw some people in my room doing c using a bunch of if conditions,idk if that solution is right tho...
For problem C, DP is not necessary.
I did DP too. Then I printed the array over amount of zeroes and ones. We get regular 2x4 Blocks:
Top left is no evens and no odds. To the right I count odds, down evens.
Somebody in my room solved C as follows:
Let $$$n_o$$$ be the number of odd elements and $$$n_e$$$ be the number of even elements.
If $$$n_o \bmod 4 = 2$$$, Bob wins. If $$$n_o \bmod 4 = 1$$$ AND $$$n_e$$$ is even, then Bob also wins.
Otherwise, Alice wins.
Proof: No freaking clue, but I printed my 100 x 100 DP table, and the results seemed consistent...
C is a bunch of ifs
C was literally you know DP or you don't
Can you elaborate?
Why it was too tough for me ?
Problem A was really too difficult to be A for others too.
Note that this is actually a Div1 contest (i.e., rated for everybody), not a Div2 (like most of what we've been having recently), so a bit of challenge is actually justified here imo. I don't feel like this one is too hard by Div1A standards.
I see that you have not given any global round so far. Even in global round, problem A is very simple
Ah, I see, my bad. I was under the impression that any contest that's rated for everyone is a Div1 contest, so I didn't actually realize that there was a difference.
dont worry, problem A and B were harder than usual
Pupil I am coming
Is there a way to solve C other than 4d DP? 4 dimenion = dp[odd][even][alice][needOdd].
D is straight forward greedy right?
yes it's simple bruteforces method. my code : 174150204
explain: first of all you check how many maximum number of odd alice can get if that is even then definetly alice will win. otherwise you can check that how many time even numbers are if that is odd time then alice choose number such that he got last even number so bob must be select one odd number so now we apply same above approch but number off odd is decreased by 1. and above all condition not sutisfy then bob will win.
Do you know what bruteforce actually mean?
ya sorry its greedy.
how can i spend nearly two hours and finally realized just some bruteforce is enough for C
Can Anyone Explain me i am got runtime_error on my 1st quetion solution in c++20 language but when i have submit same code in c++17 then i got accepted but for changing language i take 1 hour. so can anyone explain me why this happen in c++20. my c++20 code: 174108183 my c++17 code: 174139409
F is really a great problem and it took me very long time.
Here is some feedback on the problems:
I loved problem G, while I did not enjoy solving the previous problems as it was just speed-solving without thinking. The contest was well prepared and the statements were clear. Thanks to the authors!
How did you end up making sure the antichains are disjoint in G? I read the editorial but it seems to go in a different direction...
Edit: I read your code, looks like the key is doing this to the input:
It's easy to see that this transformation is valid (because no k-increasing sequence would ever use those elements anyway), but it's very interesting that after doing this the rest just "works".
I want to confirm that your interpretation of my solution is correct. I am proud of it, it felt magical when I noticed it.
Let me remark that those cells (the ones set to 0 in that for cycle) cannot be deleted, otherwise there will surely be a $$$k$$$ chain. So any solution will not delete them and therefore it makes even more sense to make them undeletable.
I suggest problem A in contests (other than div1 contest) should be at very easy and friendly to all the newbies and incomers, this contest problem A is too hard for its position.
Because if a contestant do not make any submission, he will not included in official table. If problem A is too hard, many newbies will quit and not included in the ranking table, and this contest will become another "div1" contest, only strong contestants participate.
However, it is more difficult for a contestant to gain rating in a contest surrounded by strong contestants, as I discovered in one of my blogs, it is not good for a weaker contestant who want to challenge him(her)self.
As an ABCDEFG solver, almost all problem was typical and needed at most one idea, but sometimes participating in such a contest is not always bad. (Though it's right that this contest isn't likely a Global Round)
Logic I have used : if Alice Can take even number of odd elements he wins! What's wrong in My logic? 174123447
int n; cin>>n; int o = 0; for(int i = 0; i < n; i++) { int x; cin>>x; if(x % 2)o++; } int k = o — (o / 2); string ans = "Alice"; if(k % 2)ans = "Bob";
cout<<ans<<endl;
you are directly considering that alice can take all the numbers he wants at a time but that is not the case they have to play alternatively selecting only one number at a time.
consider case
1
1 2 3
o(odd numbers)=2;e=1;
as per your solution alice selects one odd number now o=1;e=1 . now if Bob selects the remaining odd number alice will lose but as per your logic alice wins.
Hardest Div.2A I've ever seen... 174095886
Very strong indeed.. A was hard, tough contest.
In problem E, I thought for a lot of time that there may be negative numbers. Is it solvable in this interpretation?
It seems at least as hard as counting common subsequences in two arrays. Is even that solvable in subquadratic time?
Many failed system test in B
But I passed B and failed D XD
FST... So many FSTs in B...
(@Successful Hackers: what's the key of distinguishing correct solutions and wrong solutions in B?)
(-1)/2 == 0 in C++, but many contestants do not understand this...
IMO, rounding towards zero in C++ is well-intended (It has multiple reasons including consistency and performance), but evil at the same time (most of all, it is counter-intuitive!)
upd: This behaviour is also the reason why negative modulo happens on C/C++. It has persisted since C99, and while I think it should change, I guess it won't for a few years at least.
C++ has zero-overhead philosophy. And this is how division works in cpu. So it will never change in c++
What happens in python can you please explain
They did not have to care about thia why?
Python uses floor division for integer division, and the modulo is always positive. That's one thing I like about Python
It's more about forgetting about negatives than not understanding this
Probably not handling $$$k = 1$$$, also something like this works incorrectly with negative numbers:
The limit for the original array element at the (n-k+1)th index. Many messed up trying to find this
that's why one writes
a * b <= cinstead ofa <= (c + b-1) / bD:ABC are straight forward annoying casework shit. I would call these problems more or les heavy implementation.
D is greedy.Imagine the blocks <= k or > k can be like 000011100011 and figure out the last one from there.
Epic pretests for problem B, thank you!
F (and maybe G) is(are) awesome. But C, E (and maybe H) are shitty casework / Chinese-styled problems.
Problem E is very boring and complicated to implement.
I don't see any submission from you in this contest, Have you participated with alt account?!
unaddictive contest
I'll try to start a new trend of "as a tester" comments. I would like to share my feedback that I have sent to the coordinator after testing. I don't know if it was passed to the authors, but I can see that the changes I proposed were not made.
A, B: I guess they are fine, I don't really like either, also I think that both of them are too hard for div2A, and A is a bit harder than B in my opinion
C: I just don't understand why this problem exists. I assume there is $$$O(1)$$$ solution (once you know number of even and odd numbers), but why would I think if there is an obvious $$$O(n^2)$$$ dp? why are there negative numbers in input? just to trip people who will check parity as
x % 2 == 1? that's just bullshitD: the hardest part is just reading the statement, even though I think that my solution is overcomplicated, because standings say that it is much easier than E and F, while I think it is harder (?). also it is kinda weird that finding k and finding the permutation is totally independent (in my solution at least). the problem is ok though.
E: super obvious combinatorics, the problem is kinda ok for div1A maybe, I don't get why testers are struggling
F: nice problem, although it is weird how simple the solution in the end is
G: I like this one, I know that it is from Anton :) I don’t think it’s anywhere close to div1D by difficulty, but fine
H: "write eertree on queue", wow, such problem. I think that there is eertree on dequeue, so it's not like it's something groundbreaking. and TL is just insane. my $$$O(q \log q)$$$ is right on border, either allow it freely or disallow it, but I think it is a bad idea to cut off $$$O(q \log q)$$$
What's the O(1) solution for C?
Who wins only depends on (number of evens) mod 4 and (number of odds) mod 4.
Only the parity of the number of evens matters.
I did the O(1) solution for C but I am gonna fail system tests because of negative numbers its so frustrating
UPD: I don't know how but it passed system testing
if(arr[i]%2!=0)
you seem to have won the coinflip^^
ohh yeah right looks like my lucky day lol
Well, if C needed O(1) you could still do n^2, print table and pattern is very clearly visible, so i think not asking for it is a good decision
Completely agree. I also don't like A, B, and C which are the three that I solved. B had extremely weak pretests too, which made me FST.
I also felt D is really hard. Not sure why so many people solved it
G didn't exist when I tested, and it is nice, so it must be from Anton :)
Also E was H when I tested (there were 9 problems), authors' and/or coordinators' sense of difficulty must be quite off.
You are the only tester who passed all problems, and had a chance to win this round if you were not a tester. Of course you deserved to write down any comments you'd like.
Get used to your impoliteness and arrogance as always.
Anyway, the following is just to say something you might have ignored.
C: Yes, it is obvious that I've already known there are two approaches. But you never tried to have think why I determined to make two possible approaches both pass. To you, either approach is obvious and may be boring. I want to ask: is there really a huge difference for you high-rated guys if only $$$O(1)$$$ solution is allowed?
It seems you are complaining not large enough constraints, and you think it is good to make higher constraints.
If this is Div1 only, of course I will do so. But you never know (at least forget or pretend to forget) what beginners really need. Do they just need to train case works? You can check many comments on how they loved and what they learned from this DP to pass, see 1, 2, 3, 4, 5.
For checking the parity, that is also what beginners need to learn, and they did appreciate it.
To you, these features are nothing. But please put away your arrogance in your own world, and see my comments on H below.
H: Wow, this time you turned your attitude 180 degrees? Let me repeat your arguments to fit in H.
I just don't understand why your $$$O(n \log n)$$$ solution exists to pass. I assume there is $$$O(n)$$$ solution (once you see the constraints are so large and TL is so tight), but why would you think your $$$O(n \log n)$$$ can pass naturally? Just to trip people who only know fast $$$O(n \log n)$$$ solutions, that's bullshit.
The better way is to only allow $$$O(n)$$$ solution pass and let $$$O(n \log n)$$$ fail. But this time, it seems you are complaining not small enough constraints, and you think it is bad to make higher constraints.
So where is your arrogance? You are expected to solve it $$$O(n)$$$, not sub-optimal things. Why did you stop your step?
The only reason is that
You know better solution to problem C.
But you don't know better solution to problem H.
That's it. So you wish to make problem C harder so that you can pass without pain but wish to make problem H easier so that you can pass without pain.
Don't forget that:
Problem C aims to let beginners learn more.
Problem H aims to let high-rated coders like you learn more.
If you did not pass problem H in testing round, I definitely you would shut up your mouth saying that problem H it's not groundbreaking and TL is just insane.
At the very last, I am not an impolite person as you may see. When beginners are rude to me, I know they do not fully undertand the meaning of some problems that trouble them. But for you,
You deserve to be treated rudely by others, as you always do so.
Really shame on you, on your behavior, and on your ignoreance!
The last of the last, thank you very much to test our round and give useful feedback. It would be better if you could raise your comments more smoothly. Looking forward to seeing you in the testing round, and leaderboards, in the future, my dear!
Stop crying, just take your L. I have some tissues here in India if you want.
hey sows pigmike : (
do you know I have a pig here to fuck you so hard hahahaha
Wow. What the fuck is wrong with you? I don't think that any of my comments were anything close to rude. Saying that your work is bad is not rude.
Once again. Those were the comments I wrote BEFORE the round so that you could change something. I don't see where you found any arrogance or 180 turns. I didn't say that you should make problem C harder, I said that in the current constraints it is a bad problem. I didn't say that you should make problem H easier, I said that in the current constraints it is a bad problem. The reasons for that are different, yes. For problem H I literally say "either allow it freely or disallow it", because having reasonable solutions that seem to be fast enough and that are right on the border of TL is really bad. Yes, my opinion is that you should have let $$$O(n \log n)$$$ pass freely, but that is one of the options. I think that in the current state the problem is worse than either with higher or lower constraints.
If you want to nitpick comments... I think that there is eertree on dequeue, so it's not like it's something groundbreaking.
So, yeah, problem H is just shit, and your contest was bad, deal with it.
Everyone knows your polite words, fuck, shit, bullshit. That's amazing. This is your upbringing yourself. Leave it alone anyway.
To be honest, I was not aware of your feedback even before the round ended and I had nothing to do with it. Sorry if this makes you misunderstand.
Another topic is about constraints. Could you explain why such constraints were bad more detailed? For me, I don't think so. Rather, it was set deliberately by me.
I don't know why (and I don't think) the constraints of problem C is bad, as I had already mentioned in my last comment.
For problem H, I ever proposed this constraints and explained why to do so to everyone concerning this issue. This is because, as always, we allow sub-optimal solutions to pass just for kindness. As you can see, the TL of every problem is very far away from its intended solution. When you select an algorithm that can probably get TLE, you should take your own risk.
Now consider your arguments to support your opinion that H is shit.
I think that there is eertree on dequeue Why do you ignore the sentence "However I have never seen an implementation of it"?
so it's not like it's something groundbreaking Why do you try to refuse groundbreaking by an $$$O(n \log n)$$$ solution?
So is there anything other than arrogance in your conclusion?
Yes, there's some truth to it. I won't argue that there isn't some arrogance mixed in, but setting constraints such that you allow suboptimal solutions to either AC or TLE by a slim margin isn't kindness, it's basically setting a trap for the contestants. It's also not unreasonable to expect O(NlogN) solutions to pass in 2s for N = 1e6, far from it, such solutions usually are fast enough.
From your messages, you seem to be blinded by um_nik being um_nik and thus refusing to accept his (valid) criticism.
thank you liouzhou_101 , i have figured out solving game problems using dp with the help of problem c. although it has taken more time i am very happy that i have came up with a new approach to solve game problems.
Something about E, F and G.
Indeed, among testers, the grades of E, F and G have very high variance, concerning their easy implementation. Every of them happens to be super-hard or super-easy to different testers.
As you may see on the standings, our round is balanced concerning the number of people who passed every problem. So it's our honor to see that we ranked these problems in a right order.
That means, you did not grade E, F, and G so accurate, but it's not surprising.
Let the statistics speak for themselves.
I mean, I just want to mention the slight possibility that the round appears to be balanced according to the number of solves, solely based on the fact that they were ordered this way to begin with? As such, many would've disconsidered to solve some problem during contest solely due to the pressure of not having solved anythinf earlier (and by extention, you'd think that the problems, the later they appear, the harder they get, so your bet is safer with the easier problems. Although this is a bad mentality)
To futher argument this, today I was at school and the teacher assigned us to upsolve this round. For D and E, very few people caught on the solution. But at problem F, almost half found the solution in less than 20 minutes (in this time, some even implemented it)
extremely weak and poor test cases in B , is this a joke?
can anyone tell me what is room, is it just random members assign to every room? and changes in every contest or there is anything else
" is it just random members assign to every room? "
Yes and you can only make hacks on people in your room.
thanks, could you please also tell me what is the meaning of problem locked?
https://codeforces.com/blog/entry/456
Read the 5th rule
Yes, contestants are randomly assigned to rooms. It's only relevant for hacking. If you lock a problem (only possible after passing pretests), you can view the submissions of others in your room for the same problem and try to hack them (construct a test case where you think their submission will fail).
The rooms make the hacks more fair, since each person is visible from a relatively small pool. Otherwise, if anyone can hack anyone, then except for those near the top, the probability that somebody's submission would be examined by a hacker, out of thousands of people, becomes extremely small, and getting hacked becomes a case of extreme bad luck.
Nice B, awesome tests
I'm really disappointed with this contest. One would think that, being a global, problems would be great and well prepared. Well... A huge load of FSTs in B and in problem C I still can't figure out why would you include negatives, it doesn't affect the problem and can make people have WA if they do x % 2 == 1 to check if number is odd. Ideas were cool, but bad round in general.
Yes
If you experienced global round many times, you will never think like that. A global round always taught in a painful way.
And I don't know why many FSTs of B matter. Making strong pretests is obviously good to participants, but it is not mandatory. Sometimes FSTs are needed for participants to implement more error-freely and accurately. This time I failed D in system testing, but I don't blame setters.
FST means that a participant wrote wrong code, so that participant should be held accountable for the wrong code. But I often feels this fault is completely overshadowed and only setters are blamed. Isn't it?
Testcases for problem B sucks, or maybe the problem itself!!
same like Educational Codeforces Round 136 problem b also. really very bad contests
What a tough contest!
Take a look at Ticket 16229 from CF Stress for a counter example.
Weak pretest for problems B and D, also description for D, E, and F can be better.
Can someone explain to me how the non-DP solution works for C?
It's some caseworks. Let number of odd and even numbers a and b. Answer only depends on a mod 4 and b mod 2. If b is odd, Alice loses when (a mod 4==2) and wins else. If b is even, Alice wins when (a mod 4 == 0 or 3) and loses else. Proof is not so hard, so I recommend you to think about it:)
Why was there no pretest for max value = 2e9 in B((((
what the heck is there in testcase 36 in question B can anyone tell the corner case?
Can anyone explain why I'm getting TLE?
https://codeforces.com/contest/1738/submission/174127596
https://codeforces.com/contest/1738/submission/174136625
Oh my gosh you didn't type
returnafter the if statement that checks if the dp value is already calculated. So the pre-calculated values always gonna be recalculated. What a sad mistakeLol...Thankx
I strongly recommend using
-Wall -Wpedanticflags when compiling your code.In this particular case you'd get
Thanks for the k=0 in problem D that takes away my LGM.
Aren't you already a LGM? Laurie
How To Solve C in O(1) ??
Work out E in 30 minutes after the competition,and FST in problem B(QAQ).
My solution for E:
Firstly,consider a special case:there's no zero in array $$$a$$$.
We notice if we put a "partition" between $$$a[i],a[i+1]$$$,we must put a "partition" between $$$a[j],a[j+1]$$$ as well,where $$$(a[1]+...+a[i])=(a[j+1]+...+a[n])$$$ (except the "partition" in the middle).
In other words,the "partitions" are in pairs.So the answer is $$$2^{k},k$$$ is the number of pairs.
Now let's consider an array $$$a$$$ including zeros.
Remove all zeros from $$$a$$$,we get a new array $$$b$$$.
The same as the special case above,if we put a "partition" between $$$b[i],b[i+1]$$$,we must put a "partition" between $$$b[j],b[j+1]$$$ as well,where $$$(b[1]+...+b[i])=(b[j+1]+...+b[n])$$$.
Because there're zeros,the situaion is a bit more complex:
Assume there're $$$x$$$ zeros between $$$b[i],b[i+1]$$$ and $$$y$$$ zeros between $$$b[j],b[j+1]$$$,the number of plans to place "partitions" is:$$$ \Sigma^{min(x+1,y+1)}_{i=0}C^{x+1}_{i}C^{y+1}_{i}$$$.
Take care of boundary conditions:
-all numbers are zeros
-the array has zeros at both the beginning and the end
-the "partition" in the middle
wtf is B maintest 36?
do you know what is even worse? failing on main test 48.....worst contest for me till now.
that would be yesterday and today both for me, sigh wud have been 1350 by now if yesterday and today both didn't fst, and now I'll be 1100
Why just why :(
It was last minute I couldn't fix it.
Naturally, as there's not much points expected in hacks nowadays, people start reading when they think they don't have the time to solve the next problem.
Oh that makes sense now, because most of the time you have 10-20 extra minutes after solving last problem so you spend it on hacking :D
Thanks for explaining.
Div 1.000002
how to solve C through Dp?
For every move player will either choose a even or odd number (offcourse only if they are present)
At the end if alice has even sum then he wins otherwise Bob
There are basically 3 dp states
1. Number of even numbers
2. Number of odd numbers
3. Parity of alex's sum
Check CSES removal game, DP solution is based on that only imo
C was not a good problem. It was more like writing all test cases and coming up with a solution.
I did something quite similar to that
Except it was not the intended solution...
Back in my days (~5 years ago), green and blue people wouldn't call out the problems as good or bad, unless there was some unavoidable issue like wrong test cases or ambiguous interpretation.
Things seemed to have changed over the years... ( some other comments are there on this line as well )
Second problem pretests have extremely disappointing quality ^(
B's pretests are weaker than my sperm quality.
Instead say "B's pretests are weaker than my jokes quality"
Inviting low-rating testers is also a very difficult problem for me, because among my good friends, there are very few low-rating testers, but I still think that every contest should try to invite some low-rating testers. For a contest In other words, this can avoid a lot of problems.
There are probably plenty of greys, greens, and cyans that are devoted to programming and would love to test a round(myself included). However, most of them cannot test because they generally are not very close friends with any problemsetter. Problemsetters are generally high rated, and correspondingly most of their friends are probably rated fairly well.
That is why I propose making the tester role more open. Obviously, I get that it may be weird to have some stranger critiquing your problems, but you get a completely new viewpoint which could improve round quality in return. For the record, I'm not suggesting giving anyone who wants to test the round a tester role, as it's a big responsibility, but I think problemsetters should consider, "Hey maybe I don't know this person, but they seem like they can provide valuable, constructive criticism for their level."
If anyone wants to test our round, there are two steps: 1. Add my discord, it's easier because I don't reject anyone. 2.Become good friends with me,It may be difficult, because I need to know you very well. I will not invite anyone to take the test, and most of the testers in our round are invited by aquamoon.
I am glad I did well in this contest. This was a harder contest as usual and even as a pupil I was able to answer the first three questions. I am also really glad I was able to find the dp solution for the game-theory question (not sure if it was second or third question. I think it was third), although implementing the solution took me more time than it should have as I ran into a lot of problems. If I implemented the solution more efficiently, who knows, I may have even solved a fourth question, given I had 45mins after I finished the third question.
do you have du？
omg what's wrong with 300iq How did he drop to master
300iq, I also wonder.
I haven’t done any competitive programming since 2020 :) I’m a bit rusty now, as I’ve spent this time learning math and working in cryptocurrency/finance sphere instead.
why are you asghar?!
I cannot understand why this blog gets many downvotes.
Guys, what's happening? Why is this blog so heavily downvoted?
Subjectively, there were some problems with this contest. Personally I didn't like problem D much, because after deepening down I felt like some trash scene is taking place in my brain. Many people constructively criticized it, I mostly agree. But it has a strange property because of which many people had suffered from the problem: you can either find the key to solving it, and then this is a straightforward implementation, or you can wander in vain and get frustrated. I am not sure whether this property makes the problem bad or not.
Also, as -is-this-fft- said in a comment, the distribution of problems' complexity turned out to be a bit flat. I kinda agree, but, firstly, I don't agree that B is somewhat similar to CDEF in terms of hardness (it's way easier), secondly, the solution of C only relies on careful cases considering, so it is also noticeably easier than DEF. As of DEF, they are of nearly equal hardness, and maybe for me D was even the hardest among them.
Some comments denounce problem H because it is way easier to solve if you have solved some other problems in the past. Sorry, I did not even read problem H (and didn't read the problems that are similar to problem H due to the commentators), so I cannot really say anything constructive here. But basically it is OK that experience matters, and acquaintance with some techniques which are not too common helps much with participating in the contest. For example, often in math problems (and in those programming problems which are essentially mathematical) I make some conclusions in mere seconds where some other participants might spend minutes, and this is not because I am very smart, but rather because I've seen similar concepts several times in other problems. And this alone doesn't make the problem bad, and in such situations I don't run into the comments saying than problemsetters do their job poorly.
Some comments state that the contest was too Chinese, but this is also a bit subjective. I didn't feel that it was outstandingly Chinese. Yes, one had to write some code to get AC, but in my eyes this doesn't destroy the fact that most of the problems contained some beautiful ideas or were themselves questions of interest.
A comment said that the statements were too hard to comprehend, but I didn't notice it. Oppositely, I'd say everything was crystal clear to me.
Some comments said that the pretests are weak, and this is not really nice, but it's participants' task to check their solutions during the contests. Any assumptions that you make on the quality and content of pretests, you make at your own risk!
Some comments say that the contest was too hard, but come on guys. This is not even an excuse for people who participated poorly in it (because even if it was hard, it was hard for everyone), not to say this is not a flaw of the contest or mistake of the problemsetters.
My point is that all aforementioned issues are totally minor, they don't crucially spoil the contest! There weren't any failures during the contest, problemsetters definitely did their job very well. Not to say that no problems were stolen and the contest wasn't made unrated.
Damn, why do they have -156 on the announcement? They definitely didn't deserve it.
I guess too hard A and weak pretests on B led to many newbies' and pupils' performances to catastrophe and their frustrations are expressed through downvoting (a participant who attempted only 1 or 2 problems out of 8 also have 1 vote).
But I agree that this contest is without wrong statements/solutions, long queues, plagiarism, or any other heavy troubles and concluded with success.
I'm sad with the round is overblaming because this situation may cause demotivating future problemsetters...
Never mind. It doesn't demotivate me at all.
As a problem setter, it's more glad to see you guys evaluate the round by comments so that I will know how to make a round better, rather than a useless contribution. Also glad to see you think this round was a success.
By the way, CF is used for learning and discussing. I believe those beginners who downvoted this round will eventually realize how they've learned if they are progressive, and that's enough. Who cares those know nothing but blame.
Well, it doesn't demotivate you, but it definitely demotivates others. As time goes on, I feel less and less motivated to set problems for Div. 2 after seeing how every minor issue is treated by that part of the community.
I've never set problems on CF, but it feels less and less likely that I will unless they let me set a Div. 1 only round.
I might be partly responsible for that, and I'm sorry. I just don't consider contribution on CF an important number.
But yeah, downvoting the announcement is not cool. They provided a contest, it wasn't very bad. It wasn't good either, but that's ok, not everything is good.
I got some fun reading the comment by kristin_karoline saying that you attacked the blog with a bot farm. You definitely have nothing else to do Friday evening.
Well, he obviously didn't bot, but it seems completely plausible that a lot of greens and greys saw his comment as validation and downvoted the blog.
Still I wouldn't blame him, it's not his responsibility if others behave irrationally after reading his comment.
While I also wouldn't blame him for just saying out his opinion on the contest (however, I really didn't like Um_nik criticizing the round before its ending), I guess influencers (like top-10 on Codeforces by rating or by contribution and other people who have a large audience) do have some responsibility for what they say and what they do. Each their action may result in some social response, and they should at least recognize their possible impact, what Um_nik did.
As a tester, I tried my best to make this round better, although in the end I failed, unfortunately. But liouzhou101 and his friends are great writers, I hope you can give them more support, they will do better next time, instead of meaningless downvotes, next time maybe I will help earlier, this time is a bit late . As a tester, I like the personality of um_nik who dares to tell the truth, but I will not express my true opinion on the problem in the comment area of cf.
It always seems to happen. Whenever there are some legitimate complaints about the round, it feels like an army of people see it as validation for "the round is bad". But the round wasn't bad. It was mediocre, perhaps, but not bad and doesn't deserve negative votes.
In particular this round had weak pretests. I don't see anything wrong with that, pretests are a part of the contest format. In recent years, pretests have gradually become stronger and stronger. This has led to many people expecting pretests to always be strong and see weaker pretests as "the problem was poorly prepared, the contest is trash, the setter is probably an idiot". If I recall correctly, originally pretests were only meant to be a slightly less feel-bad variation of the TopCoder system, where the only pretests are the samples and you can even submit without passing them.
While I can agree with the sentiment, I think some of the issues are more serious than you're describing.
I have heard of several people that understood D incorrectly and wasted several minutes by solving the wrong problem, so calling the statements crystal clear is just patently false. Obviously this hurts the competition and to me might be the biggest issue with the round.
The problem with the pretests is not only having extremely bad pretests -- it's why include the corner case in the first place? Why give negative numbers in B and C? It doesn't make the problem more interesting in any way, it's just a "gotcha" to fail people that forget an obscure detail of how their language works.
But bad pretests do make a contest significantly worse by allowing hacks, which are an extremely unfair mechanic. Participants are divided in rooms randomly, and you can only get hacking points based on how many people in your room made a mistake and if you are the first person in the room to start hacking. Also, if you get hacked, you get extra information that people who were not hacked do not have. Furthermore, if your point is "you shouldn't assume anything about pretests", then what is the point of having them in the first place? How much testing should you do, when you have absolutely no information on the pretest contents?
The flat difficulty gradient is a trend with recent rounds and there have been several blog posts complaining about it (having fewer problems is fine!), but this contest is definitely not the only one to suffer from that particular problem.
What's the formula of calculating which people get T-shirts?
Or when will the contestant be aware of whether he got the T-shirt or not?
I am also waiting for this. liouzhou_101, KAN?
I have been accused of cheating for problem B submission. I am sharing the pair of submissions which, according to the system message I received, "significantly coincide": 174109848 and 174107830.
Clearly the 'solve' function which implements the logic for the problem is completely different. Both codes have different space efficiency and even the method for implementing the logic is completely different. However, the basic template that has been used by me and the other guy is same. I don't think it is fair to accuse someone of cheating and penalizing them because the template matches which is clearly written before the contest starts.
When will the list of t-shirt winners released? KAN, antontrygubO_o, liouzhou_101
Congratulations to tshirts 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.