Привет, Codeforces!
В Feb/23/2024 17:35 (Moscow time) состоится Educational Codeforces Round 162 (Rated for Div. 2).
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов, Максим Neon Мещеряков и Роман Roms Глазов. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
UPD: Разбор опубликован
Good luck to everyone!
HERESY! Weak CPers are not allowed to use a picture of the Lord as their pfp.
I advise you to quickly change your pfp and repent for your sins before the Holy Church Of Bateman is forced to take punitive action.
Oh I'm sorry :/
But I'm still not changing it
Such a short and clear announcement I hope problems statements be like this too!
Hope able to AK this round
Good luck to everyone! (please upvote i need contribution)
This comment has been deleted.
post something that makes any sense otherwise you will be downvoted
Excited to get to Expert
Good luck on getting it
Excited to reach expert too DeletedAccountforever
Rushdi Excited to C U become CM
GL for both of you guys ! 😊
3rasii bas bamza7 lesaa mtawleen
😊 nothing is impossible !
Hope to reach 2024
I think the title should say [Rated upto div2] instead of [Rated for div2]
Div. 2 includes all ratings below 2100 (if there's no Div. 1 contest)
Oh then why we have div3 and div4 contests.. if no such division exists?
Div. 3 and Div. 4 are not exclusive to Div. 2. Usually Div. 3 includes Div. 4 and Div. 2 includes Div. 3 and Div. 4. The only exception so far, to my knowledge, was https://mirror.codeforces.com/blog/entry/121579 this Div. 1 & 2 & 3 contest.
Historically, there were no Div. 3 and Div. 4 long time ago. They were added later as a part of Div. 2 for new type of contests that are newbie-friendly.
My last contest in this winter vacation
my first codeforces contest today
What a coincidence it's my first codeforces contest today too
OMG that is really cool
Good luck for you!!!
3Q for ur reminder:(, love from China
Chinese OIer
good luck from good duck !!!
Score distribution?
It's an educational round.
Damn, it seems to me or they specifically ask this question only under every Div3, 4 and Eductional rounds
actually not. Almost under every round.
Who tested?
Educational rounds are mathforces af, thats a skip
You are freaking annoying. Learn math
I know math but dont enjoy it in DSA problems
I like math problems :D
Enjoy the contest!
stay up to late again:）
Small and clear announcement. Hopefully we will enjoy this contest. </>
Good luck everybody. Hope to get positive delta :)
Missed opportunity to name problem C. as "Find C"
Do we write outputs for each test case as it comes or all the way at the end?
Either way works, however it's much simpler and more efficient to output as it comes.
Finally, Goodbye 2023 has a worthy competitor.
It's like Div 1.5
I found it easy as compared to other edu rounds.
Div 2.5
B>>>C
wtf? just kill the nearest mob
Speedforcing abcde
B < A
According to my solve times, B < C < A < E < D < F.
problem D :(
it was just about binary search.
What's your approach?
for each index,i checked on both sides and if any side's sum exceed the number at current index than can compress the range.Also note that if any side's range have all number same then will not consider that side.
how did you find if all numbers are same in a range?
For example, arr=[1,1,2,3,3,3] i stored the ranges (0,1) , (2,2) , (3,5) in a vector 'vec' in sorted manner. It can be done in O(n).
now suppose i want to check if (4,5) has all number same,what will i do? i will find the largest index in vec such that vec[i][0]<=4, now i will check if vec[i][1]>=5 than (4,5) lies under the range (vec[i][0],vec[i][1]) otherwise some numbers are diff.
Just binary search things...
you can check it easy if all elements in the segments are the same or not you can use prefix sum and check if the summation in the segment is equal to r-lI did it with sparse table.
Found out the maximum value in the given range [l, r], then checked if sum(a[l], a[l+1], ..., a[r]) == maxVal * (r-l+1).
Can you suggest me some problems where I can practice sparse table?
These are some I can remember right now. You can try any other questions which require range queries without update.
E too easy to be an E, swap D and E
cheaters ruined the contest again :(
just train more, yours perfomance is bad not because of cheaters
Nice problem F! Thanks!
How to solve it? My intuition is that we will perform 2nd operation at most once. Since number of 1s stays constant , we will try to merge 1s as close as possible.
That's it! (I didn't realize we needn't do the 2nd operation twice in the contest QWQ)
When we perform the 2nd operation only once, we can consider on the reversed string. We can try all positions for the highest bit, and binary search on the final length of the string ignoring leading zeroes.
If the positions of the highest bit and the lowest bit are determined, the greedy solution is to put all 1 outside to the last few 0s in the interval, so the prefix of some length doesn't change. So we can use hash or suffix array to compare the prefixes, and then the best starting position can be determined.
But I think it's hard to write it.
I finally joined the dark side, selling my soul to Atcoder!
If you want to build intuition and upsolve problem D without looking at the editorial, try out 1901D : Yet Another Monster Fight. I've added hints as well.
A major hint for this problem:
Think about how the C++ comparator is able to figure out if 2 elements are identical.
after getting 15 WA on problem C, I wished contest end earlier.
screwed up, going gray again
can you share the approach for C? thanks in advance
it's called brute force approach, guess the solution and submit until AC
so basically what I did was it must has something to do with prefix sum, so I computed that and may involve prefix cnt(0) so I used that, but couldn't figure out there is length involved so failed to AC.
in B is it not optimal to kill the nearest monster?
It is.
nearest with low hp
it does not matter
I got wrong answer 4 times in the contest because I forget to sort the position array and after I used sort it got accepted so I think it matters (https://mirror.codeforces.com/contest/1923/submission/247981283)
you only need to sort based on position if multiple monsters are at same position the you can take them in any order
hint for D pls
think of binary search.
If you have an range minima data structure and a range maxima data structure, can you figure out if all elements in a range are identical?
it can also be done through binary search by storing the ranges of identical numbers in sorted manner.See my code.
consider range [l, r], when you can not eat any slimes in [l, r] using only [l, r] slimes?
think about binary search + preffix sum
Why so tough time limit in E?
The intended solution is most likely small-to-large merging. It is not uncommon for the centroid decomposition to have a large constant factor.
how to approach B?
Loop from the closest monster to the farthest (you need to take only the absolute value of all monster positions and then sort them), but you need to know each monster's health after the sorting, so you need to use something like a vector<pair<int,int>> where the first value is for position and the second value is for the index of that monster corresponding for its health . Now just loop from the closest to the farthest and sum their health and check how many rounds you need to get rid of the current sum, Rounds_required = ceil(current_sum/k).
If at any time the rounds required are bigger than the current monster position, then we can't kill that monster so break and print no
"it's better to use ( current_sum + k — 1 ) / k for ceiling ". said by LGM
.
Need More Practice for Educational Rounds. Btw Can anyone tell me the approach for C.(B>C)
Very nice problems
How to hack others?
any hint for problem c????
Basically, if you have $$$1$$$'s in array $$$a$$$, they will be at least $$$2$$$ in array $$$b$$$ and all other elements will be at least $$$1$$$. So, for some $$$l$$$, $$$r$$$ you just need to check if sum on subarray from $$$l$$$ to $$$r$$$ is at least it's length $$$+$$$ amount of $$$1$$$'s in it. $$$l=r$$$ is an edge-case.
I want to eat your pancreas
The Pet Girl of Sakurasou
Typo in problem D's tags: https://imgur.com/TvwOJcP
Did anyone recognize C was 1856B
Yes, I solved the question today, but I'm still unable to solve Question C. I attempted to use a segment tree but failed.
A: Let L=the minimum position of i such that a[i]==1, R=the maximum position of i such that a[i]==1, the until occurences of 1 become a single block, R-L will decrease 1 if you do operation on position R, otherwise it will not decrease. So the answer is (R-L)-(cnt-1) where cnt is the count of occurences of 1.
B: For each 1<=i<=n we need sum(j:abs(x[j])<=i)(a[i])<=k*i to kill monsters with distance <=i in i turns.
C: If L==R answer is no. Otherwise, for each a[i]==1 we need some j such that a[j]>1 and let a[i]+=1, a[j]-=1. Then we need sum(i:a[i]==1)(1)<=sum(j:a[j]>1)(a[j]-1). We can check this condition in O(1) by prefix sum.
D: Assume slime i is eaten by some slime to the left (the other case is similar), and all slimes used to eat i will form an interval [j, i-1]. So we need to find the maximum j such that sum(j, i-1)>a[i]. If j==i-1, slime i-1 can eat slime i directly. If value of a[j...i-1] is not all the same, then there will be a largest slime which can eat all other slimes in range [j, i-1] then eat slime i. Otherwise, all slimes in [j, i-1] have the same size and cannot eat each other, and slime i-1 is not larger than slime i. So we need to extend this interval to the left to find some k such that a[k]!=a[i-1] (if such k exist).
E: Small-to-large merge. Let dp[u][c]= (the number of nodes v in subtree of u, such that v is color c, and nodes on the path from u to v (except v) are not colot c). Then the number of valid paths with lca=u is sum(v1)(dp[v1][color[u]]) + sum(v1,v2,c)(dp[v1][c]*dp[v2][c]), where v1,v2 iterates over childs of u, c iterates over all colors on subtree of u, and v1<v2, c!=color[u]. The first term means valid paths start from u, and second term means valid paths start and end in subtree of u. To calculate the value we have dp[u][c]=sum(v: child of u)(color[v]==c) (if c!=color[u]), dp[u][color[u]]=1, we can maintain imformation in std::map and merge them small-to-large.
Can you explain what merging small to large means? I had the same dp relation but got TLE on testcase 10.
Thanks
Problem E can also be solved with DP on auxiliary trees.
Can anyone please tell me why does this code won't work for problem C :(
Your answer is $$$NO$$$, but should be $$$YES$$$ ($$$2, 2, 1$$$).
thanks man, got it
Will you help me in solution of D also?
Maybe your idea is wrong? In bs you did you should check if there exist more, then $$$1$$$ different value on a segment. Or i didn't get you code.
My idea was right, just making a small mistake. ~~~~~ Anyway thanks man ~~~~~
Okay, you're welcome!
B >>> D > E > A > C
I felt B was a standard implementation problem
I know it is, but I got frustrated by not being able to find out a slick way to implement it.
Ugm... It is just $$$\forall x \ge 1 \; x \cdot k \ge \sum_{i \in [1, x]}F(i)$$$, where $$$F(i)$$$ is sum of hp of mosters on point $$$i$$$ and point $$$-i$$$.
Hmm, this looks simpler.
Anyone who got WA on test 2 at problem D, then managed to solve it? What was missing? I did a binary search on prefix sums while checking for the existence of different elements using two segment trees (minimum != maximum). I got WA on test 2, and I couldn't find one where it was not working.
Same here . I had the same approach but WA on test case 2.
You don't just have to check the existence of different elements. If your segment found by binary search contains all equal elements, you will need to extend it until a different element is found.
I found the test I got incorrect on:
My program gives 2 -1 -1, it should have been 2, -1, 1. I guess I didn't pay enough attention when implementing.
Let's say we have 3 9 9 9 9 9. We're checking how far right we need to go to eat 3. Simple binary search will result in -1 (no answer for it), because it will first check 3 9s but they're the same so then it will try more than 3 9s, etc. You need to process 1-length case separately.
This is the answer. Took me a while to realize why my program was not working. Thanks!
In problem D sample input and ouput it is given in the third testcase that 2 2 3 1 1 will give an output of 2 1 -1 1 2 but cant slime 3 be eaten when 2 eats 2 and then eats 3. Making the expected output 2 1 2 1 2 or am I going wrong somewhere
"A slime can eat its neighbor only if it is strictly bigger than this neighbor. " So 2 can't eat 2.
slime1 can not eat slime2.
A slime can eat its neighbor only if it is strictly bigger than this neighbor
F is beautiful! Too bad I only managed to solve it a few minutes late lol
Can someone hack it? 247947284
247976858 Can you give me test case wrong ? My program WA on test 2 (Problem D)
Thanks! when i revised my code but it's TLE (my code use O(nlog(n)^2)) 247988327
You can use a sparse table instead of segment tree to reduce the time complexity to $$$O(n*logn)$$$.
Can anyone find out the my mistake Thanks[submission:247947411]
void solve() {
ll n, q; cin >> n >> q; vector<ll>a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; } vector<ll>b(n + 1, 0); for (int i = 1; i <= n; i++) { b[i] = a[i] + b[i - 1]; } while (q--) { ll l, r; cin >> l >> r; if (l == r) { cout << no << endl; continue; } ll tem = b[r] - b[l - 1]; ll h = r - l + 1; if (tem >= h / 2 + (h - h / 2) * 2) { cout << yes << endl; } else { cout << no << endl; } }}
Your answer is $$$YES$$$, but should be $$$NO$$$.
COULD YOU MAKE SAMPLES IN TASK C BETTER?
I think problem D can be solved using binary search
and a bit data structures :p
And problem A using greedy
Do anyone know how can my O(n * log(n)^2) solution for problem D got TLE, since n * log(n)^2 is only around 10^8
247977945
Thank you so much
I think you don't consider Segment Tree constant per query, which is very big.
I've got TLE because of that too. Is the constant really that big? Why it isn't just log(n)?
Well, when you already have $$$10^8$$$ time complexity, it is big enough to get TLE. I don't remember the exact value.
My O(nlog^2(n)) solution using segment tree and binary search got accepted. 247957289
lucky you :o
.
Why does C have so many hacks?
even tourist got hacked? tf
does anyone know that missing edge case?
I don't think there's an edge case possible for that task? (except L==R which his submission covers). My code is exactly the same as tourists so I'll probably get hacked as well smh
What is an "easy" solution of problem E? I solved it exactly as this problem.
I also solved it using this idea, some people have solved it using small-to-large merging.
I just saw your comment. I already posted my solution elsewhere but here it is again.
It consists in one dfs. The idea is to keep track of which colors were accessible before on the dfs tree, with multiplicity. When branching, we set the current color to multiplicity = $$$1$$$ because it then loses its multiplicity (the path needs to be beautiful). But then it needs to regain its old multiplicity $$$+1$$$ when we end the dfs.
tourist C hacked
now he is unhacked
D: For each index ,I gonna binary search on the answer. So consider position i, we have to check if after x seconds, we can eat this slime or not.
Im computing the left side first, that mean we considering only from 1 to i-1.
In the position i and after x second, there are two case:
After finishing the left side, we do the same on the right side and compare the answer 247990076
E : I saw a lot of simpler solution for problem E (merge set/map on tree, etc...). Anyway, I have another technique for E that is "Auxiliary Tree", which was very useful and generic in some specific type of problems. You can find it here : https://mirror.codeforces.com/blog/entry/76955. This problem is similar to E, which you can try to solve it first : 613D - Kingdom and its Cities. You can read my solution for E here : 247980215.
Bonus
Thanks! This make sense for me.
Thanks for the bonus, helped me fully understand Auxiliary Tree.
What is the hack on C? Asking for a friend..
There seems to have been some issue with the system (probably related to Polygon), they're rejudged and most of the WA hacks are gone now.
Unfortunately, hacks for C were judged incorrectly due to a very peculiar case of UB :(
We are sorry for that, all hacks have been rejudged. The solutions during the contest were judged correctly, so this affected only the hack phase.
Yeah, I was so confused. I literally went through my code a dozen times to see what was wrong. Thanks for the prompt fix.
This comment has been deleted.
247954847 How this solution is getting TLE?
it may not appropriate to write such comment but
There is a case where my code for C is failing, i tried a lot to debug even stress testing but still couldn't found anything! it's failing on token 59831 on testcase 3
i don't know what's minor mistake i'm making 247924659
can anyone help me ?
Here's a counter test
Your code prints
YESinstead of the expectedNO.Thanks for reply. Now i finally get it! it's more simpler than i thought
What about this test!
Can someone explain why I got TLE 247937101
Use Fast I/O
Approach for solving Problem E using auxillary tree and DP.
Suppose for each color $$$\textbf{c}$$$ we perform a $$$\texttt{dfs}$$$ on the tree and calculate number of nodes in subtree of node-$$$i$$$ of color $$$c$$$ such that none of it's ancestor has color $$$\textbf{c}$$$. Now we divide our answer in two cases:
But this will take $$$O(n \cdot n)$$$ time. To optimise this, we compress the tree in a way such that we only take nodes of color $$$\textbf{c}$$$ (and some extra nodes less than equal to number of nodes of color $$$c$$$ in number) without losing any information that we could obtain for any node of color $$$\textbf{c}$$$. Now we can use the same logic without any problem.
For each color our complexity would then reduce to $$$O(\text{number of nodes of color c})$$$ (ignoring the extra $$$\log$$$ factor that comes because of $$$\text{lca}$$$ and $$$\textbf{sorting}$$$. Here is my submission for the problem.
It can also be done with one dfs and an array. The code is really short.
Holy shit 🤯 I feel so dumb now.
But thank you for sharing your solution as well and explaining it. Edu rounds are meant to learn new techniques.
Hi, can you explain what the above code does?
Can you explain your code ??
I am not good at reading code. Is your solution the same as this code . If it is do you know the name of the algorithm?
is problem D prefix/suffix sum problem? then using binary search on pref(left), suff(right) then take lower..? but how to handle case where having same size adjacent?
I took care of this case by first going through the whole array and extracting the adjacent subarrays of same values (in the form of a vector of pairs (left index, right index)). Then, when binary searching, I would call the condition not met whenever the currently considered subarray lied in one of the precomputed "adjacent subarrays of same value".
To handle this with a good complexity, I used another binary search to find the good (left index, right index) candidate with which I should check if I am inside or not. It's like geometry, so maybe there are easier ways to do so.
To make the implementation easier, you could use DP. Define $$$dp[i]$$$ to be the index of the leftmost consecutive identical element that ends at $$$i$$$.
Using this DP array, how to check if the range $$$[l, r]$$$ has identical elements? Just check if $$$dp[r] \leq l$$$. If yes, then the range has identical elements.
Now, you can do a binary search on $$$[0, i - 1]$$$ to figure out the answer.
Submission
Any small counter testcase for my C 1923C - Find B; submission 247973573 as well? I have used all the TCs posted by AVdovin and 29logN
There you go. Should be $$$NO$$$, but your is $$$YES$$$.
1
4 1
1 1 1 3
1 4
Expected Ans: YES Edit: Test case is wrong
Expected $$$NO$$$, ig?
Yes, the expected answer should be NO.
Hello Everyone, Hope Everybody is doing great. I am stuck at problem C, can someone help me, what's wrong with my code
248047400 this code is after i have take the input array
for(int i=0;i<n;i++){prefix[i+1]=prefix[i]+a[i];}while(q--){ll l,r; cin>>l>>r;ll k=r-l+1;if(k==1)cout<<"NO"<<endl;else{ll sum=k/2+2*((k+1)/2);if(sum<=prefix[r]-prefix[l-1])cout<<"YES"<<endl;elsecout<<"NO"<<endl;}}According to me it should be correct,but failed at some 58k token.
Find possible b's for
1 1 1 1 4and1 1 1 2 3on paper and with your solutionYou cannot find right?
They have same sum, but for 1st you cannot, while for second it is
2 2 2 1 1. I've just fallen into the same trap.Oh yes, I meant the first. I thought as you said "find" there will be a solution.
Video Editorial for problem C
Why are red coders visible as rated contestants in the final standings?
Video Editorial for problem C : YOUTUBE EDITORIAL LINK Audio : English
unrated contest pleaseeeeee!!!!
Hey folks, can someone please help me figure out why my solution for C fails in the second test case.
use long long int as sum of elements of the array will be greater than the maximum capacity of regular int
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Who else failed the system test for problem C because they used
2e5instead of3e5for the array size? (And somehow passed the pretests?)lovely contest became specialist after a lot of struggle