### doreshnikov's blog

By doreshnikov, history, 4 weeks ago, translation,

Hello Codeforces!

Sorry for a bit delayed English announcement, we are glad to invite you all to Codeforces Round #744 (Div. 3), third division round held on Sep/28/2021 17:35 (Moscow time). This round was prepared by me and MikeMirzayanov and we hope that you'll find the problems interesting and enjoy solving them.

I would like to thank MikeMirzayanov for helping me with both writing and preparing the problems for this round. Since it's the second Div. 3 round held I'm involved in but only the first one I'm preparing problems for from zero all the way to the end, without his guidance it would've taken much more of my time.

Also special thanks to nizamoff, andreumat, QAZZY, Vladosiya, CtrlAlt, vladmart, Igorjan94, okwedook, I_Remember_Olya_ashmelev and Aris_244_ for testing the round and giving their feedback on the problems as well as to Gassa and geranazavr555 for proofreading and correcting the statements. This round is very noticeably better than it could've been without your contribution. And last but not least, thanks to everyone who'll be participating! This round contains 7 to 8 problems and is expected to be of decent level of difficulty for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. We tried to make tests strong enough but it doesn't at all guarantee that open hacks phase will be pointless.

You will be given 7-8 problems and 2 hours 15 minutes to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

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

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Good luck and have fun!

UPD: Editorial is out!

• +300

 » 4 weeks ago, # |   +19 Is there a way to become a tester if there is no communication with codeforces admins?
•  » » 4 weeks ago, # ^ |   +100 For such rounds, I myself usually write requests to test those who have a long history of participation (years), have no incidents with code matches, and so on. I will write to you in PM :-) Thanks!
•  » » » 4 weeks ago, # ^ |   +21 Thanks! I would be grateful if you give me at least one chance.
•  » » » » 4 weeks ago, # ^ |   0 You should be grateful, you got a chance
•  » » » 4 weeks ago, # ^ |   0 is there a specific level for the tester Would someone below expert be useful
•  » » » 4 weeks ago, # ^ |   0 Hello MikeMirzayanov, my code was only once found plagiarised a few years ago because I was stupid back then and from that point on I haven't cheated at any platform. Can I still dream to become a tester at codeforces in some contest in the future?
•  » » » » 4 weeks ago, # ^ |   0 I think specialist isn't enough for testing maybe some authors would I have seen newbies test sometimes maybe it's good to see what a beginner could do but generally it's not very useful because the more skilled the tester is the more possibility he can find issues with the problem And I did that stupid mistake like 3 times not to gain any raiting I would never gain 1 raiting like that but I participated while I had terrible focus and i didn't want to lose so much rating before Scpc and got caught the last time and that made me feel like shit and I didn't do that again since that time but I guess it's too late to fix that who cheated once isn't trust worthy anymore because it's possible to not get caught if you put some effort on it they wouldn't trust you even if you won't do that again because maybe now you could cheat without them knowing :(
•  » » 4 weeks ago, # ^ |   +7 It's also one of my questions.****
•  » » 4 weeks ago, # ^ |   0 @nizamoff your pp is awesome.
•  » » » 4 weeks ago, # ^ |   +3 what is pp?
•  » » » » 4 weeks ago, # ^ |   +4 Profile picture?
•  » » » » 4 weeks ago, # ^ |   -8 i think it is "butt"
 » 4 weeks ago, # |   +36 My first unrated round.
•  » » 4 weeks ago, # ^ |   +5 I love seeing your progress chart. Inspiring
 » 4 weeks ago, # |   +5 i hope to be specialist after this round ..
 » 4 weeks ago, # |   +1 It may be a rare 8-problems div 3 round!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +12 Also it's rare to see something like this : same same same same same same same same same same same same same same same ....... code. Butdifferent people 🤯
•  » » » 4 weeks ago, # ^ |   0 How? are they cheating ?
 » 4 weeks ago, # |   0 OH MY GOD! I can't wait for this div 3 contest! I heckin' love div 3 contests!
•  » » 4 weeks ago, # ^ |   +1 BatChest! I heckin' can't wait to become cyan!!
 » 4 weeks ago, # | ← Rev. 2 →   -17 As a contestant, I hope the time complexity of me becoming an expert is $O(1)$.
•  » » 4 weeks ago, # ^ |   +61 10000000000000000 is $O(1)$...
•  » » » 4 weeks ago, # ^ |   0 Yeah, unfortunately :(
•  » » 4 weeks ago, # ^ |   +9 As long as the space complexity of your corny jokes remains $O(1)$. :P
 » 4 weeks ago, # |   0 Will a non-trusted participant be rated? New one here can not be trusted.
•  » » 4 weeks ago, # ^ |   +1 Yes it would be rated for non trusted participants with a rating below 1600
 » 4 weeks ago, # |   +2 Just failed School's selection round for NOI.
•  » » 4 weeks ago, # ^ |   +22 Just relax and keep going.I really admire that you have the opportunity to participate in information competition in the stage of middle school. The future will be full of light and hope,Just keep going. I believe as long as you persist on learning programming, u can become the person u want. No matter NOIP first level, or NOI gold medal,u still have the opportunity,u still have the hope and energy!!!!!
 » 4 weeks ago, # | ← Rev. 3 →   +13 This is one of most awaited contest for me , a week without contest on codeforces is hard :( .
 » 4 weeks ago, # |   +2 I hope I can become blue after this round.
•  » » 4 weeks ago, # ^ |   +2 Same for me. Best of luck!
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   -23 I hope I can become cyan after this round.
•  » » » » 4 weeks ago, # ^ |   +7 I hope I become green :)
 » 4 weeks ago, # |   0 Will be fun. I'm all fired up.
 » 4 weeks ago, # |   +1 honestly, many of us was waiting for this round, thanks
 » 4 weeks ago, # |   0 Very nice! Looking forward to my first rated round
 » 4 weeks ago, # |   -23 I wish that i become Specialist after this round. Upvote for best wishes. Thanks and Good luck to all.
•  » » 4 weeks ago, # ^ |   +13 Oops!! downvoted by mistake
•  » » 4 weeks ago, # ^ |   0 it will be hard but wish you success!
 » 4 weeks ago, # |   +4 A round after more than a week. Wish ya'll the best of luck.
 » 4 weeks ago, # |   +15 lighthearted meme
 » 4 weeks ago, # |   -8 My first round :)
 » 4 weeks ago, # |   -9 Enjoyed your first div3 round, hopefully will also enjoy the second one. Really excited about the div3 round.
 » 4 weeks ago, # |   -24 Always better to participate in contest instead chatting with gf. Hahaha
•  » » 4 weeks ago, # ^ |   +8 What is a gf?
•  » » » 4 weeks ago, # ^ |   0 I see you're a man of tradition
•  » » » » 4 weeks ago, # ^ |   0 yes, man of culture indeed.
 » 4 weeks ago, # |   -12 Will this round be easier than the last Div.3 contest?
•  » » 4 weeks ago, # ^ |   +2 This was my first comment, and I don't know why this is so downvoted why is it downvoted?
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   -9 If you are less than Expert. Then there are high chances for your comment to get downvoted. This happens with me too.Edit: thanks for proving what i said above.
 » 4 weeks ago, # | ← Rev. 3 →   -17 Deleted
 » 4 weeks ago, # | ← Rev. 2 →   +3 I am on a streak lately, I became 5* on Codechef few days back and qualified for hackercup T-shirt too, I hope my streak continues!Wish Me Luck!UPD: Didn't do very good but since I avoided negative delta so I think the streak is still on.
 » 4 weeks ago, # |   0 How do I withdraw from this?
•  » » 4 weeks ago, # ^ |   0 you don't need to withdraw. As long as you don't submit a solution your candidature will not be considered.
•  » » 4 weeks ago, # ^ |   0 Open https://codeforces.com/contestRegistrants/1579/friends/true and click on the [x] next to your name.
 » 4 weeks ago, # |   0 Going to be a trusted participant after this. Yay!
 » 4 weeks ago, # |   0 Loved the gradual increase in difficulty in the last contest conducted by +doreshnikov , hope to see a simillar round today!
 » 4 weeks ago, # |   -10 There is too much of a difficulty gap b/w A and B !! B is not at all a regular Div.3 B problem.
•  » » 4 weeks ago, # ^ |   -8 Exactly bruh, The B is easily a 1000+ rated problem.
•  » » 4 weeks ago, # ^ |   0 B was an easy one if you have solved pancake sorting on leetcode . Here instead of reversing the array, we have to rotate it and with that less constraint even a brute solution will be accepted
•  » » » 4 weeks ago, # ^ |   0 Any problem can be described "easy" in someone's perspective. But it wasn't an ideal Div.3 B problem.1.
•  » » » » 4 weeks ago, # ^ |   0 Yes, I agree E1 was much easier than B.
•  » » 4 weeks ago, # ^ |   0 Unless you know how to do selection sort.
•  » » » 4 weeks ago, # ^ |   0 To be precise..Insertion Sort
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 To be precise — either will do.UPDATE. Confirmed by the editorial.
 » 4 weeks ago, # | ← Rev. 2 →   +4 implementationforces
 » 4 weeks ago, # |   -6 i hate this round , all implementation based
 » 4 weeks ago, # | ← Rev. 3 →   +10 Sorry to bother folks who are participating in today's round, but today's round requires a serious plag check, problem B had a sudden surge in submissions from 3K to 7K in just 5 minutes. Like seriously? I don't think B was an easy one to solve for most folks below the 1300 rating (I got it right after like 5-6 attempts).
•  » » 4 weeks ago, # ^ |   0 i agree
•  » » 4 weeks ago, # ^ |   0 Just because you can't doesn't mean anyone else can't.
•  » » » 4 weeks ago, # ^ |   +4 Firstly, who said I didn't? Secondly, I am referring to the sudden surge in the submissions for B in such a short time, not about who's able to solve the problem.
•  » » » 4 weeks ago, # ^ |   0 Yes you're right @20203246 I solved in 2nd attempt.
•  » » » 4 weeks ago, # ^ |   0 I was able to do it mate
•  » » 4 weeks ago, # ^ |   0 there were a blog and a youtube chanel (same person) posted full AC code from A to E2 while the contest were ongoing
 » 4 weeks ago, # |   +7 While Polycarp is on vacation Casimir is taking over.
 » 4 weeks ago, # |   +30 Today's round had nice problems (especially F and G). Thanks to MikeMirzayanov for amazing m2.codeforces.com platform (I had connection problems and the lightweight version was very useful). :D
 » 4 weeks ago, # |   +1 Enjoyed this round. Especially E2.
 » 4 weeks ago, # |   0 Holly… Amazing div. 3 round! Btw. anyone knows why cf-predictor is down?
•  » » 4 weeks ago, # ^ |   +21 Mike must have closed off Codeforces API to reduce server load.
 » 4 weeks ago, # |   0 This problem is so hard for me :(
 » 4 weeks ago, # |   0 How to solve E2 ?
•  » » 4 weeks ago, # ^ |   +1 Suppose l_i is the increase in the number of inversions if you add i_th element to the beginning and r_i is the increase in the number of inversions if you add i_th element to the end.It's easy to observe that neither of l_i or r_i depend on the order of first i-1 elements. So, just add min(l_i,r_i) to the answer at each step.
•  » » 4 weeks ago, # ^ |   +11 For E2, first apply coordinate compression.Then, using a segment tree/binary index tree, calculate whether prepending or appending the element is better. It's better to prepend the element whenever there are more processed things greater than the current element. Better to append the element whenever there are more processed things less than the current element.130179241
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 It's better to prepend the element whenever there are more processed things greater than the current element. Better to append the element whenever there are more processed things less than the current element.Is there a proof for this process working greedily? I mean wouldn't the answer change for the (i+1)th element change depending on where the ith element is placed? A bit confused over this intuition. (The position of the ith element may add to the inversion count of the (i+1)th element)
•  » » » » 4 weeks ago, # ^ |   0 Not really, the ith element can only be either added to the beginning or the end, so the only thing that matters is among the first (i-1)th numbers,how many numbers are smaller than the ith number if you are adding it to the beginning, and how many numbers are greater than the ith number if you are adding it to the end.
•  » » 4 weeks ago, # ^ |   +8 You can also solve it using: C++ pbds 
 » 4 weeks ago, # |   +1 Is there a way faster than nlogn for E2? I was so happy when i came up with a multiset, but it still TLE
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 I used coordinate compression + segment tree. Multiset won't work as you can't find distance in constant time. There is something called ordered set, maybe use that. I haven't used it personally.
•  » » » 4 weeks ago, # ^ |   +1 wait, does distance( ms.begin(), iterator ); take linear time?
•  » » » » 4 weeks ago, # ^ |   +2 Yes.
•  » » » 4 weeks ago, # ^ |   +8 I did use ordered multisetYou can view my Submission here
•  » » » » 4 weeks ago, # ^ |   0 Thank you mate I didn't know about that, Here is my submission using ordered_multiset submission
•  » » » 4 weeks ago, # ^ |   0 Well I learnt something, thank you guys!
 » 4 weeks ago, # |   +3 Loved the contest, The Problem D on this contest is similar to a previous Div 3 round D problem. Link to the similar problem : https://codeforces.com/contest/1506/problem/DI request everyone , who read the problem D or solved it to go through it also once. The concept required to solve both the problems are similar.It is such a nice question on the application of Heaps(Priority Queues).
•  » » 4 weeks ago, # ^ |   0 Thanks, mate. Your solution cleared some of my doubts on heaps and priority queues. :)
 » 4 weeks ago, # |   +4 Good round. BTW, how to solve G?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +47 The final answer will always be less than $2*max(Ai)$ so you can make a 2-d dp of $n * 2e3$ where $dp[i][j]$ will give the minimum length of remaining part of segment on the right assuming that you are at $j$ distance from the start of the segment after processing first $i$ values.Code
•  » » » 4 weeks ago, # ^ |   +13 If I am not wrong, in your soln you have assumed there exists a soln when we never go to any -ve number. Can you give proof of this?P.S. Correct me if I am wrong.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +19 I initialised the first segment at positions greater than 0 as well to handle this case.
•  » » » » » 4 weeks ago, # ^ |   +13 So, you took all the points from [1,2e3] as possible starting points. Cool trick. I figured out that max ans will be 2e3 but didn't know how to maintain both the boundaries as well as current location. Thank you!
•  » » » 4 weeks ago, # ^ |   0 Thanks a lot! I solved G!
 » 4 weeks ago, # |   0 3 questions gang?
•  » » 4 weeks ago, # ^ |   0 Affirmative. Solved A,B and E1.
 » 4 weeks ago, # |   0 Did I just participate in a div-2 round?
•  » » 4 weeks ago, # ^ |   0 No
 » 4 weeks ago, # |   +24 What would be problem rating of E1 ? 800 ?
 » 4 weeks ago, # |   0 why nlogn solution give TLE on E2?
•  » » 4 weeks ago, # ^ |   +1 My segment tree solution passed. So, you must be doing something wrong.
•  » » » 4 weeks ago, # ^ |   0 i was using policy based data structure. Its complexity is logn i guess?
•  » » » » 4 weeks ago, # ^ |   0 You have to read the documentation on policy based data structures, but I won't be surprised if order_of_key or count is $\mathcal{O}(n)$.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +7 count in a multiset is $\mathcal{O}(k + \log N)$, where $k$ is the count returned.order_of_key is $\mathcal{O}(\log N)$.Note: find_by_order is also $\mathcal{O}(\log N)$
•  » » » » » » 4 weeks ago, # ^ |   0 I think he has TLE because of mss.count(). He should use std::map. I think his code will be like:  int n; cin >> n; int arr[n]; for (int i = 0; i < n; i++) cin >> arr[i]; op_set s; ll ans = 0; map mss; for (int i = 0; i < n; i++) { if (i == 0) { s.insert(arr[i]); mss[arr[i]]++; } else { int pos = s.order_of_key(arr[i]); ll ans1 = pos; ll ans2 = s.size() - pos - mss[arr[i]]; //cout << ans1 << " " << ans2 << endl; ans += min(ans1, ans2); s.insert(arr[i]); mss[arr[i]]++; } } cout << ans << endl; 
•  » » » » » » » 4 weeks ago, # ^ |   0 Yes, it gains AC: 130194814
•  » » » » » » » » 4 weeks ago, # ^ |   0 Why ans1 = pos . I think it should be more than that numbers less than a[i] will be in multiple frequency but your ordered set constains them only once
•  » » » » » » » » » 4 weeks ago, # ^ |   0 I have ordered multiset, because in using orset I have comp $\textbf{less_eqaul<>}$
•  » » » » » » » 4 weeks ago, # ^ |   0 How are you Handling Duplicate elements?????
•  » » » » » » » » 4 weeks ago, # ^ |   0 std::map
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Is your op_set ordered multiset or similar to multiset.??
•  » » » » » » » » » 4 weeks ago, # ^ |   0 ordered multiset
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Noiceee
•  » » » » 4 weeks ago, # ^ |   0 Time complexity of mss.count() is logarithmic in size and $\textbf{linear}$ in the number of matches. So I think your solution is $O(n^2)$
•  » » 4 weeks ago, # ^ |   0 130192451 — AC with some changes to your code
•  » » » 4 weeks ago, # ^ |   0 Thanks
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 It was because of multiset's count function, it can go up to O(N) (N : number of occurrences of the number). Should have used a map to count the occurrences.
 » 4 weeks ago, # |   0 where to access the editorials of #744 (Div.3)?
•  » » 4 weeks ago, # ^ |   -57
•  » » » 4 weeks ago, # ^ |   0 Got tricked again. XD
 » 4 weeks ago, # |   +4 Great round. But I would have appreciated some drawings in G, as in C.
 » 4 weeks ago, # |   +6 RIP my rating . I was trying right shift in problem B :')
•  » » 4 weeks ago, # ^ |   +1 RIP
•  » » » 4 weeks ago, # ^ |   -6 I could have solved 7 problems today :) Disgusting .
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 #metoo
•  » » » 4 weeks ago, # ^ |   +3 Such a waste of effort . After 1 hour , I have realize that . C,D,E1 all took 1 hour just . B took whole the time and feeling terrible for this >_<
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 It took me 1 hour to solve problem C, but 21 minutes to solve D,E,E1, and E2.
•  » » » 4 weeks ago, # ^ |   +1 It took me 37 minutes to solve ABDE1 and 1.5 hour to solve C. 20 minutes to solve E2 (after the contest). Amazing!
•  » » 4 weeks ago, # ^ |   0 I also did the right shift first, after I just changed the value of shift offset from d to r-l+1-d.
•  » » » 4 weeks ago, # ^ |   0 Yeah the statement was kind of misleading, when they shoes how the shift should work in the examples they started by the results, i got tricked too xd
•  » » 4 weeks ago, # ^ |   0 Same man!!
•  » » 4 weeks ago, # ^ |   0 same issue bro. ≧ ﹏ ≦
 » 4 weeks ago, # |   0 I didn't able to solve any question By the way I try solve the first question but unable
•  » » 4 weeks ago, # ^ |   0 the next time will be good :D
•  » » » 8 days ago, # ^ |   0 Thanks i'll try
 » 4 weeks ago, # |   +3 As I remember, Problem D was already used in past contests with different statement but same idea
 » 4 weeks ago, # |   +18 It would have been better if F had integers upto $10^9$ instead of 0's and 1's .The problem would have been similar to this and we would have to just process Range AND Queries on individual components
 » 4 weeks ago, # | ← Rev. 2 →   -21 My reaction seeing that the guy name was Casimir: Brazilian meme
 » 4 weeks ago, # |   0 Implementforces, Bruteforces :DD
 » 4 weeks ago, # |   +3 The problems were literally all over the place.Even deciding which ones to solve was more difficult than E1.
 » 4 weeks ago, # |   +2 How to solve G? something like dp?
 » 4 weeks ago, # |   0 Can someone elaborate the problem C please, still I can't understand what it wants!!
•  » » 4 weeks ago, # ^ |   0 It's asking you to check if you can construct a grid solely using 'V' shaped patterns of size K or greater.
•  » » » 4 weeks ago, # ^ | ← Rev. 5 →   0 4 7 1 Spoiler*.....* .....*. ..*.*.. ...*...why here answer 'NO', There is a V shape from position 3 3 of size 1
•  » » » » 4 weeks ago, # ^ |   0 Because the first '*' in the first row is not a part of any V. The smallest V (K = 1) consists of 3 '*'s.
•  » » » » » 4 weeks ago, # ^ |   0 oh, got it. Thanks a lot
•  » » 4 weeks ago, # ^ |   0 First , understand by yourself how a tick of size d is made. I hope you got it.Then , suppose you have a n X m grid . You have painted some ticks of length >= d on it . Now , in the question , you are given a painted grid. You have to tell whether this grid can be generated or not !
 » 4 weeks ago, # |   +5 THE EASIEST E1 EVER! :)
•  » » 4 weeks ago, # ^ |   0 but don't get hacked due to weak testcases...
 » 4 weeks ago, # | ← Rev. 2 →   0 Can someone help me to figure out the mistake with my logic/code for problem E2?(thanks in advance)Logic: During each insertion, let the current element be K, we add min(number of elements strictly lower than K, number of elements strictly greater than K) to the answer. I implemented this using PBDS multiset.my submission
•  » » 4 weeks ago, # ^ |   0 I too have an almost identical solution (and an identical result). Considering that I created it with only ~15 minutes remaining, there must an embarrassing mistake somewhere in there. My submission
•  » » » 4 weeks ago, # ^ |   0 ordered_set contains unique elements only once so this code fails for duplicate elements
•  » » 4 weeks ago, # ^ |   0 ordered_set contains unique elements only once so this code fails for duplicate elements
•  » » » 4 weeks ago, # ^ |   0 I changed it to multiset by changing less to less_equal in the following segment:From: #define ordered_set tree, rb_tree_tag, tree_order_statistics_node_update> To: #define ordered_set tree, rb_tree_tag, tree_order_statistics_node_update> 
•  » » » » 4 weeks ago, # ^ |   0 Oh! they it may work, I always use pairs my code is similar to you.
•  » » 4 weeks ago, # ^ |   +1 you are not doing mp[v[0]]++;
•  » » » 4 weeks ago, # ^ |   0 my code works flawlessly now, thanks a lot bro
 » 4 weeks ago, # |   +1 T~T,It was another very violent topic, and then I saw that I finished it in three minutes, but I felt good on the whole
 » 4 weeks ago, # |   0 How to solve G?
 » 4 weeks ago, # |   0 thx for the contest
 » 4 weeks ago, # |   +17 A to F easy solutions with Code and Explanations Happy Coding. AJust check if the Count of B equals (length of the string)/2. Codevoid solve() { int a = 0, b = 0, c = 0; string s; cin >> s; for(auto c: s) { if(c == 'B') b ++; } if(2 * b == s.length()) { cout << "YES\n"; } else { cout << "NO\n"; } }  BIterate this algorithm n times.For each, i from 1 to n find an index of the minimum element from the array i to n , lets name it ind. and left shift the whole subarray i to ind (ind — i) times. Codevoid solve() { int n; cin >> n; vector v(n); for(int i = 0; i < n; i ++) { cin >> v[i]; } vector> ops; for(int i = 0; i < n; i ++) { int ind = i; int ele = v[i]; for(int j = i; j < n; j ++) { if(v[j] < ele) { ele = v[j]; ind = j; } } int dis = ind - i; if(dis > 0) { ops.push_back({i + 1, ind + 1, dis}); vector temp = {v[ind]}; for(int j = i; j < ind; j ++) { temp.push_back(v[j]); } for(int j = i; j <= ind; j ++) { v[j] = temp[j -i]; } } } cout << ops.size() << endl; for(auto it: ops) { for(auto i: it) { cout << i << " "; } cout << endl; } }  CFor each element {i, j} of the matrix go as far maximum upwards in both left and right until both the top elements of the V (tick) are '*', if the size of this V > k mark all the elements we currently visited in a temporary matrix.If there is a '*' left in the string which is not marked in final temp matrix return no else return yes. Codeint mat[20][20]; bool isthis(vector v, int i, int j, int K, int n, int m) { int x = j; int y = j; int k = 0; vector> pos; while(i >= 0 && y < m && x >= 0) { if(v[i][x] == '.' || v[i][y] == '.') { break; } pos.push_back({i, x}); pos.push_back({i, y}); k ++; i --; x --; y ++; } if(k < K) { return 0; } for(auto it: pos) { mat[it[0]][it[1]] = 1; } return 1; } void solve() { int n, m, k; cin >> n >> m >> k; vector v(n, string(m, '.')); memset(mat, 0, sizeof(mat)); int ans = 0; for(int i = 0; i < n; i ++) { cin >> v[i]; for(int j = 0; j < m; j ++) { isthis(v, i, j, k + 1, n, m); } } for(int i = 0; i < n; i ++) { for(int j = 0; j < m; j++) { if(v[i][j] == '*' && !mat[i][j]) { cout << "NO\n"; return; } } } cout << "YES\n"; }  DJust always chose 2 people which have maximum meeting hours left. Codevoid solve() { int n, m, k; cin >> n; int i = 1; priority_queue> pq; for(; i <= n ; i ++) { cin >> k; if(k) pq.push({k, i}); } vector> ops; while(pq.size() > 1) { auto i1 = pq.top(); pq.pop(); auto i2 = pq.top(); pq.pop(); ops.push_back({i1[1], i2[1]}); i1[0] --; i2[0] --; if(i1[0]) { pq.push(i1); } if(i2[0]) { pq.push(i2); } } cout << ops.size() << endl; for(auto it: ops) { for(auto i: it) { cout << i << " "; } cout << endl; } }  E1Iterate the given list left to rightTake a deque.If it is empty push the current in the deque. If the current element in deque is less than the front push it in front of deque else simply push in back of the deque. Bonus :- how to solve a different problem if elements are not unique. Codevoid solve() { int n; cin >> n; deque dq; int j; for(int i = 0; i < n; i ++) { cin >> j; if(!dq.empty() && j < dq.front()) { dq.push_front(j); } else { dq.push_back(j); } } while(!dq.empty()) { cout << dq.front() << " "; dq.pop_front(); } cout << endl; }  E2Similarly iterate the given list left to right If deque is empty push the current element anywhere.Maintain a gnu pbds ordered set which gives us a number of elements less than a current element in a vector. so for each upcoming element find a number of elements that were less than and greater than the current element with the help of the ordered set now if the number of elements less than the current element is greater push the current element to the back of the deque and add greater as ans to the inversion count else do the opposite push the current element in front of the deque and add nuber of lesser elements in the answer to inversion count. Code#define ordered_set tree, null_type,less>, rb_tree_tag,tree_order_statistics_node_update> typedef long long int ll; ll P = 1e9 + 7; void solve() { ll n; cin >> n; deque dq; ll j; ordered_set X; map mp; ll ans = 0; for(int i = 0; i < n; i ++) { cin >> j; int less = X.order_of_key({j, -1}); int tot = i; int great = tot - less - mp[j]; // cout << great << " " << less << " " << j << endl; if(great < less) { dq.push_back(j); ans += great; } else { dq.push_front(j); ans += less; } X.insert({j, i}); mp[j] ++; } // while(!dq.empty()) { // cout << dq.front() << " "; // dq.pop_front(); // } // cout << endl; cout << ans << endl; }  FConnect nodes i to (i + d) % n in a graph. Find all the cycles in that graph. if the bitwise and of all elements of any cycle > 0 return -1;else put all those elements in the exact form of their appearance in the array to make it cyclic append the same elements array twice and let's say if there are n elements in the array.find the shortest path of each one to the nearest 0 in the cycle. take a maximum of all such shortest paths.with this method, we will really make all elements 0.Bonus, assume that elements are not necessarily binary then also the below code and algorithm can be modified easily. Codevoid solve() { ll n, d; cin >> n >> d; vector vis(n), v(n); for(ll i = 0; i < n; i ++) { cin >> v[i]; } ll ans = 0; for(ll i = 0; i < n; i ++) { ll curr = i; vector t; ll o = 1; while(!vis[curr]) { t.push_back(v[curr]); o &= v[curr]; vis[curr] = 1; curr += d; curr %= n; } ll k = t.size(); if(k == 0) continue; if(o) { cout << "-1\n"; return; } vector> bits(1, vector(2*k, INT_MAX)); for(ll i = 0; i < k; i ++) { ll val = t[i]; for(ll j = 0; j < 1; j ++) { if((1<< j) & t[i]) { if(i > 0) bits[j][i] = bits[j][i - 1]; } else { bits[j][i] = i; } } t.push_back(t[i]); } for(ll i = k; i < t.size(); i ++) { ll val = t[i]; for(ll j = 0; j < 1; j ++) { if(t[i] == 1) { bits[j][i] = bits[j][i - 1]; } else { bits[j][i] = i; } ans = max(ans, i - bits[j][i]); } } } cout << ans << endl; } 
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 @Fawkes For problem 2 (B) the problem statement mentions: Any sorting method where the number of shifts does not exceed n will be accepted.  So did this mean that when we take one interval i.e from I to n (like in your soln) we can only shift max n times or did it mean that the total number of shifts shouldn't exceed n?because if we take the example: 5 4 3 2 1 then for I = 0, we shift 4 times, and then I = 1 we shift 3 times so the total would exceed n, no?
•  » » » 4 weeks ago, # ^ |   0 You may shift by more than 1 in a single operation. In your example, you pick shift by 4 (as a single operation) and get 1 5 4 3 2, which fixes 1 in it's correct place in 1 shift operation.
•  » » » » 4 weeks ago, # ^ |   0 I see, so it mean that the sum of all the interval shifts i.e << x sum of all such x's can exceed n but the total number of times we perform this shift must not exceed n, correct?
•  » » » » » 4 weeks ago, # ^ |   0 Exactly. :D
•  » » » » » » 4 weeks ago, # ^ |   0 Got it, thanks!
•  » » 4 weeks ago, # ^ |   0 what is the reason to decrease two big values by only one can not it be decreamented by minimum of these .I mean to say min(i1[0],i2[0]). why does not this process give best answer while(pq.size()>=2) { pairpp1=pq.top(); pq.pop(); pairpp2=pq.top(); pq.pop(); v=min(pp1.ff,pp2.ff); c+=v; if(v>0) ans.pb(mpr(pp1.ss,mpr(pp2.ss,v))); pp1.ff-=v; pp2.ff-=v; if(pp1.ff>0) pq.push(pp1); if(pp2.ff>0) pq.push(pp2); }
•  » » » 4 weeks ago, # ^ |   0 Imagine three people with times: 6 6 2.You would answer 6, since you would pick both persons with a = 6. But the real answer is 7, those two people with a = 6 should talk with each other 5 times, and the last person should talk to both of them separatelly.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Ohh Nice explanation I was searching for that kind of test case . U have made it easy.I got it Thanks to u.
 » 4 weeks ago, # |   -11 Why am I not able to hack any solution or even been able to lock any problem during Codeforces Round #744 (Div. 3) ?
•  » » 4 weeks ago, # ^ |   0 Div 3 is different from Div2 and combined rounds. Here, you get a hacking phase of 12 hours after the contest ends.
•  » » » 4 weeks ago, # ^ |   0 Thanks, do you know why people downvote a comment like this?
 » 4 weeks ago, # |   +1 Nice round, with great problems.Although the order of problems could be better, the problems were great!Thanks :)
 » 4 weeks ago, # |   0 Most unbalanced div $3$ round ever :(The difficulty was like $A < E1 < B < D < C$ as I felt.
•  » » 4 weeks ago, # ^ |   0 What was the key idea for A?
•  » » » 4 weeks ago, # ^ |   +3 In problem $A$, you can either remove $(A, B)$ or $(B, C)$, that means you've to remove $B$ whenever you're removing $A$ or $C$, so the $\text{count}(B)$ should be equal to $\text{count}(A) + \text{count}(C)$ to make string empty at the end.You just have to check that.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 Thanks.Damn, I got it, but... I read a problem too quickly and inattentively, that's why I lost an important aspect. The morality for me (and other beginners) is that I shouldn't hurry at the contest, there is enough time to solve all problems.
 » 4 weeks ago, # |   +4 In problem F, I have used the fact that once some a[index] becomes 0, it will always remain 0 and will turn a[(index+d)%n] to 0 as well.. So, at each step if there's no new index where 0 is formed.. ans will be -1, else we can store these new indices to use them in the next step till all indices are converted 0.So, if at each step "X" new indices are formed.. the process will go on for N/X iterations .. making it X*(N/X)I am not pretty sure about this complexity and method.. Can someone provide a counter case/hack it, or affirm it ?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 Your approach is pretty much similar to my approach. I did multisource bfs. Time complexity of my solution is $O(n)$.Link to my submission
•  » » » 4 weeks ago, # ^ |   0 Yeah right!! mine is also in a way multisource BFS only.
 » 4 weeks ago, # |   +3 Who made these test cases? E1 hacks are going insane with very straightforward hack.
•  » » 4 weeks ago, # ^ |   0 Can you give an example? I don't know what makes so much solutions to fail :0
•  » » » 4 weeks ago, # ^ |   0 Look at the solutions that fail by TLE. It should be pretty easy to see why.
 » 4 weeks ago, # |   0 Can someone explain approach for C plase
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 this is my solution to it , you must try to find the root that genirat left and right diagonal and put them like visited or used, and if it must be big then k or equal the left and right *, the code, sorry for my bad English. void solve() { int t; cin >>t; while(t--) { int n, m, k; cin >>n >>m >>k; vector s(n); lp(i, n) cin >>s[i]; bool vis[n][m]; clr(vis, 0); for(int i = k; i= 0 && j-a>=0 && j+a= k ) { for(a=0; i-a>= 0 && j-a>=0 && j+a
•  » » 4 weeks ago, # ^ |   0 Try to find potentional center cells,say {x,y} and calculate the minimum of its left and right arms, say d. If d>=k, add a tick in another grid of size d at {x,y}. After you have done this for all potential center cells, check whether the original grid and the grid you made are same or not. My solution:130153692
 » 4 weeks ago, # |   0 B submission WA I was trying to solve be for more than 1 hour but it was still giving the wrong answer. The codeforces engine was giving a different answer and my machine was giving different. Mine was correct. I later submitted the problem with very minor change and it got accepted. It was some undefined behaviour I guess, if anybody could explain why that happened, I would be really grateful. Accepted Solution
 » 4 weeks ago, # |   +1 please take a look into hack #758216, the result is "unexpected verdict".(I mistakenly submit invalid input, then I got such result. Maybe the validator of G is wrong.)
 » 4 weeks ago, # |   +3 I have tried a video solution for the problem F: https://www.youtube.com/watch?v=8qC3qyQsE8s Hope it will help you if you need it.
 » 4 weeks ago, # |   0 Hi any one could help me to solve problem D, give me the idea or full code, this is my code i got WA, cause their is no tutorial, thanks in advance, and sorry for my English. void solve() { int t; cin >>t; while(t--) { int n; cin >>n; vii v(n); lp(i, n) { cin >>v[i].f; v[i].s = i+1; } sort(v.rbegin(), v.rend()); vii ans; int i=0, j=1; while(v[i].f&&v[j].f) { ans.pb({v[i].s, v[j].s}); v[i].f--; v[j].f--; for(int a=j;a+1
•  » » 4 weeks ago, # ^ |   0 When posting your code, try to include them in spoiler and block tags, so that they maintain their indentation. As for D, the basic idea is to use a max heap, (priority_queue in C++). The idea is to take two indices with the maximum sociability every time and have them meet each other. Their sociability decreases by one everytime, so, you decrease that and if their sociability is still greater than 0, push them back into the max-heap. My submission/*Author-Nilesh Chandra(isocyanide7)*/ #include using namespace std; #define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); #define ll long long #define dd double #define pb push_back #define ff first #define ss second #define Mp make_pair #define pll pair #define pii pair const ll Mod=1000000007; const ll INF=999999999999999999; const ll NN=(ll)(1e6+5); template T Min(T x,T y){if(x T Max(T x,T y){if(x>y) return x;return y;} ll power(ll x,unsigned ll y,ll mod=Mod) { ll res=1; x=x%mod; if(x==0) return 0; while(y>0) { if(y&1) res=(res*x)%mod; y=y>>1LL; x=(x*x)%mod; } return res%mod; } template T hcf(T a,T b) { if(b==0) return a; return hcf(b,a%b); } void solve() { ll n; cin>>n; priority_queue pq; for(ll i=1,x;i<=n;i++) { cin>>x; if(x>0) pq.push({x,i}); } vector ans; while(pq.size()>1) { pll p=pq.top(); pq.pop(); pll q=pq.top(); pq.pop(); ans.pb({p.ss,q.ss}); p.ff--; q.ff--; if(p.ff>0) pq.push(p); if(q.ff>0) pq.push(q); } cout<>TT; for(ll tt=1;tt<=TT;tt++) { //cout<<"Case #"<
•  » » » 4 weeks ago, # ^ |   0 thanks
•  » » » 4 weeks ago, # ^ |   0 can you please explain as to why letting two with the max sociability meet each other would result in maximum no. of meetings ?
•  » » » » 4 weeks ago, # ^ |   0 We would want to make sure that the number of meetings is the maximum. Taking the indices which currently have the maximum sociability does this, because everytime, we are decreasing the sociability, so the indices that have maximum sociability changes after a point of time, which means meetings are scheduled as long as they are possible. Let us take a counter-example: say, A={1, 2, 3}. Now, if we considered the indices with the minimum sociabilty, we will be able to schedule only two meetings-> (0-1) and (1-2). On the other hand, if we considered indices with the maximum sociability everytime, we will be able to schedule 3 meetings-> (2-1), (2- 1) and (2-0).
 » 4 weeks ago, # |   +19 I would like to report a system bug in problem G.When I submit my solution, it gets time limit exceeded at test set 22. But when I looked at test set 22, it have three test cases, and first one array length is 10000. But problems says the total number of G does not exceed 10000, so it is not a valid test set. I look at others solutions passed during contest, and the total number is 18. So test set 22 is not generated by authors, but by hackers after the contest. Then I tried to generate an invalid test set (3 test cases with total number of n 30000) and hacked others code (I only hacked people who are not officially participate the contest), they all succeed. Therefore, please remove these test sets that sum of the n > 10000, and rejudge these hacked solutions for problem G. It is unfair for participated who solved problem G but exe time is larger than 333ms.
 » 4 weeks ago, # | ← Rev. 2 →   0 It's rare to see something like this : same same same same same same same same same same same same same same same ....... code. Butdifferent people 🤯
•  » » 4 weeks ago, # ^ |   0 And they are almost submitted at same time. Someone mentioned that a youtuber released video editorial for problems when contest was running :(
•  » » 4 weeks ago, # ^ |   0 you are right lots of cheaters got high ranking but it is worthless if you dont know the logic and directly submit it.
 » 4 weeks ago, # | ← Rev. 4 →   0 Thnx for great round, even though I wasn't so luky. Anyway I may have misunderstood problem B, I used Bubble sort considering swaps as d = 1 circular shifts, on paper it all make sence but yet it get me wrong answer on test 2. this is my submission 130155379 , could any good one of you help me with it ?
•  » » 4 weeks ago, # ^ |   0 Swapping adjacent elements is not an efficient way of sorting the array.To go straight to the point, the maximum number of operations/shifts your program could need is $\frac{n(n-1)}{2}$ when the the array is in the form $a_1>a_2>\dots>a_n$. By the way the number of such swaps needed to sort the array is the same as the number of inversions in the array if you want to look into that.
•  » » » 4 weeks ago, # ^ |   0 Thnx bro, much appreaciated.
 » 4 weeks ago, # |   0 I'm new here, so the round should be rated for me but, the contest is showing itself in the unrated section in my profile contests, also I'm not in the standings. I did solve 4 questions during the contest. Can anyone tell me what's this issue?
•  » » 4 weeks ago, # ^ |   0 Did you register for the contest?
•  » » » 4 weeks ago, # ^ |   0 yes
•  » » » » 4 weeks ago, # ^ |   0 Then you will find yourself in : Contest > Standing > Friends standings with your all friends who attend this contest.
 » 4 weeks ago, # |   0 C was more difficult than D according to me. I ended up using most of the time to solve C. It just got stuck in my head. E1 was a joke. Lesson: READ. READ ALL PROBLEMS.
•  » » 4 weeks ago, # ^ |   +1 Better Lesson: See the submissions in dashboard to find next easiest problem.
 » 4 weeks ago, # | ← Rev. 2 →   0 What is invalid test in Hacking? I have also used endl but dtill getting this error? SpoilerValidator 'validate.exe' returns exit code 3 [FAIL Expected EOLN (test case 1, stdin, line 3)] close BtwIs it only for me or for everyone that codeforces is acting wierdly today ..It is tryng to covert to russian all the times.
•  » » 4 weeks ago, # ^ |   0 Send ur generator
•  » » 4 weeks ago, # ^ |   0 there's strict check for tests. I guess you added extra space in the end of line
 » 4 weeks ago, # | ← Rev. 2 →   0 problems were good
 » 4 weeks ago, # |   0 Could anyone please help me understand why I got TLE in E2? I used Fenwick tree + coordinate compression, so this should be O(nlogn) but somehow it fails in testcase #18.My attempt from the contest (or slightly modified version that's easier to read).
•  » » 4 weeks ago, # ^ |   +1 Same here but with seg tree, I really don't understand
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 Omg found it, man. It's because of the unordered_map. Here is the solution with unordered_map and Here is the solution with map. The first one fail with 2 seconds while the second passes with 343 ms. Like BROO. Why is this happening? I thought unordered_map is faster than map :(
•  » » » » 4 weeks ago, # ^ |   +1 Damn, you're right... Wow, this feels terrible.
•  » » » » 4 weeks ago, # ^ |   +1 It is always sensible to use map over unordered map. You may think that unordered map can give you O(1), but cases can be generated to exploit it's hashing method which will result in Collison everytime you want to use it which will be O(n). Long story short, use map which guarantees O(lgn).
•  » » » » » 4 weeks ago, # ^ |   +1 Of course I would do that but I didn't know about it. I just thought the unordered_map is just a map where the keys are not in order. :) Fml
•  » » » » » 4 weeks ago, # ^ |   +1 but if tests are not generated to kill hashing method, unordered_map runs faster than map.
•  » » » » » » 4 weeks ago, # ^ |   +3 Totally. I think the idea is that in most cases an additional log(n) doesn't matter enough (and doesn't give TLE) so using std::map over std::unordered_map would be strongly preferred for me in the future since it makes me not worried about anti-hashes.
•  » » » » » » » 4 weeks ago, # ^ |   +1 It is actually possible to use unordered_map without worrying about collisions, here : how to avoid getting hacked using unordered_set
 » 4 weeks ago, # |   0 I think E1 is more suitable for the difficulty of B than the actual B...
 » 4 weeks ago, # |   0 Will probably get downvoted to hell for saying this but this round had a bunch of issues....
 » 4 weeks ago, # | ← Rev. 3 →   0 Hi ! is there any one who can help me with this ? in problem B , the first test ,my output to testcase 3 is : 2 : 1 3 2 — 3 4 1 but is gives me a WA : wrong answer Element a[0] = 4 is greater than element a[1] = 1 (test case 3)but its not logical ! if you shift the elements in the way that I said , the array will be sorted ! can you find my mistake ? my submission : 130240370
•  » » 4 weeks ago, # ^ | ← Rev. 12 →   0 I guess what you are referring is the Jury's answer. for every [l,r] that you're considering you do cout<
•  » » » 4 weeks ago, # ^ |   0 THANKS !
 » 4 weeks ago, # | ← Rev. 2 →   -8 I have solved four questions in this contest and having rank between 2500-3000, but now they are saying that I have copied the solution of the problem, but I haven't. I am coding in ideone.com, is there any problem with it. I thought after this I will have a 1300+ rating. please help, how will I convince that I do not copy any solution...
•  » » 4 weeks ago, # ^ |   0 if u wrote the solution in secret mode, then no problem otherwise everyone could have seen your code and they may have used it. So in that case it is a problem. You have to ensure that your code doesn't gets public during the contests.
•  » » » 4 weeks ago, # ^ |   -8 I have not been aware of this fact, so in that case, I will be rated or not?
•  » » » » 4 weeks ago, # ^ |   -8 you are still rated
•  » » 4 weeks ago, # ^ |   0 There have been many cases similar like yours, because when you use ideone.com in public mode, everyone can see your code and copy it. There is no way for you to convince me that you did not copy the solution. The best way to solve this problem is in the next contest, you should use ideone.com in private mode.
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 -_-
•  » » » 4 weeks ago, # ^ |   0 nice meow ~
 » 4 weeks ago, # | ← Rev. 3 →   0 I am new to codeforce.I used two accounts one in which I try the codes and the other on which I submitted I realised it is showing me that the code coincides which is obvious because both are my accounts .I realised that this can't be done so I won't do it next time but what about this time will I lose out on the ratings?
 » 4 weeks ago, # |   0 Hi mike , I just got a message from codeforces that my code matches with atarax/13017197. But in that question, everyone's logic was expected to be the same and the implementation was also expected to be the same even though there are some differences in the implementation of both the solutions(my solution, atarax/13017197). I don't even know this guy he is from some different university that I don't even know about. And I do have a clean record I have just one such message in the past that's because i was new on codeforces at that time and I didn't know that I can't submit the same solution from 2 different id's (both were my id's); Please help me out if you can.
 » 4 weeks ago, # |   0 Why the cheaters are not rated ?? They should deserve negative delta!
•  » » 4 weeks ago, # ^ |   -13 For you with a light heart :)
 » 4 weeks ago, # |   0 When we will be getting the editorial?
 » 4 weeks ago, # | ← Rev. 5 →   +3 In D, the most common solution that I have come across involves heaps and priority queues. However, in my initial approach I used DP by modelling the problem as the 0-1 Knapsack Problem. I 1st calculated the sum of the sociability of all the people in a test case, and since each talk would require the sociability of both the participants to decrease by 1, the maximum possible talks in a meeting is (sum of sociability)/2 Therefore, the size of the knapsack can be set equal to (sum of sociability)/2 and the weights set and the values set will be the same, i.e., the input array of sociability of each person. Therefore, by finding the maximum weight that can fit inside the knapsack, we can maximise the number of talks in the meeting. However, my solution fails on the 69th test case of the 2nd test set. Here is my submission. I would appreciate any help in pointing out the flaws in my logic or implementation.
 » 4 weeks ago, # |   +1 Solutions to all problems in video format :)solutions
•  » » 4 weeks ago, # ^ |   +1 thanks, i subscribed too.. keep it up
 » 4 weeks ago, # |   0 Nice contest with interesting problems.
 » 4 weeks ago, # |   0 Hello, I solved 1 problem in Div 3's contest yesterday. But my rating went down. What is the reason?
•  » » 4 weeks ago, # ^ |   0 Your rating depends on your previous rating and your rank, not on how many problems you solved. Read this for further understanding.
 » 4 weeks ago, # |   0 Failed system testing for Problem E2, could someone tell me why this is TLE? The second last test case also had 200000 length but it passed well within the time limit. My code
•  » » 4 weeks ago, # ^ |   +1 It is the unordered_map in the worst case time it's time complexity for insertion can be O(n) and not O(1). https://codeforces.com/contest/1579/submission/130266275 just by using map your code gets AC
•  » » » 4 weeks ago, # ^ |   0 thanks, that's tragic. makes me wonder when the unordered_map shouldn't be used since i even passed the pretests so didn't give it a second thought
•  » » » » 4 weeks ago, # ^ |   0 Sometimes you might want to use pbds hash maps, like cc_hash_table and gp_hash_table. There are helpful tutorials on CF — the authors even mention how to prevent excessive hash collisions, which might be helpful for the casual unordered_map as well.
•  » » » » » 4 weeks ago, # ^ |   0 I followed this blog and was able to pass the test cases. should I just keep it in my template? haven't seen anyone using this though
•  » » » » » » 4 weeks ago, # ^ |   +1 I've seen ppl using this; personally I've used it a few times. But in this very case, it wasn't needed — note that ordered_set is very slow, but it is enough to complete this task. The operations we need to support are "add x to the set" and "count how many elements that are < / <= are on the set". If we somehow distinguish equal values appearing on distinct positions, we can complete this task simply with order_of_key queries. My suggestion is, instead of adding x to the ordered_set, add f(x) = (x * BASE) + pos, where BASE is some constant (sufficing BASE > n) and pos is the position of the added value. Now, for all values y < x, f(y) < x * BASE, and for all values w > x, f(w) > x * (BASE + 1) — 1. As you can see, the queries are pretty straightforward now, and we don't suffer from unordered_map etc. To conclude, sometimes changing the values might be easier and more efficient than the hash function.
 » 4 weeks ago, # |   0 In this round #744 Div.3 I was falsely accused of cheating/plagiarism even though I used a self written code except of this part while (pq.size() > 1) {while (pq.size() > 1) { int num = pq.top().first; int idx = pq.top().second + 1; pq.pop(); int num1 = pq.top().first; int idx1 = pq.top().second + 1; pq.pop(); num--; num1--; I copied it from this reference Thisbut I just changed a few things like instead of outputting the top I just signed it to an integer of num and index and did it twice because I needed the largest 2 numbers and made the while loop from 2 because I needed at least 2 numbers. as if the rest of the code I've always been writing my code the same way even if you try to look at my older submissions you will notice so. I hope this issue is resolved and Thanks.
 » 4 weeks ago, # |   0 Can someone please tell me the approach for F and G.
•  » » 4 weeks ago, # ^ |   0 F: If a position has a value of 0, it will never change. If a[i] = 1 and a[i + k] = 0 (where k is the length of rotation), then we can make a[i] = 0 in one turn. (maybe you need to switch a[i] and a[i + k], I don't remember if the rotations are left or right oriented)Let's build a circular graph of n vertices. If a[i] = 0, then dist[i] = 0, else set the initial distance of vertex i to inf. Then use a multisource BFS from all vertices with dist = 0 to compute the answer — the edges start at vertex i and go to vertex number i — k (mod n). Whenever a vertex labeled with 1 is accessible from a vertex 0, we add him to the queue, update the "distance" etc. The answer is the maximum distance over all vertices (or -1, if for any vertex v, dist[v] = inf holds after the computation finishes).
•  » » » 4 weeks ago, # ^ |   +8 Thank you it was helpful.
 » 4 weeks ago, # |   +16 when will the editorials be released? (sorry for being a little impatient)
 » 3 weeks ago, # |   0 Can someone help me understand the offset in problem B? From the problem description: [1,4,1,3] -> [3,1,4,1], offset 1 and [4,1,3,1] -> [3,1,4,1], offset 2. I understand this, l and r for these are 1 and 4.Then there's this example: [1,3,2,8,5], where choosing l=2, r=4 and d=2 yields [1,8,3,2,5] Shouldn't this be [1,2,8,3,5]? Am I missing something stupid? Any help would be appreciated.
•  » » 3 weeks ago, # ^ |   0 It was [3,1,4,1] then it became [1,4,1,3] after moving all the elements to the left by 1. Also they are in cycle so if it is in the first position and wants to move to the left by 1 then it will become the last. Same thing with this it was like this at first [3,1,4,1] and after offsetting it became like this [4,1,3,1].I hope I helped you.