Hello, Codeforces! Or, as we like to say in Romania: Sus Sus Sus, ca la Strehaia tată!
I am glad to finally invite you to participate in Codeforces Round 875 (Div. 1) and Codeforces Round 875 (Div. 2), which will start on May/28/2023 17:35 (Moscow time). In both divisions, you will be given 6 problems and 2 hours and 30 minutes to solve them.
The problems were authored and prepared by Andrei_ierdnA, Doru, Gheal, IacobTudor, LucaLucaM, RedstoneGamer22, SlavicG, Sochu, alecs, andrei_boaca, andrei_iorgulescu, lucaperju, valeriu and me ( tibinyte ).
I would like to thank:
- errorgorn, for his wonderful coordination.
- irkstepanov for further help with logistics of organization.
- Alexdat2000 for russian translation.
- alin_gb18, rsj, dario2994
jampm, Psychotic_D, prvocislo
cristi_tanase, atodo, BucketPotato
Moolamp, magnus.hegdahl, Gary2005
Geanina_the_Great, erkam, PurpleCrayon
Um_nik, gamegame, conqueror_of_tourist, penguinhacker, AlexLorintz, lucri, _Vanilla_, Vladithur, status_coding, Luci_badea1000, bycicle, myvaluska for testing the round and providing useful feedback.
- freak93 for no morning refreshment.
- MikeMirzayanov for great platforms, codeforces and polygon!
Scoring Distribution
div 2: $$$500-750-1250-1750-2500-3000$$$
div 1: $$$500-1000-1750-2250-3000-3500$$$
The editorial has been published here!
And here are our winners!
| # | Div 1 | Div 2 |
|---|---|---|
| 1 | Ormlis | kotrin |
| 2 | 1a2b3c4 | CLOCKS_PER_SEC |
| 3 | dorijanlendvaj | IHatePaiu |
| 4 | tourist | Lihwy |
| 5 | Radewoosh | VietCek |
As a non-newbie, I miss being newbie :(
As a specialist tester, i specialist tested.
yo teach me your ways
This may be a way of speaking for the question group. They may be saying this in another way to wish us a better ranking!
as a newbie, i wish i will become like you
As an average tester, I average tested.
As an average setter, I average setted.
As an average solver, I average solved.
As an average setter, I haven't average setted.
As an average setter, I haven't average setted
as i walk through the valley of the shadow of death
I take a look at my life and realize there's nothing left
eminemforces
you all act like you never seen a white person before
No racism here
things are getting a bit out of hands
As non-setter, I haven't setted at all.
i see pepe, i press upvote
As a non tester, I didn't test.
As a specialist competitor, I'll compete specially.
As a bad tester,I tested like good tester.
didn’t Mike say you can’t put the wrong colors for usernames?
Get a life?
can't :D.
sadface.cpp
Anything is possible if you put your mind to it :D
sus
As a setter, I didn't test.
Cringe! Just make regular announcements
I am a simple man: i see pepe the frog, i upvote the blog
Why so few authors? What happened to the rest?
We were asked by the Codeforces admins to shorten the author list.
Wasn't everyone's name colored grey initially? What happened?
Practice, hard work, and dedication.
Only 14 authors :D
As a pupil,IDK why I like to watch grand masters.
All problems are tricky but good!
nvm typo wanted to reply to someone else
ok
OMG PEPE EMOJI!!
Kind request to question setter. Please try to keep,
1) questions are balanced,
2) different topics ( rather than one single topic ),
3) cover largest input and longest run time test cases and yet keep one or two edges cases so contest could be fun with hacks.
4) give clear explanation for the example test cases.
" keep one or two edges cases so contest could be fun with hacks "
Its not fun for the guy who gets hacked.
true. but it gives you the feeling like ICPC.
You may think that you have solved problem, but it could fail final system testing.
Also, when we have left very little time left and we cant solve/implement problems anymore, it is good to try to hack.
UPDATE :
There is some misunderstanding, I failed to clearly pointing out that hacking and ICPC aren't related. Personally I find weak pretests or excluding edge cases very enjoying. Also, if pretests are passing, then there should be some suspense whether final system test will pass or not ( like an ICPC ) .
Feeling like ICPC? Who told you that there is system testing in ICPC?
adityagamer , I dont know if they changed it recently or not.
But this is what I know about ICPC finals,
https://youtu.be/kIbgLrquTx4?t=31411
https://youtu.be/15Wyj_-PG9I?t=30869
That's not hacking. The scoreboard is frozen near the end of an ICPC competition. Those clips show the scoreboard being unfrozen after the end of the contest. The yellow submissions are ones that were submitted in the last hour when the scoreboard was frozen.
I didn't say its hacking. I said, some of the submissions could fail final system testing, if edge cases are not considered in pretests. adityagamer said, there is no system testing in ICPC, but I guess, there are few pending problems which are done tested after the contests.
All I am saying is,,, there should be some suspense after the pretests, whether the final system testcases will pass or not.
Of course there is no hacking in ICPC, I never said There is hacking ICPC.
Please reread comment above and stop being annoying. If you're unable to see that there's no "system testing" in ICPC (it's clearly explained in Erekle's comment) then don't even start/continue conversation.
man got 300+ downvotes from a single comment thread
ratings or downvotes, does it matter ?
to some extent, yes (30%) for me
great thinking, rating and contribution don't matter on codeforces. Contribution doesn't since it's ratist community and rating doesn't since you get nothing to show for it
We've started working on the round over half a year ago and we most likely won't be making radical changes one day before the start of the round.
I hope you enjoy the round regardless :thumbsup:
Yes agreed. makes sense, not to change testcases-files or any other critical data.
But, problem statements could be changed ( for better understanding, or test cases explanations could be changed )
Are you implying that we made a conscious effort to make the statements hard to understand?
!!!!!!! I have clearly stated that, ""for better understanding"" .
Do you really think that you are giving something new for community with this comment? You are just saying obvious things.
1) Do you really think that you are giving something new for community with this comment ?
No, I am not giving SOMETHING NEW , but I am reminding something which is OLD AND GOLD, which recently most of the question setters have forgotten in past consecutive contests.
If these things are obvious things, then why question setters are not doing what is so called OBVIOUS ?
You will understand it by yourself just when you will become a problemsetter. You advice is just "make a good contest, please". It is obvious.
For example, the balance of a contest is subjective and thus cannot be measured by authors and coordinators. One need dozens of testers to make a balanced round.
And also. Imagine you have a slightly unbalanced round. What will you do? Throw away one or two tasks and try to come up with another tasks?
Your problem is that you think that coordinators or problem-setters are incompetent in some way. It's better to try to approach your questions in another way: why the rounds are like they are now? Which things I don't know and don't understand about problemsetting?
All the best to heard-mentality-crew... have positive delta... xD
The contest clashes with the leetcode biweekly contest 105. Please do something about the timing :)
Update
As I can see my comment has initiated a spread of hate towards a certain platform in the thread, I would like to clarify that we live in a world of free will, thus anyone can opt to give either of the two contests according to their preference. I'd myself choose the codeforces contest due to the better quality of questions. My comment was only intended to make the round makers aware of a clash between the two contests and nothing else. Finally to everyone, who blindly downvoted my comment due to their specific hate for a platform just shows their herd mentality. Rest I hope for everyone to have a great performance in the contest.
Get your prioties straight. This contest doesnt clash with leetcode biweekly, leetcode biweekly clashes with this.
Exactly! Leetcode problems are easy. Codeforces is the real challenge
I was just commenting to let them know. No need to get so worked up about it :)
don't be rude, the guy just wanted to write both contests, and you told him to forget about it
it was a joke
Guess time to prioritise leetcode now
Thy wish has come true
As grey. I hope be specialist next round uWu
As a <newbiw i wants to give the round
As a participant, I like participating.
leetcode biweekly + div2 both tomorrow. But everyone gonna choose div2...
LeetCode is not real CP
omg grey round!
longest duration contest 2:30 hr.
It's not the longest, there were several contests that lasted 3 hours.
Yes, but many 6 problems div2 contest lasts 2:15 hr.
Can anyone please give me advise? how can I practice hard problems(like 1600+ rating) so that i can solve problem D,E within the contest time? I am trying to up solve but feeling so hard. What strategies can I follow? Thanks in advance.
I completely ignored the fact that the blog writer has a -14 rating
actually he got negative due to hacking. he was expert.
Wow! A negative-rated author! Hopefully, enjoy this round (❁´◡`❁)
As a contestant, i am waiting...
What is "Scoring Distribution: TBD"?
TBD = to be determined
Thanks!
tibinyte Orz
Good Luck for everyone
vuw
Vuw
Vuw
Vuw
Vuw
Sniff sniff, i smell AmOnGuS!!!
sus
Is this Div2 rated for participants with rating < 2100 ?
You can only participate in div 1
isn't div. 2 open for CM? It's neither a combined round
Yes. A CM can participate in either div2 or 1 and have EDU round rated for them.
Edit : But not in a div 2 within a separate div 1 — 2 round unless he registered when he was still expert.
For rounds with separate Div 1 and Div 2, CM can only participate in the Div 1 round
Are you sure about this? I usually see CMs profiles and have rated div2 in contests history even after being CM. Anyways, I registered for the div2 when I was still blue
Edit : Upvoted. I think you're correct. I had a look over some random pages of the common registrants for the div2 and I rarely found a CM registered. The ones registered did so when they were yet expert.
whaaa.. What's your source for that?
Based on at least 100 or so rated rounds in the past two years, and also if you check the scoreboard for the Div 2 rounds that had an accompanying Div 1, there are no CMs. IIRC, Mike or other system managers manually removes CMs from the Div 2 registration or smth.
thx for your reply. This seems highly confusing and inefficient. I bet it'd make waves but ffs make CMs div. 1 or div. 2 only
damn where scoring distribution? is it soo hard to publish it at least 1 day before the round? why almost nobody does that now...
Don't know why, but I never care about scoring distribution O.o
Same. Still, a bit strange to not see it one day before the contest. The authors have been preparing the contest for months, why couldn't they use a few minutes to write the points distribution?
Always welcome weekend rounds :) First rated contest for me in a long time.
fighting!!!
good luck everybody!!!
Anything is possible if you put your mind to it :D
Timing clashing with Leetcode Contest :(
Maybe I won't be allowed to wait until summer vacation, let's go tonight！
who let a negative rated guy set problems 😡
the real question is,,, Who let the dogs out...
who.... who... who.... who.... !!!
sorry it was me
Is this round is rated?
Yes
Good luck everyone!
I hoep everyone will get good marks in this contest. Good luck!
MikeMirzayanov please postpone this contest , today is IPL final , Probably dhoni would be playing for the last time today and everyone wants to see him. Please Postpone the contest Gheal
set your priorities straight. Mike and the codeforces team isnt here to please everyone with their contest timings and the contest will not be rescheduled for such petty reasons
Finally BCCI postponed IPL
CF>> IPL, even god postponed the IPL Final to today so that we can enjoy both!
RescheduleForces!
(()def()r(es??again?
Please, if the round is postponed also this time, try to tell it earlier
Good luck
I'm crossing my fingers and toes, hoping I don't plummet from my precious blue rank in today's game. It's a delicate balance, you see—I'm teetering at a hilariously precise 1601 points. Wish me luck!
don't cross your fingers, otherwise you won't be able to type)
Wish me luck too!
CSK match >>>> CF contest :) feeling sad because not going to participate in this round
why are you sad when your comparison has
4 >bruh now I am very very sad Na match dekh paya aur na contest de paya :( contribution -6 ho gaye wo alag
same with me , but no problem tommorrow we would see the one and only legend msd lift the IPL trophy
Should have given it. Better than watching rain :)
Lol it rained
Best of luck to me :)
I was registered for the contest when I was an expert. But I just noticed that I am a candidate master, but registered for div2. I think it would be better if the system would inform you about this.
Just as former world champion Magnus Carlsen won the recent chess tournament and came back again at the top, tourist(Gennady) should also try to get his first position back today :)
+76 is needed for CM. is it possible??
why are you asking me
WTF 1053 problems solved for the last month?
Problem B be like, you hurry up & I'll give you a penalty! :)
tourner dans le vide
Problem B is s*ck
FSTs loading...
nice round,but i forgot something and got lot of wrong:(
Div 2 contest exists Easy ass permutation problem be like: Did you miss me?
XD
Really dissapointed by B problem (Div. 1). There is 4 sec TL, and my $$$\mathcal{O}(n\sqrt{n})$$$ solution with hashmap doesn't pass. I tried to optimize it many times, using fast hashmaps, different pragmas and other methods.
Judging by standings I can conclude that I'm not the only one with this problem. But some people have achieved +5/+10/+20, others not.
TL 4 sec implies that $$$2 \cdot 10^5 \cdot 650 \cdot [hashmap time] = 1.3 \cdot 10^8 \cdot [hashmap time]$$$ will pass!
If author's solution has another complexity TL must be 1sec. If author's solution is just 2 times faster for example you can't ban people with $$$\mathcal{O}(n\sqrt{n})$$$ solution — this is not Codeforces politics.
So, AB were good tasks, C was interesting too, but I just waste all time to speed up B, it was terrible round.
just don't use hashmap lol
I have ML without it
I need $$$[650][2 \cdot 10^5]$$$ array of $$$32$$$-bit integeres. This is $$$4$$$ byte $$$\cdot 650 \cdot 2 \cdot 10^5 = 520000000$$$ byte = $$$520$$$ MB.
Since
j < SQin your solution, you can create an arrayint[SQ][n+1]. Just don't access the array if the second value is not in the range [1, n].Also you only need to clear n elements between test cases. Here's my submission: 207611902.
I spent around 1 hour switching between unordered map, gp_hash_table and cc_hash_table and trying various optimizations to remove TLE and MLE :/.
In the last 5 mins, I replaced it with a binary search on a vector containing deduplicated pairs, and their count and got pretests passed, though I still expect TLE during systests.
Sometimes it is faster to just use regular (tree) map and check whether the element exists in the map before accessing (avoids unnecessary insertions). Not sure if this was intended though.
Is it still possible to increase the time limit and rejudge submissions at this point? I'm another affected participant who tried messing with
unordered_mapand stuff which didn't work, while some solutions that just used binary search instead ofmap(207592515, for example), which should have the exact same complexity, passed.Try a stronger hash function
lowerbound in vector works faster than hashmap in this kind of problems, from my experience
Decided to optimize D at the last second(after 1hr of being indecisive XD), it changed runtime from 3700 ms -> 1700 ms. But idk if it's actually just weak tests. Try hacking it 207664263. This problem would probably have many TLEs.
UPD: Turns out the initial 3.7s solution TLEd, but this one still passes in 1.7s
How to solve B div1/ D div2?
For the problem C do we have to use DFS? If anyone have use DFS to solve please can you share submission link.
207591419
Lol i did knew about DFS bit but didn't actually know well so i was watching a youtube video and implementing side by side. But at end i got TLE on pretest 3. Submission
Not sure if it will pass system tests: https://codeforces.com/contest/1831/submission/207626584
div1 B too easy to come up with a solution but constraints too bad, it spoiled the contest for many people. Almost solved d1C, i think, could smb please write the solution? wanna check if mine is correct
I am not sure about B constraints, I wrote the first thing which came to my mind and it passed in 2.1s. It's not optimal, surely it can be easily optimized to 1.5s and probably to <1s with some effort. But tbh I am not completely sure it will pass systests, I did not prove complexity. Upd: passed systests in 2.1s
Regarding C, I did not solve it but I think one of the important insights is that any 2 intersecting (but not nested) segments [A;B] and [C;D] can be replaced with 3 non-intersecting segments [A;C) [C;B] and (B;D]. Then we can somehow remove all intersecting segments and solve a much easier subtask where segments can be only nested (build a tree from them).
Yea I'm kinda bummed out because for d2D/d1B I had a java solution early on that got TLE, and I tried a lot of things but just couldn't get it under the TL. Then I converted the same code into c++ (which I barely know) and it passed, but by then I already wasted 1+ hours.
Can anyone tell me what is wrong with my code for div2C (sorry its java lol): https://codeforces.com/contest/1831/submission/207667860
Great Contest! If you are stuck on Problem A, Problem B, Problem C (Div2) then this editorial might be helpful: link
Great explanation for C. Finally got it.
how to solve D?
idk
Bruh
you need to use the fact that the values of a[i] and b[i] are less than "N".
So, for each pair (a[i],b[i]), we have to traverse till sqrt(N) at max, and see if the reverse pair exists or not.
first of all, shard the pairs(a[i],b[i]) based on the first value (a[i]). Also sort each shard for applying faster search operation using binary_search.
We also need to keep track that how many times particular pair has been encountered in past, to do so we need a map < pair <int, int > , int > where map[(x,y)] denotes, how many times particular pair (x,y) has been encountered yet.
Core logic part is here now, suppose (a[i] , b[i]) and (a[j] , b[j]) are expected pair, then we will
a[i] * a[j] - b[i] = b[j], for better understanding I will use (x,y) and (p,q) instead of (a[i],b[i]) and (a[j],b[j]) from now on. so, (x*p — y == q) must hold in order to count the pairs.if shard[x] has value 'y' in it, that means, we have a pair (x , y) somewhere. Now, any pair (x , y) and (p, q) to be in the answer, we must make sure that
x * p <= 2*n, otherwise answer is never possible ( because of the restriction that 1 <= y <= n && 1 <= q <= n,,, their sum will be 2 <= y + q <= 2*n. ) , that's why x * p must be less than 2 * n ;So, now using above facts, please go through code,
Wow, thanks a lot, pretty cool solution. I was close to it during the round, but wasn't able to write exact solution
Edit: Oops, forgot checking by [] creates the element if it isn't already present. These unnecesary inserts and increase in query time due to map size probably leads to a 2-3x increase in running time leading to TLE.
Does gp_hash_table really use $$$\gt 500MB$$$ to store $$$2 \times 10^5$$$ elements????
gp_hash_table to store pairs (207666127) -> MLE
binary search on vector of deduplicated pairs (207666127) -> AC with 10KB memory usage
Also is there a faster than $$$O(n \sqrt n \log(n))$$$ solution to Div2D / Div1B? I spent like 1 hour optimizing it to remove TLE and then MLE T_T.
$$$b_i\le n$$$, so you only need to maintain a bucket with size $$$n$$$
Oh so since $$$a_i \leq \sqrt{2n}$$$, you just maintain a $$$\sqrt{2n} \times n$$$ vector for counts which fits in around 500MB of memory?
no, you enumerate the a_i which is $$$\le \sqrt{2n}$$$ (assume that is $$$v$$$), and you only need to maintain a bucket with size $$$O(n)$$$ (which is also $$$O(n)$$$ in memory) to calculate the occurrence of $$$va_i-b_i$$$. After that, you clear the bucket.
Every time you search in a map / unordered_map, if value you are searching for is not present, it always creates new element for it. So it is $$$O(n\sqrt{n})$$$ memory if you use them.
Thanks, I forgot that. Thats also likely a significant reason for the TLE T_T.
I do think there's no need to set the memory limit to 256MB instead of 1024MB. It is trivial to optimize the memory of knapsack on tree to $$$O(n)$$$ my storing the dp values into the return value of dfs.
What is second test case for D?
Is it possible to solve F by SMAWK + persistent segment tree?
I see, maybe it needs to be some online version of it?
Confusing Round. C is a good problem.But B is just a Trash.
As an average coder, I average code, but I'm not average here.
with the whole army of testers and setters the pretests are still this bad + stupid constraints.
Had the new idea in the last 15 minutes. My heart can't handle this.
what's the new idea ?
How to solve div2 C?
Link
Finally a good contest and not Speedforces. B was so time-consuming tho.
Judging by the number of people upset over Div2 D(Div1 B), I doubt the editorial would be satisfying(though I expect to learn something different/new). Still would love to know any approach that worked for you guys. Was stuck on this problem for 2 hours :(
My approach was to split everything into buckets by A. Then we need to iterate through small buckets (A <= sqrt(MAX*2)) in an outer loop because otherwise, a*a will be too large and iterate through all buckets in an inner loop.
At each iteration, calculate the answer for pair of buckets. To do it efficiently, sort elements in buckets, and use the smaller (by the number of elements) bucket as a needle and the larger as a haystack, do a binary search to find the number of matching elements.
Also, we need to match every A <= sqrt(MAX*2) bucket with itself but it is fast so can be done in a variety of ways.
I think my submission 207627709 is pretty clear but I am not sure if it was the supposed solution. Passed in 2.1s, probably could be optimized to 1s.
I thought about the exact same optimization during the contest but wasted too much time trying to prove its worst-case time complexity. Here is my submission 207739872 after the contest. I still haven't figured the time complexity part yet. Do you (or someone else) have any insights?
Don't know why but I thought that there will be edge from u to v and not from v to u and treated the graph like a directed graph which resulted in a bad contest
This is the moment that I am very nervous about system testing. I solved problem div1 C in the last minute. If any of the div1 B and C passed, I will reach master! Please, don't FST, don't FST, don't FST.
UPD: I passed B, and I will reach master.
UPD again: Yes !! I passed C. In my estimation, problem 1C problem have a difficulty of at least 2300, and this problem will be the highest rating problem I have ever solved in contest.
Congrats! What extension do you use?
congrats
Congratulations
in problem C , my idea was build a normal tree, and if there in a level at least one node that became upove the parent I increase (reading) by one . is this idea wrong ?
Seems that many people passed pretests on D with 500MB of memory (me included). Could it have been a good idea to increase the memory limit to 1024MB instead?
That might've been an unintended solution, in which case the memory limit should've been 256 MB. I also passed Div.1 B with 506 MB, just hoping for no FST (although it seems very likely)
UPD: Luckily I didn't FST. Although I believe that the solution might be hackable.
Well, the editorial solution seems to use the same idea as mine, maintaining a large 640x200000 array. I don't know much about memory but it should probably use a similar amount, unless arrays use up significantly less memory than vectors.
Afaik, arrays don't use (significantly) less memory. I realize now that my comment doesn't really make sense — I didn't notice that the editorial was already published.
14 people dedicated their lives to CP. 14 people prepared this round. 14 people. 14. AND IT IS STILL A TERRIBLE ROUND.
for me , problems C<A<<<<<<<<B
Same
so angry with myself. I messed up on B and then was too late for everything else. I was allocating an array of the max size so I got always TLE without figuring out why for more than an hour...
B was very bad for me.
Yeah, solved 1830B - The BOSS Can Count Pairs in $$$O(n^2)$$$. Solution
OMG
What? How did this pass?
This solution has been optimized by GCC after applying auto-vectorization for type
floatin a for-loop (FMA instruction set), in other words the for-loop has been parallelized on low level by processing $$$8$$$ floats per one iteration (SIMD — Single-Instruction-Multiple-Data), because iterations of for-loop are independent.Could you share any resource for the same?
_aka5h, Elagamy, I read two articles: «A Guide To Vectorization With Intel C++ Compilers» and «GCC Autovectorization — A journey throught compiler options, SIMD», then experimented on old codeforces problems (most of them has limitation $$$n=100000$$$ or $$$n=200000$$$ and you can try to solve it). Also I used godbolt.org to see assembly. Maybe I read some other blogs from first pages from google, but I don't remember it.
I think you should become a tester.
To make sure that unintentional time complexity doesn't pass.
The dilemma is a tighter time limit might've made the constraints so restrictive that even a fairly well written solution with the right time complexity would receive TLE verdict (especially in a language like Python or Java).
wow it's a great optimization,How to learn the performance of interacting between CPU and memory ?
I've learned about instruction set like this, but i want to know how to benefit from this knowledge in the coding paradigms?
How to approach D ? got stuck , but couldn't think anything in linear time
For problem D, I am having difficulty thinking of a solution with less than O(n^2) time complexity. How should I approach this? For the entire duration, I was thinking of leveraging the fact that the sum of two elements can be at most 2*n and was not able to think of anything else. So far, I have only seen people using fancy data structures which I have never heard of.
Try to think about pairs with ai <= sqrt(2 * n) and pairs with ai > sqrt(2 * n)
In the first case you can iterate over all j
In the second case you can iterate over all sums cause 2 * n / ai < sqrt(2 * n)
See my solution using only binary search(as a fancy thing).
Check Jiangly's O(n*sqrt(n)) solution
Might cross 1700 today for the first time in my CF journey 💙. I'm lucky that the contest was rescheduled because my internet connection was terrible yesterday.
Congrats! My god what a journey you have.
please guide for B div 2
It's a little hard to explain, but my code should be ok to read. We are essentially finding the longest "streaks" of the same value from each array. Then taking the max of sums each one. (Say if there is a streak of length 2 with value 3 from A, and a streak of length 5, with value 3 from B, we just add 2 + 5, and take the max over all of these values values). Its (kinda?) easy to see that the longest streak in array "C" will be comprised of one subarray from A and one subarray from B.
Proof that we can do this: We can greedily remove all values before the two subarrays. then merge the two subarrays together. (try to prove it to yourself through simulating it)
https://codeforces.com/contest/1831/submission/207591101
suppose a[] = [_ _ _ _ x x x x _ __ _ _ ] b[] = [_ _ x x x _ _ _ ]
You need max length subarray of equal elements
for this you need a subarray from (array a) and a subarray of same element from (array b) and concatination of both will contribute to ans
at last ans will be max of both subarray length
fr(i , n) { lli val = v[i]; lli cm = 1; lli j = i + 1; while(j < n and v[j] == val) { cm++; j++; } i = j — 1;
// storing subarray of equal element size in temp array at particular index of that element
// same for both array a and b at last finding max of both size
lli ans = -1; fr( i , n + n + 1) { ans = max(ans , temp1[i] + temp2[i]); }
GreatForces
C was fun.
How to approach problem 1831C - Copil Copac Draws Trees ?. Got TLE while solving using Queue 207622849. Couldn't figure out why it is getting TLE.
You should set vis[i]->true while you push the node into the queue
for today B problem i am understanding something wrong
We can merge like this:
There is a segment of eight 2's in the middle.
what if this
- 3 1 1 1 1 3 2 2 2 2 3
- 3 2 2 2 2 3 1 1 1 1 3
what should be the answer.? according to me 4 i am not seeing largest subarray of equal elements
We can get 8:
Again, there is a segment of eight 2's in the middle.
thanks a lot . got it .
I cannot see that we can combine every segment of a array with b array. sorry if my doubt seems silly to you
Yes, you simply needed to count the largest number of consecutive occurrences of each number in each array separately and take the maximum sum of those sums for each unique number.
Does the third question of div2 requires some knowledge of tree or it can be solved normally wihtout trees,as soon as i saw tree in the problem statement i left
There should be some basic knowledge of tree to understand the problem statement properly. but this problem can be solved using DFS.
i don't know dfs and bfs...seems like it's the time i should start focusing to learn something new
Things you should know about tree to solve Div2C:
Missed the contest but my ratting saved from going down :p
сколько стоил АК
I don't understand what you said
"How much does an AK cost?" Maybe some Russian movie dialogue about AK 47 smth
Great Contest, learnt something new in BFS 1831C - Copil Copac Draws Trees
Problem C — BFS-like solution:
I keep 3 sets:
written,processedandcurrent_edges.written: Nodes that are written at the moment, but not fully processedprocessed: Nodes that are fully processed.current_edges: edges that are going to be processed.Also, per each node, I keep a set of edge pointers.
At the beginning of the solution, add 1 to written set.
While there are nodes to be processed, keep processing (processed.size() < n)
For each edge in current_edges set, get both nodes (one of them is alredy processed at this point, but I was too lazy to do the additional if statement), and insert to current_edges set all the edges that are greater than cure. Then, delete all these edges from it's edges index. If the set is empty, then insert it to processed set, otherwise, it should be processed fully so insert it into written set instead.
Solution link: https://codeforces.com/contest/1831/submission/207672990
It's a pitty I didn't got AC in the contest. I had a bug with lower_bound(...).
I had a similar solution, I maintained an adjacency list so didn't need to use lower bound(because if once a node is inserted into current_edges it is either going to be processes fully in this iteration itself or the next iteration)
Did I miss some
O(n)solution for D div 2 / B div 1? I tried square root decomposition, but I either get TLE or MLE. If I save the pairs asmap<ii, int>I get TLE (which is understandable, as it isO(nlog(n)sqrt(n)). If I save them asunordered_map<i64, int>(using some hashing of course) I get MLE.My time complexity is O(nsqrt(n)) https://codeforces.com/contest/1831/submission/207629338
Can't wait for rating update! :)
you are master! congrats :D
Thank you!
Master on ALT, CM on main account?
lol
So happy to. Victory thank, you
Very good problems, well done guys!
Thank you! Which one was your favourite?
In div1E it was very fun to figure out the precise invariant for operations, very cool and novel (at least to me). Definitely a highlight.
Div1D is nice, div1C is good, and div1F looks interesting too (I'll try to solve it later).
I wish I could, but can't try... way out of league
Thanks for the round, finally blue!
congrats
Thanks man :)
D is a great problem with stupid Memory limit
I might be paranoic but I thought 1024MB is just a big spoiler. For me reading 1024MB in that problem just means "do some nsqrt memory dp".
Setting $$$n \le 10^5$$$ to reduce memory also seemed to spoil a little, what setter does $$$n \le 10^5$$$ if not for $$$O(n \cdot \sqrt{n})$$$ or $$$O(n \cdot log^2)$$$ solutions? There was also a scam that worked quite well with this limit.
I get we could set 1024MB limit to all problems, but I was unsure we wouldn't run into technical issues then.
And the hld to reduce memory was posted not long ago so I thought most people knew about it...
Nevertheless, I'm happy you enjoyed the idea of the problem.
This is one of the best rounds I've taken in a while, Tho Mle for Div2 D could've been less strict, Thanks!
can u explain problem 2 of div 2
ehhhhh
can anyone explain me about problem 2 in div 2
You are given 2 arrays a and b of length n. You have to merge these two arrays into c of length 2*n such that c has maximum length sub-array of equal element.
Suppose
a={1,2,2,3}andb={2,2,1,1}. We can merge it like,c={1,2,2,2,2,3,1,1}.herec[2,4](1 indexed)sub-array contains equal element. So answer is 4. Note that, We can also merge it in different way. Just keep mind that the Order of elements of array a and b will not change.Thank you
Div2 b Taught me not to use arrays when you can use vectors，
include<bits/stdc++.h>
using namespace std;
define endl "\n"
define ll long long
define F first
define S second
define no cout<<"NO\n"
define yes cout<<"YES\n"
define tests int t; cin >> t; while (t--)
define sai ios_base::sync_with_stdio(0);cin.tie(0);
define upp(str) transform(str.begin(), str.end(), str.begin(), ::toupper);
define low(str) transform(str.begin(), str.end(), str.begin(), ::tolower);
typedef vectorvi; const ll mod = 1e9 + 7, mod2 = 998244353; bool ispow2(long long int i){return i&&(i&-i)==i;}
//___________________________________________________________________________________________// void solve() { int n; cin>>n;
} int main() { sai tests { solve(); } }
can any one tell me where Iam making mistake div2 problem b
In fact, I had already passed B during the competition, but I only got 225 points on B
okay
Thanks for the code
Would someone be able to check why my solution to Div 2 D TLEs on case 8?
It's basically the same as the official solution and runs in O(n*sqrt(n)), so I'm unsure why it TLEs.
Maybe its because you are passing the Vectors by value in the checkSum function. Try to pass it by reference
Problems D seems like a typical atcoder ABC F