### mesanu's blog

By mesanu, history, 2 months ago,

Hello Codeforces!

flamestorm, SlavicG, MikeMirzayanov and I want to invite you to Codeforces Round 849 (Div. 4).

It starts on Feb/03/2023 17:35 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

• ICPC rules with a penalty of 10 minutes for an incorrect submission;
• 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
• after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
• by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behaviour. To qualify as a trusted participant of the fourth division, you must:

• take part in at least five rated rounds (and solve at least one problem in each of them),
• do not have a point of 1400 or higher in the rating.

Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.

Many thanks to the testers: _Vanilla_, badlad, Gheal, Phantom_Performer, Kita, Nihad_Nabelsi, prvocislo, keta_tsimakuridze, Bakry, RedstoneGamer22, tibinyte, KrowSavcik, haochenkang, myvaluska, sandry24, BucketPotato, Vladosiya, pashka.

We suggest reading all of the problems and hope you will find them interesting!

Good Luck!

UPD: Editorial is posted.

• +261

 » 2 months ago, # |   +3 Hell yeah!!
 » 2 months ago, # |   +34 Eat an ice cream for positive delta :D
•  » » 2 months ago, # ^ |   +1 Done Sir.
•  » » 2 months ago, # ^ |   +3 i did it and finally get a positive delta lol
•  » » 2 months ago, # ^ |   +5 Ate this too much!!, Hope to reach specialist in this round.. After performing like specialist in some rounds, there comes one round such that sometimes I am not able to perform as expected. It's all about consistency.. Will try my best in tomorrow's div 4 round. Wish me luck :)
 » 2 months ago, # |   +19 As a tester, I suggest you participate!
 » 2 months ago, # | ← Rev. 2 →   0 I'll get 200 delta.Good Luck!
 » 2 months ago, # |   +28 As a tester, I enjoyed this round and I recommend everyone to participate!
•  » » 2 months ago, # ^ |   0 Let this round div. 4 brings everyone a good mood.
 » 2 months ago, # |   +27 As a newbie tester I recommend fellow newbies to participate :)
•  » » 2 months ago, # ^ |   0 Thank you, I was really looking forward to this round!
 » 2 months ago, # |   -11 I want this round to be unrated!!!
•  » » 2 months ago, # ^ |   0 Just don't participated live and give it virtually after contest. Ez Win.
 » 2 months ago, # |   0 first unrated
•  » » 2 months ago, # ^ |   0 Also my first unrated!
•  » » » 2 months ago, # ^ |   0 It's not.
•  » » » » 2 months ago, # ^ |   0 My rating hasn't updated yet, but any rating change I get from this round will be roll backed when they rate yesterday's round
•  » » » » » 2 months ago, # ^ |   0 Ah, okay. Sorry.
•  » » 2 months ago, # ^ |   +46
•  » » » 2 months ago, # ^ |   +6 How many times are you people gonna repost this
•  » » » » 2 months ago, # ^ |   +6 FOREVER!
•  » » » » » 2 months ago, # ^ |   0 ABSOLUTELY!
•  » » 7 weeks ago, # ^ |   0 :)
 » 2 months ago, # |   +36 As a tester, this is the best div4 I've tested so far.
•  » » 2 months ago, # ^ |   -58 As a tester, I want more upvotes than Gheal.
 » 2 months ago, # |   0 As a non-tester, this round is supposed to be the best Div. 4 round.
 » 2 months ago, # |   0 I hobe to solve at least 4 problems :)
•  » » 2 months ago, # ^ |   +10 Insha Allah.
•  » » » 2 months ago, # ^ |   0 Allah bless you
 » 2 months ago, # |   +28 As a tester, I enjoyed this round so much I forgot I was testing
 » 2 months ago, # | ← Rev. 2 →   0 Another round for fast code writing.
 » 2 months ago, # |   0 First, please update the rating of the two past tests!
 » 2 months ago, # |   +2 Eagerly waited for unrated contest.
 » 2 months ago, # |   +45 As a tester, i loved this contest too much but not more than Pringles.
 » 2 months ago, # |   +6 I am very excited for this contest, may be it will be a good contest for all the newbies like me, to become pupil or specialist
 » 2 months ago, # |   0 As a newbie Robot, I'll take on this Round. Let's see who's the best newbie out there.. --ChatGPT
 » 2 months ago, # |   0 All the best everyone
 » 2 months ago, # |   0 Finally my time to shine.I let my rating sink to be rated for div4. Lets go!!
•  » » 2 months ago, # ^ |   0 Good luck.
•  » » » 2 months ago, # ^ |   0 Same to u :)
 » 2 months ago, # |   0 Hope in this contest my rating will increase...who else is thinking.... Thanks Codeforces and mesanu,flamestorm,MikeMirzayanov for this contest...:)
•  » » 2 months ago, # ^ |   0 THANK YOU SlavicG GUGUSTIUC
 » 2 months ago, # | ← Rev. 2 →   0 Will I be rated for this contest?
•  » » 2 months ago, # ^ |   0 yes it will be rated for you. however, you will not be included in official standings because you have participated in < 5 rated rounds. this round is rated for all people with rating < 1400
•  » » 2 months ago, # ^ |   0 Yes
 » 2 months ago, # |   +5 At the end of the contest , some people will be happy and some will be sad, Be of the first kind
 » 2 months ago, # |   0 Let's go!
 » 2 months ago, # | ← Rev. 2 →   0 Best of luck everyone! Hope everybody will learn something new from the contest:)
 » 2 months ago, # |   0 As not a tester, I invite you to challenge together
 » 2 months ago, # |   0 Will the round be rated for me ? This is my second round, so I am not a trusted participant. My rating is 364.
•  » » 2 months ago, # ^ |   0 Yes, bro.
 » 2 months ago, # |   0 Yes, MikeMirzayanov sir is here. And look at the length of the contest (2:25)!
 » 2 months ago, # |   0 Why do some write comments for a contribution?
 » 2 months ago, # |   0 Can you please change the staring time of the contest? It starts after the Izho and info(1)cup contest. It would be great if you changed the time a bit later or to another day.
 » 2 months ago, # | ← Rev. 2 →   -19 .
•  » » 2 months ago, # ^ |   +2 The world doesn't work that way brother.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 i do that even the whole world is against me till the end of the eternity i will do
 » 2 months ago, # |   +4 ![ ]()
 » 2 months ago, # |   +18 omg keta_tsimakuridze tester
•  » » 2 months ago, # ^ |   +21 omg prvocislo tester
 » 2 months ago, # |   0 Wishing for a positive delta.
 » 2 months ago, # |   0 Let's Goo
 » 2 months ago, # |   +7 omg mesanu and flamestorm setters
•  » » 2 months ago, # ^ |   +41 dude you forgot your signature
•  » » » 2 months ago, # ^ |   0 Marinush
 » 2 months ago, # |   0 Oh, My God. After so many months later Div.4... Thanks for the div.4 
•  » » 2 months ago, # ^ |   0 what is your name?
•  » » » 7 weeks ago, # ^ |   0 Abir Kundu
 » 2 months ago, # |   0 Good weekend, good div.4!!!
 » 2 months ago, # |   0 As a newbie tester I recommend fellow newbies to participate
 » 2 months ago, # |   +3 It's been six days since typeDB round has finished still no problem rating update and no user rating update. Something weird there's been about the codeforces recently.
 » 2 months ago, # |   +2
 » 2 months ago, # |   -38 everyone sees a tiger, but the one who is the most attentive will find the elephant.
 » 2 months ago, # |   0 i wanna the first 3 easy
 » 2 months ago, # |   +3 Good Luck contest For Every OneThis contest must be successful for EveryBody
 » 2 months ago, # |   -17
 » 2 months ago, # |   0 Hello! JavaScript,C++
 » 2 months ago, # |   +4 OMG SlavicG Round!
 » 2 months ago, # |   0 Finally, my first div-4 contest after becoming specialist
 » 2 months ago, # |   0 Tayler Swift Div. can't wait!
 » 2 months ago, # |   +2 Will I be rated in this round cause the rating of last div2 round hasn't been updated yet and I am still a pupil,but if last round's rating update I will become specialist.
•  » » 7 weeks ago, # ^ |   0 Congratulations bro, you are a specialist now
•  » » » 7 weeks ago, # ^ |   0 Thanks
 » 2 months ago, # |   0 Best of luck
 » 2 months ago, # |   0 I need div 5
 » 2 months ago, # |   0 ratings roll back again of Last Div 3
 » 7 weeks ago, # |   0 I'm wondering how the rating will change for those who turned to be a specialist in the last div2 round, if it is rated.
•  » » 7 weeks ago, # ^ |   0 or in any of the last 3 contests
•  » » » 7 weeks ago, # ^ |   0 The rating should be updated now
 » 7 weeks ago, # |   0 Does the Penalty start from the begin of the contest or my first visit to contest/codeforces?? like if the contest start on 2:00 and I enterd the contest 2:30 and solved a problem at 2:35. Then the Penalty equal 35 or 5?
•  » » 7 weeks ago, # ^ |   +5 35
 » 7 weeks ago, # |   0 I eagerly wait for this round
 » 7 weeks ago, # |   0 Superrrrrrrrrr excited
 » 7 weeks ago, # | ← Rev. 3 →   +8 congratulation SlavicG for becoming CM from expert
 » 7 weeks ago, # | ← Rev. 2 →   -13 I am specialist but i am still rated for the round. WHYYYY? make this round unrated for people above 1400.
 » 7 weeks ago, # |   0 Woooahahshasfhazfz
 » 7 weeks ago, # |   0 Can't wait to see hmzqaq's performance in this round. (He's duck_pear)
 » 7 weeks ago, # | ← Rev. 2 →   -25 ..
•  » » 7 weeks ago, # ^ |   +6 You waste your mother's time for nine months.Marinush
•  » » » 7 weeks ago, # ^ |   0 You too..
 » 7 weeks ago, # |   +5 Stringforces!
 » 7 weeks ago, # |   +8 Good Div4 round, like always!
 » 7 weeks ago, # |   0 G2 is quite hard for div4..?
 » 7 weeks ago, # |   +31 Who's the cool Pikachu in problem B?
 » 7 weeks ago, # | ← Rev. 2 →   0 My mission AK with charm (solving all problems without any wrong submission) accomplished!!
 » 7 weeks ago, # |   +4 Nice problem set, solved all😊
 » 7 weeks ago, # |   0 how to solve F?? by not getting tle
•  » » 7 weeks ago, # ^ |   0 Seems like lazy propogation on segment tree. Calculating the value is O(1) as sum of digits would convert to a single digit in 2-3 operations.
•  » » » 7 weeks ago, # ^ |   0 You have to realize that for any a[i] you really only do the operation a couple times, and then it becomes a 1 digit number, which won't change. So just keep track of the indexes that are 1 digit numbers and don't bother visiting those.
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 There's no need for lazy propagation. Range updates and single queries can be done with a normal segtree storing differences of consecutive elements. 19192561
•  » » » » 7 weeks ago, # ^ |   0 Inspiring
•  » » » » 7 weeks ago, # ^ |   0 nice, good trick
•  » » 7 weeks ago, # ^ |   +6 You can either solve it using Fenwick tree like I did, or there's an alternative approach as well which doesn't use trees at all.The sum of digits operation will only be applied at most 3 times on $a[i]$. So, make an 3 arrays, the $1st$ one will be storing the numbers obtained by using the sum operation on all $a[i]$ once, the $2nd$ one is when the sum operation is used twice, and similarly for $3rd$.Now, all you need to do is to check for all $i$ in $[l,r]$ how many times it occurs.
•  » » » 7 weeks ago, # ^ |   +3 hmmmmmmmmmm,nice approach
•  » » » 7 weeks ago, # ^ |   0 Then it becomes a scanline problem? Or maybe coordinates compression with pref-sum? Or there are easier solutions?
•  » » » 7 weeks ago, # ^ |   0 Why 3 times?After 2 operations only a number becomes single digit number right?
•  » » » » 7 weeks ago, # ^ |   0 Take $999,999,988$ it will become $1$ digit number after $3$ operations
•  » » » » » 7 weeks ago, # ^ |   0 got it. Thank you!
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 I solved it with dsu I observed that a number will not be updated many times so that I let a number to be updated no more than ten times. When the number of updates for a particular index reached >10 I will make the parent[i]= findparents(i+1) Using the above approach whenever an index would be encountered for greater 10 times it will be skipped to the next index and then with the help of dsu I will reach the required index My submission — https://codeforces.com/contest/1791/submission/191990981time complexity will O(n*10+q)
•  » » » 7 weeks ago, # ^ |   0 Idk how u guys think of this solution during contest,but hats off to u guys..... I will upslove it tomorrow. Ok bye, Netflix............
•  » » » 7 weeks ago, # ^ |   0 I used DSU as well but solved it slightly differently. If any number is < 10 it will never need an update again and we can add it to the same set as the element at i-1.
•  » » » » 7 weeks ago, # ^ |   0 No I mean the number of operations applied on a number cannot be greater than 3 (which I randomly took 10)
•  » » » » » 7 weeks ago, # ^ |   0 Right, I got that. I’m saying I solved it differently by actually reducing the number and if the reduced number was <10 I added it to the set of the i-1 number
 » 7 weeks ago, # |   0 How to solve E? I am stuck.
•  » » 7 weeks ago, # ^ |   0 cnt = count of minus in arrayif cnt%2==1 final array only one minuselse just sum of array
•  » » 7 weeks ago, # ^ |   0 If there are even number of negative elements then the answer will be simply the sum of all elements of the array. Otherwise the answer will be sum-(minimum absolute value in the array).
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 I see, thank you guys for your simple explanation.
 » 7 weeks ago, # |   +12 Awesome contest.
 » 7 weeks ago, # |   0 Solved E and G1 in last 19 minutes of the contest!
 » 7 weeks ago, # |   0 Good problems this time, I had fun with F, first time using Fenwick tree by myself.
 » 7 weeks ago, # | ← Rev. 3 →   +3 ❤️ First time I solved A,B,C,D ✅ (in 32 min)
•  » » 7 weeks ago, # ^ |   0 started contest after 40 mins :sweat_smile:
 » 7 weeks ago, # |   0 Can someone explain how the 9th testcase is possible in problem G2, or just how to do the problem in general
 » 7 weeks ago, # |   +9 Screencast with solutions for all problems in case someone is interested.
 » 7 weeks ago, # |   0 What are the ideas behind D and F?
•  » » 7 weeks ago, # ^ |   0
•  » » » 7 weeks ago, # ^ |   0 Thanks! Didn't notice that it was already out.
 » 7 weeks ago, # |   0 very cool problems, was my first Div4 Round!! otho was able to solve only first 3, got stuck at the fourth and spent like 1hr45mins on that problem alone LMAO, should've moved on to other problems now that i think about it.
 » 7 weeks ago, # | ← Rev. 7 →   +5 A & B: implementaion.C: 2 pointers. D: Count the occurence of each different chars for every prefixes and suffixes. The answer is max(count(prefix(i))+count(suffix(i+1))).E: Dynamic programming. Let dp[i][flag]=the maximum value we can get from first i elements, where flag is true if we've fliped the sign of a[i-1],a[i]. Similar with 1787C - Remove the Bracket.F: A number can be updated of most 3 times (then it will have only 1 digit, which means, it will not be changed anymore) so we don't need to update a same element for more than 3 times. We can use segment tree to store the number of updates (although there can be simpler solutions, it's easier for me to copy a prepared segtree template). For all 1<=a<=10^9, the maximum digit sum of it is 81 (when a=999,999,999), and for 0<=a<=81, the maximum digit sum is 16 (when a=79), and for 0<=a<=16, the maximum digit sum is 9 (when a=9). G1: The cost of each portal is a[i]+i, sort them and we can get the answer.G2: The cost of each portal is a[i]+min(i,n+1-i), but we need to add an extra cost if all the portals we've used are on the "right part" of the number line (which means they are closer to n+1 than 0). Therefore, we need to consider for 2 situations: First, consider we use at least one "left portal". We can use the left portal with minimum cost and sort the remain portals. Second, consider we only use "right portals". We also solve this situation by sorting, but we need to add min(2*i-n-1) to our total cost. First we use portals by the order of their cost, and when we can't use the next portal, we check all remained portals and try to use them.By the way: MikeMirzayanov look at this please!
•  » » 7 weeks ago, # ^ |   0 E was one liner after some simple observation.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Elegant solution for problem E: - If number of negative numbers is even then maximum possible sum will be sum of absolute value of all array elements. - If number of negative numbers is odd then maximum possible sum will be sum of absolute value of all array elements except absolute minimum one minus absolute minium one.
•  » » 7 weeks ago, # ^ | ← Rev. 3 →   0 @YocyCraft your approach of D is giving TLE on test case 3. Can you please explain in more depth maybe I misunderstood it. Edit : Okay got it by using two freq maps we can implement in O(n)
 » 7 weeks ago, # | ← Rev. 2 →   0 can someone hack on problem F submission? I think it should TLE.
•  » » 7 weeks ago, # ^ |   0 Done
•  » » » 7 weeks ago, # ^ |   0 Is mine hackable for F? submission
•  » » » » 7 weeks ago, # ^ |   0 I think no if your segtree is ok
•  » » » » » 7 weeks ago, # ^ |   0 Solved F without segtree, is my submission hackable :) ?
•  » » » » » » 7 weeks ago, # ^ |   0 Done
•  » » » » » » » 7 weeks ago, # ^ |   0 That means it must be solved with segtree? there is no other way?
•  » » » » » » » » 7 weeks ago, # ^ |   +1 You can solve it without segtree. You can see solution in editorial or you can see tops' solutions. For example Jiangly solved it with DSU
•  » » » » » » » » » 7 weeks ago, # ^ |   0 can you tell what is going wrong in my code in the same problem.(I am failing test case 3rd i have used fenwick tree tough).
•  » » » » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 UB if mp[v[idx - 1]].size() is zero and operations is positive: else if (operations > (int)mp[v[idx - 1]].size()) { cout << mp[v[idx - 1]][mp[v[idx - 1]].size() - 1] << endl; 
•  » » » » » » » » » 7 weeks ago, # ^ |   0 I updated but still it is giving me same error.
•  » » » » » » » » » 7 weeks ago, # ^ |   0 v[idx - 1]
•  » » » » » » » » » 7 weeks ago, # ^ |   0 still failed.
•  » » » » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 1 6 12 999999997 999999997 999999997 999999997 999999997 999999997 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 
•  » » » » » » » » » 7 weeks ago, # ^ |   0 can I ask one question How are you so fast at debugging?(I also wanan be that fast that will help me a lot).
•  » » » » » » » » » 7 weeks ago, # ^ |   0 No, I'm toooooooo slow. I should notice this bug after second-third code reread, but I was reading it during 11 minutes...Now I was just reading your code and comparing it with some others: your BIT seams OK, then bug must be in other parts of codeI've checked update: OKI've checked query: found UBWhat's left? Only filling of mp, you just fill without check that this element is already in mapJust small advice: use local variables like: thisint elem = v[idx - 1]; int sz = (int)mp[elem].size(); if (operations == 0) cout << elem << endl; else if (operations > sz) { if (sz) cout << mp[elem][sz - 1] << endl; else cout << elem << endl; } else { cout << mp[elem][operations - 1] << endl; } 
•  » » » » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Yes, you are correct it is more readable and understandable.
•  » » » » » » » 7 weeks ago, # ^ |   0 lol
•  » » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 hello, is this 192033289 for problem F hackable ? @Igorjan94
 » 7 weeks ago, # |   +3 Fun problemset. Managed to solve everything in 1:08, which I am quite proud of. E was very elegant, F and G2 were also nice.
•  » » 7 weeks ago, # ^ |   0 F was some standard stuff after you know it will take atmost 3 op to reduce the no to the final form.
•  » » » 7 weeks ago, # ^ |   0 Yeah, it is. But I still think it was nice.
 » 7 weeks ago, # |   0 i was expecting atleast one graph question xD
•  » » 7 weeks ago, # ^ |   0 me too lol.
 » 7 weeks ago, # |   0 Great contest. Thanks guys :-)
 » 7 weeks ago, # | ← Rev. 3 →   0 Very cool that F can be solved with set and DSU. I got stuck on BIT implementation because I don't have a template for it and have only solved a few CSES problems using it. Forgot about the limitation of 3 change operations. Thought G2 would be DP, but the binary search solution is quite elegant. 10/10 problemset overall.
 » 7 weeks ago, # |   0 did anyone use priority queue for the g2 question?
 » 7 weeks ago, # | ← Rev. 2 →   0 My live screencast with explanations for all problems. I have tried to re-explain last problem in the end after I solved it. The problems were very interesting. I felt the last problem was a bit on the harder side for a Div 4 round.
 » 7 weeks ago, # |   0 What's wrong with this solution of E 192043725? Thanks.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 The return value of your sol functuon is int instead of long long.
•  » » » 7 weeks ago, # ^ |   0 thanks
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Sir it was int overflow Spoiler#include using namespace std; long long sol(int n, vector& v){ long long qneg = 0, min_mod = 2e18; long long abs_sum = 0; for(int i = 0; i < n; ++i){ if(v[i] < 0) { qneg++; v[i] = v[i] >= 0 ? v[i] : -v[i]; } abs_sum += v[i]; min_mod = min(min_mod, v[i]); } if((qneg % 2 == 0)) return abs_sum; return abs_sum - 2 * min_mod; } int main() { int t; cin >> t; for(int i = 0; i < t; ++i){ long long n; cin >> n; vector v(n); for(long long& x : v) cin >> x; cout << (long long)sol(n, v) << '\n'; } return 0; } 
 » 7 weeks ago, # |   0 F was straight-forward lazy propgation question once you figured out it will take atmost 3 operations. I just copy pasted some template.
•  » » 7 weeks ago, # ^ |   0 I could not find the template for range update and point query. I could only manage to find for point update and range query smh.
 » 7 weeks ago, # |   0 D owned me, why am I so stupid >W<
 » 7 weeks ago, # |   0 can anyone hack my G2?I feel it not correct,even i pass the pretest https://codeforces.com/contest/1791/submission/192031288
•  » » 7 weeks ago, # ^ |   0 ok, I hack it myself. this is my first hack >W<
•  » » » 7 weeks ago, # ^ |   0 Try to hack my solution with yours hack test
•  » » » » 7 weeks ago, # ^ |   0 Uhhh~~~ I succeed
 » 7 weeks ago, # | ← Rev. 2 →   0 What is wrong with my solution for F? https://codeforces.com/contest/1791/submission/192046957
•  » » 7 weeks ago, # ^ |   0 You are only calculating up to two operations for every number, while there are numbers like $999\ 999\ 988$ which become 1-digit numbers only on the third operation.
•  » » » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16706 from CF Stress for a counter example.
 » 7 weeks ago, # | ← Rev. 2 →   0 Can anyone tell me why my dsu based code is giving runtime error ! It's well under the time complexity and limit. https://codeforces.com/contest/1791/submission/191951510
 » 7 weeks ago, # |   0 What's Segment tree doing in a div 4 round ?
•  » » 7 weeks ago, # ^ |   0 Look at the editorial. The intended solution doesn't use segment trees.
•  » » 7 weeks ago, # ^ |   0 You needn't use Segment Tree. In fact, dsu(Disjoint Set Union) can also pass F.
•  » » 7 weeks ago, # ^ |   0 Segment Tree is one of the ways of doing it.
 » 7 weeks ago, # |   0 Is there any penalty for unsuccessful hacking attempt/reward for Successful hacking attempt?
•  » » 7 weeks ago, # ^ |   0 no
•  » » 7 weeks ago, # ^ |   0 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
•  » » 7 weeks ago, # ^ |   0 Thank you
 » 7 weeks ago, # |   0 Very nice problems. Thanks for the contest. I managed to solve A,B,C,D,E,G1 within 50 minutes but could have had F as well if I knew segment tree.
 » 7 weeks ago, # | ← Rev. 2 →   0 F can be solved using set . you can update each index max 2 times . So after performing operation , if the result value is less than 10 , just erase that index from the set . code : https://codeforces.com/contest/1791/submission/191938508
 » 7 weeks ago, # |   0 Why G2 got a lot of hacks in first hour?
 » 7 weeks ago, # |   0 did someone do the g2 question using priority queue?
 » 7 weeks ago, # |   0 I did upsolving G2 :( That's too bad... I could all solving...Thanks for the great contest!
 » 7 weeks ago, # |   0 I can't understand how it works in Problem E. After all, we need to take exactly the neighboring elements and change the signs in them. If there are 7 numbers, for example -1 -2 -3 4 -1 -2 -3 the sum of 16 is not possible.
•  » » 7 weeks ago, # ^ | ← Rev. 6 →   0 First, take -3 and -1 as a boundary, then the array will become -1 -2 3 4 1 -2 -3 Next, take -2 and -2 as a boundary, then the array will become -1 2 3 4 1 2 -3 Last, take -1 and -3 as a boundary, then the array will become 1 2 3 4 1 2 3 You can make all the element in $[l,r]$ positive if $a_l<0$ and $a_r<0$ and $a_{l+1} \cdots a_{r-1}$ are positive, so it is not correct to take neighboring elements.
•  » » » 7 weeks ago, # ^ |   0 Select 2 neighboring elements and change their signs. That's what the condition says. I don't understand it.
•  » » » » 7 weeks ago, # ^ |   0 That's right. But for example, -1 2 -3, you can do such operations: 1 -2 -3 1 2 3 and that shows you can choose two negative numbers and turn $[l,r]$ positive
•  » » » » 7 weeks ago, # ^ |   0 Think it this way: '-' sign can just travel anywhere along array, bcoz if we do operation on 1 positive and 1 negative number signs of them will interchange, in this way we can make '-' sign travel along array.
»
7 weeks ago, # |
Rev. 2   -8

--Problem D from this contest submission link: --can anyone help me to findout the bugs of my code. its giving wa in test 2 in 160th differ. i can't figure it out i need the help of you experts. expecting your kindness. Thankyou

# include <bits/stdc++.h>

using namespace std;

# define ll long long

int main() { int t; cin >> t; while (t--) { ll n; cin >> n; string str; cin >> str; set s; int k = 1; vector v; int w = 0; for (int i = 0; i < n; i++) { s.insert(str[i]); w++; if (k == 1) {

         if (w != s.size())
{
v.push_back(s.size());
w = 0;
i--;
s.clear();
k = 0;
}
}
}

v.push_back(s.size());

sort(v.begin(), v.end());

if (v.size() == 1)
{
cout << v[0] << endl;
}
else
{
cout << v[0] + v[1] << endl;
}
}


}

•  » » 7 weeks ago, # ^ |   0 Take a look at Ticket 16709 from CF Stress for a counter example.
•  » » » 7 weeks ago, # ^ |   0 thanks a lot bro.
•  » » » » 7 weeks ago, # ^ |   0 bro did you manage to get pass 160th token?
 » 7 weeks ago, # |   0 I o_bserved it wont take more than 4-5 operations for problem F but still i thought my code wont iterate more than 4-5 times. I missed the case where any index gets query of type 1 of more than 5 times and not being called for query type 2. I unnecessarily did overthinking on whether I should have added min(5,cnt). I should have blindly added without thinking at all. After seeing TLE I got frustrated and forgot that I did some thinking on this check of min(5,cnt) .Now i feel stupid not to add this check of min(5,cnt)_
 » 7 weeks ago, # | ← Rev. 3 →   0 Why my solution for problem D is wrong 191979249? and that is the code:(for single test case):UPD: I solve it using this method and it is accepted int n; seth1; seth2; cin >> n; char c[n]; int ar[n]; for(int i=0; i> c[i]; h1.insert(c[i]); ar[i]=h1.size(); } for(int i=n-1; i>0; --i){ h2.insert(c[i]); ar[i-1]+=h2.size(); } sort(ar,ar+n); cout << ar[n-1]; 
•  » » 7 weeks ago, # ^ |   0 first loop should be upto n-1
•  » » » 7 weeks ago, # ^ |   0 This code is accepted
 » 7 weeks ago, # | ← Rev. 2 →   0 deleted
•  » » 7 weeks ago, # ^ |   0 Sir, what exactly makes you think the answer will be maximum in the way you are splitting the string?
•  » » 7 weeks ago, # ^ |   0 You can check my answer  int n; seth1; seth2; cin >> n; char c[n]; int ar[n]; for(int i=0; i> c[i]; h1.insert(c[i]); ar[i]=h1.size(); } for(int i=n-1; i>0; --i){ h2.insert(c[i]); ar[i-1]+=h2.size(); } sort(ar,ar+n); cout << ar[n-1]; 
 » 7 weeks ago, # |   +3 Well, it was surprising to me to know how the code for G2 went TLE during the comp (Though I know it was tightly bounded, it passed the given TCs after the comp, THE SAME CODE)... Can somebody hack it or let me know if it is still tightly bound on those TL? Here's the code — #192051148 Python o_O
•  » » 7 weeks ago, # ^ |   +3 Your code hacked by me :)
•  » » » 7 weeks ago, # ^ |   +6 Yes. Thanks. Thought it'll go TLE. :))
 » 7 weeks ago, # |   0 Can someone explain F?
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +8 The naive approach would be to iterate from $l$ to $r$ and apply the changes as mentioned in the statement. However, the time complexity is $O(nq)$ for this approach which will TLE.Consider what happens when we apply the operation $a[i] := d(a[i])$ to an index $i$ (here $d(x)$ denotes the sum of digits of $x$). Clearly, $d(a[i])$ is $O(\log a[i])$, since there are $O(\log a[i])$ digits in $a[i]$, and each of them is upper bounded by $9$. So roughly the operation corresponds to doing $x \mapsto c \log x$.Intuitively, the idea is that this reduction is huge, and the number of times you will need to apply this operation till you get a single digit number is quite small. At least you can show that every time we apply this operation on a number having at least 2 digits, the number of digits never increases after applying this operation, and in fact it decreases by at least 1 after at most 2 operations. So you need at most $18$ operations (which is a very loose bound, and the editorial shows that you can replace it by $3$) under these constraints to get to a single digit number, which satisfies $x = d(x)$. So after a small number of operations on $a[i]$, you end up with a single digit number, after which applying the operation on it doesn't change the number.So let's do this mentally: maintain a (sorted) list of indices which have $a[i] > 9$. These are the indices on which doing the operation can potentially change the number. When you're applying the update on a range, you find the indices in this list that will need a change (the remaining ones are fine as they are). Let's not think about how we will find the indices at this point. For each index, we will process it at most $18$ times before it gets out of the list. So overall, the total number of indices considered is $18n$.Now using a std::set and lower_bound, you can find and update the (sorted) list in $O(\log n)$ time per operation.
•  » » » 7 weeks ago, # ^ |   0 So, if we have list [1, 2, 3, 4, 5], and l, r = 2, 3, we start at a[1] = 2, then we check every other element <= r and if it's < 10, we erase it? So, if a[1] and a[2] will become < 10 after that, our list will be [1, 4, 5]
•  » » » » 7 weeks ago, # ^ |   +8 Yes
•  » » » » » 7 weeks ago, # ^ |   0 Ok, thanks
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 used the same concept but i got runtime error on test 3 whats the issue ?
•  » » » » 7 weeks ago, # ^ |   +9 You did low = *it; after removing the iterator from the set. From here, iterators that are erased are not valid anymore. You should set the value of low before you erase it.
•  » » 7 weeks ago, # ^ |   0 ApproachMake an array (vector a, initialized to 0) for checking whether elements are less than or greater than equal to 10 (10 is because you cannot change values below 10). Take one number c(initialized to 1).If values in input array v from [l,r] are less than 10 then you have [l,r] that you don't need to update in the future. So, keep this information in array a. HowUpdate array a in range [l,r] as c. Then do, While (l>=0 && a[l]!=0) keep decreasing l and updating a[l] = c (This helps to merge some other range where values are less than 10). Do the same thing to the right `While r
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 It gives TLE. Ignore it
 » 7 weeks ago, # |   0 Any Test Cases for Hacking in Question F and G2
 » 7 weeks ago, # |   0 Will successful or unsuccessful hacking attempts affect my position in standing?
 » 7 weeks ago, # |   +9
 » 7 weeks ago, # |   0 my first fst round... it teach me a lot.
 » 7 weeks ago, # |   0 is the rating out?
 » 7 weeks ago, # |   0 can someone kindly help me on problem 4? what if the input is: knllvucvub? what would be the output for it?
•  » » 7 weeks ago, # ^ |   0 answer will be 9
•  » » » 7 weeks ago, # ^ |   0 yes, got it. Thank you.
 » 7 weeks ago, # |   +1 Anyone tell me why this got hacked for G1? Submission https://codeforces.com/contest/1791/submission/191967985
•  » » 7 weeks ago, # ^ |   0 Rishabh_coder you used the condition : if(c < arr[i]){ break; } , it should be : if(c <= arr[i]){ break; }
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 coins can't be zero?
 » 7 weeks ago, # |   0 When will the ratings update?
•  » » 7 weeks ago, # ^ |   0 The contest still need to remove cheaters after system test. So just wait for 1~2 h.
•  » » » 7 weeks ago, # ^ |   0 cool thanks :)
 » 7 weeks ago, # |   0 Can anyone help me understand why is the contest unrated for me please?
 » 7 weeks ago, # | ← Rev. 3 →   0 When are ratings updated? I am excited to see my new green color.
•  » » 7 weeks ago, # ^ |   0 Same :)
•  » » 7 weeks ago, # ^ |   0 It is fantastic!
 » 7 weeks ago, # |   0 It was an enjoyable contest, thanks
 » 7 weeks ago, # |   0 unrated,┭┮﹏┭┮
 » 7 weeks ago, # |   0 Why does the contest show as unrated for me even though I am a newbie?
•  » » 7 weeks ago, # ^ |   0 Because ratings are not updated as of now. That's why it is showing unrated for now. It will take some time then it will display as rated.
 » 7 weeks ago, # | ← Rev. 2 →   0 Problem F ,range update and point query was very nice.I solved it using square root decomposition:).
 » 7 weeks ago, # |   0 Did they change tests for C. I had done a typo in my code, a <= was == but it went through during the contest and it was accepted, it was accepted after the competition as well, but just today it turned into being not accepted. From a positive rating change to a negative rating change, nice.
•  » » 7 weeks ago, # ^ |   0 Your code was tested on the added test cases from the hacking phases, the final testing started after the hacking phase was ended around 12 hours ago and that is why it changed today.
 » 7 weeks ago, # | ← Rev. 2 →   0 I didn't get the rating. Does anyone get ? **** NOTE: This is my first contest
•  » » 7 weeks ago, # ^ |   0 not yet
•  » » 7 weeks ago, # ^ |   0 Not yet. I guess it will be updated within few hours.
 » 7 weeks ago, # |   0 I like how G2 has like 58 tests but still wrong greedy solution gets AC
 » 7 weeks ago, # |   0 i have some issues with the problem F I used https://cp-algorithms.com/data_structures/fenwick.html#finding-sum-in-one-dimensional-array they skipped my submisions
 » 7 weeks ago, # |   0 what can i do i get skipped my problems
•  » » 7 weeks ago, # ^ |   0 Your code might have significantly matched with someone else's code then. You can check your talks or post about it on a specific blog about same.
•  » » » 7 weeks ago, # ^ |   0 Which blog?
 » 7 weeks ago, # |   0 My solution is skipped and i didn't Cheat we just at same university and think in same way
•  » » 7 weeks ago, # ^ |   0 ~ think in same way hnmm that makes sense
•  » » » 7 weeks ago, # ^ |   0 We have the same coach to lern us how to solve
 » 7 weeks ago, # | ← Rev. 3 →   0 I recently got a message from Codeforces team that my solution 191923515 matches with 192031691. But I used the segment tree code template from 188598221 which was used long ago in some contest and I usually use the same template as this one. MikeMirzayanov please check it once, I haven't copied the code from some other user, I just used a previously used template of code which I usually use for implementation of segment tree. We all study at the same university so we use the same template of code we shared once. I hope the plagiarism is removed and my solution is judged.
 » 7 weeks ago, # |   0 I used exactly the same idea written in the editorial in problem F but my code gets TLE during the system test ,please somebody should look at this https://codeforces.com/contest/1791/submission/191992725
 » 7 weeks ago, # |   0 My submissions for the last contests were skipped however I neither had copied someone else code nor I made my code public. I submitted the solution that is later skipped within 7-8 minutes after the start of the contest and 3-4 minutes after the submission of previous solution. It was just a coincidence that some other person out of 30000 people giving contest had use the same logic and even use the same name for the variables(x and y as the problem was related to coordinates). I request you/Codeforces to revert your decisions as it was just a coincidence and I never had used any kind of malpractices while solving problems, I give contests to practice coding problems and rating is not of much importance to me that I use unfair means to solve problems.
 » 7 weeks ago, # |   0 My solution for the Question B (Vkas/191968402) was found to be coinciding with Raka_03/192030254 and my solutions were skipped. However, This was mere a matter of pure coincidence and I don't have any contact with the other person concerned. This is also clear by the fact that my other solutions are very much different from his solutions. Kindly consider my request sympathetically. At least accept my submissions for the other questions where my solution was found to be genuine. I am not sure what was the main reason for this mishappening. I always use jdoodle for writing and compiling my code. Also, I clean up the editor after submitting the code. Hence, I am not sure whether IDE might be the reason. In any case, I will make sure that I work with more caution in future so that these things don't repeat. I hope you will consider my case and accept my submissions.
 » 7 weeks ago, # |   0 My solution 191883487 for the problem 1791B significantly coincides with tithi01/191909383 and all my solutions were skipped . There is a high probability of similarity between solutions in this problem , In addition , I have solved this problem in about 10 min.
 » 7 weeks ago, # |   0 Hopefully, this was my last rated Div. 4 round.
 » 7 weeks ago, # |   0 I recieved a message from codeforces regarding plagiarism , I just used the same template of segment tree which was forwarded in our institute , and my code 192031691 only matches with the template of 191923515 and doesnt match with my logic as we are in the same college so just template is same , else our logic is completely different , I implemented it the other way, it is no cheating case, please consider my solution, and make it rated for me. Thanks in advance.
 » 7 weeks ago, # |   0 I,Timi66,AK.
 » 7 weeks ago, # |   0 My submissions for the last contests were skipped however I neither had copied someone else code nor I made my code public (You said that my solution 191884065 for the problem 1791B significantly coincides with solutions Salonig/191878195, Evlalia/191901103). There is a high probability of similarity between solutions in this problem, cause we just think the same way. It was just a coincidence that some other person out of 30000 people giving contest had use the same logic and even use the same name for the variables (x and y as the problem was related to coordinates, but not all of variables is the same). I request you/Codeforces to revert your decisions as it was just a coincidence and I never had used any kind of malpractices while solving problems.
 » 7 weeks ago, # |   0 Why my div 4 was skipped
 » 7 weeks ago, # | ← Rev. 3 →   0 Your solution 191875350 for the problem 1791B significantly coincides with solutions hsn/191875350, Rajesh_459/191876092. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.This is frustrating also felt very insulting, the solution of B is very simple so anybody could have similar solution as mine. So MikeMirzayanov please consider my submission.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 same with uAttention!Your solution 191911973 for the problem 1791B significantly coincides with solutions Anhtuan2007tc/191911973, Clitch/192012321, Clitch_01/192019606. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.B is very simple so so anybody could have similar solution
 » 7 weeks ago, # | ← Rev. 4 →   0 Attention!Your solution 191911973 for the problem 1791B significantly coincides with solutions Anhtuan2007tc/191911973, Clitch/192012321, Clitch_01/192019606. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.B is very simple so anybody could have similar solutionAlso, when i check his submissions, he submitted a lot. All of them are wrong. He has the same idea because this is just implementation. During the contest he took 1 hour to solve B. I don't know why his solution is similar to mine . Please take a look.
 » 7 weeks ago, # |   0 PLZ can someone explain why my G1 submission got HACKED @Nobdefender https://codeforces.com/submissions/R2M#
•  » » 7 weeks ago, # ^ |   0 Also if possible plz explain why this was accepted https://codeforces.com/contest/1791/submission/192228364
 » 7 weeks ago, # | ← Rev. 2 →   +3 I got a mail from the codeforces that my solution 191964891 for the problem 1791G1 significantly coincides with solutions heavierfire/191964891, abhinav.maurya202/191979043. It is a pure coincidence case and I have not copied it from anywhere. The variables used in the code are pretty common and there is a very high probability that it can be used by others. And also the logic for the problem was also very standard in my opinion.So I request you to please have a look and consider my submissions for the contest.Thanks
 » 7 weeks ago, # |   0 wrong answer 437th numbers differ — expected: '35', found: '8'whats the 437 th input of f ??