### Supermagzzz's blog

By Supermagzzz, history, 5 months ago, translation,

All problems were developed by me Supermagzzz and Stepavly.

1367A - Short Substrings

Author: MikeMirzayanov

Editorial
Solution

1367B - Even Array

Авторы: Supermagzzz, Stepavly

Editorial
Solution

1367C - Social Distance

Авторы: Supermagzzz, Stepavly

Editorial
Solution
Editorial
Solution

1367E - Necklace Assembly

Автор: MikeMirzayanov

Editorial
Solution

1367F2 - Flying Sort (Hard Version)

Editorial
Solution
Tutorial of div3 E-onwards #1

• +92

 » 5 months ago, # |   -90 Thanks for fast Editorial!!
 » 5 months ago, # |   -106 Fastest editorial i have ever seen !!!
 » 5 months ago, # | ← Rev. 2 →   -130
 » 5 months ago, # | ← Rev. 2 →   -105
 » 5 months ago, # | ← Rev. 2 →   -153
 » 5 months ago, # |   +24 Practice really helps you... After continuous practice my first contest where I solved A,B,C(yaa I know Div 3) but still it's a big achievement for me... Looking Forward to Global RoundI'm new here can anyone tell about CF Global Round... I mean is that different from Div1+2 round??
•  » » 5 months ago, # ^ |   0 I think it's that both div.1 and div.2 will participate in the same contest with the same tasks.
•  » » 5 months ago, # ^ |   +40 Well you solved ABC in Codeforces Round #644 (Div. 3) tooYou sir just lied
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +9 That Day all the three problems had more than 11k submissions they were easy and that time I was not that serious about CP as I'm now...But still I don't know why the sense of relief and satisfaction I got today was the best... It really felt good...
•  » » » » 5 months ago, # ^ |   0 I felt like Lewis Hamilton in a Mercedes! Get in there Lewis!
•  » » » » » 5 months ago, # ^ |   +1 I felt like Maldonado, getting wrong submissions here and there.
•  » » 5 months ago, # ^ |   0
•  » » » 5 months ago, # ^ |   0 Thanks a lot! E was really confusing me
•  » » » 5 months ago, # ^ |   0 Thanx bro, nice explanations!
 » 5 months ago, # |   -80 Task D took soul out of me but never showed Accepted
•  » » 5 months ago, # ^ |   +61 You have 0 submissions in your profile right now. Probably you did not solve any question and still saying this (weird flex) or solved them from a second account. Either way, not healthy brother. Please refrain from doing this.
 » 5 months ago, # |   -28 Hello guys! I'm new to codeforces and I enjoyed this div 3 contest even tho i only solved first 3 problems. Div 1 and 2 contests demotivated me..can someone tell me is this contest was rated or unrated ?
•  » » 5 months ago, # ^ |   +2 It's rated.
•  » » 5 months ago, # ^ |   +2 Yes, it was rated for all the participants with a rating less than 1600 or are a new participant.
•  » » » 5 months ago, # ^ |   +1 Can you tell why my ratings didn't change even though i have a lower rating?? Is it the case for anyone else too?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 I had a look at your submissions for the contest. Apparently, you have been marked as "out of competition" (denoted by the asterisk above the username). I hope you followed the participation guidelines.
 » 5 months ago, # |   0 How to solve F2's last testcase for 16 operations?
•  » » 5 months ago, # ^ |   0 Keep 5 5 9 9 and move the rest accordingly
 » 5 months ago, # |   +76 C can be solved without handling cases separately. You can justappend $100\ldots0$ at the beginning and $00\ldots 01$ at the end of the string ($k$ zeros in each sequence)
•  » » 5 months ago, # ^ |   0 This is clever, very clever.
•  » » » 4 months ago, # ^ |   0 hi I am getting wrong answer can you tell me why? My code is :  int t = sc.iin(); while (t-- > 0) { int n = sc.iin(); int k = sc.iin(); String s = sc.sin(); int ans = 0; ArrayList a = new ArrayList<>(); for (int i = 0; i < n; i++) { if (str.idc(s, i) == '1') { a.add(i); } } if (a.isEmpty() == true) { ans += Math.floor(n/k+1); } else if (a.size() == 1) { int j = a.get(0); int ii = j-(k+1), jj = j+(k+1); while (ii >= 0) { if (str.idc(s, ii) == '0') ans++; ii = ii - (k + 1); } while (jj < n) { if (str.idc(s, jj) == '0') { ans++; } jj = jj + (k + 1); } } else { int j = 0; while (j < a.size() - 1) { int l = a.get(j); int r = a.get(j + 1); if (r - (l + k + 1) > k) { ans++; } j++; } } pp.println(ans); } 
•  » » 5 months ago, # ^ |   0 shit like this make me go *wtf is wrong with my brain. Anyway thanks mate.
•  » » 5 months ago, # ^ |   +7 Give me five I appended k zeros at the beginning and k zeros plus 1 at the end. 83967055
•  » » 5 months ago, # ^ |   0 I did the same
•  » » 5 months ago, # ^ | ← Rev. 3 →   -14 Can anyone say the approach?
•  » » » 5 months ago, # ^ |   0 Appending 100..0 at the front and 0..001 at the end ensures that the distancing conditions from the ends are already satisfied. Alternatively, say count is the number of zeros lying between two ones. In that case, subtract k from count to satisfy distancing condition from one end and then dividing the remaining count-k by k+1 i.e, (count-k)/(k+1) would give us the number of seats that can be filled. As for the leftmost case, initialise count=k as we don't have to worry about the distancing condition from the left. For the rightmost segment count/(k+1) would give the answer. Here's the code implementing it 84039536
•  » » » » 4 months ago, # ^ |   0 Can you give an example, I am not getting it.
•  » » 5 months ago, # ^ |   -10 I also did the same
•  » » 5 months ago, # ^ |   -10 Actually i did the same
•  » » 5 months ago, # ^ |   0 How about handling no cases and doing using segment tree? xD
•  » » » 5 months ago, # ^ |   0 how will you use segment tree here?
•  » » » » 5 months ago, # ^ |   0 83956065 here's how, though I've used BIT instead of segment tree.
•  » » » » » 5 weeks ago, # ^ |   0 I used prefix array lol. Idea is that I append 1 instead of 0 only when there is no 1 in the range -k to +k and I found that using prefix array in constant time. https://codeforces.com/contest/1367/submission/96411562
•  » » » 5 months ago, # ^ |   0
•  » » 5 months ago, # ^ |   0 That's smart, thanks.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +10 .u can try this https://codeforces.com/contest/1367/submission/83999647 .
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 Another approach: You can iterate through the string and keep a count of zeros from the last '1'. If count becomes greater than k, increment ans by one and assign count = 0. If present element is '1' and count < k, decrement ans by one and assign count = 0. 84095691
•  » » » 5 months ago, # ^ |   0 Thank you so much.
•  » » 5 months ago, # ^ |   0 I got TLE for that.
•  » » 5 months ago, # ^ |   0 I did C using prefix sums. here is the link, https://codeforces.com/contest/1367/submission/83981310
 » 5 months ago, # |   -30 You can actually solve problem c : social distancing in O(n) time complexity and O(1) space complexity like this : #include #include using namespace std; int main() { int t; scanf("%d", &t); while (t--) { int n, k; scanf("%d %d", &n, &k); char room[n]; scanf("%s", room); int max = -1, ans = 0; for (int i = 0; i < n; ++i) { if (room[i] == '1') { if (i-k > max) ans += ceil((i-k-max-1.0)/(k+1.0)); max = i+k; } } if (max+1 < n) ans += ceil((n-max-1.0)/(k+1.0)); printf("%d\n", ans); } return 0; } 
•  » » 5 months ago, # ^ |   -20 The space complexity if $\mathcal{O}(n)$ , and not $\mathcal{O}(1)$, because you create the vector room. Here is my in-place solution: int main() { int tests; scanf("%d", &tests); while (tests--) { int n, k; scanf("%d%d", &n, &k); int total = 0; int last = -1; for (int i = 0; i < n; ++i) { char c; scanf(" %c", &c); if (c == '1') { if (last == -1) total += i/(k + 1); else total += (int)((i - last - 1 - k)/(k + 1)); last = i; } } if (last != -1) total += (n - last - 1)/(k + 1); else total = ceil(((double)n)/(k + 1)); printf("%d\n", total); } } 
•  » » 5 months ago, # ^ |   0 can u explain the logic please?
 » 5 months ago, # |   -7 This contest was almost DIV 2 ..... PS — Good problems
•  » » 5 months ago, # ^ |   +4 yep div3 is getting more and more difficult.
 » 5 months ago, # |   +20 It felt like a Div 2 contest after C
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 You can do problem C using a simpler approach. Initialize ans = 1, count = 0. count stores the value of the present table with respect to the previous '1'. If count becomes greater than k then, place a person on the table, i.e. increment your ans by one and assign count = 0. If you come across a '1' and count <= k then that the previous person was wrongly placed on the table, so decrement ans by one and assign count = 0
•  » » » 4 months ago, # ^ |   0 thanks for this approach even better then editorial give, I was struggling with that problem from several hours.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Here is the code: 84095691
•  » » » 5 months ago, # ^ | ← Rev. 3 →   0 Bro Your code gives wrong output for test case:19 3100100000It gives 0 output whereas correct output is 1.
•  » » » » 5 months ago, # ^ | ← Rev. 4 →   0 For this test case k = 3, whereas number of empty seats between the first and fourth seats is 2. The problem statement says it is guaranteed that the rules of the restaurant are satisfied for string s. So this test case is wrong.
•  » » » » » 5 months ago, # ^ |   0 Oops,silly me Sorry Bro
 » 5 months ago, # |   +3 How to do D but while preserving the order of characters from s in t.
•  » » 5 months ago, # ^ |   +8 I misread the question in contest, and actually tried solving this. The only solution I could come up with, was to generate all possible subsequences of size m from s, and check if b is valid for that string.
•  » » » 5 months ago, # ^ |   0 It can be optimized a bit as different values in b will correspond to different characters and vice versa so we can choose p(no of different values in b) alphabets and construct a string t accordingly and check if it is a subsequence of s. I could not optimize it any further.
•  » » » » 5 months ago, # ^ | ← Rev. 6 →   +8 But, different values won't necessarily correspond to different characters, for example take the following string.t: aacb: [2, 1, 0]different values correspond to same characterIn fact same values may correspond to different characters. Take the following example.t: cabb: [0, 2, 2] Although, I think the following can be done. Try to solve this question too like the actual question, but instead of assigning the greatest character to indices containing zero, assign a number which will be used to store information whether characters t[i] < t[j] or t[j] < t[i]. Assign k = m; Assign k to all unvisited indices containing zeros, in a different array let's say ans. Now for each unvisited index containing zero, iterate over all non zero indices j and subtract abs(i - j) (where i is the current index containing unvisited zero) from them, and mark the current zero index as visited. Decrement k and go to step 2. The above algorithm is same as the solution to the original problem, but instead of assigning characters, we are assigning numbers.Dry run for "cab":1. b: [0 2 2], visited: [F, F, F], ans: [-1, -1, -1]2. b: [0 1 0], visited: [T, F, F], ans: [3, -1, -1]3. b: [0 0 0], visited: [T, F, T], ans: [3, -1, 2]3. b: [0 0 0], visited: [T, T, T], ans: [3, 1, 2] Now, in ans array if ans[i] < ans[j], then t[i] < t[j] must be true. Therefore, we can use ans array to generate a valid subsequence from s, using backtracking.Although, I am not sure what will be the time complexity of the same.
 » 5 months ago, # |   0 Can someone please tell me what's wrong with my submission to C? https://codeforces.com/contest/1367/submission/83970779
•  » » 5 months ago, # ^ |   0 The loop with the search with lower_bound is not ok. You check only the distance to the next 1, not to the previous one. And, you cannot only check every kth index, you would need to check each one.
•  » » » 5 months ago, # ^ |   0 Thanks I got it now.
•  » » 5 months ago, # ^ |   0 Try keeping upper bound for the rightmost and setting left as you traverse. check ithere
 » 5 months ago, # |   +64 For E, we may observe the following:Suppose the length of the necklace is l. Then the necklace can be decomposed into l/gcd(l,k) consecutive portions of length gcd(l,k). These l/gcd(l,k) portions must be identical by the k-beautiful property. Now we store the frequencies of every letter, and check if sum over all letters, frequency[letter]/(l / gcd(l,k)) exceeds k. If so we have a necklace of length l, else there is no necklace of length l.
•  » » 4 days ago, # ^ |   0 But why the gcd works here?
 » 5 months ago, # |   0 It felt more of a DIV 2.5 contest. btw good problems, enjoyed solving them.
 » 5 months ago, # |   +30
•  » » 5 months ago, # ^ |   0 please do make vedios of atleast e or f , this is div3 afterall.
•  » » » 5 months ago, # ^ |   0
•  » » 5 months ago, # ^ |   -40 Please don't upload the videos just after contest. Do this at least 12 hours after contest is over. Some people will tend to watch your video immediately afer contest instead of upsolving. Thanks.
•  » » » 5 months ago, # ^ |   +3 Why do you think you have to tell people what to do?
•  » » » » 5 months ago, # ^ |   -6 And why do you think i forced him to do anything? I just said my point in a manner of request. He is free to do anything what do he wants.And people downvoting my comment are same which regularly post shitty things like-- I have been practising for 3 years and i am not improving-- instead of upsolving.
•  » » » » » 5 months ago, # ^ |   +3 I think you also have an option of not watching the videos before 12 hours?
•  » » » » » » 5 months ago, # ^ |   0 He is worried about those who don't improve even after practicing for 3 years. Haha
•  » » » » » 5 months ago, # ^ |   0 ur profile shows registered 4 months ago
•  » » » » » » 5 months ago, # ^ |   0 No, you misread what i was saying.
 » 5 months ago, # | ← Rev. 2 →   0 I did the C in this way .. first marks all ones and make all invalid seats upto k as ones on the both sides. later simply occupy first seat which is zero and later occupy every zero which comes atleast after k seats from the previous zero. 84029131
 » 5 months ago, # | ← Rev. 2 →   +38 I had a different approach for both E and FI created a count, c, of occurrences each letter, and then I iterated over each factor, f of k. Then I checked for the highest multiple of f that was a valid length using patterns of length f. For each multiple m * f, I took the sum of floor( c / m) for each count, and if the sum was >= f, it was valid.The main idea I used was that we would minimize the number of operations by finding the longest subarray of the sorted array that was also a subsequence of a . I kept a sorted map of numbers to a sorted list of indices the number appears at. Then I iterated through the map and kept track of the longest subarray found.
•  » » 5 months ago, # ^ |   0 E -> how about taking top f elements in count, c, array and then take the least element l among them. then, ans=max(ans, f*l)
•  » » » 5 months ago, # ^ |   0 Your approach doesn't allow the same letter to be used more than once in the repeating patternsay you had this test case: 1 13 3 aaaaaaaabbbbc Your counts would be 8, 4, and 1. The factors of 3 are just 1 and 3. For 1, applying your approach would give us 8For 3, applying your approach, the minimum is 1, giving us 3The correct answer, however, would be pattern of aab repeated 4 times, which is a length of 12.
•  » » 5 months ago, # ^ |   +5 Check this solution. You could use gcd
•  » » 5 months ago, # ^ |   0 Any proof why it is true " the longest subarray of the sorted array that was also a subsequence of a" ?
•  » » » 5 months ago, # ^ |   +9 The elements that are not moved have to form a sorted subsequence. So if we can maximize the length the sorted subsequence, the number of operation is minimized.
•  » » » » 5 months ago, # ^ |   0 Thanks.
•  » » 5 months ago, # ^ |   0 Thanks for helping me find my mistake in E.Was doing everything correctly except for adding the floor of C/2 instead of the floor of C/M. It just slipped my mind and I was rotating all necklaces by half of their length and hence trying to find a palindrome, I needed to find if there can be M similar blocks instead of 2 similar blocks. Thanks once again.
•  » » 5 months ago, # ^ |   0 can you please elaborate on keeping the track of the longest subarray . I don't think we can do that just iterating linearly .
•  » » » 5 months ago, # ^ |   +1 That's true, I did gloss over that a bit. When I iterate from one unique number to the next largest, there are 2 possible casescase 1: The last index in the previous number is less than the first index of the current number. Then we can just extend the subsequence and continue to the next numbercase 2: case 1 is not true. In this case, we need to start a new sequence, but there's 3 things we need to look at. a. We take the earliest index of the current number that is greater than the last index of the current number and add those number to the end of the current sequence. b. We then also look for the longest sequence of just the previous and current numbers. For each index of the previous number, we find the earliest index of the current number that is after it, and we have a subsequence with just those indices. c. We find the latest index of the previous number that is smaller than the first index of the current number and start our new subsequence with them.submission link: 84023424
•  » » » » 5 months ago, # ^ |   0 Thank you so much! Even though I didn't fully understand your explanation, it gives me some hints. Here's my c++ implementation 84279237 for those who are not familiar with kotlin (like me). The implementation is different but I believe the idea is the same.
 » 5 months ago, # |   0 Why greedy approach for distributing letters to cycles works in problem E? Because I think that in general it shouldn't work. Let's say we have buckets of size 6 and 10 and want to fill them with values 5, 5, 6. Then the best choice is to put two 5s in bucket of size 10 and 6 in bucket of size 6. Greedy approach doesn't work in this case. Does problem E satisfy some constrains that allow for greedy approach to work?
•  » » 5 months ago, # ^ |   +9 Because of the way to form the graph, all the cycles will have the same size, a graph of size n with edges between i and (i+m)%n, will have gcd(n,m) cycles of size n/gcd(n,m).
•  » » » 5 months ago, # ^ |   0 Thanks! I get it now
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Thanks
•  » » » 5 months ago, # ^ |   0 How cycle size is exactly gcd(n,m)? Is there any proof of it?
•  » » » » 5 months ago, # ^ |   0 Someone explain this. Same doubt.
•  » » » » 5 months ago, # ^ |   +14 Imagine that you have a number i, and you replace it with (i+m)%n in one operation, now, we will calculate the first time that this number will be equal to i again, we can show that we want to find the smallest k such that ( i + k * m ) = i ( mod n ), we can substract the i's and left k * m = 0 ( mod n ), so k = n / gcd( n , m ). and, if we start with each number after n / gcd( n , m ) we will find a cycle, that's why all cycles will be equal, and if each one has size n / gcd( n , m ), there will be gcd( n , m ) cycles.
•  » » » » » 4 days ago, # ^ |   0 Thanks a lot
•  » » » » 5 months ago, # ^ |   +3 In a necklace of length m, if you rotate by k, you notice that you require each subcycle (starting with any bead, and jumping k hops at a time) in the necklace to have same beads. Now each sub-cycle will be produced by starting at i, and then after jumping k steps for x no. of times we will reach back at i. This completes our sub-cycle i.e. ($i + kx \equiv i mod m$) where x as you can see is the no. of jumps taken to reach back at i, also is the length of this sub-cycle.Or, ($i + kx - my = i \implies kx = my$) for some integer y.Now to find the min. x such that above equation holds, you see k and m are fixed, so kx = my = lcm(k, m). And as we know lcm(k, m) = km/gcd(k, m) = km/g.Therefore, ($x = lcm(k, m)/k \implies x = km/kg \implies x = m/g$). Hence proved length, x of sub-cycle produced is size/gcd(size, k). Now to prove that no. of subcycle will be gcd(k, m):you can see that each sub-cycle will of equal size, starting with some i, j, ... , also each element has to be a part of exactly 1 such subcycle, thus product of no. of subcycles and size of each such subcycle must be 'm', hence the proof follows.
•  » » » 4 days ago, # ^ |   0 But what's it's proof?
 » 5 months ago, # |   0 Can someone help me with my code for Prob.C: Submission
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 see this test case : 7 11000001Your solution gives the output as 1, but it should be 2 because we can place '1' at 3rd and 5th position.
 » 5 months ago, # |   0 https://codeforces.com/contest/1367/submission/84030518 pls can anyone tell y it is giving error in test case 54 of pretest 2 thnks in advance
 » 5 months ago, # |   0 In problem C for block that is neither first nor last,why cant we do (number of zeros in block)/ (2*k+1)
•  » » 5 months ago, # ^ |   0
•  » » » 5 months ago, # ^ |   0 can u tell error in mine? https://codeforces.com/contest/1367/submission/84030518
•  » » 5 months ago, # ^ |   0 i was doing the same ... got WA!
•  » » » 5 months ago, # ^ |   0 me too
 » 5 months ago, # |   +37 I also explain solutions to these problems at the end of my screencast of the round if you would like a more visual explanation that what the excellent editorial here provides.
•  » » 5 months ago, # ^ |   0 thank you
•  » » 5 months ago, # ^ |   -11 Can you give an elaborate explanation for the solution of question D? I did not understand it!:/
•  » » » 5 months ago, # ^ |   +6 What part was confusing?The idea is as follows: All of the zeros in the initial array correspond to the largest letter that is in the answer string. Therefore, we can insert that largest letter into all spots that contain a zero. Once we have inserted these largest letters, we can subtract out their contribution from all other spaces. This will allow us to easily locate all instances of the second largest letter, because those positions will be zeros.
•  » » » » 5 months ago, # ^ |   -13 oh i am so sorry! i meant question E! The one with the necklace beads! Can you please explain that in a elaborate manner?
•  » » » » 5 months ago, # ^ |   0 thanks...great explanation...
•  » » » » 5 months ago, # ^ |   -10 Great Explanation ... please explain F1 too ---In the below code what we wanna do or what is the easiest idea to solve  lli n; cin>>n; paira[n]; loop(i,n){ lli x; cin>>x; a[i] = make_pair(x,i); } sort(a,a+n); lli ans = 0; lli cnt = 0; FOR(i,0,n) { if(i==0 or a[i].S>a[i-1].S) cnt++; else cnt=1; ans = max(ans,cnt); } print(n-ans); 
 » 5 months ago, # |   0 Hello All, I have a question related to Social Distancing. Input: 6 2 000000 This input comes under the separate case mentioned in the editorial which is "a string consisting only of zeros". So we don't need to remove any zeros from the beginning or end. So answer should be floor(6/2) which is 3. But the correct answer as per the sample test case is 2. Can someone explain where I understood incorrectly? Thanks
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 It is not floor(n/k), but floor((n-1)/(k+1))+1
•  » » 5 months ago, # ^ |   +1 It's ceil(n/(k+1))
•  » » 5 months ago, # ^ |   0
•  » » 5 months ago, # ^ |   0 Lets say n=6 and k=2. The given string is "000000" You fill 1s greedily. First, we fill position 0 with 1. The new string is 100000 Notice that the remaining empty slots are n-1. Now you need a gap of k elements, and after that you can have another '1'. So, basically you need to look for intervals of length (k+1) in this space. Thus, (n-1)/(k+1)
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 It's not related to the question you asked.pk1993 , Why did your rating start from 0? My rating started from 1500. I started participating around 2 years ago. Is there any change in the codeforces initial rating system?
•  » » 5 months ago, # ^ |   0 Arithmetic solution for C: https://codeforces.com/contest/1367/submission/84060536
 » 5 months ago, # |   +4 I believe I have a really nice solution (as well as clean) for the problem E -> 84022899
•  » » 5 months ago, # ^ |   0 Looks like 84012097
•  » » » 5 months ago, # ^ |   0 lol i was looking for ways to solve E and found my own code
•  » » 5 months ago, # ^ |   +1 I don't understand the concept of GCD here...Please explain :)I did this - while(t--) { lli n,k; cin>>n>>k; string s; cin>>s; int a[26]={0}; lli ans = -1; loop(i,sz(s)) { a[s[i]-'a']++; } for(lli j=n;j>=1;j--){ lli val = j; lli cnt=0; loop(i,26){ cnt+=(a[i]/val); } while(cnt>0 and k%cnt!=0) cnt--; ans = max(ans, cnt*val); } cout<
•  » » » 5 months ago, # ^ |   +6 If you observe carefully, you will see there will be some cycles forming of same size. So we will check each size possible of the necklace. let's say we want to check if necklace size of x is possible or not. Let's say g = gcd(x, k). After g beards in the necklace, the letter has to be the same. So there will be g cycles. x sized necklace will consist g cycles of (x/g) size. Now we need to check if we can get g cycles of (x/g) size. This gcd idea can be a bit hazy, if you are finding it hard to understand, I will highly recommend you to draw some pictures and the thing... It really helps get a concept clearly :D And then let me know if you have further doubts. Happy Coding :D
 » 5 months ago, # |   +20 I could not understand the tutorial of Problem F. Can somebody please elaborate a little more. Thanks in advance. I just want to understand the logic here. The implementation part is clear to me.
•  » » 5 months ago, # ^ |   +6 Let's say we have an array [3,10,10,1,3,7,7,0] . We can map it to [3,5,5,2,3,4,4,1] so the coding part become easier. Now let's sort it [1,2,3,3,4,4,5,5]. Now we need to find the longest sub-sequence in the original array, which is also a sub-array for the the sorted array (If you subtract it's length from n, you will get the answer) . You can see here a interesting fact that [3,5] or [2,3,4,4] can't be a answer because it is a sub-sequence for the original array but not a sub array for the original one. So it's clear that there there has to be body , prefix, suffix . Body has to contain all the all element fully (It means if there are 5 4's , it has to contain all the 5 4's.) and prefix would be the maximum you can take legally before body's first element (simply the amount of (body's first element)-1 equals element before the body starts) and suffix would be the maximum you can take after body's last element(simply the amount of (body's last element)+1 equals element after the body ends). This is the basic idea. But there is a case, you also need to focus on. You need to check all the possible sub-sequences containing only two different elements. I got AC doing this 84144777. Please let me know, if you have any further doubts. Happy Coding :D
•  » » » 5 months ago, # ^ | ← Rev. 3 →   0 nice problems
•  » » » » 5 months ago, # ^ |   0 I never said we need to take the LIS. We need to take fulled connected increasing sub-sequence! In your case we if we sort the array, it would be [ 0 1 2 3 ] and the original array is [ 0 2 1 3 ]. We have take a the maximum sized subarray from the sorted array which also have to be a sub-sequence of the main array. We can't take [0 2 3] as it isn't a sub-array of the sorted array. We can take [0 1] or [2,3] ! Hope this helps you to clear the fact!
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   +3 yup bro I got it just few seconds ago... Thanks Bro :P Farhan132
•  » » » » » » 5 months ago, # ^ |   0 Anytime Bro!
•  » » » 5 months ago, # ^ |   0 Saw your code. Feels like you used priority_queue to store the no. of a[i]s present in the array by storing 1+p[a[i]].top() into p[a[i]]. Isn't it?But, still didn't get how are we finding the length of the increasing subsequence in the original array(after coordinate-comp.) which is also the subarray in the sorted array? How are we doing this using priority_queues? I noticed you are taking the maximum of the b[i]s which is, of course, the size of each priority_queue. So ain't we only considering all the elements of the same type(all elements being equal to "x") as the only candidate for increasing subsequence(which is subarray when array gets sorted). Please help !!
•  » » » » 5 months ago, # ^ |   0 If you look carefully in my code. I have not used priority queue! I just declared it as I was trying different methods. I tried 2-3 times with priority_queue before this and seems like implementing with it kinda impossible for me! To find the right sub-sequence, I am taking a number fully, (like if there is 3 1's, I will take all the three), then let's say before the first 1, there was 2 zeroes. So I will take them too. Now If all the 2's exists after the last 1, I will continue to the two and will take a prefix = ( 3 (one) + 2 (zero's before one) ). If not then I will take the number of 2 after the last 1 as suffix! And will move to two as 0 prefix. If get clear on this part, it would become really easy for you to do the rest!
 » 5 months ago, # | ← Rev. 2 →   +4 I did F2 without dynamic programming.Basic idea: The subsequence which should not be touched while making operations would have the set of numbers as $b_1, b_2 \ldots b_k$, where $b_1 < b_2 \ldots b_{k-1} < b_k$. And it must have complete segments for every number $b_2, b_3 \ldots b_{k-1}$, whereas it could have incomplete intervals for $b_1$ and $b_k$.84032732
•  » » 5 months ago, # ^ |   0 The part of idea is clear for me. Can you please explain a bit about the implementation? I am finding it hard to understand.
•  » » » 5 months ago, # ^ |   +3 First case where I used deque(just for simple understanding, it's not even necessary) is the case when $k$ in the above sequence is greater than $2$. We can use sliding window for calculating it.Next case, where I used a queue is when $k=2$, so both $b_1$ and $b_2$ are incomplete intervals.
•  » » » » 5 months ago, # ^ |   0 I actually got a idea by myself and it took 5 WA to get the AC. Thanks a lot for the help and sorry I thought first to try my idea then yours.As It took me 28 hours to get AC, so I was late in reply.
•  » » 5 months ago, # ^ |   0 could you please elaborate more ?...thanks
 » 5 months ago, # | ← Rev. 2 →   0 What is the time complexity for this code ? (Question E ) , if |S| = 10 6 while(t--) { lli n,k; cin>>n>>k; string s; cin>>s; int a[26]={0}; lli ans = -1; loop(i,sz(s)) { a[s[i]-'a']++; } for(lli j=n;j>=1;j--){ lli val = j; lli cnt=0; loop(i,26){ cnt+=(a[i]/val); } while(cnt>0 and k%cnt!=0) cnt--; ans = max(ans, cnt*val); } cout<
•  » » 5 months ago, # ^ |   0 $O(n\log n)$, because $cnt_j$ is bounded by $n/j$, so the whole thing grows at a rate of $H_n = O(n\log n)$. The added condition k%cnt!=0 will speed it up in some cases, but in the situation $k=1$ for example, it won't make a difference. It's hard to quantify how much it will affect the runtime in other cases, since it basically depends on the number of divisors of $k$ which are in the range $[1, n]$, as well as how "spread out" they are in that interval.
 » 5 months ago, # | ← Rev. 2 →   -10 I guess C can be solved in an easier approach and straight forward way. #include using namespace std; #define ll long long #define ull unsigned long long void run(void) { int n, k; cin >> n >> k; string x; cin >> x ; int c = k, i = 0, ans = 0; while(ik){ c = 0; ans++; } i++; } if(ans < 0) cout << 0 << endl; else cout << ans << endl; } int main(void) { int t; cin >> t; while(t--) run(); return 0; } Time complexity: O(N) Space complexity : O(1)
•  » » 5 months ago, # ^ |   +1 What's with this new trend of $\textbf{O(1)}$ space complexity ? And in your code you have read the whole string using, string x; cin >> x ; That is clearly $\textbf{O(n)}$ space.
•  » » » 5 months ago, # ^ |   0 I think they may be referring to auxiliary space usage
•  » » » 5 months ago, # ^ |   0 He probably meant to say O(1) extra space.
•  » » » 5 months ago, # ^ |   0 The space needed for storing the string is same for all the solutions. But my code doesn't need space which grows at the time to execution. Hope you understand brother.
 » 5 months ago, # |   0 Supermagzzz In Question C instead of floor((number of zeros)/k) it should be ceil((number of zeros)/(k+1))
 » 5 months ago, # |   +44 For those scratching their heads about F2 test case 3 #4999, try the following input (the correct answer is 2): 1 6 1 0 0 1 1 0 
 » 5 months ago, # |   +20 Checker for problem D was wrong during the contest. My submission was hacked and it now fails on test 1 (it didn't during the contest)
 » 5 months ago, # |   +2 I think the testing was not appropriate for the 4th ques during the round ,during the round it showed to pass on first test case but after the round it was hacked on same test case (I did not pay attention to change the code as it was shown accepted and lost the score after the hack)
 » 5 months ago, # |   0 PROBLEM C without formulas and handling cases seperately---->Simply use greedy approach and put one's from left to right if it satisfies the condition (i.e currentindex-previousindexhavingone > K)and increase the answer by 1 whenever in future your condition gets violated (might be due to subsequent one) you decrease the answer by 1.Here is the code --------> #include using namespace std; int main() { int t; cin >> t; while(t--) { int n,k; cin >> n >> k; string s; cin >> s; int curr = 0, ans = 0; if(s[0] == '0') ans++; curr = 0; //curr means current index for(int j=curr+1; j k) { s[j]=1; ans++; curr=j; } } cout << ans << endl; } return 0; } 
 » 5 months ago, # |   0 There also exists an O(n) solution for C: 83977850
 » 5 months ago, # |   0 My noob solution for C. Iterated the array thrice.  int n,k; cin >> n >> k; string s; cin >> s; int count=0; int free=0; for(int i=0;i=0;i--){ if(s[i]=='1'){ count=k; } if(s[i]=='0' && count){ s[i]='1'; count--; } } for(int i=0;i
 » 5 months ago, # |   0 solved E without graphs.. just gcd and some basic operations: solution
 » 5 months ago, # |   0
 » 5 months ago, # |   0 In Editorial of Problem "1367C — Social Distance", it is mentioned that,"all the tables in each block are free, then in each block we can put (number of zeros)/k. Sum these values over all blocks."I find this as wrong. ( Referred some of the comments below, and collated this )It is actually, for each block,answer = answer + ((number of zeros) / (k+1)).Also, if the remainder is greater than 0, then, add +1 to the answer. i.e., if(((number of zeros) % (k+1)) > 0)
•  » » 5 months ago, # ^ |   0 Can u pls tell what is wrong in my code- its giving WA on 201 test case https://codeforces.com/contest/1367/submission/84069351
 » 5 months ago, # |   0 My approach for problem — CWe need to find number of unoccupied table which can be occupied so lets marks those table, or change s[i] = 0 to s[i] = x. Than count number of x in our final string x. Working iterate from 0 to strings length (n).1)if s[i] is 0 than check the index of prev 1 or prev x in the string 2)if i — prev1 is > k marks this 0 as x and store this position (prev x).3) if s[i] is 1 check for prev x.(which is already stored)4) if i — prevx <= k change s[prevx] to 0 5) marks prev1 = i.Submission Link — https://codeforces.com/contest/1367/submission/83973628
 » 5 months ago, # |   0 in the editorial of social distance i cannot understand the statement res += (len + k) / (k + 1); what this statement doing?
•  » » 5 months ago, # ^ |   +10 It is basically $\textrm{ceil}$$(\frac{len}{k+1}), \textrm{ceil}$$()$ being the ceiling function. As C++ $\textrm{ceil}()$ function can be inaccurate, an alternative to avoid that is $\textrm{ceil}(\frac{a}{b}) = \frac{a+b-1}{b}$.
•  » » » 5 months ago, # ^ |   0 Can u pls tell what is wrong in my code- its giving WA on 201 test case https://codeforces.com/contest/1367/submission/84069351
•  » » » » 5 months ago, # ^ |   0 I couldn't understand the logic, but here's a test case where your code fails: 1 7 2 1000001 Expected answer: 1, Your output: 0.
•  » » » » » 5 months ago, # ^ |   0 yeah i got where i was wrong thanks anyways:)
•  » » » 5 months ago, # ^ |   0 thank you your reply but can you tell me what is the role of this statement in this program.
•  » » » 5 months ago, # ^ |   0 moreover how your coming up with this formula ceil(len/k+1)?
•  » » » » 5 months ago, # ^ |   0 After you obtain a block containing purely zeroes, and there is no restriction on the first table's selection, how do you fill tables optimally? Definitely you can start from the leftmost table, and fill subsequent tables accordingly. For a block of length $len$ $[0,len-1]$, you can fill tables $0, k+1, 2*(k+1),...$ until $s*(k+1) < len$. In short, we have to find number of multiples of $(k+1)$ present in $[0, len-1]$ (including 0), which is $\lceil\frac{len}{k+1}\rceil$.
 » 5 months ago, # |   +10 this time editorials solutions are very bad there are other very elegant solutions with less time complexity
•  » » 5 months ago, # ^ |   0 yeah I am still not able to understand the approach of problem C and at same time finding my approach slighly easy to understand.
 » 5 months ago, # |   +6 Here’s another solution for E. Upper bound on complexity is $O(\sigma(k) \log n),$ where $\sigma(k)$ is the number of divisors of $k,$ and $\sigma(k) = O(\sqrt{k}).$A string $v$ is $k$-beautiful $\iff$ there exists a string $\pi$ such that $v = \pi^m$ and $|\pi|$ divides $k$.Imagine we had a magic function, $F(p),$ that told us the maximum $m$ such that we can afford $v = \pi^m,$ for some $\pi$ with fixed $|\pi| = p$.Then we could just iterate over the divisors of $k$ in order to find divisor $p$ such that the product $p \cdot F(p)$ is maximal; that product would be our answer.Now let’s implement $F(p).$We have an upper bound on the number of repetitions of $\pi$, it is $\lfloor n / p \rfloor$.Also, if we can afford some string $v,$ then we can afford any prefix of $v$.So we can do binary search on $m$ from $0$ to $\lfloor n / p \rfloor$ inclusively.Given $p$ and $m,$ how do we check that we can afford $v = \pi^m,$ for some $\pi$ with fixed $|\pi| = p$?Turns out this is pretty easy: the answer is $p \le \sum_{i=1}^{26} \lfloor t_i / m \rfloor,$ where $t_i$ is the number of letters with code $i$ in the original string $s$ (e.g., $t_1$ is the number of letters ‘a’).It is assumed that $\lfloor t_i / 0 \rfloor = \infty, \, \infty + \infty = \infty,$ and $p \le \infty.$ In practice, you should treat $m=0$ as a special case. Here’s another explanation for it: we can always afford an empty string, even though the final answer (but not $F(p)$) is always $\ge 1.$
 » 5 months ago, # |   +7 what happened to problem D?
 » 5 months ago, # |   +3 is problem D gone?
 » 5 months ago, # |   +2 Why was problem D removed?
 » 5 months ago, # |   0 Is problem f actually the famous LIS problem?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +27 Not exactly. It is not just increasing. Ths subsequence should be a continuous subarray of the sorted array.
•  » » » 5 months ago, # ^ |   0 i am unable to do implementation if F2 can you help me ...
•  » » » 5 months ago, # ^ |   0 Then it can be done with a simple two pointer I guess(or am I wrong?) Then why is dp used?
•  » » » » 5 months ago, # ^ |   +19 Can you elaborate more on how you use two pointers?
•  » » » » » 5 months ago, # ^ |   0 first we iterate over the hole array. let R be 0 at first.(the array is 0_indexed) then let us be on step L of iteration. now as long as you can increase R such that sub array [L, R] is increasing. modify ans by size R — L + 1. (ans = max(ans, R — L + 1)) then at last ans is the answer. tell me if I'm wrong.
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +16 Sorry for being unclear. Let the original array be $a_1, ...,. a_n$ Let $b_1, ..., b_n$ be the sorted array of $a$. What I mean is that you should find the longest subsequence(not continuous) of $a$ such that it is a continuous subarray of $b$.I am talking about F1 for simplicity . the case for F2 is little more complicated.
 » 5 months ago, # |   -21 Why the F is problem D removed. It is so unfair. Finally after so long I had a good contest and now I'm so annoyed. The problem didn't seem wrong and if it was there should be some points given to the persons who attempted D first and wasted their time.
 » 5 months ago, # | ← Rev. 2 →   0 @MikeMirzayanov Why is the 4th problem removed? We didn't waste time on it for anything. You should get it back. It didn't seem wrong either
•  » » 5 months ago, # ^ |   0 Same bro, wasted so much time on D, would've surely cracked F1 if D wasn't there in the first place.
•  » » 5 months ago, # ^ |   0 https://codeforces.com/blog/entry/78866?#comment-643650 please bother to read this and then say anything
•  » » 5 months ago, # ^ |   0 MikeMirzayanov You know there was a problem with D. I wasted a lot of time in D. I would call it cheating with users if the contest will be still rated though i can getting a raise of 120+. Many people felt that problem and got affected.
 » 5 months ago, # | ← Rev. 2 →   -9 i dont think they remove the problem D deliberately, it's just somethings wrong with the testing system, right?pls dont remove D, i spent an hour just to solve it
•  » » 5 months ago, # ^ |   0 I also spent hours to solve d pls don't remove it
 » 5 months ago, # |   +24 Here is an intuitive and easily implementable solution for E : Consider a nested loop, the inner loop ('j') representing the length of the smallest segment which is repeated over the cycle and outer loop ('i') represents the number of times this segment will occur in the cycle. Both the loops will run from 1 to n. Now we just have to check which pair (i,j) is valid. This can be done easily using an array storing the frequency of each letter in the string and calculating the maximum length of the segment that can be achieved for given 'i'. Refer to the code snippet given below : for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i*j>n) break; int shift=k%(i*j); if(shift%j!=0) continue; int sum=0; for(int c=0;c<26;c++) sum+=(cnt[c]/i); if(sum>=j) ans=max(ans,i*j); } } 
•  » » 5 months ago, # ^ |   +3 please explain line int shift=k%(i*j); if(shift%j!=0) continue in more detail. Thanks in advance
•  » » » 5 months ago, # ^ |   +24 i*j is the total number of beads in the necklace. So shift represents the number of times I need to rotate before achieving the same configuration. I need to ensure that shift is divisible by j because j is the period after which same segment repeat. sum represents the length mentioned in the last line of my previous comment. I hope it's clear now. Ask again if it's still not clear, I will try to elaborate more. Do leave an upvote
 » 5 months ago, # |   +7 Wouldnt it be easier to do F with 2d dp? then its actually pretty simple once you notice the trick to rewrite the array.
 » 5 months ago, # |   0 People like me who spent a lot of time to solve D are affected. So I think contest should be unrated.
•  » » 5 months ago, # ^ |   0 there is an issue in problem D checker and they are fixing it, hopefully it will return soon Your text to link here...
•  » » 5 months ago, # ^ |   0 Think of those who spend more than 1 hour and finally solved it , wouldn't be unfair for them if it becomes unrated .P.S.:- I couldn't solve D.Happy Coding!!!
 » 5 months ago, # | ← Rev. 4 →   +1 There is a solution for C which is pretty easy. Let's compute prefix sum array for our string. Now let's iterate over string with a window from i-k to i+k and check if there is any '1' already sitting there or not (prefix[min(n,i+k)]-prefix[max(1,i-k-1)]. If it does not then place '1' over there ( increase answer by 1) and go i+k+1 else just do i++.
•  » » 5 months ago, # ^ |   0 yaa same i have also done
 » 5 months ago, # |   +3 can somebody help me in implementation of F2
 » 5 months ago, # |   0 Can someone please help me spot the bug in the code as my code is failing on test case 2? I'm a beginner. Thanks in advancehttps://codeforces.com/contest/1367/submission/84063733
 » 5 months ago, # | ← Rev. 2 →   0 Can anyone help me out...I am getting WA on 175th no. of 2nd test case of Social Distance(1367C) problem of this contest. #include using namespace std; #define ll long long int #define tc ll t;cin>>t;while(t--) #define lp(i,j,k) for(ll i=j;i=k;i--) #define pb(x) push_back(x) #define F first #define S second #define mod 1000000007 #define fast ios_base::sync_with_stdio(false);cin.tie(NULL); #define vec(pk,pk1) vector pk(pk1,0) #define vect vector v int main() { fast tc { ll n,k;cin>>n>>k; string s;cin>>s; ll prev=-1;ll c=0; if(s.length()==1&&s[0]=='1'){ cout<<"0"<-1){ ll x=(i-prev-1); if(x>=(2*k+1))c+=1; prev=i; } else if(s[i]=='1'){ c+=(i/(k+1)); prev=i; } } //cout<
 » 5 months ago, # |   +1
 » 5 months ago, # |   +3 can someone help with a bit more clear explaination of probelm F2?? I'm not happy with the above explaination
 » 5 months ago, # |   0 Can anyone please check my solution? https://ide.codingblocks.com/s/259679
 » 5 months ago, # |   0 What is upsolve?
•  » » 5 months ago, # ^ |   0 Upsolve means solving problems after the contest.
•  » » » 5 months ago, # ^ |   0 Thanks man.
 » 5 months ago, # |   0 Why not for F1 editorial? Anyone please explain the logic of problem F1?
•  » » 5 months ago, # ^ |   0 F1 is only an easy version of F2. In F1 the constrain are small and some additional conditions are given.
 » 5 months ago, # | ← Rev. 3 →   0 debug my code please for problem c #include using namespace std; int main() { int t; cin>>t; while(t--){ int n,k; cin>>n>>k; string str; cin>>str; if(k>=str.length()){ bool r=false; for(int i=0;i=str.length() && j=str.length()){ break; } } if(br){ break; }else{ res++; str[i+k]='1'; i=i+k; } } } //cout<
 » 5 months ago, # |   0 Can someone tell me why did my rating not increase after giving the contest??
 » 5 months ago, # |   0 is there anyone explain me problem E editorials briefly? i can't understand the the given editorial.. thanks a lot
•  » » 5 months ago, # ^ |   +6 check my method in a previous comment https://codeforces.com/blog/entry/78864?#comment-643686
 » 5 months ago, # | ← Rev. 2 →   +3 For $E$, one could also do the following . Notice that, we must construct strings which are cyclic and repeat after "$k$ $rotations$" . Let's think that we need to construct some $x >= 1$ number of blocks of the form {$a_1 , a_2, .. , a_t$} , {$a_1 , a_2, .. , a_t$} , {$a_1 , a_2, .. , a_t$}, .... $x$ $times$. The length of the answer in this case is $t * x$. We immediately observe that $t$ must be a factor of $k$. So, let's loop over all factors of $k$. For each factor ($t$) we need to determine the maximum $x$ that works. Notice, that if $x$ works, then $x - 1$ also works. So, we can binary search here . The complexity is $O(\sqrt{n} * 26 * log(n))$ . Implementation of the above approach : https://pastebin.com/pjajDF0a
•  » » 5 months ago, # ^ |   0 i followed yr approach but i keep getting WA on test 2.
 » 5 months ago, # |   0 Please help! In C, why does (#of0 — k) / (k + 1) work?
 » 5 months ago, # |   0 I saw someone solved F2 using std::set, here's the link 84018692. Can someone help explain it? Or can anyone tell how to solve F2 with shorter length of code?
•  » » 5 months ago, # ^ | ← Rev. 4 →   +13 Wow, this solution is very clean, no DP needed at all. The basic idea is as follows: we can pre-sort all of our values and use two pointers to find the largest segment that appears as a subsequence in the original array. Now, say your sorted elements are [0, 0, 1, 1, 2, 2]. If we wanted to find out whether, say, [0, 1, 1, 2] appears as a subsequence in our original array, we need the following observation: we need all of the middle elements (i.e. 1's) and only some 0's and some 2's. Which 0's and 2's should we take? Well, it would make sense that we should take the earliest 0's that appear and the latest 2's that appear. This is the core idea behind that solution.Now, to explain the actual code: v stores {element, -index} pairs and sorts it so that when we start iterating over a new element, we will be looking at the latest occurrence. The set s1 stores the indices of all of the elements of the current value, and the set s stores the indices of all the other elements that are currently in our subsequence (note that the segment from [i, f] is the current subsegment). To decide whether we can add a new element, we essentially need to make sure that the only elements in s are the ones that appear after our current one, so we increment our back pointer and delete from the set until this is the case.At the end of each iteration, s and s1 contain the indices of the longest subsegment of the sorted array ending at index f that can be found as a subsequence in the original array, so we update our answer with the current subsegment size.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   0 It's a really strange idea. With the help of your extremely clear explanation, I now understand how it works. Atfer sorting, the author's aim is to find a longest subsegment which satisfies some kind of restriction as the following picture shows. Then when adding a new element, we need to delete those elements illegal in s as the following picture shows. And actually, s1 is not needed. It can be replaced just by a stack.Thx a lot for your clear explanation!
•  » » » 5 months ago, # ^ |   0 Thank you so much iamhpp and Kognition for this solution! This is a very elegant and concise way to solve such a difficult problem.
»
5 months ago, # |
-19

what's wrong with this code? it's not working for 4th test case. can anyone help me please? the 4th question.

# include <bits/stdc++.h>

using namespace std; void fastio(){
ios_base::sync_with_stdio(false); cin.tie(NULL); }

# define ll long long

int main(){ #ifndef ONLINE_JUDGE

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

#endif
int t; cin>>t;
while(t--){
string s; cin>>s;
sort(s.begin(),s.end());
string d=s;
auto n=unique(s.begin(),s.end());
s.resize(distance(s.begin() ,n));
//cout<<s;
map<char,int> mpp;
mpp.clear();
for(int i=0;i<d.size();i++){
mpp[d[i]]++;
}
int m; cin>>m;
vector<char> ans(m,'0');
vector<int> v(m,0);
for(int i=0;i<m;i++){ cin>>v[i];}
int b=s.size()-1;
int i=m;
while(i>0){
int c=0;
for(int j=0;j<m;j++){
if(v[j]==0){
c++;
}
}
//cout<<c;
while(mpp[s[b]]<c){
b--;
}
//cout<<s[b];
int x=0;
for(int j=0;j<m;j++){
if(v[j]==0){
ans[j]=s[b];
x+=j;
v[j]=-1;
}
}
b--;
for(int j=0;j<m;j++){
v[j]-=abs(j-x);
}
// for(int j=0;j<m;j++ ) cout<<v[j]<<" ";
i-=c;
}

for(int i=0;i<m;i++){ cout<<ans[i]; } cout<<endl;

}

return 0; }

 » 5 months ago, # |   0 if anyone can please point out error in this code 84093874 thanks
 » 5 months ago, # |   +1 Here's a similar question to Problem F (Flying Sort): Click.
•  » » 5 months ago, # ^ |   0 I remembered I did this before and I was looking for this problem during the contest but couldn't find it. Thanks for bring this out!
 » 5 months ago, # |   +3 I'm not understand dynamic programming approach in F2. Can someone give me example and simulate step by step ? What's dp[1], dp[2] , .....so on in this example ? What's the relation between dp[i] and dp[i-1] ? Thanks.
 » 5 months ago, # |   +1 I am not able to understand the following lines that were written in the editorial of the f2 question ( refer last line of the editorial contest 650 of problem f2). can anyone explain me? It is necessary to separately consider the first numbers in the subsequence and the last, since the first should include their suffix, and the last should have their prefix.
 » 5 months ago, # |   0 In the last sample problem, of F2 After modifying the array,2016 15 1 10 0 14 0 10 3 9 2 5 4 5 17 9 10 20 0 9It becomes,2010 9 1 7 0 8 0 7 3 6 2 5 4 5 11 6 7 12 0 6and the highlighted ones are sorted largest sorted subsequence in length 5 so the answer should be 15, or am i missing something.
•  » » 5 months ago, # ^ |   0 In this subsequence how will you enter the no 5, which is not highlighted, into the subsequence you have formed by following the algo mentioned in the question??? I think that's what you missing (I too had the same problem)
 » 5 months ago, # |   0 Can anyone point out to why this code is not working https://codeforces.com/contest/1367/submission/84133718 problem C: Social Distance
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 .
 » 5 months ago, # | ← Rev. 3 →   0 You can also use suffix and prefix strategy to solve problem C. https://codeforces.com/contest/1367/submission/84069306
 » 5 months ago, # |   0 why am i not rated for this contest ?
 » 5 months ago, # |   0 Can anyone please explain how the answer is 10 in the fifth sample case of E20 5 ecbedececacbcbccbdecanswer->10
•  » » 5 months ago, # ^ |   0 Have this combination of beads.. this satisfy the condition mentioned ccbccccbcc
 » 5 months ago, # |   0 For D in the editorial code, how are we ensuring that we aren't picking a letter which appears lesser times in S than needed?
•  » » 5 months ago, # ^ |   0 while (j->second < g.size()) j++; 
 » 5 months ago, # | ← Rev. 4 →   0 Can Someone Explain this following line in the editorial of Problem C."then in each block we can put [number of zeros/k]".Suppose Example is n=6 k=1 So maximum tables will be 3 but according to this formula answer will be 6 i.e (6/1)Any Catch which i am missing?
•  » » 5 months ago, # ^ |   0 No, the editorial is wrong.
•  » » » 5 months ago, # ^ |   0 Thanks spookywooky for replying,I checked the solution there it's written (len+k)/(k+1). Can you explain me how our we getting this formula?
•  » » » » 5 months ago, # ^ |   0 The blocks (ie. len) is of calculated length, see the three points above in the editorial. Then, the meaning of len is as if the whole string would be of len zeros. No 1 left, no 1 right.In such a string we can put a 1 at first position, then for every block of k+1 positions one more. This is exaktly (len+k)/(k+1)I would have preferred to write (len-1)/(k+1) + 1, which is the same.
•  » » » » » 5 months ago, # ^ |   0 why (len+k)/(k+1) ? and not (len)/(k+1)? Not able to get it.Can you explain?
•  » » » » » » 5 months ago, # ^ |   0 You can put a 1 at position zero. Then you are left with len-1 items, and can place (len-1)/(k+1) items. So answer is (len-1)/(k+1)+1Since $(a+b-1)/b = (a-1/b)+1$ it is that $(len-1+k+1)/(k-1)=(len+k)/(k-1)$
•  » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 I am very much near to it brother Just one thing i wanna ask,Why it is (len+k)/(k+1) and not (len+k)/(k)?
•  » » » » » » » » 5 months ago, # ^ |   0 If the string is like 1000000... and has n zeros, then you can place n/(k+1) ones in it.Because you need to let k zeros as is, then change one to '1', and so on.
•  » » » » » » » » » 5 months ago, # ^ |   0 Thank You So Much for the explaination Brother.
 » 5 months ago, # |   0 Can anyone help me understand these last lines of F2 editorial — It is necessary to separately consider the first numbers in the subsequence and the last, since the first should include their suffix, and the last should have their prefix.
 » 5 months ago, # |   0 I can't understand the editorial for problem F2. Can anyone explain me what's wrong?That is, the task came down to finding the maximum sorted subsequence in the array. So if we have testcase: 5 0 1 2 4 3 The max sorted subsequence in the array will be 0 1 2 and the answer will be (n = 5) — 3(length of the max sorted sequence)? But if we move 4 to the right we can get sorted sequence only in one move?
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 In the original array, you just need a non-decreasing subsequence(not necessarily contiguous), but those values must be contiguous in the sorted array (otherwise you would have to insert something in between them without moving the elements themselves, which is impossible with given operations). So the max sorted subsequence is 0 1 2 3 because it is contiguous in the sorted array but is a non-decreasing subsequence in the original. Therefore the answer is 5 — 4 = 1 as expected.
•  » » » 5 months ago, # ^ |   0 Thanks! Got it.
 » 5 months ago, # |   0 In F , for the case: n=4 , a=[0,2,1,3] longest sorted subsequence is 3 , then as per editorial answer is 1 (4-3=1) right ? But expected answer is 2 ? Can someone explain what i am understanding Wrong ?
•  » » 5 months ago, # ^ |   0 It is supposed to be the longest non-decreasing subsequence that is contiguous in the sorted array. In this case, the sorted array is [0, 1, 2, 3]. The only longest subsequences that satisfy this are [0,1] and [2,3]. There is no contiguous set of 3 elements in the sorted array that are non-decreasing in the original. So as per the editorial, 4 — 2 = 2.
•  » » » 5 months ago, # ^ |   0 Missed the point that elements have to be continuous .got it now . Thanks
 » 5 months ago, # | ← Rev. 2 →   0 Can someone provide strong test case for E? I got this: wrong answer 65th numbers differ — expected: '15', found: '12' from test #3This is my code. void solve(int n, int k){ vector v(26,0); char ch; for(int i = 1 ; i<=n; i++){ cin >> ch; v[ch-'a']++; } for(int i = n; i>=1; i--){ //i is length int repeat = (k%i==0)? i:min(k%i,i-k%i); if(i%repeat!=0){ repeat = 1; } int b = i/repeat; bool ok = false; for(int j = 0; j<=25; j++){ repeat-=(v[j]/b); if(repeat<=0){ ok = true; break; } } if(ok){ cout<
 » 5 months ago, # |   0 Can someone explain the implementation of F2. When doing the dp for the longest non-decreasing subsequence, how is the 'contiguous in the sorted array' requirement checked? Also isn't LIS an O(n^2) dp, so how does it fit in time constraints?
•  » » 5 months ago, # ^ |   0 LIS wont work hereand LIS can be done in O(nlogn) using binary search.
 » 5 months ago, # |   0 why (len + k)/(k + 1) in problem c. why not (Len)/(k) ??
•  » » 5 months ago, # ^ |   0 Check the comments before
•  » » » 5 months ago, # ^ |   0 ok
 » 5 months ago, # |   0 If anyone is stuck in C here is some example with case discussed in the tutorial Here
 » 5 months ago, # |   0 In editorial it's said that in F2 the answer is always n — length of the longest sorted subsequence. But there is no proof for that. Tell me if I'm right or wrong. Having found the longest sorted subsequence, I can in one step make it one element longer. So it's gonna take (n — length) steps to sort the whole array. Suppose there's a way to sort the array in even less number of steps. Then on some step I'll make current subsequence at least 2 elements longer which is impossible because I only move one element per step.
 » 5 months ago, # |   0 In anyone of you is wondering why your code for F2 failed for test case : 3(4999th), well it's because you didn't consider that case when your subsequence will contain two different elements.For the sake of reference here is the test case:t = 1  n = 20  array = 3 2 7 9 14 8 6 11 10 7 5 7 2 8 8 4 7 1 13 12 16 answer : 15,if yours is 16 this might be the reasonMy submission AC: i too ignored that case :)
 » 5 months ago, # |   0 Can someone please explain me how did this code snippet help in finding the maximum sorted subsequence? for(int i=0;i
 » 5 months ago, # | ← Rev. 2 →   0 Can anyone please explain what is dp2 and dp3 for in problem F?
 » 5 months ago, # |   +5 I'll try to explain my solution of 1367F2 - Flying Sort (Hard Version) in details.Disclaimer: it's hard way to solve it. Horrible wall of textI'll describe things in order how I was solving it.First, I checked: is any element moved only once? The answer is yes. Proof is following.Suppose that there is some element you had to move multiple times. Throw off all moves of this element except last move. Sequence in the end is same, so we got better answer. Proved.Second, I checked: how to sort array using only moves to the left? Well, main observation: all moved elements form a prefix of array. This means, if any element should be moved, then its final position should be within the prefix. But we know the prefix should be also sorted, so all elements less than the value of moved element should be also moved. We need to minimize number of actions. It's same as minimize length of prefix. Assume that there is no elements with same value. Then, by definition of "highest" moved element we know that all other elements won't move, so finding highest moved element is equivalent to find first stationary element, and equivalent to maximizing length of suffix with elements not moved. Then algorithm is: find minimum element that should not be moved, then move all elements with value less than it in decreasing order. How to find lowest element that should not be moved? Well, iterate array values in decreasing order while their positions are decreasing. All those elements don't need to be moved. So last elements in this list is highest stationary element, and first element with position higher than previous should be moved. Algorithm to sort using only moves to the right is similar.Regarding to assumption about no similar elements: I was solving simple case first, so I'll mention it later.Third. Is there always stationary element? Yes! Proof: assume for some input optimal answer is to move all elements. Pick any element as stationary. Move all elements with value less than stationary to the right in increasing order. Move all elements less than stationary element to the left in decreasing order. We got sorted sequence. So, this answer is better. Contradiction.Fourth. We know that elements split into three parts: stationary, moved to the left, moved to the right. Also, there is always at least one stationary element. From nature of operations follows, that moved to the left elements form a prefix, and moved to the right elements form a suffix, and stationary elements all in between.Summary: elements split into three parts: stationary, moved to the left, moved to the right. there is always at least one stationary element. elements moved to the left form a prefix, elements moved to the right form a suffix, stationary elements all in between. My idea is following. We don't know which element is stationary. Try each element as if it is stationary. But there is two issues to deal with: we don't know how many other stationary elements, and elements that should be moved to right is interleaved with elements that should be moved to the left.Let's deal with "interleaving" first. (Still taking assumption that there is no similar elements) From fact that element is stationary, means that all elements with higher value, should be in front of it. Similarly, all elements with less value should be after it. This means, that if any element with value higher than stationary element and in front of stationary element, it will be moved to the right. So, we only need to consider elements with value below stationary element for using "move to the left", and sort only them with it. All other values will be moved to the right and don't interfere. Similar thing holds for "move to the right".Now, let's deal with number of stationary. My solution to this issue is: there is always rightmost stationary element. Thus, try each element as if it is rightmost stationary element.So, for tests without duplicates of numbers, my solution is following: try each number x as rightmost stationary. build list of numbers less than x and greater than x, use algorithm above to sort both sequences, and take minimum of steps among all options among x. You can find all.To solve general case, we need to revisit algorithm to sort sequence using "move to the left" action, and "interleaving". In algorithm we use difinition of "highest" not moved. Now, last moved element can have same value as first stationary element. Moved with the same value as stationary can be only after value next in sorted list.To make clear, I'll state task for sorting using move to the left only. We consider only those numbers with values not exceeding picked as stationary. Also we have position of picked number. And we wan't to not move it, and sort every value below it into increasing subsequence. I'll use brackets for picked number. Examples:  [0] 1 0 1 // initial 0 [0] 1 1 // after sort 0 1 [0] 1 // initial 0 1 [0] 1 // after sort 2 10 5 8 4 5 6 1 [7] 4 9 // initial 1 2 4 4 10 5 8 5 6 [7] 9 // after sort 1 0 1 0 2 2 1 1 2 [2] // initial 0 0 1 1 1 1 2 2 2 [2] // after sort 1 0 1 0 2 2 1 1 2 [2] 2 // initial 0 0 1 1 1 1 2 2 2 2 [2] // after sort Third example is to show how values above stationary are ignored. Last two cases are general cases. Crucial undestanding is in them. So there are two cases: (last example) when there is at least one element from the right with same value as picked one, it should be moved, so number of steps is just number of same values at right plus number of all elements with less value. when it is rightmost element within group of same value, then we need to greedy pick previous group (look for stationary ones in fourth example!) Second case case is most tricky. If rightmost position of previous group by value doesnt exceed, then we need to recursively solve for rightmost of previous group. Otherwise, we have to move rightmost of previous group, thus we can calculate how many elements we need to move.Alright. This was coded by me in few hours, with some mistakes though, but nevermind. Most complicated thing is ahead. Now we need to consider both directions. Now we can move in both directions. And here is the most trickiest case, and it's luckly straight in the samples: // part of last sample 9 2 5 4 5 17 9 10 20 0 9 // initial 2 5 4 5 17 9 10 20 0 9 9 // you can do this! Looks like trivial. But! Where is here rightmost stationary? It's last element! But it shows general idea. You can partialy shift group to the right. Probably you can handle that using two dp in both directions, but I didn't want to do that, so I just tried to move each prefix of group to the right. As long as I know that picked element is rightmost stationary, I don't need to sort anything to the right, I only sort to the left, and every other element which is greater value considered as moved. And some prefix of current group is considered to moved to the right. It took a day to debug all stuff.Summary: implement dp that tells for each element how many moves you need to sort all values not greater than it and making it rightmost stationary. using this dp, check each element as rightmost stationary, and also try move to the right within each group of same value each prefix. Here is version of code with debug. 84434347 It has reconstruction of sequence of actions, and checker. And here is cleaned code. 84513543
 » 5 months ago, # |   0 For problem E why can't we just iterate and the find the number of repeating modk directly. For example if we have length 6 = 0 0 0 0 0 0 and k = 3. Then by going over once, we know the array is = x 0 0 x 0 0. So our array is now [2,2,2] which we need to fit with our beads. Similarly for k = 4. And a necklace of length 6 = 0 0 0 0 0 0 We get this array after traversing through mod = x 0 x 0 x 0 So now our array is [3,3] which we need to fit with our beads.
•  » » 5 months ago, # ^ |   0 In other words, the array would consist of (length/HFC(length,k)) elements with each having a value of HFC(length,k). We can solve the rest using Greedy.
•  » » » 5 months ago, # ^ |   0 Here is the solution https://codeforces.com/contest/1367/submission/84585024
 » 5 months ago, # | ← Rev. 2 →   0 a
 » 5 months ago, # |   0 Codeforces round#650 Div 3 Problem: 1367C Social Distance https://codeforces.com/contest/1367/problem/C my code is not working . Please help me. My code: https://ideone.com/Dt76cw
 » 4 months ago, # |   0 How to solve D?I am unable to understand editorial ............pls Help!
 » 3 months ago, # |   0 Hey. guys! About problem C: we DO NOT NEED to write s[j]=='1' in line int right = j2*k)res+=(len-k)/(k+1); } } cout << res << "\n";  My sol: 91778273
 » 5 weeks ago, # |   0 Can someone help me with F1?
 » 13 days ago, # |   0 Hello!! I don't undertand why in problem 1367E Necklace Assembly, If I take the position way i+k÷ m I have a cycle Sorry for my english. I need your help.