Hello Codeforces!

On Friday, February 23, 2024 at 14:35UTC Educational Codeforces Round 162 (Rated for Div. 2) will start.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

• 39 hours ago, # ^ | 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.

  • 39 hours ago, # ^ | Oh I'm sorry :/ Spoiler

• 40 hours ago, # ^ | Hope to able to solve ABC in this round

• 39 hours ago, # ^ | ← Rev. 2 →   -20 This comment has been deleted.

• 37 hours ago, # ^ | post something that makes any sense otherwise you will be downvoted

• 37 hours ago, # ^ | Good luck on getting it

  • 37 hours ago, # ^ | Excited to reach expert too Angooo Rushdi Excited to C U become CM GL for both of you guys ! 😊

    • 37 hours ago, # ^ | 3rasii bas bamza7 lesaa mtawleen

      • 22 hours ago, # ^ | 😊 nothing is impossible !

• 28 hours ago, # ^ | Div. 2 includes all ratings below 2100 (if there's no Div. 1 contest)

  • 28 hours ago, # ^ | Oh then why we have div3 and div4 contests.. if no such division exists?

    • 28 hours ago, # ^ | 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://codeforces.com/blog/entry/121579 this Div. 1 & 2 & 3 contest.

    • 28 hours ago, # ^ | 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.

• 27 hours ago, # ^ | my first codeforces contest today

  • 19 hours ago, # ^ | What a coincidence it's my first codeforces contest today too

    • 18 hours ago, # ^ | OMG that is really cool

    • 16 hours ago, # ^ | Good luck for you!!!

    • 14 hours ago, # ^ | my first as well!

• 21 hour(s) ago, # ^ | 3Q for ur reminder:(, love from China

  • 20 hours ago, # ^ | Chinese OIer

• 25 hours ago, # ^ | It's an educational round.

• 22 hours ago, # ^ | ← Rev. 2 →   0 Damn, it seems to me or they specifically ask this question only under every Div3, 4 and Eductional rounds

  • 18 hours ago, # ^ | actually not. Almost under every round.

• 21 hour(s) ago, # ^ | You are freaking annoying. Learn math

  • 18 hours ago, # ^ | I know math but dont enjoy it in DSA problems

• 20 hours ago, # ^ | I like math problems :D

• 15 hours ago, # ^ | Either way works, however it's much simpler and more efficient to output as it comes.

• 16 hours ago, # ^ | I found it easy as compared to other edu rounds.

• 16 hours ago, # ^ | wtf? just kill the nearest mob

  • 16 hours ago, # ^ | i couldnt get the implementation right for B , C was just prefix sum

    • 16 hours ago, # ^ | priority_queue or even std::sort should work

      • 16 hours ago, # ^ | hi can you please check with my code once i know i made it too much complex but i still used the same approach you mentioned. here it is

        • 15 hours ago, # ^ | ← Rev. 4 →   0 you cannot sort only distances without hp, after sorting your monster[1][i] doesnt correspond to monster[0][i], use vector<pair<int, int>>

          • 15 hours ago, # ^ | I am sorry. Thanks i blindly believed gfg editorial without reading furtherly.

      • 15 hours ago, # ^ | yup sorted it in the end

• 15 hours ago, # ^ | According to my solve times, B < C < A < E < D < F.

• 16 hours ago, # ^ | it was just about binary search.

  • 16 hours ago, # ^ | What's your approach?

    • 16 hours ago, # ^ | 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.

      • 16 hours ago, # ^ | how did you find if all numbers are same in a range?

        • 15 hours ago, # ^ | 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...

          • 14 hours ago, # ^ | ← Rev. 2 →   0 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-l vector<ll>id(n+1); for(int x=1;x<=n;x++){ if(v[x]==v[x-1]) id[x] =id[x-1]+1; else id[x] = id[x-1]; } if(id[r]-id[l]==r-l) all elemnts are the same

            • 11 hours ago, # ^ | Nice trick!

          • 11 hours ago, # ^ | Understood it! Thanks

        • 6 hours ago, # ^ | I did it with sparse table. Spoiler

• 16 hours ago, # ^ | just train more, yours perfomance is bad not because of cheaters

• 16 hours ago, # ^ | 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.

  • 16 hours ago, # ^ | 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.

• 16 hours ago, # ^ | But I think it's hard to write it.

• 15 hours ago, # ^ | can you share the approach for C? thanks in advance

  • 15 hours ago, # ^ | 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.

• 16 hours ago, # ^ | It is.

• 16 hours ago, # ^ | nearest with low hp

  • 16 hours ago, # ^ | it does not matter

    • 15 hours ago, # ^ | 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://codeforces.com/contest/1923/submission/247981283)

      • 15 hours ago, # ^ | you only need to sort based on position if multiple monsters are at same position the you can take them in any order

        • 15 hours ago, # ^ | yes you are right I thought you are saying it does not matter for the original comment author

• 15 hours ago, # ^ |

• 16 hours ago, # ^ | think of binary search.

• 16 hours ago, # ^ | 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?

  • 16 hours ago, # ^ | it can also be done through binary search by storing the ranges of identical numbers in sorted manner.See my code.

• 16 hours ago, # ^ | 2 times binary search,front and back

  • 16 hours ago, # ^ | whats value to search

    • 16 hours ago, # ^ | Prefix to all and to all the a(i) search 1~(i-1) and (i+1)~(n)

      • 16 hours ago, # ^ | so as you can see it need two time search

• 16 hours ago, # ^ | hint

• 16 hours ago, # ^ | think about binary search + preffix sum

• 15 hours ago, # ^ | The intended solution is most likely small-to-large merging. It is not uncommon for the centroid decomposition to have a large constant factor.

• 16 hours ago, # ^ | ← Rev. 3 →   0 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

  • 14 hours ago, # ^ | "it's better to use ( current_sum + k — 1 ) / k for ceiling ". said by LGM

• 15 hours ago, # ^ | think binary search on prefix sum

• 16 hours ago, # ^ | ← Rev. 2 →   0 To determine if the answer for a query is yes, you need to the number of non-ones from L to R. Instead of sum-cnt*2 > 0, try sum-cnt*2-num_nons (where num_nons is the number of values in the range that is not 1).

  • 16 hours ago, # ^ | After number of non-ones,then what ?

    • 14 hours ago, # ^ | That's it. Just create another prefix array that allows constant time counting of the number of "non-ones" from [L,R]. It is optimal to set b[i] to 1 when c[i] is not 1, and then set b[i] to 2 when c[i] is 1. If b's sum is too small, then it suffices to increase one b[i] to match c's sum. If b's sum is too large, the answer is "NO". What amoad forgot to do was consider all indices where c[i] is not 1, as b[i] would be 1 and therefore part of b's count. I hope this explanation makes sense

• 16 hours ago, # ^ | try this test 1 1 1 1 3 2

• 3 hours ago, # ^ | ← Rev. 2 →   0 for the array 1 1 1 2 2 with query from 1 to 5 ,your code will say yes , while the actual answer is no. got -3 before figured this out finally and had to take a whole different approach

• 16 hours ago, # ^ | ← Rev. 2 →   0 we construct "good" array just using 1 (but if there is already 1 in original array we can write 2 instead) then just compare sums between l and r (can be done with prefix sum) and if sum[l:r] of original array is less than "good" array its ans is "NO" else "YES"

• 16 hours ago, # ^ | Basically, if you have 's in array , they will be at least in array and all other elements will be at least . So, for some , you just need to check if sum on subarray from to is at least it's length amount of 's in it. is an edge-case.

  • 16 hours ago, # ^ | I want to eat your pancreas

    • 16 hours ago, # ^ | The Pet Girl of Sakurasou

• 16 hours ago, # ^ | Yes, I solved the question today, but I'm still unable to solve Question C. I attempted to use a segment tree but failed.

• 16 hours ago, # ^ | Can you explain what merging small to large means? I had the same dp relation but got TLE on testcase 10.

  • 16 hours ago, # ^ | using tmii = map<int, int>; tmii& dfs(int node,int prev){ tmii& mp=*new tmii(); for(int next:adj[node]){ if(next==prev) continue; tmii& mp2=dfs(next,node); if(mp.size()<mp2.size()) swap(mp,mp2); for(auto [color,cnt]:mp2){ if(color!=c[node]) ans+=(ll)mp[color]*cnt; mp[color]+=cnt; } mp2.clear(); } ans+=mp[c[node]]; mp[c[node]]=1; return mp; }

    • 15 hours ago, # ^ | Thanks

• 15 hours ago, # ^ | Problem E can also be solved with DP on auxiliary trees.

• 15 hours ago, # ^ | In problem C Why a[i]=1 ?

• 15 hours ago, # ^ | ← Rev. 2 →   0 3 1 1 1 3 1 3 Your answer is , but should be ().

  • 15 hours ago, # ^ | thanks man, got it

  • 12 hours ago, # ^ | Will you help me in solution of D also?

    • 11 hours ago, # ^ | Maybe your idea is wrong? In bs you did you should check if there exist more, then different value on a segment. Or i didn't get you code.

      • 11 hours ago, # ^ | My idea was right, just making a small mistake. ~~~~~ Anyway thanks man ~~~~~

        • 11 hours ago, # ^ | Okay, you're welcome!

• 16 hours ago, # ^ | I felt B was a standard implementation problem

  • 16 hours ago, # ^ | I know it is, but I got frustrated by not being able to find out a slick way to implement it.

    • 15 hours ago, # ^ | Ugm... It is just , where is sum of hp of mosters on point and point .

      • 15 hours ago, # ^ | Hmm, this looks simpler.

• 16 hours ago, # ^ | ← Rev. 2 →   0 Same here . I had the same approach but WA on test case 2.

• 16 hours ago, # ^ | 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.

• 16 hours ago, # ^ | ← Rev. 7 →   0 I found the test I got incorrect on: 3 2 2 1 My program gives 2 -1 -1, it should have been 2, -1, 1. I guess I didn't pay enough attention when implementing.

• 15 hours ago, # ^ | 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.

  • 15 hours ago, # ^ | This is the answer. Took me a while to realize why my program was not working. Thanks!

• 16 hours ago, # ^ | "A slime can eat its neighbor only if it is strictly bigger than this neighbor. " So 2 can't eat 2.

  • 15 hours ago, # ^ | ah sorry, my bad, should have double checked. also, Thanks

• 16 hours ago, # ^ | slime1 can not eat slime2. A slime can eat its neighbor only if it is strictly bigger than this neighbor

int t; cin>>t;
while(t--){
   ll n,k; cin>>n>>k;
   ll hel[n];
   for(int i=0;i<n;i++){
     cin>>hel[i];
   }

   map<ll,ll> m;
   int mon[n];

   for(int i=0;i<n;i++){
     ll x; cin>>x;
     if(x<0) x=x*-1;
     mon[i]=x;
     m[x]=m[x]+hel[i];
   }

   ll cnt=0;      
   ll p=0;
   int flag=0;
   for(auto &ele:m){
      ll extra=cnt+((ele.first-p)*k);
      if(extra<ele.second){
        flag=1;
        break;
      }
      ll remain=extra-ele.second;
      cnt+=remain;
      p=ele.first;
   }

   if(flag==1) cout<<"NO"<<endl;
   else cout<<"YES"<<endl;
}

• 15 hours ago, # ^ | cnt+=remain; here is your mistake! you shouldn't increase the value of cnt everytime. Rather you have to update the value, as cnt is used here to calculate the remaining time. so it should be: cnt=remain;

  • 15 hours ago, # ^ | Thanks man

• 15 hours ago, # ^ | test: 1 7 1 5 10 4 4 1 1 correct output: 1 1 -1 1 2 1 2 your output: 1 1 -1 1 2 3 2

  • 15 hours ago, # ^ | ← Rev. 2 →   0 Thanks! when i revised my code but it's TLE (my code use O(nlog(n)^2)) 247988327

    • 15 hours ago, # ^ | You can use a sparse table instead of segment tree to reduce the time complexity to .

  • 3 hours ago, # ^ | Your test case really helps, thanks! I realized that with the special case that the neighbor is greater than the current item, it doesn't satisfy the condition for a single binary search anymore.

• 15 hours ago, # ^ | 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; } }

  • 15 hours ago, # ^ | ← Rev. 2 →   0 6 1 1 1 1 1 1 4 1 6 Your answer is , but should be .

  • 15 hours ago, # ^ | Wrote exact same code and got so frustrated thinking what is wrong in this and left the contest.247975227

• 15 hours ago, # ^ | Test case

15 hours ago, # | ← Rev. 2 →   +64 I think problem D can be solved using binary search

• 15 hours ago, # ^ | and a bit data structures :p

• 14 hours ago, # ^ | And problem A using greedy

  • 11 hours ago, # ^ | And we can solve 1923F - Shrink-Reverse using greedy algorithm with string suffix structures :D

• 15 hours ago, # ^ | I think you don't consider Segment Tree constant per query, which is very big.

  • 15 hours ago, # ^ | I've got TLE because of that too. Is the constant really that big? Why it isn't just log(n)?

    • 15 hours ago, # ^ | Well, when you already have time complexity, it is big enough to get TLE. I don't remember the exact value.

      • 14 hours ago, # ^ | My O(nlog^2(n)) solution using segment tree and binary search got accepted. 247957289

        • 14 hours ago, # ^ | lucky you :o

• 11 hours ago, # ^ | maybe because you sorted cordinate before filling it, not sure about the other things

• 15 hours ago, # ^ | even tourist got hacked? tf

  • 15 hours ago, # ^ | does anyone know that missing edge case?

    • 15 hours ago, # ^ | 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

      • 10 hours ago, # ^ | Maybe my view of problem will help you: Let's notice, that we can fill "one" to indexes with other elements, and then fit our sum with big numbers to indexes with one. a[1 1 1 100 100] -> b[67 67 67 1 1]

• 15 hours ago, # ^ | I also solved it using this idea, some people have solved it using small-to-large merging.

• 13 hours ago, # ^ | ← Rev. 2 →   +5 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 = because it then loses its multiplicity (the path needs to be beautiful). But then it needs to regain its old multiplicity when we end the dfs.

• 15 hours ago, # ^ | now he is unhacked

• 14 hours ago, # ^ | Thanks! This make sense for me.

• 15 hours ago, # ^ | 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.

• 15 hours ago, # ^ | Yeah, I was so confused. I literally went through my code a dozen times to see what was wrong. Thanks for the prompt fix.

• 13 hours ago, # ^ | Here's a counter test Your code prints YES instead of the expected NO.

  • 13 hours ago, # ^ | Thanks for reply. Now i finally get it! it's more simpler than i thought

• 13 hours ago, # ^ | What about this test!

• • 13 hours ago, # ^ | Thanks for suggestion

• 13 hours ago, # ^ | It can also be done with one dfs and an array. The code is really short.

  • 13 hours ago, # ^ | Holy shit 🤯 I feel so dumb now.

    • 12 hours ago, # ^ | But thank you for sharing your solution as well and explaining it. Edu rounds are meant to learn new techniques.

• 12 hours ago, # ^ | 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.

  • 12 hours ago, # ^ | ← Rev. 2 →   0 To make the implementation easier, you could use DP. Define to be the index of the leftmost consecutive identical element that ends at . If , then . If , then . Using this DP array, how to check if the range has identical elements? Just check if . If yes, then the range has identical elements. Now, you can do a binary search on to figure out the answer. Submission

• 11 hours ago, # ^ | 5 1 1 1 1 2 2 1 5 There you go. Should be , but your is .

• 11 hours ago, # ^ | ← Rev. 3 →   0 1 4 1 1 1 1 3 1 4 Expected Ans: YES Edit: Test case is wrong

  • 11 hours ago, # ^ | Expected , ig?

    • 11 hours ago, # ^ | Yes, the expected answer should be NO.

• 3 hours ago, # ^ | why not switch to java or cpp ?

• 2 hours ago, # ^ | Can you explain what's the meaning of sum in your code?

  • 119 minutes ago, # ^ | Basically sum is the minsum of the array for which good array is possible Suppose pattern {1 1 1 2 2 2} -->3 one and 3 two if we decrease any of the two then it wouldn't be good array and this pattern would be min sum possible for length 6 good array possible {1 1 1 2 2} max sum for which good array of length 5 is not possible. {1 1 2 2 2} min sum for which good array of length 5 is possible. let say length of array is k then we need min sum of k/2 one's and (k-k/2) two's for array of length k to be good array

    • 114 minutes ago, # ^ | ← Rev. 2 →   0 An example : 1 1 1 3. It should be "NO" but accroding to your solution your sum = 2 + 2 * 2 is exactly 1 + 1 + 1 + 3. Then you output "YES".

      • 108 minutes ago, # ^ | thank you, i should practice more...

• 111 minutes ago, # ^ | Find possible b's for 1 1 1 1 4 and 1 1 1 2 3 on paper and with your solution

  • 108 minutes ago, # ^ | You cannot find right?

    • 83 minutes ago, # ^ | ← Rev. 3 →   0 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.

      • 2 minutes ago, # ^ | ← Rev. 2 →   0 Oh yes, I meant the first. I thought as you said "find" there will be a solution.