Hola, Codeforces!
We are pleased to invite you to participate in Codeforces Round 936 (Div. 2), which will start on Mar/22/2024 17:35 (Moscow time).
The round was prepared by exhausted, max0000561, azureglow and myself.
This round will be rated for participants whose rating is below 2100. Participants with higher ratings may participate out of the competition.
You will be given 6 problems and 2 hours to solve them. We hope you find them interesting.
We would like to thank:
- 74TrAkToR for coordinating the round.
- Our testers A_G, teraqqq, green_gold_dog, meowcneil, Noinoiio, sdyakonov, molney, IzhtskiyTimofey, zwezdinv, Nickir, Kihihihi, sergeev.PRO, lerasimus, 127.0.0.1, RomkaRS, makrav, Vash_nick, pskobx, VitalyKo, marzipan, zarubin, lunaTu, moniMono, xalwa, Gmix_Ivan_Zolo_57, Lelyte, KoT_OsKaR, __Foam, DamagedMoss5883, Iron_Fenix, OR_LOVe, Sonya_2009, tmari_sun, tfoppers, kuzyaa.
- MikeMirzayanov for Codeforces and Polygon platforms.
Special thanks to KoT_OsKaR and teraqqq for their help in creating tasks.
Good luck on the round and high rankings to everyone!
Score Distribution: 500−1000−1500−1750−2250−2750.
UPD: The date of the round has been changed to avoid interference with a competition on another platform.
UPD: Editorial
As a tester, this is one of the coolest rounds I've ever seen
As a participant,I wanted to have a bite from pizza
as a participant im happy to hear/read that
I have to ask: do you really believe that?
It's one of the coolest for me. Enjoyed D and solved F
yes, any other questions?
Can I have a slice of pizza, please ?
That pizza looks delicious
really ? then your standard is very low for pizzas
Why alt? Scared of downvotes?
It seems like you are the one who is scared of downvotes and deletes his comment by editing if it gets a lot of dislikes.
I am afraid of upvotes
LOL :D
As a tester, I think that this round is very nice
Good luck guys!
As a tester, I recommend you to buy computers for the lowest price
Does anyone eat pizza without sauce or mayonnaise? Anyway it looks delicious.
pizza with mayonnaise is crazy
pizza is good with ranch sauce))
Good job bois! I hope this contest will serve as a cornerstone for many to reach the heights of 1C. The best part is an afterparty in Marino. The great Holiday of Vyval is coming!!!
Enjoy the process!
pizza without toppings ??
Hopefully it is the start of 74TrAkToR's Redemption Arc
Believe me,it will
The unusual round time tho :)
It is usual time.
Ouuu my bad
They just added the Russian time lol
Which time is "Russian"?
I mean the time it's showing to me is according to Russia i.e., 17:35
Hope reach pupil after this round
GL for everyone!!!!
Good luck <3
Good luck guy
Hope everyone will get positive abs(Good bye 2023's) delta.
Hopefully mathforces❤️
sorry, but no
Phew , crisis avoided
sigmaforces
It is 2:00 a.m. and now I'm hungry 🥺
You didn't have to do this to me.
I think the timing is showing in UTC+3 for everyone
probably fixed now
I think you posted the wrong time
Pizzas and kudos to the authors for continuing the trend of attaching pictures!
It's great to see CF round's authors posting images of their daily life again <3
wow!That pizza looks so delicious!
Hoping for a pizza with positive Delta toppings...
Users on this site have pretty weird satisfaction downvoting any thing they see,even their own picture. [:
The Sigma Me ,downvotes bullet proof. AHAHAHA gimme all you got!
Yay 74TrAkToR First Round Coordination in 2024 !
Participation from India will be lower due to IPL match.
The upd says "The date of the round has been changed to avoid interference with a competition." What competition is that?
Average 74TrAkToR moment
Now I want Pizza... :)
Hope for a exciting contest <3
traktor bros going to cook us
UPD: The date of the round has been changed to avoid interference with a competition on another platform.
Which platform?
Yeah that's my question too. Can't find anything in Clist.
https://codeforces.net/blog/entry/127325
Interesting
The traktor bros are about to serve up something fierce
Good luck guys!
Ramadan Kareem
I hope that round's problems would be like Pizza !!
.
If I could get 1600 by the contest,I would be excited all day long.Try my best！
Wish you All the Best Bro, hope you will!
Thank you.Good luck!
Sorry，I'm not good at graph theory and got stuck in problem C.wuwu~
Bro，you smell so good.
74TrAkToR :(
Why do I remember it was March 21st? Did I make a mistake？
check upd
wonderful!! one small problem... I AM INSIDE UR HOUSE :3
good luck everyone :>
Seriously? Goodbye 2024 in March?
pls everyone give me dislikes! I want to have lowest contribution!
EVERYONE DISLIKE MY COMMENT! I HATE THE JUDGES, I HATE EVERYONE!
As a tester, our problems are well prepared, and as a tradition give me negative contribution. Please everyone give me dislikes!
sorry, someone took my laptop
sorry about that Sir
Ah yes, the evil maid attack.
OH OH OH OH OH OH OH OH OH OH OH OH OH OH OH OH !
74TrAkToR Round !!!!!!!!!
74TrAkToR Round !!!!!!!!!
74TrAkToR Round !!!!!!!!!
74TrAkToR is the person in the photo you ? It looks very ......
it is not surprising that such comments are left by gray authors
I think there is a problem about pizza ^-^, Good luck everyone
As one of their lecturers I strongly recommend you to participate in round! Hope you like it!
Hopefully it is the start of 74TrAkToR's Redemption Arc
Yes,brother,as you see,I am back!
Who asked?
In one of recent contests, I submitted wrong algorithm but it passed the pretest so that I got FST on it. I hope the data in this contest is difficult enough that it will minimize the likelihood of FST. By the way, I hope I can become Expert.
I'm currently unrated. Will I get rating?
As a tester who forgot to test a round for three months, this round is very cool
IPL is clashing with this contest
CF>ipl
hope to reach gm in this round!
As a participant, this is one of the coolest rounds I've ever seen
First solves:
Believe me today B and C just gave my skills a serious reality check.
congrat. !
How to solve problem C?
Binary search on the answer and greedily cut every sufficiently large subtree.
I implemented that but somehow got WA. Can you please have a quick look at my solution to see where my mistake lies? Thanks
252801186
You are updating subtree sizes incorrectly. Say a is a parent of b and b is a parent of c. You cut c and subtracted its size from b. Now you cut b and subtract its updated size from a. But a was calculated using old subtree size of b, so you didn't subtract enough. You should calculate subtree sizes during the same dfs.
You're absolutely correct! Thanks.
I had the subtreeSize method in my lib and was lazy to implement it and then missed this :)
I'm doing exactly this but getting WA2. Where is my mistake? 252806411
It's not guaranteed that the tree is given as (parent, node) pairs.
Oh my god... Thank you
But wouldn't there be too many options for cutting and each option affecting the answer ?
Suppose we are looking for some x.
A few important notes:
By removing k edges from a tree, we divide it into k+1 trees.
If we can't split our tree into k+1 trees with a minimum size of x, then we don't have an answer for x.
If we have an answer for x, then we also have an answer for x-1, but not necessarily for x+1.
If we don't have an answer for x, then we don't have an answer for x+1 either, but not necessarily for x-1.
And the solution:
Let's choose any vertex of the original tree as the root (e.g., 1). We will use DFS since it uses a depth-first approach. We will start our DFS from the selected vertex and count for how many vertices the current vertex can be the root. We will count until we have more than or equal to x vertices. We will then "remove" the edge from the current vertex and its ancestor (simply say that this vertex does not yield any vertices for the ancestor) and add this to the list of possible new trees (simply add 1 to some counter).
Why would this be the optimal solution? Because we are using DFS, we will compute for the deepest vertices first, which means we will have the closest to x and greater than or equal to it value in the current branch, which leaves as many other vertices in the rest of the tree for us as possible.
All that remains is to implement how we will search for x, and as I said, if we have an answer for x, then we have an answer for x-1, and if we don't have an answer for x, then we don't have an answer for x+1 either, which is enough to say that binary search will work.
My solution: 252786253 (I'm sorry for somewhat dirty code, I was trying to implement is as fast as I could after I found out the solution).
hi, I also do exactly like this but I dont know why I got WA :( I will be very happy if you can spend some time look through my code :) 252794634
I'm sorry but I don't understand what you are doing. For starters, you have two dfs instead of one. Also, no offense but I find your coding style difficult to read. The best I can do is direct you to my submission 252744762
Thanks for looking at my code! I found out the error alr, it is because I only cut the node when its weight >= ans and max weight of children node < ans, where ans is the answer we are looking in binary search. I shouldnt include the condition about the max weight of children nodes in my dfs1 function.
In your solution, could you please tell that in can() func, what's the purpose of checking sz >= x again (at the end)? In all provided test cases, that condition never got satisfied. Thanks for sharing your solution, btw.
Root has no parent so there is no $$$(v, p_v)$$$ edge to cut and hence I thought I had to handle it separately. However, upon further consideration, it appears that the logic inside DFS handled it just fine too since it's basically the same.
Is E based on inclusion-exclusion principle???
My solution has nothing to do with PIE. First observe that $$$p_{m_1} = s_1$$$ and $$$a_{s_1} = n$$$. Now solve the problem for $$$p$$$ and reverse of $$$s$$$ independently. Iterate over $$$p$$$ in reverse, it's easy to find the number of candidates for each position.
This was a really interesting round for me! Problem B was annoying simply because C++ % operator apparently does not work for negative numbers.
How did you solve that problem? Was stuck on it throughout the contest
My approach was to find the maximum subarray sum over a using Kadane's algorithm. Then, simply add this sum into the contiguous subarray that holds the maximum subarray sum. Do this k times, each time updating the new maximum subarray sum and you will get the answer.
Hope that made sense.
Thanks for the explanation but I was asking about how you tackled the mod operator for negative numbers.
(Got my answer, so no need to reply)
Hey, at least now you won't make the same mistake again! Many players use a library for modular arithmetic. I use
atcoder::modint, check it out.Damn, thanks
An easy workaround would be to use
(x % mod + mod) % mod. (You can write it as a function to make the code shorter)Thanks
C >>>>> D (D is a garbage problem imo, literally solved in 10 minutes, just failed to implement 3 times)
I solved C in 5 minutes but skipped D because it wasn't obvious to me. I think both problems are a bit boring but not bad for their positions in Div 2.
I didn't solve C for an hour straight (how do you prove that greedy works?).
D just felt like an implementation problem to me, not much thinking involved.
Let S be a subtree that has >= x-1 children, and all its children have < x-1 children
So cutting any of its children will invalidate the tree instantly
If you have remaining cuts to make, we have two choices
1- to cut now
2- to leave this and cut later
We need to prove that cutting now is the best option every time
Suppose that cutting now will make the tree invalid and cutting a parent edge later will make the tree valid
Remember that we have >= x-1 children right now, so the tree can be invalid only if the remaining tree without the current subtree has < x nodes, which will make any parent cut also invalid
Which contradicts our assumption, so if there is a solution for x, we should always cut once we have >= x-1 children
For each partition $$$P$$$, consider a deepest vertex $$$v$$$ where it differs from the greedy one $$$GP$$$. It means that greedy cuts edge $$$(v, p_v)$$$, where $$$p_v$$$ is parent of $$$v$$$ but $$$P$$$ doesn't. Note that it's impossible for $$$P$$$ to cut $$$(v, p_v)$$$ if $$$GP$$$ doesn't cut it.
Let $$$u$$$ be the lowest ancestor of $$$v$$$ such that $$$P$$$ cuts $$$(u, p_u)$$$. Let's exchange these edges: consider $$$P' = (P \cup (u, p_u)) \setminus (v, p_v) $$$. We gained one new good component rooted at $$$v$$$ and lost one good component rooted at $$$u$$$ (and also increased the size of some component above $$$u$$$ but that's besides the point).
Hence $$$P'$$$ is an equally good partition with a smaller "deepest different vertex". Choose $$$P^*$$$ to be the minimal partition by this criterion to infer $$$P^* = GP$$$.
C humiliated me
Surprisingly difficult C : Tree Cutting, but interesting nonetheless. I've added my hints and thought process on CF Step
3000 people solved it.
That doesn't change my viewpoint though, since I'm extrapolating from my past experiences of seeing problem C. Of course, there's bias involved.
E << C and D. I wasted too much time on C and D so ran out of time to debug E but I feel I'm close :(
Problem difficulties are always subjective. I solved C in 5 minutes but spent an hour on E because I went in the wrong direction. I had
dp[gap]= number of permutations withmax - len = gap. It has interesting but complicated updates. I thought it could be solved this way, but eventually, I gave up and found a simpler solution.Is this correct approach for D — We need to iterate over all the bits from 30 to 0 and try to merge numbers in pairs of two using DSU, depending upon whether that bit is set in x or not ?
Problem C is the reason for my headache today.
Would anyone be able to tell my WHAT is wrong with my code for problem B?
Do not mod
best_sumandsumin the loop, maximum subarray sum can exceedmod(but cannot exceedint64_t). Mod itbest_sumafter the loop.Okay, that does make sense. Thank you a lot man, I was so frustrated I couldn't think reasonably.
You are welcome but I'm a girl UwU
Yooo you just helped me on some interview problem in discord yesterday. Wasn't expecting to see u here, and thanks btw
how to not be blank on problems like E?
how to not be blank on problems like C?
can anybody tell why some test cases are not giving the correct answer : link
may you should use, fast exponentiation, you are using simple multiplication which will take O(k) time per test case...
Same issue as a few comments above: https://codeforces.net/blog/entry/127272?#comment-1131325
Thanks man
You are welcome but I'm a girl UwU
I cracked the approach for problem D, just 1 minute after, ending of contest,
would have increased my delta by a lot :(
whats idea of D?
Say we are looking for a partition into subarrays with
OR = x(instead of $$$\le$$$). Then you can only partition at positions where the prefix xor is a submask of $$$x$$$. Such partitions are monotone by inclusion, so it is sufficient to consider a small subset of maximal masks $$$\le x$$$. Namely, $$$x$$$, and((x >> bit) << bit) - 1for eachbitthat is set inx(think of it as trading the current bit for all smaller ones).Can you please explain further?
I hope the pretests are strong, cuz I passed D mostly by guessing
In today's contest I solved D but couldn't solve C.
In last div3 I solved E but couldn't solve B.
I don't know whats happening to me 😞
i found c a little difficult than usual, i don't know how it got 3000+ submitions.
telegram
??
cheaters
downvoted
got Accept D in the last 5 minutes. I regret not to use the initial idea (binary search) to solve this problem. My rank got down like 800 positions.
Why this solution fail on $th test case problem D
include "bits/stdc++.h"
using namespace std;
void solve(){
int n,x; cin>>n>>x; vector<int> v(n),bit(32); for (int i = 0; i < n; i++) { cin>>v[i]; for (int j = 0; j <= 30; j++) { int mask=1<<j; if((v[i]&mask)!=0){ bit[j]++; } } } int curr=0,ans=0,pre=0; for (int i = 0; i < n; i++) { curr^=v[i]; int post=0; for (int j = 0; j <= 30; j++) { int mask=1<<j; if((v[i]&mask)!=0){ bit[j]--; } if(bit[j]%2==1){ post|=mask; } } int temp=curr|pre|post; if(temp<=x){ ans++; pre|=curr; curr=0; } } if(ans==0 || pre>x || curr>x){ ans=-1; } cout<<ans<<endl;}
int32_t main() {
int t = 1; cin>>t; for (int i = 1; i <= t; i++) { solve(); } return 0;}
3000+ solve on c and I am not one of those geniuses.
Am I the only one whose confused about the problem B's statement?
What most people have done is take the maximum Subarray Sum using Kadane's Algo in the beginning and then just keep on taking that subarray along with the present added element using operation.
My question is: Won't the subarray become bigger as we keep on adding elements and then the entire array would be taken at once? This, in my opinion, would WA every solution.
i think taking whole array will reduce the max sum.
because if you take full array sum would be lower than the smaller size one
Leave it at this point. I don't even know what the hell I'm doing these days. Thanks for helping me out!
Suppose at some moments, you choose to get a bigger array. Then the sum of elements which you extend will be larger than 0. However, if that happens, which means the initial subarray you choose by using Kadane algorithm is not the optimal one (since it will be better to extend that subarray with those elements).
...select any contiguous subarray of the array a (possibly empty) and insert the sum of this subarray anywhere in the array.. So, you will put that subarray sum in the main array and continue to do the same.no, I thought it was problem of maximize (sum mod 1e9+7), i.e maximize answer itself, not find the max sum then take mod 1e9+7.
A -> Simple sorting and sum
B -> Kadanes algorithms and then fast exponentiation
C -> Binary search on answer
D -> could not do during the contest :(
In B, O(k) is enough to pass, doesn't need fast exponentiation tho
but k = 2e5 , test_cases = 1e4
total -> k*t = 2e9 , may pass may not pass, better to extra safe when exponentiation
The sum of k over all test cases does not exceed 2e5
It is guaranteed that the sum of the values of $$$n$$$ and $$$k$$$ for all test cases does not exceed $$$2⋅10^5$$$.
I did not see that, I assumed they will try to fail on fast exponentiation.
please help me understand this, k can be equal to 2.10^5 right, isnt that 2e9 complexity, isnt it guaranteed to TLE?
Sum of all $$$k$$$ in all test cases together is limited to $$$2⋅10^5$$$
If you will have in some test case $$$k = 2⋅10^5 - x$$$, in all other testcases $$$k$$$ can't be greater than $$$x$$$
Sum of all k in all test cases together is limited to 2 * 10^5
If thats the case what the complexity? I thought it should be strictly <= 10 power 8
We are talking about calculating $$$2^k$$$ with a cycle instead of a binpow
requires $$$sum(k)$$$ for all testcases
requires $$$sum(log2(k))$$$ for all testcases
"It is guaranteed that the sum of the values of n and k for all test cases does not exceed 2*10^5."
please help me understand this, k can be equal to 2.10^5 right, isnt that 2e9 complexity, isnt it guaranteed to TLE?
I got in too late and couldn't even solve the first problem :(
can anyone please look into my submission: submission thank you
Your code does not sort the array anywhere hence median in cases with 3+ elements is wrong
No no it does
In the case for n=2, output should depend on wether array[0]==array[1]
Hence, it gives wrong answer for testcase 1 1
thanks man!
Can anyone help why my code is not correct??
I am checking at every index if the bitwise or of bitwise or of previously made sections and xor of right section is <=x, if yes I am incrementing the answer.
Just blame it on Problem B and C, they're the brain-busting culprits of the day.
Can question B be done without kadane's algo? something even simpler maybe?
Since freedom of place of insertion is given, I guess the greedy approach (kadane) is very intuitive.
I believe that Kadane's algorithm is the simplest way to solve this problem. All other approaches I can think of have higher complexity (from the O(n) Kadane algorithm to O(nlogn) D&C, Segment Tree, etc. and O(n^2) brute force) and, in fact, harder to understand and implement (even brute force)
Ahhh i see, i was thinking maybe i am over complicating things by using kadanes for this question, turns out it was fine. thanks for the reply!
You're welcome
you can do it using segment tree actually there is a part on edu section explaining it (its on segment tree part 1 — step2) but its not simple at all
i solved it with o(n) dp u can check it outsolution
fuck me.
forgot to mod the maximum of the sum of contiguous subarrays and i had no clue about how it would cause wa on test 3.
not trying to complain here. it's just that next time you see me i be gray.
Same mistake brother
I solved D in 15-20 minutes, spent a hour on C and still have no idea.I suck at Binary search.
What is your idea on D
Problem ABC : Simple greedy.
Problem D : Bitmask, and it's a bit harder than my expectation.
Problem E : Ridiculous problem which can be placed at div.2 C in former contests.
Problem F : Just a trival DS problem.
So what's the cool point of this contest ??? The unreasonable difficulty distribution?
The cool point is that you are using alternate account
It probably isn't an alt, he just registered late on CF.
in E I boiled down the problem to the following expression
SUM(product(ai)) for all expressions such that we can reduce 1 from aj and add 1 to ai any number of times subject to constraints i<j. example
expression -> 4!2!2!3! we can have the following expressions 4!3!2!1! or 7!0!1!3! but cannot have 3!3!2!3!
how to solve it further.
PS: SUM(ai) is bounded by n (2*10^5)
Do we have any graph solution for E?
That's probably the worst round I have participated in for a long time.
why
Because the answer is too obvious for you?
please shut up, Huym_nik
The pain in your comment. Stop being envious of gifted people, it's not his fault that you're not gifted enough to be a red coder, please cry harder.
He was saying that because Um_nik didn't give constructive feedback, or tell them how they can improve, he just said "trash round u suck", which is not a good thing.
Gifted gray writes smart comment, omg!!!
That's probably the worst comment I have read in for a long time.
Sir, In this community everybody wants a Constructive feedback from a elite level/Rank holder like you. Then why are you promoting a Amazing level of Worst Feedback!
Hope u are safe.
Bro, I think you should practice a little bit. It's not you who are stupid, it's just that the tasks are difficult
Are you teaching a Great White Shark how to swim !!... x_x
-100 delta lets goo
lezgoOOooO
man i literally did the same error as you, just taking mod one more time would've been enough . That too so much time was left after B , failing system test is rough.
Did not like it.
Cool contest! This is one of my worst performances recently :(, is F intended complexity n log n? I wrote a n log^2 n solution and TLE'd by a constant factor...
My $$$n \log^2 n$$$ solution passed, although I think it is good constant factor because all I'm doing is adding and multiplying things (mostly adding though). I also included pragmas.
for problem F, i passed pretests, i can't pass pretest on system test, please rejudge, thank.
Sorry for my poor English
I can pass the system test under C++20 (GCC 13-64) https://codeforces.net/contest/1946/submission/252811990
I hope you can give me AC
Didn't notice that C++20 has came back LOL
https://codeforces.net/contest/1946/submission/252811990
Pass pretest with remained time <200ms means TLE on system test mostly.
can anyone explain what's wrong with my code Solution
As you can see on the checker's verdict: wrong answer 30th numbers differ — expected: '1000000004', found: '-3', you aren't handling negative numbers under modulo correctly.
Thanks Bro
Problem D shares the approach with a problem on HDUOJ 2 weeks ago: (Chinese)
D. Legal Pairs
(I personally do not recommend this OJ from my experience in this contest: the statements were unclear and there had been serious queueing issues)
it's just for me? I just intuitively unclear on how applying Kadane's algorithm once is sufficient to get AC (problem B)
isn't max subarray sum varies every time we insert max subarray sum? because since max subarray sum become larger so that it may include elements on left and right side that were originally unable to include?
Yes, it's not trivial to see, but also not difficult. I asked aryanc403 to elaborate on this in his stream. Timestamp
The crucial idea is this. If the maximum sum subarray looks like
Then, all the extensions to the left or to the right have a net negative value. (Otherwise, you could use that extension to increase the sum).
Now, suppose you place the incoming $$$S$$$ at a different position, like so
Then, the max sum now is $$$S$$$ + middle + $$$S$$$. But we know that the middle extension will be negative, so it's better to keep it like so
Even in this case, the maximum sum subarray would not contain any extensions to the left or right. Why?
Hence, the maximum sum subarray is $$$2 \cdot S$$$.
Hi, for problem B
5 1 4 -2 8 -12 9
In this test case, we add -12 in the first operation like this 4 -2 8 -12 -12 9 then sum will become -5 if we take the modulo of the -ve number then and would be 10^9+2 why the correct answer 17 here? please explain.
how to solve E?
Can someone explain why this solution does not TLE? I tried to hack it during the contest, but I couldn't. It uses a memset to reset memory in every test case, which is O(T*MAXSIZE). Does the compiler make some optimizations somehow?
Liked the round overall, D is an extremely nice problem, and i liked F too.
Nevertheless, pointing out some issues : BC are both boring and imo not correct for their spots. Tree dp + binary search, and kadane's algorithm really dont fit for the 2nd and 3rd easiest problems, and also are quite standard.
F TL??? the fastest solution for F is merely 2s..... and i had to do quite a bit of constant opt to fit the TL (tho i wasnt using pragmas, my fault ig). Please make TLs more lenient. I dont see why n needed to be so large. Is there some bad solution?
I liked E too, but i think the ideas behind it (and maybe even the problem) have occured before, because it looks standard, but if not, then nothing against it.
I would request round authors to kindly not put standard tasks in BC positions. Again, thanks for the round.
It's not relevant but I love your previous round. Expecting your rounds in the future
Why do people love calling every problem which is not ad-hoc — "standard"? ....
Because the problems are standard....what should i call them instead?
There are ofcourse non ad hoc problems which are not standard, but ad hoc problems by definition cannot be standard.
in F we have $$$O(n \log^3 n)$$$ solution that works in about 6.5 seconds with proper optimization, so in order to cut it we made TL 6s and big $$$n$$$ and $$$q$$$ limit (to mention our $$$O(n \log^2 n)$$$ solution works in 1.6s without extra input optimizations and stuff like pragmas)
I think a particular bad solution I think they wanted to weed out was solutions like this one: 252793752, which has complexity $$$\mathcal{O}(n \log^3 n)$$$, I think? Optimizing it was one of the harder and more beautiful parts for me.
EDIT: bruh sniped
I opened problem C, turned off my laptop and went to play basketball( Thanks for the contest! A and B were cool.
Bro really has a healthy lifestyle
I love Winston Caster
Nice contest with ultra cool tester...
nooo
The ratings are updated (lightning fast rating changes).
My F code took about 1s in the AtCoder code test, but it took 4s in the CF code test (almost maximum case).
Again, I think it's best not to hold a contest until C++ is completely fixed. I think it will surely be ruined due to constant factor in the near future.
Bad round. Don't ever cook again.
I tried solving D with a different approach, getting wrong on pretest 2 but cannot find the error.
My approach was to split the given array again and again till it satisfy the three conditions, while iterating through the array:
as soon as any subarray satisfy these condition i increase the counter and reset ans variable to 0.
my approach might be wrong, I will be glad if anyone points out my mistake
here is my code
Bro you can send the code as a spoiler or as a link
Upd:Thanks for listening me<3
void solve(){ int T; cin>>T; while(T--){ int n,x;cin>>n>>x;
vector<int> ayo; vinput(ayo,n); // to input the vector int mini=0; vector<int> suf(n); int su=0; for(int i=0;i<n;i++){ // created a suffix vector with xor su=su^ayo[n-1-i]; suf[n-1-i]=su; mini=mini^ayo[i]; //calculated minimum value that can be obtained (xor of all the numbers) } if(x>=mini){ //minimum value should less than equal to x int ans=0; // xor of all the numbers with current set int count=0; //number of sets with which i will take OR int prim=0; // store the OR with all the previous pairs; for(int i=0;i<n-1;i++){ ans=ans^ayo[i]; if(ans<=x && suf[i+1]<=x && (prim||ans||suf[i+1])<=x){ prim=prim || ans; count++; ans=0; } } cout<<count+1<<endl; } else{ cout<<-1<<endl; } }}
Because it fills so many places
is hacking phase open or it was withu=in contest??
Can someone help me? (I got in the contest very late dont judge pls)
A. Median of an Array:
Out first test: 1 2 1 3 1 1 1 3
nvm I think I got the whole idea wrong
Is it possible to solve slight variation of B, where instead of max(sum) modulo 1e9+7 for an answer, max(sum modulo 1e9+7) (way harder, i think)
that would be orange problem or purple at least
In problem F my $$$O(n \log^3 n)$$$ passes but $$$O(n \log^2 n)$$$ with unordered_map gets TL 7 🤡
252809693 and 252810082
can anyone explain why? is u_map constant that bad? I'm confused
(as a side note: choice of constraints in this problem is dumb, at least ML could've been 1024mb easily, but I would also decrease limit on $$$n$$$ and $$$q$$$ for $$$3 \cdot 10^5$$$ or something)
Refer to this blog/entry/62393.
I don't think this is a reason in this case
Sadly,they still failed to cut all the $$$O(n\log ^3 n)$$$ solutions.
Why you didn't write what is permutation of length n in F's problem statement?
problem C mega sexy
Why am I disabled by admin?
Yesterday I signed up for my codeforces account FromOceans, Then I participated in a contest (it was "Codeforces Round #936 (Div. 2)"), and the next day I logged in with my account only to see "disabled by admin"?? I didn't cheat in the game (I can publish vscode's timeline if I need to), nor did I do any DDos attacks on the website?
I don't know where I'm supposed to post, and the account I signed up to explain doesn't seem to be able to post, only comment under existing posts.
If there are any errors in English grammar, please point them out.
How can I @ admins?
MikeMirzayanov
C was great
What is this 252777884 Pq_oqtg_96VtCmVqT_tqwpfu
I get WA on test 2 (problem C) but the test is too far for me to debug. Can anyone tell me the wrong case with this submission: https://codeforces.net/contest/1946/submission/253016060. Thank you
74TrAkToR About my problem of being rechecked in code https://codeforces.net/contest/1946/submission/252762903, most of which I have written in https://codeforces.net/contest/1914/submission/238131112, all the changes in which only add binary algorithm,In this problem, everyone is going to use this algorithm， this is just a coincidence, can you cancel my punishment
MikeMirzayanov
After slove problem c, I have been dealing with problem d, and the other side has also handed in a wrong code about problem c, which is enough to prove that the two of us did not copy
MikeMirzayanov If the other party has my code, then it will not be wrong in a simple place, and then change to the same code as me, I think this can prove that our code is written by ourselves, I hope to re-check our code, our code is different in many details, but it happens to be similar to what is written on the outline, please please re-check the code between us, revoke the punishment about me, thank you https://codeforces.net/contest/1946/submission/252762903 https://codeforces.net/contest/1946/submission/252777912
I am innocent but codeforces blame and they took the cheek of my rating and even did not count the contest. I just want to codeforces that : "Please! Give my rating back".
253431622 I met a very strange problem in B,I almost wrote the same code in the turoial,but I received many times wrong answers with the prompt the the solution is executed with error 'signed integer overflow',I used long long and it doesn't work,why?
It was an amazing round!!!
266117318 anyone plz tell where I am doin wrong
this round changed my life!
big thanks to developers for this hamster combat