Теперь раздел EDU доступен и на английском языке ×

### Блог пользователя vovuh

Автор vovuh, история, 10 дней назад, перевод, ,

1374A - Необходимый остаток

Идея: vovuh

Разбор
Решение

1374B - Умножай на 2, дели на 6

Идея: vovuh

Разбор
Решение

1374C - Перемещай скобки

Идея: MikeMirzayanov

Разбор
Решение

1374D - Массив с нулевым остатком

Идея: vovuh

Разбор
Решение

1374E1 - Чтение книг (простая версия)

Идея: MikeMirzayanov

Разбор
Решение

1374E2 - Чтение книг (сложная версия)

Идея: MikeMirzayanov

Разбор
Решение

1374F - Сортировка циклическими сдвигами

Идея: MikeMirzayanov

Разбор
Решение
Разбор задач Codeforces Round #653 (Div. 3)

• +89

 » 10 дней назад, # | ← Rev. 2 →   0 Please Someone Explain Why i am Getting TLE in Test case#5 of Question DMy Submission is : 85376735
•  » » 10 дней назад, # ^ | ← Rev. 2 →   +7 You didn't take into account the case when till the end a[i]==a[j] then first condition is overlooked and cnt is increased and i is incremented and this keeps going on. Then it becomes O(n^2). Also you have to use long long to prevent overflow. I made minor changes to your code, and it got accepted. Link
•  » » » 10 дней назад, # ^ |   0 Thanks...
•  » » 9 дней назад, # ^ |   0 when you find a collection of identical numbers in the sorted array -> instead of (iterating over the remaining numbers in the collection for each of those Identical numbers in the collection) i.e time complexity of O(n^2) . you can do smart work and do int a single iteration for example see my submission : 85471233 and try to understand though its not the best , as i am also not much experienced
•  » » 5 дней назад, # ^ |   0 Use map stl instead of an array...I was also having the same problem...array index out of bound is the error..
 » 10 дней назад, # |   0 For problem D-Zero Remainder Array, why does my code get a TLE on test 8 despite using a similar approach? My code: https://codeforces.com/contest/1374/submission/85382181
•  » » 10 дней назад, # ^ |   +1 Use map instead of unordered map. Unordered map worst time complexity is O(N).Even I got penalty :(
•  » » » 10 дней назад, # ^ |   0 Please tell me how you come up with an approach to solve the first question.
•  » » » » 10 дней назад, # ^ |   0 I just found the nearest factor of x which is less than or equal to n. I'll add y to it and see if it's greater than n. If it's greater than n then I'll subtract x from it
•  » » » 10 дней назад, # ^ |   +1 Even my first submission was with an unordered_map :(. Got penalty.
•  » » 10 дней назад, # ^ |   +9 Or, you can use a custom hash function.This is a really good blog post on the topic.
 » 10 дней назад, # | ← Rev. 4 →   0 Finally Editorial Published. Thanks vovuh and team.
 » 10 дней назад, # |   +7 After Long Time
 » 10 дней назад, # |   +3 Please organize another div3 round. This was a div3 round after a long time. Newbies like me need div3 rounds continuously.
•  » » 10 дней назад, # ^ |   +1 Agreed. This one was great round! We need more!
•  » » » 10 дней назад, # ^ |   0 I also enjoyed this round. Please more div3 rounds on weekends!
•  » » 10 дней назад, # ^ | ← Rev. 2 →   0 I don't know why, But I get better results in Div2 rounds. The reason could be that I'm to slow when I'm coding
•  » » » 10 дней назад, # ^ |   0 If you think you need speed then you should do atcoder beginner. By doing that you will gain speed and even fast debugging.
•  » » » » 10 дней назад, # ^ |   0 Thanks
 » 10 дней назад, # |   -75 The comment is hidden because of too negative feedback, click here to view it (hahahhaah gottt you)
 » 10 дней назад, # |   -53 D question was really a cancer. vovuh thanks a lot for amazing contest E hard is interesing
 » 10 дней назад, # |   -32 Am I the only one who think that this was the best round ever ?!
•  » » 10 дней назад, # ^ |   0 you reached specialist that's why :)) well done
•  » » » 10 дней назад, # ^ |   -6 Yeah!I want more contests made by vovuh <3
 » 10 дней назад, # | ← Rev. 3 →   -17 Can E1 be done using DP?
•  » » 10 дней назад, # ^ |   -76 wow newbies know dp greatttt
•  » » » 10 дней назад, # ^ |   -6 Bad idea..
•  » » » » 10 дней назад, # ^ |   -27 i am just happy
•  » » » 10 дней назад, # ^ |   +3 what do you mean?I knew it when I was unrated.
•  » » » » 10 дней назад, # ^ |   -25 ohhhhhh that is eeven great broooo
•  » » 9 дней назад, # ^ |   0 i don't think so. i don't have any idea about dp. this type of problems always solving with greedy approach
 » 10 дней назад, # |   -39 https://codeforces.com/contest/1374/submission/85385019 Solution for B
•  » » 9 дней назад, # ^ |   0 WHY ARE YOU PEOPLE DOWNVOTING ??????
•  » » » 9 дней назад, # ^ |   0 TELL ME IS THERE ANY PROBLEM WITH THIS CODE how can you simply downvote an AC CODE****????
•  » » » » 9 дней назад, # ^ |   0 After solved a easy problem no need to comment here that's hide the important comment.
•  » » » » 8 дней назад, # ^ | ← Rev. 3 →   0 PThakur_16 The thing that one's code is accepted does not matters . One Uploads some code which has new idea or any new approach and has great time complexity. But your code has neither unique concept nor is efficient . Yours code time complexity is very poor . So don't post your code just to recieve UPVOTE . If you have some new concepts or some new idea then only post.
 » 10 дней назад, # | ← Rev. 2 →   +14 Ahsant. problem E2 is really nice (and hard). But the proof is not clear to me. I mean the analysis of number of times the operation is done.Upd: Yeah got it now. The editorial was also clean. Well that's why I always take part in Div3s.
 » 10 дней назад, # | ← Rev. 2 →   0 I solved E2 by applying ternary search on number of common books, but i don't have any proof that it is unimodal. Can someone explain me how it is unimodal or my solution is hackable?
 » 10 дней назад, # |   +1 Can anyone explain other solutions of E2, as I saw many solution using bit tree ,treaps, ternary search.
 » 10 дней назад, # |   +11 Gr8 set of questions.....All of them seem doable.... although problem E(s) was a bit heavy on maintenance side....
 » 10 дней назад, # |   0 Could someone please help me with the problem E1 easy version. I implemented the idea which is iterating over the books of the three vectors and finding the cheapest price, but it always gives a wrong answer on test case 13.My answer is cheaper than the actual answer given by the system. Thanks in advanceThis is my submission to the problem
•  » » 10 дней назад, # ^ |   +8 your problem is in line 258, you should make ctr1 = i + 1 not ctr1 = i because you want to test the next two books you can get not books you've already took fix it and you will get AC
•  » » » 10 дней назад, # ^ |   0 @ETheHedgehog Thanks a lot and sorry for the late reply.
 » 10 дней назад, # | ← Rev. 3 →   0 For Problem D: Find the ai % k for each element in a. Then find the one with the highest frequency (mode). Let x be the number with highest frequency and f be the number of times it occurred .If the new formed array (with ai % k) is empty or full of zeros the answer will be 0. Else the answer will be x + (k * (f — 1)) + 1.Solution Python3 -- > 85419324
•  » » 9 дней назад, # ^ |   0 I did not get the + 1 part as to why the ans = ( ) + 1. Once you reach k times some number, you need key number of steps to reach key. why k *() + key + 1?
•  » » » 9 дней назад, # ^ |   0 The +1 is because the first number used is 0, not 1. So we need one step more than the highest number we need to use.
 » 10 дней назад, # | ← Rev. 3 →   -10 In problem B, I have another simple solution Spoiler Alertwhile ($n$ % 6 == 0), we (divide $n$ by 6) and increase the counter oncewhile ($n$ % 3 == 0), we (divide $n$ by 3) = (multiple $n$ by 2 then divide $n$ by 6) and increase the counter twiceif after removing (6-divisors) and (3-divisors) from $n$ and (Unable to parse markup [type=CF_MATHJAX] have another divisors and we cant remove it with those buttons we have (*3, /6). So the answer is nootherwise the answer is the counter Solutionint query(ll n) { int cnt = 0; while (n % 6 == 0) n /= 6, res += 1; while (n % 3 == 0) n /= 3, res += 2; cout << (n == 1 ? res : -1) << '\n'; return 0; } 
•  » » 10 дней назад, # ^ |   +3 It is the same thing, you have counted the no. of 2's and 3's in the factorisation of the number in the first loop. Then the remaining 3's in the second loop and no. should be reduced to 1 for answer to exist.
 » 10 дней назад, # |   -12 E1 to E2 so big gap.E2 tooo hard for div3..... E1-1600 dificulty & E2-2500 dificulty :( 
 » 10 дней назад, # |   0 In E1 we can sort all books and pick books greedily. We need to keep track of number books liked by Alice and Bob, and a stack that stores books that are liked by single person only. Code
 » 10 дней назад, # |   0 For video explanation watch https://youtu.be/9pr8sY9hfkE
 » 10 дней назад, # |   0 Can somebody pls find the error in my code for E2 https://codeforces.com/contest/1374/submission/85464212. My procedure: Fist solve the problem like E1 and find out the number of items.If it is greater than M then erase 10 and 01 items and add 11 items.If it is less than M then we can add one 01,00,11,10 or we can remove one 11 item and add 01 and 10 items.
•  » » 10 дней назад, # ^ | ← Rev. 2 →   0 Are you keeping in mind about having k books when deleting?. I think when after doing E1 we have say x books. If xm then we have to delete two books (one liked by alice and one liked by bob) and add one book that both of them like
•  » » » 10 дней назад, # ^ |   0 Yes the condition of k is always satisfied and we cant add greedily always maybe we can remove a book both of them likes and add 10 and 01 books
•  » » » » 10 дней назад, # ^ |   0 When x
 » 10 дней назад, # | ← Rev. 2 →   0 In problem B, My solution: def main(n): count = 0 while n != 1: if n % 3 != 0: return -1 elif n % 2 != 0: n *= 2 count += 1 else: n /= 6 count += 1 return count 
 » 10 дней назад, # | ← Rev. 3 →   -7 problem E1..wrong ans test case 5...i can't find wrong my code...please help me to finding wrong or give me some small test http://codeforces.com/contest/1374/submission/85463861
•  » » 10 дней назад, # ^ | ← Rev. 2 →   +4 You can put same in spoiler or provide link. Page becomes weird in this way. Their is an option to provide link when you post comment.Oh. you have already provided link , so what was need of pasting whole code
•  » » » 10 дней назад, # ^ | ← Rev. 2 →   -9 i pasted code for more attraction...edited
•  » » 10 дней назад, # ^ |   +7 This is a trash way of presenting code.
•  » » » 10 дней назад, # ^ |   0 edited
 » 10 дней назад, # |   0 Can someone tell me why I got TLE for the D. I used unordered_map. My submission link 85385662
•  » » 10 дней назад, # ^ |   0 Change unordered map to ordered map.
 » 10 дней назад, # |   0 Codeforces Round #653 (Div. 3) D. Zero Remainder ArrayIn this Problem , if we consider a input — 1 2 5 4 4then as per the solution provided,the output is 7 but if we conside like —1 .when x = 1 , we will server one of the 4 (4+1=5 and 5%5=0) then x will become 2 2. when x = 2 , we will add it to the remaining 4 and it will become 6 and x will become 3 3. At this step , x is incremented and becomes 4 4. Now if we add 4 to the 6 , it will become 10 and 10%5==0 and then x becomes 5So the answer should be 5 . . Is it ? ? ?
•  » » 10 дней назад, # ^ |   0 It was given that you can't apply first operation to same indexed element more than once. You have performed first operation of adding+incrementing x twice on second element
•  » » 10 дней назад, # ^ |   0 No. You can add x for the number in array only one time. You cant do 4 + 2 + 4.
•  » » 10 дней назад, # ^ |   0 No, because this line was mentioned in the question. You cant do more than one operation on the same element "The first operation can be applied no more than once to each i from 1 to n."
 » 10 дней назад, # |   0 My Video solution for the contestProblem A,Problem B, Problem C The video is time stamped for your convenience (check the description).
 » 10 дней назад, # | ← Rev. 2 →   0 Can someone please help me, why my submission of problem A is getting TLE if I'm using a single while loop for a test case.My submission: https://codeforces.com/contest/1374/submission/85356771Thank you!
•  » » 10 дней назад, # ^ |   0 1000000000 1 99999999consider this test case provided many times. Your single loop will run 99999998 times in each test case, which will definitely cause TLE
•  » » » 10 дней назад, # ^ |   0 Okay, thanks
 » 10 дней назад, # |   +9 Can someone please tell me what is wrong with this greedy approach for E2 : SpoilerLet's sort the books in 4 types : Type 1 : Books that only Bob likes. Type 2 : Books that only Alice likes. Type 3 : Books that both of them like. Type 4 : Books that none of them like. Let's find the maximum amount of books of Type 1 or Type 2 that can be picked. They would simply be (m-k). Let's denote it with allowed  Greedily pick those books that either Alex or Bob likes in the following way : Let t1 denote least time taken for an unpicked book of type 1. Similarly t2 for type 2 and t3 for type 3 following above criteria. Pick book based on which value is smaller of (t1+t2) or t3. If we had already picked up "allowed" amount of books of type 1, we would have to pick up book of type 3. Now this picking process continues till we had already picked up at least k books of liking for Alice and Bob. We can fill in the rest of the remaining books with those unpicked books taking least time. This approach fetched me a WA on test 12. I looked in the status and a lot of people got the same result on same test case. Can someone pls help. Thanks in advance
•  » » 10 дней назад, # ^ | ← Rev. 2 →   +35 Consider the test case below — your method would choose book 3 over 1+2 but then you still need to add another book which leaves you with a best cost of 5. You could instead pick 1+2 and get a cost of 4. 4 2 1 2 0 1 2 1 0 3 1 1 3 0 0 
 » 10 дней назад, # |   0 http://codeforces.com/contest/1374/submission/85468392, can anyone tell me why am I getting TLE on 20th testcase in problem E1.
 » 10 дней назад, # | ← Rev. 3 →   +5 "and move it to the beginning (so the negative balance becomes zero again and the answer increases by one). This move is much more optimally than moving the current closing bracket to the right.""Moving a closing bracket to end" or "an opening bracket to beginning",doing either of these will result in the same answer ,so why the second one is optimal ?
•  » » 9 дней назад, # ^ |   0 I think you are right, these moves are equal. I can be very stupid sometimes, sorry for this confusing sentence, I'll remove it from the editorial.
 » 10 дней назад, # | ← Rev. 2 →   -6 Can someone explain me why I am getting Wrong Answer in E2. https://codeforces.com/contest/1374/submission/85472085My logic: lets call the 1 1 books as both. if both+Alice < k: then not possible also if both+Bob
•  » » 10 дней назад, # ^ |   0 Man, if you are a newbie, why then try a problem that only grandmasters can solve?
•  » » » 10 дней назад, # ^ |   +16 Why not solve it just for the sake of problem solving.
•  » » » 10 дней назад, # ^ |   +13 Just like Errichto said if you have ideas for a problem then exhaust them before checking the solution. If in the end he cannot solve it, then fine but don't discourage people from trying
•  » » » 9 дней назад, # ^ |   0 All grandmasters start coding by being a newbie.
 » 10 дней назад, # | ← Rev. 2 →   +4 I had a really simple solution for E1:I claim that Alice and Bob will both read exactly $k$ books that they each like. If we had a selection where both of them read more than $k$ books that they liked, then we can subtract out books (which decreases the total time) of $11, 10, 01$ until one of them has read exactly $k$ books that they like and the other has read $K \geq k$ books that they like. However, if one of them has liked $K-k$ more books, then they must have read at least $K-k$ books where they were the only one to like it. Thus, we can take out these books as well, which gives us a selection of books where they read exactly $k$ books that they each like, which is better than the original selection (where at least one person liked more than $k$ books).Now, based on the claim, if they read a $10$ book, they must also read a corresponding $01$ book in the optimal solution. Thus, the problem now just comes down to pairing these $10$ and $01$ books. We can do this greedily (I'll leave the proof for you). We sort the $10$ and $01$ books independently, and match them from lowest time to highest. Now, we essentially have created $11$ books from $10$ and $01$ books, where the time of this double-book is the sum of times of its two parts. We can just treat this double-book the same as a normal $11$ book, so we can sort the $11$ and $10+01$ books all together and take the first $k$ smallest times to find our answer.
•  » » 9 дней назад, # ^ | ← Rev. 2 →   0 I implement like this approach but why getting wrong on test 5? my codeUpdate: I found my mistake.
•  » » 9 дней назад, # ^ |   0 Loved your approach to this problem :D
 » 10 дней назад, # |   0 Has anyone solved problem D using sorting and 2 pointer approach?
•  » » 10 дней назад, # ^ |   0 Check this.
•  » » » 9 дней назад, # ^ |   0 Yeah got it. Thanks a lot.
 » 10 дней назад, # |   0 can anyone explain from where does that formula in the editorial come from?
 » 10 дней назад, # |   0 Can anyone please help why am i getting wrong answer on test case 12 of problem E2. My code — https://codeforces.com/contest/1374/submission/85427982 Initially I have taken all books which is interesting for both.Then if it is less than k then i have taken from remaining books which are in sorted order until the count of interesting books for both is equal to k.After that i have replaced the books interesting for both with books interesting to 1 only(2 books added for each 1 book interesting to both removed).Afterwards I have just added more books to make the total count m.I am not being able to figure out what is wrong in this approach. Plz. help.
 » 10 дней назад, # |   0 Hi, can any one explain me why am i getting memory limit exceeded on test 5 in my solution for problem D https://codeforces.com/contest/1374/submission/85477191
•  » » 10 дней назад, # ^ |   0 HI. I think you haven't seen the constraints of k in the problem. K is up to 10^9, so as you try to go through every possible remainder or element (not so sure about that), this leads to TLE.
•  » » » 9 дней назад, # ^ |   0 Yeah okay. Thank you.
 » 10 дней назад, # | ← Rev. 2 →   0 Why i am getting wrong answer for this submission(Problem E1): https://codeforces.com/contest/1374/submission/85476850 Please help!!
•  » » 10 дней назад, # ^ | ← Rev. 2 →   0 I am having that too. Wrong Answer at Test Cases 5 85481457I don't know why but feels like there is some thing we are missing.Guys help!!
 » 10 дней назад, # |   0 Okay,so I used a different approach to solve D without any map. Hence I thought,I might share it. First replace arr[i] by arr[i]%k. Then we can sort this array.Now we iterate over this sorted array using a counter variable c which counts no of same a[i] encountered till that point.And then simply find max value of c*k-arr[i]. 85390239
•  » » 10 дней назад, # ^ |   0 Same Idea!
 » 10 дней назад, # |   0 https://codeforces.com/contest/1374/submission/85367241 problem D.. idk why i am getting WA on tc 2...i had the same approach as in editorial...can someon help please!!
 » 10 дней назад, # | ← Rev. 4 →   +7 Imho this approach for E2 is easier: first, let's take k elements from 11 group (if this group is smaller than k — take all books from 11 group and first k - size(11) books from each 01 and 10). If number of books that we took is greater than m — the answer is -1. Now, we have some set ans of books that we took (size(ans) <= m), and we have 5 possible transitions: first 4 is to simply add the cheapest book from one of the sets, and 5th is to delete the most expensive book from 11 set and add 2 books from 01 and 10 sets (after this transition we will add cost(added) - cost(deleted) to the answer. After each of this transitions number of books in ans increases by 1, thus we have to make m - size(ans) iterations, (in each iteration we will try to add as less as possible to the answer). This approach can be easily implemented by storing pointers for each group. My code — 85363378.
•  » » 10 дней назад, # ^ |   0 When you say “ first, let's take m elements from 11 group (if this group is smaller than m — take all books from 11 group and first m — size(11) books from each 01 and 10” I guess you mean K instead of m
•  » » » 10 дней назад, # ^ | ← Rev. 3 →   0 Oops, you are right. Thanks!
 » 10 дней назад, # |   0 Can somebody explain E2
•  » » 10 дней назад, # ^ | ← Rev. 2 →   +4 I think my approach could be a bit easier to understand. Time complexity : O(n*logn^2).My approach matches with Mike for the beginning. First create 4 separate prefix sum arrays for 11,01,10,00 types.For each i from 0 to m, choose i 11-types and then select best (k-i) books of 01 and 10 types in order to fulfill the requirement. So till now we have selected a total of (i + (k-i) + (k-i) = 2k-i) books. We now need m-(2k-i) more books. Let's say this value as X. So now you need X smallest numbers from the 3 sorted arrays(01,10,00 types)From here you can just apply a simple binary search to find the Xth smallest number from the 3 sorted arrays of 01,10,00 types and get the indices upto which you must include to get the total X booksNote1: you must apply binary search on the original sorted arrays, NOT the prefix arrays.Note2: for 01 and 10 types, the starting indices for binary search will be from (k-i) because you have already chosen them before to fulfill the requirement.Now since you have found the indices(upto which you must have to include) for each array with binary search, you can simply calculate the total sum and compare it with the current minimum.P.S: implementation could be a bit heavy with this approach
 » 10 дней назад, # |   0 Another solution for E1: I sorted 01, 10, 11 books independently. Now you need to reach k books for both Alice and Bob. So we either have to pick 11 or (a 10 and a 01). We can greedily pick whichever is cheapest. Create a new v10[i] + v01[i] books. Combine v11 books with this new tuple of books, sort them and pick the k smallest values. 85376690
•  » » 9 дней назад, # ^ |   0 Easy one. Thanks a lot.
 » 10 дней назад, # |   +3 please someone explain me this..Then we need to find two consecutive pairs with the same first values and swap these two elements in the permutation. Because in fact these two numbers are equal in the array and have consecutive values in the permutation, we guaranteed change the parity of number of inversions. Problem F
 » 10 дней назад, # |   0 Pls explain why I'm getting WA in testcase2 of problem D. https://codeforces.com/contest/1374/submission/85355292
•  » » 10 дней назад, # ^ |   +4 Here in your code variable ele is storing the minimum value of all i%k whose if condition is true. lets understand this with an example, 1 3 3 1 2 2 Here d={1: 1, 2: 2} Initially, maxi=0 Firstly, value of i will be 1 and d[1]>maxi i.e 1>0 so, maxi becomes 1 and ele becomes 1. now, for i=2 condition is true, i.e d[2]>maxi i.e 2>1 so, maxi becomes 2 but ele remains 1 as you are storing minimum value encountered. So, this is wrong as if you change maxi you should change ele accordingly. you can make it right by using a condition that if maxi==d[i%k] then you should choose the minimum i%k, else you should change the value of ele to current i%k.  if d[i%k]>=maxi: if(maxi==d[i%k]): ele=min(i%k,ele) else: ele=i%k maxi=d[i%k] With it your submission gets AC 85494164
•  » » » 9 дней назад, # ^ |   0 Thanks man! Such a silly mistake while writing code! I think I'm really careless.
 » 10 дней назад, # |   0 For anyone having trouble understanding the 1374E2 - Reading Books (hard version) editorial: I think they meant 'but elements of 11-group are not free' instead of 'but elements of 00-group are not free'.
 » 10 дней назад, # |   0 For problem D, consider the test case n=3, k=7 and a={1, 1, 1}. With this approach the answer would be 21. But we can do it in 7 steps only. The required remainders are {6, 6, 6}. Which can be obtained by 1+5, 2+4 and 6. So array {7, 7, 7} can be obtained in one full cycle only.
•  » » 10 дней назад, # ^ |   0 You can only perform the add operation at a particular index Atmost once.If the problem was actually what you interpreted it to be, I guess it would've been much harder.
•  » » » 9 дней назад, # ^ | ← Rev. 2 →   0 Lol my bad :-) thanks for clarification
 » 10 дней назад, # |   -18 E2 is shit!
 » 10 дней назад, # | ← Rev. 2 →   0 - Problem E1:  - have doubts from editorial> If k−cnt is less than zero .....then return -1 why?and next question : what would be the output of the following input: 3 1 1 0 1 1 1 0 3 1 1 thanks in advance .........
•  » » 10 дней назад, # ^ |   0 cnt is the number of books taken from the 11-group.If cnt is greater than k then it cannot be the answer. If k-cnt which is the number of books to be taken from 01 and 10 group is less than the size of either 01 or 10 group then also it cannot be the answer. As to the answer of your input it will be 2. Hope i can make you understand.
•  » » » 10 дней назад, # ^ | ← Rev. 2 →   0 thanks a ton for responding @coding_lover is it necessary to take from the group 01 and 10: i mean for instance let k=2 cnt=3 and other group(01,10) has zero candidates. cant we just choose the least two candidates from cnt ? 
 » 10 дней назад, # |   0 Hey guys, if any of you having difficulty in understanding the editorial of problem E1. Here's a video to help you out. Thank you!
 » 10 дней назад, # |   0 my accepted solution in python3: n,k=map(int,input().split()) alice=[] bob=[] both=[] for _ in range(n): t,a,b=map(int,input().split()) if a and b: both.append(t) elif(a): alice.append(t) elif(b): bob.append(t) if len(alice)+len(both)0: if(alice[i]+bob[i]=len(both)): while k>0: ans+=alice[i]+bob[i] i+=1 k-=1 else: while k>0: ans+=both[j] j+=1 k-=1 print(ans) 
 » 9 дней назад, # |   -7 IS THERE ANY PROBLEM WITH THIS CODE FOR PROB B https://codeforces.com/contest/1374/submission/85385019
•  » » 9 дней назад, # ^ |   -6 BY THE WAY THIS IS AC code
•  » » » 9 дней назад, # ^ |   +2 If you not found any problem with your solution.then why you post here your solution for twice.we have editorial..No need your solution for B.
•  » » » » 9 дней назад, # ^ |   0 ACTUALLY MANY DOWNVOTED MY CODE
•  » » 7 дней назад, # ^ |   0 PThakur_16 Your code is neither having new concepts nor is efficient time complexity wise.So, I don't understand why you use to post your codes. We already have editorials.DOn't Spam the comments section. If your code got accepted then be happy.Btw your code is having poor time complexity.
 » 9 дней назад, # | ← Rev. 2 →   0 Can't understand cyclic shifts sorting. Can someone explain why odd parity fails to give answer ?Also why in the end two elements wont be sorted?Problem F
•  » » 9 дней назад, # ^ |   +6 Let's consider you are doing cyclic shift with permutation a1,a2,a3 then after doing cyclic shift the permutation will be a3,a1,a2 . Now one thing to note here is that the number of inversions done in one cyclic shift is 2(a3 is now before a1 and a2) , so every time we perform cyclic shift, the number of inversions done are increased by two or in another way we can say that we can never swap two numbers therefore if the required number of inversions have an odd parity we can never sort them.
•  » » » 9 дней назад, # ^ |   0 Thanks, also why in the end two elements wont be sorted?
•  » » » » 9 дней назад, # ^ |   +5 I think that if we have put all the elements till the last third element(in the sorted order) at their correct positions then we won't get last two elements unsorted as if we get the last two elements unsorted than the parity of the number of inversions in that sub problem(that particular state) will be 1(i.e. odd) which cannot happen.Also as it was not mentioned in the problem that all the numbers are different therefore such a condition may arise when we have two equal numbers. But contradictory if we have equal numbers then i think we might be able to sort even if we have number of inversions with odd parity as:-Let's consider 1 3 1The number of inversions is 1 but after one cyclic shift we can actually sort it.
•  » » » » 9 дней назад, # ^ |   0 Because two unsorted elements is one inversion, and we cannot get rid of one inversion.
•  » » » » 9 дней назад, # ^ |   0 "Then let's just cut off the first element and solve the problem without it. At the end we have only two numbers that can be not sorted and we can check all three possibilities and choose one which is suitable for us (it's always exists because the number of inversions is even)."Picked this from editorial. What are the three possibilities?
•  » » » » » 3 дня назад, # ^ |   +1 The three possibilities are the three cyclic permutations of the last three elements. 123 -> 123,231,312
•  » » » » » » 3 дня назад, # ^ |   0 Thanks
•  » » » 8 дней назад, # ^ |   0 Sir, if you can kindly say what we are going to do if there are duplicate elements in the array? I am unable to understand the editorial. Plz pLz help
•  » » » » 3 дня назад, # ^ |   +1 I think in that case we should skip checking the parity of the number of inversions and do next step as it is.If it takes us to a situation in which the last two elements are unsorted then we can check for all the three permutations(cyclic) of the last three elements and if none of them makes the array sorted then there won't be any possible answer.
•  » » » » » 3 дня назад, # ^ |   0 But , I find people changing the number of inversions if there are duplicate elements and the number of inversions is odd
 » 9 дней назад, # | ← Rev. 2 →   0 Please Someone Explain Why i am Getting TLE in Test case#5 my submission is : 85516199
•  » » 9 дней назад, # ^ |   0 try test case, where size of string is 1e6 and every bracket is ')'
 » 9 дней назад, # |   0 Can someone help me i am getting TLE in D part Here is my submission https://codeforces.com/contest/1374/submission/85529755 Thanks
•  » » 9 дней назад, # ^ |   0 try test case t = 1 1 1000000000 999999999
 » 9 дней назад, # | ← Rev. 2 →   0 In E1, I get the part where the editorial says that if k-cnt is grater than the size of 01 or 10 group.It means we do not have enough books to satisfy the condition that "Alice likes at least k books from the chosen set and Bob likes at least k books from the chosen set" but why the answer is -1 when we get k-cnt is less than zero. If k-cnt is less than zero cant we just choose k elements/books which are from 11 group as we have enough books in 11 group itself.Also, I have another doubt, why is it optimal to choose all the elements of the 11 group. For example n = 3 k = 1 1 0 1 1 1 0 4 1 1 Here if we take 4, it is not the minimal answer as we can have 1+1=2 as minimum. Did i get the question wrong?
 » 9 дней назад, # | ← Rev. 4 →   0 please help me with my solution for E1. Am getting WA. link
•  » » 9 дней назад, # ^ |   +1 The problem is in this part of your code for(ll j=x;j
•  » » » 9 дней назад, # ^ |   0 AC. Thanks a lot.
 » 9 дней назад, # | ← Rev. 2 →   0 What exactly is Problem E1 asking? Explain testcase.Input: 8 4 7 1 1 2 1 1 4 0 1 8 1 1 1 0 1 1 1 1 1 0 1 3 0 0 Output: 18 
•  » » 9 дней назад, # ^ | ← Rev. 2 →   0 problem statement : minimum time required such that a likes atleast k books and b likes atleast k books approach: there can be two cases- A likes a book and B doesn't and B likes a book and A doesn't. combination of these two gives that a like 1 book and B likes 1 book. Total time of this case will be Time of A+Time of B. while another case is that A likes a book and B likes that too. It also gives the result that A likes 1 book and B likes 1 book. Total time of this case is the time given . So for both to read 1 book minimum time will be the minimum of both cases. following the same approach for all k-1 books. .
•  » » 9 дней назад, # ^ |   0 I will try to explain the given test case. a01- 1,1,4 a11-1,2,7,8 if we consider the vector a01 then also we will have to consider vector a11 because in vector a01 there is no contribution in liking of b. so we have to consider all k=4 elements of a11 and so the result is 1+2+7+8=18
 » 9 дней назад, # |   0 Please help.I am Getting WA in Problem E2. My code:(https://codeforces.com/contest/1374/submission/85530060)
•  » » 9 дней назад, # ^ |   +5
 » 9 дней назад, # |   0 sorry,the code of the solution of E2 have some errors, it can't run in my computer,such as for (auto [value, position] : st) res.push_back(position); in the line 119 and st.erase(prev(st.end())); in the line 26could any one help me? thank
 » 9 дней назад, # |   0 Can anybody help me? for E2 (reading books hard version). I m getting wrong answer in test case 12 and my answer only differs by 1 from real answer.
 » 8 дней назад, # |   0 Can anyone explain the error in my submission in problem D https://codeforces.com/contest/1374/submission/85390655
 » 8 дней назад, # | ← Rev. 2 →   0 How does the given solution for question B ensure that there are no other prime factors other than 2 and 3 for the given n?
 » 8 дней назад, # |   0 Can somebody elaborate the Problem A.How does he come up with these terms n−nmodx+y and n−nmodx−(x−y) i don't understand these terms.
 » 8 дней назад, # |   0 Can anyone tell me why my solution to Problem D is getting Memory limit exceeded?Link to my solutionI think my code takes even less memory as compared to the code in editorial, since I am not using an array to store the numbers! :\
 » 7 дней назад, # |   0 I have some problems understanding the editorial of 1374D - Zero Remainder Array.Firstly, he says that you "fix" an element. What does that mean? Does he mean that the subsequent element which has the same remainder has to wait for the next cycle?Secondly, this part of the editorial k− ai mod k=i holds (i.e. the number of such elements that we can fix if we add the value i mod k to them). He uses ai mod k in the LHS and i mod k in the RHS... was that just a mistake?
 » 7 дней назад, # |   0 Is it possible to make a binary search solution for problem A ? if so, then please share your code.
 » 7 дней назад, # |   -8 int question E1 why we are taking all 1 1 elements? there might be one case where addition of 1 1 elelments have more reading time then reading time without taking them. somebody explain.
 » 7 дней назад, # |   0 I am solving E1, following same approch as tutorial, still getting wrong answer on test case 4. here is my code:Code in JavaCan someone look and tell what am I doing wrong?
 » 6 дней назад, # | ← Rev. 2 →   0 Can anyone help with D? Why answer at least is k⋅(max(cnt)−1, how we come to that?
 » 6 дней назад, # | ← Rev. 3 →   0 Can anyone help, what I'm doing wrong? I'm getting WA in E2.My logic for solving this — Make min heap for all 00, 01, 10, 11. Get element from 11 or (01 and 10) whoever gives me lowest sum for contributing to k likes. After repeating step 2 for k times, get element from 00, 01, 10, 11 whichever contributes minimum to sum and repeat this till total books read goes to m. my submission — 85968003Thanks in advance!
 » 6 дней назад, # |   0 Please look into my solution. I think I'm adding some more elements than what's required but my logic is clear. I cannot find where the error is in my logic or code . Here's my submission https://codeforces.com/contest/1374/submission/85868319please let me know if you can find a problem. I am getting WA on test 5.
•  » » 41 час назад, # ^ |   0
•  » » 40 часов назад, # ^ |   0 I think later on you could replace a pair of two books that each like with a single book that both of them like
 » 5 дней назад, # |   0 Can someone explain problem D's solution more clearly?I didn't get it. Thanks in advance!
•  » » 5 дней назад, # ^ | ← Rev. 3 →   0 Suppose the array elements are {8,7,1,8,3,7,5,10,8,9} and k = 6 you will have to add {4,5,5,4,3,5,1,2,4,3} these to ith element to get remainder 0 but you can only add a number once suppose there are 3 element in array which require 5 so first will get 5 second will get 5+k and third will get 5+(2k). So if 5 is the biggest number with max_count = 3 ans is k*(max_count-1)+5.
 » 5 дней назад, # |   0 On Question D Zero Remainder array can anyone explain why my submission is getting Memory Limit Exceeded MySubmission
•  » » 4 дня назад, # ^ | ← Rev. 2 →   0 I got it bro. The thing with your solution is that you're running a loop from 1 to k. In the question, k can be as large as 1e9. Hence we iterate only through the elements of the map.To cure the MLE error, only take k as long long . Rest all as int.YOUR MODIFIED SOLUTIONhttps://ideone.com/XFVuey
•  » » » 4 дня назад, # ^ |   0 Thanks bro, will try this.
 » 5 дней назад, # |   0 I did exactly what is written in the tutorial for B. But still I got wrong answer in TestCase 5. When I did the a check that after dividing with both 2 and 3 (for getting respective powers) that the resulting number is 1 or not, my submission passed. This is weird.
•  » » 5 дней назад, # ^ |   0 Any reason why this happened?
 » 4 дня назад, # |   0 My approach:First step:I am greedily allocating the common taste books, followed by remaining books of alice and bob. With this, I am ensuring at-least k-books are included in the list and the time is minimized.With this, easy version got accepted.Second step:If booksRead > m, I am reducing the numbers by replacing the individual taste with the common taste books. If booksRead < m, I am greedily allocating the least time taken book from the remaining entire books available.It seems that I am missing something in my code. Due to that, the hard version got failed in the test case 12. Here's the submission link: https://codeforces.com/contest/1374/submission/86028907Can someone please explain what I am missing in my code?
 » 4 дня назад, # |   0 Please tell me, why do we have exactly optimal solution when we take ")" to the end of string in problem C.
•  » » 4 дня назад, # ^ |   0 How to prove?
•  » » » 4 дня назад, # ^ |   0 Since there are equal number of opening and closing brackets, you may take '(' or ')' to beginning or end of the string to get the optimal solution. And you are reaching this solution once the existing valid bracket sequences are removed/invalidated from the actual string.
•  » » » » 4 дня назад, # ^ | ← Rev. 3 →   0 Thanks. I can`t undestand how can you prove something so easy)) Really, it is very difficault for me. May be some secrets? Because it is a bit "dangerous" to solve the problem with out proving....
 » 2 дня назад, # |   0 my soln is showing error while on my local machine it is showing right answer.someone please help 85351451