Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### Melnik's blog

By Melnik, 3 years ago, , First accepted Div1: 00:00:58 kriii

First accepted Div2: 00:00:59 Baneling3

Author's solution

First accepted Div1: 00:03:30 egor.lifar

First accepted Div2: 00:04:43 Baneling3

Author's solution

First accepted Div1: 00:08:30 nuip

First accepted Div2: 00:10:19 ColdSu

Author's solution

First accepted Div1: 00:15:47 arsijo

First accepted Div2: 00:18:01 ColdSu

Author's solution

First accepted Div2: 01:05:21 CountOlaf

Author's solution

First accepted Div1: 00:16:33 mcfx

First accepted Div2: 01:12:52 Nisiyama_Suzune

Author's solution Comments (104)
 » 3 years ago, # | ← Rev. 3 →   how do u prove that the solution to D is ?When u are processing dp, it seems like depending on how many prime factors i has.So i think it should be ?
•  » » No, because you only need to choose the smallest prime factor each time.
•  » » If you go one by one and factor every number from l to r, the running time is indeed . However, to speed this up, we instead use a Eratosthenes sieve-like approach: from l to r, look at all the multiples of 2, then all the multiples of 3, then all the multiples of 5, etc.. The running time is thus which was proven by Euler (?) to be approximated by .
•  » » » Why is this solution giving tle whereas this passes.In first soln I am storing all the distinct primes of a no than calculating the ans whereas in second soln I am dividing by smallest prime factor each time. I also calculated the total no of times the loop is executed in both the solutions and the first soln has less execution. Can anyone help on this ?
 » 3 years ago, # | ← Rev. 2 →   Would you mind sharing why most people got E WA'd by using dp[sprefix][xcnt][flag]? I tried to come up with a counterexample but nevertheless failed.
•  » » Try this sample. Some of the solutions, that get WA24, fail on this test:10baaabbbcac5babbc2(The correct answer is "YES" as you can see).
•  » » » 3 years ago, # ^ | ← Rev. 2 →   I see. My friend has also made a hack to my own program: 7 abababc 3 ababc 1 Many thanks!
•  » » » Thanks! This was a saviour
 » Can anyone please tell me what I did wrong on problem C so I got WA on test 58 :(28220911
•  » » The question asks you to find the sum of cost of vouchers whose intervals don't intersect. You don't entertain that possibility. You just find the minimum cost of the required interval length whose starting point is before it, but that doesn't guarantee that they don't intersect.For eg, Your code fails on: 3 3 1 2 1 1 1 1 2 2 3 Answer is -1 whereas your code prints 2. Your code takes two intersecting intervals which should not be the case.
 » 3 years ago, # | ← Rev. 2 →   Can anybody help me please ? :)C solution
•  » » it gives 3 instead of 2 on foll test case:- 3 6 1 3 1 4 6 2 7 9 1 Mistake in ur code is that when u binary search,according to your code you should check all possible coupons for whom st>last and time==left. but say if a[mid] follows the condition it may be possible that a[mid+1] also follows these 2 conditions and furthermore may have lower cost causing the error.But u change r to mid-1 hence never searching for lower cost in indices greater than mid.
•  » » » Ah, thanks a lot. :DThen, can I edit my approach or this solution is basically wrong?
•  » » » » Well it seems to me that ur soln is wrong and atleast it is not the best approach. You may see my solution if needed - http://codeforces.com/contest/822/submission/28246016
•  » » » » » I saw your solution, but I was able t understand your logic, plz example it to me. I tried by using map but getting tle.
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   Maybe bcoz map is slower u may be getting tle. What i am doing is for each i, for each cupoun that ends on day i we will check for best matching cupoun that starts after i and of duration x — duration of given coupon which is stored in ans array
•  » » » » » » » http://codeforces.com/contest/822/submission/28693823 still getting tle
 » Can anyone please tell me what I did wrong on problem C so I got WA on test 58 :(28220911
 » It's embarrassing although my solution for D passed I couldn't prove it before reading the editorial. Thanks!
 » 3 years ago, # | ← Rev. 2 →   I dont know why i got E wa on test 172,which is the last case. Can any one help me？？？ My submission
•  » » Oops,i got wa because of my hash,mod 264 is stupid
•  » » » Could you explain why?
•  » » 3 years ago, # ^ | ← Rev. 2 →   I also got WA on test 172 :( Can you help me with this ? 28386238
 » For people who are still struggling or trying to understand problem c solution and not able to understand editorial (like me :p ), i want to explain it since i solved it now.Brute force solution is O(n^2) which i think everyone can get. We want O(n) or O(nlogn).Approach: 1)store interval {l,{r,cost}} in vector>>a 2) First sort the intervals vector>>a wrt left point. 3) Iterate over vector a and store duration in another vector vector>min_value[N] (It contains left point and cost). This vector will contain information about all intervals with a specific duration.Good thing is min_value[d] will contain interval information in sorted wrt left point (isn't it ?) 4) Now we will find our answer similar to our bruteforce approach. Bruteforce is to iterate over all intervals , and for each interval we will take O(n) to find min_cost. We are trying to reduce this O(n) to O(logn) to make our solution O(n logn). 5) So start iterating , choose first interval , we know it's duration d , our need = x - d; we have intervals in our vector min_value[need] which is sorted wrt to left point , we want to find that index in min_value[need] which has it's left point greater than current interval's right point. we can find that using binary search and obtain minimum cost. There will be many possible interval satisfying our interval condition , we can choose any with min_cost , so we also need to precompute min_cost in all intervals ahead of that index (similar to prefix sum) Here is my solution , see this everything will make sense.
•  » » codenote Thanks for the explanation :) But I have a small doubt in your code.  // this is the crux to find desired cost in O(1) :) for(int i=0;i=0;j--) { min_value[i][j].second=min(min_value[i][j].second,min_value[i][j+1].second); } } Consider a case where there are N elements in the array only 4 distinct values as their cost so your min_value[j].size() will be ~ N/4. Now you are doing it for all N so it will be O(N^2) right ? Correct me if I am wrong!
•  » » » its linear as total number is number of RANGE is n & we touching every RANGE just once. check it what I say.
•  » » 3 years ago, # ^ | ← Rev. 2 →   your explanation helped :) But one thing is not clear to me. Can you explain this to me?There will be many possible interval satisfying our interval condition , we can choose any with min_cost , so we also need to precompute min_cost in all intervals ahead of that index (similar to prefix sum)how and why does this work? thanks :)EDIT: I got it now. :D
•  » » It looks like author's solution is a bit different. He adds to a processing queue two kinds of tuples: {{l, Type.ForPossibleAnswerCalculation}, {r, cost}} and {{r, Type.ForMinCostHashTableUpdate}, {l, cost}}. Queue sort arranges tuples of the first kind by left border and the ones of the second kind by right border. Because at the moment when you process a travel that starts at li all tuples with r < li already processed, bestCost[needLen - curLen] contains best possible value.
•  » » I don't understand this part in your code — // this is the crux to find desired cost in O(1) for(int i=0;i=0;j--) { min_value[i][j].second=min(min_value[i][j].second,min_value[i][j+1].second); } } Why are you changing the costs attached to the intervals ? Please explain
 » For Problem D, this code, gives TLE on test 18, I think it has the same time complexity as intended. Could anyone help me with this. Thanks.
•  » » Your code's complexity is R.log(R) whereas the intended complexity is R.log(log(R))No need to divide x by all its factor to find dp[x]. Just divide it by its smallest prime factor.dp[x] = dp[x/sp[x]] + (sp[x]*(sp[x]-1))/2 will work, sp[x]: smallest prime factor of x. Preprocessing the sp array is O(R.log(log(R)) and the calculation of dp will be O(R).
 » 3 years ago, # | ← Rev. 5 →   Melnik, What if for C we consider the following solution:-1) We sort the vouchers in increasing order of the cost. O(nlogn)2) Then for each voucher Vi we find a Vj (j>i) such that the intervals don't intersect, and such that duration of the Vi+Vj is x. We return the first Vj we find satisfies this conditions.Time complexity — O(n^2)Is the above solution conceptually correct?(Other than having poor efficiency)
•  » » Yes
•  » » » But it is giving wrong answer on pretest 4. You can check my submission — 28227628
•  » » » » You are not checking further for any Vi as soon as you find Vi+Vj==x. It can be possible that for next Vi you will find appropriate Vj such that total cost is less compared to previous.
•  » » » » » Thanks for looking into it :)
•  » » I used the same logic as you described and it gives timeout in 4th test case. Here is the link -> 28221981
•  » » » Obviously, apna wala approach is O(n^2), and required efficiency is nlogn.
•  » » No, it's wrong. Try this case:4 51 3 41 2 53 5 64 5 8Your answer = 12Actual answer = 11
•  » » » Thanks for pointing it out.
 » In D, "So, we proved that all d i should be prime", how is it proved bcz spliting a composite number into 2 gives less comparisons?? can someone explain this
•  » » "how is it proved bcz spliting a composite number into 2 gives less comparisons"You said it yourself: splitting is cheaper. So we should split, as much as we can -> we have split it into primes.
•  » » » thanks, got it!!
•  » » » Hi johnLate, Dont you think then even must be split in only pair of twos and odd with a triplet and all other into pair. This should result in minimum cost . However I am not getting same answer. Thanks
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   Each group of a stage must have the same size. For example, you can split 15 into 3,3,3,3,3 or 5,5,5. But you can not split it into 2,2,2,2,2,2,3 or something like that.Example for n=15: In the first stage split into 5 groups of x=3 girls, do x(x-1)/2 comparisons for each group, then solve the problem for the resulting 5 girls. f(15) = 5 * 3(3-1)/2 + f(5) [Note: It is f(n) = n/x * x(x-1)/2 + f(n/x), it is NOT f(n) = n/x * f(x) + f(n/x)]
•  » » » » » Cool! Thanks
 » O (n) solution for C 28236057
•  » » For each value of i, we may have many possible values of ind but we need to find one for which cost is minimum. You are just checking the first possible value of ind only!
•  » » » Thanks for the reply! However, I first sort all the vouchers according to the cost in ascending order and then I pick the first voucher. So, the first one has minimum cost.
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   Say if m does not satisfies the condition, you take l = m+1 ( rembeber that if duration of coupon is greater than or equal to x than we can simply ignore them right from the start hence second condition really never makes sense as we can assume all coupon have duration less than x!) . But it may be possible that m-1 may satisfy the condition or similarly any value less than m even though m may not satisfy the condition! In your soln, You need to find out smallest index between l and r that satisfies the 2 condition!
•  » » » » » I got it. Thanks
 » Can someone explain author's solution in C. Why 2 types of queries {-1,1} and why updating bestcost online like this works.
•  » » Firstly notice that we are adding both 'l' and 'r' to queries vector as this will help us refrain from intersecting intervals. Then on the other hand we have to also keep track of whether the value is the start of interval or end of the interval, so {-1,1} are used.The main thing to see is that bestCost is updated when 'r' is found and ans is updated when 'l' is found.This thing makes sure that an interval doesn't uses bestCost from any other intersecting interval before "ans" is updated on 'l'.
 » HELP!!! How to FORGIVE!! •  » » Haha, funny bug :DI'll fix it soon.
•  » » » hahahahaha
 » 3 years ago, # | ← Rev. 3 →   Can somebody help regarding my solution for D. It's giving runtime error on test 1. I think there is a problem with my sieve because after commenting that program runs correctly on test 1. But my sieve function looks good to me. 28250621
•  » » Runtime error cause you are using too much memory! And even if you decrease the memory complexity, you'll still get tle anyway.
•  » » » As far I know allowed memory is approximately 1500 MB and mine uses approximately 80 MB. So I think memory is not a problem.
•  » » See I submitted 2 solutions. With sieve 28250621 and without sieve 28250581. They both almost use same amount of memory but sieve one is giving RTE.
•  » » » Fix rep(i,2,NMAX) to rep(i, 2, NMAX — 1) and for(j=2;i*j<=NMAX;j++) to for (j=2;i*j
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   Flyce Thanks .I was using memory out of index. :)
 » Div 2 C wrong ans test case 25. Any help?http://codeforces.com/contest/822/submission/28250623
 » DIV2 wrong answer on test 13, but I really think it is right(binary search for len of every voucher). Anyone help? http://codeforces.com/contest/822/problem/C
•  » » sorry... the problem is C. I forget that...
 » For C what I did was made a array of vectors of duration. Then while traversing the queries I know that the required duration is x-(r[i]-l[i]+1) and in duration vector I find the starting position with binary search and apply RMQ. I got runtime error on test 3. Is there anything wrong with this approach?
 » Can anyone help me with hashing to find lcp in problem E? Do we precalculate hash values and then in every DP state find it in O(logN) — only binary search? Please help.
•  » » http://codeforces.com/contest/822/submission/28265538 I managed to solve it. Learned a bit more about hashing and realised all I need is rolling hash and in O(1) I can easily get hash of some segment. So, per dp state only log(n) is needed to binary search for max lenght.
 » "But if we divide this stage into two new stages, then number of comparisons is " . how do we get this equation ?
•  » » In first stage: There are "n/a" groups of a elements each. So comparisons are (n/a)*(a)*(a-1)/2 = n*(a-1)/2For Second stage: There are "(n/a)/b" groups because from first stage "n/a" elements go ahead. So comparisons are (n/(a*b))*(b)*(b-1)/2 = n*(b-1)/(2*a)
 » Can somebody help in finding why my Div2 C is giving wrong answer.. I know my solution will give TLE but why is it giving WA.. I need to know,what's wrong with the approach,I already know it's not efficient,but I cant figure out why WA in testcase 12..SOLUTIONMy approach : I created a vector that contains duration of vacation,start time,end time and cost in that order.. Next,I sorted it... Next,starting with i = 0 , from the beginning of this vector,I find the required duration (x — duration[i]) I use lower_bound to search for this value compare all such elements having the same duration (x — duration[i]) I understand it will yeild TLE,but WA,I can't understand..Please help!!
 » Could someone help me with my solution on problem C? Why is it failing on test 3?I sort segments (l, r) by left bound, then while being in segment i, I update mincost with all segments with r_k < l_i which have not been used for updating yet.
•  » » 3 years ago, # ^ | ← Rev. 3 →   UPD: found failing test case:) 3 6 1 9 1 2 5 1 6 7 1 my solution: -1 correct answer: 2
 » Can anyone help me with my code? I got Runtime error on problem C but I don't know why. Thank you very much! http://codeforces.com/contest/822/submission/28261279
 » In Problem C, I'm really amazed no one mentioned the O(Max(l i, r i)) for i = 1 → n greedy solution!The solution is only possible due to the low range of l i, r i which is less than 2·105 We simply use this fact to store the vector of pairs of {r i, cost i} at index l i in an array called left , and do the complement of this in another array (i.e. store the vector of pairs of {l i, cost i} at index r i in an array called right)Then we loop for every i = 1 → Max(l i, r i) and fix our index i to be the left bound and check for every pair j at left[i] to see if we have encountered a non intersecting segment before it that has the length X - (left[i][j].r - i + 1) in an array called best for example and minimize our cost by the current which is the cost of the current pair left[i][j].cost and whatever was saved in the complementary segment length in our array best[X - (left[i][j].r - i + 1)]After we have processed the fixed left index, let's see if there's a segment has its right index at this same index i, if so we need to min update the value of its length in our array best to use it in the future at further indices, and this way we're sure we can never have intersecting segments, because we query first and then update.I hope I haven't made it much worse than the obvious O(n·log(n)) which could be due to binary searching or using a map/set to store higher ranges.All in all, here's the link to my submission for further detail -> 28237414
 » 3 years ago, # | ← Rev. 2 →   Update: Never mind! My brain did not work until I wrote the comment!I was going through the submission 28257135 for problem E. I was wondering what is the time complexity of below two statements. 1.  sort(u1, u1 + L, [](int a, int b) { return str[a] < str[b]; }); 2.  for (i = 0, j = 0; i < L; i++) { if (i == 0 || str[u1[i]] != str[u1[i - 1]]) j++; sa[u1[i]] = j; } 
 » regarding problem D in the point of all di should be prime:it can also be thought of as: suppose number d with n1*n2 = d (where n1 and n2 >= 2 and are prime), without splitting, comparisons made are: n1n2(n1n2 — 1) / 2. with splitting, comparisons made are: n2n1(n1 — 1)/2 + n2(n2 — 1)/2 (supposing that d is splitted to n2 groups with n1 participants in each group), now subtract the second equation from the first one : 0.5((n1n2)^2 — n2(n1^2) — n2^2 + n2), rewriting the expression: 0.5n2((n1^2) * (n2 — 1) — (n2 — 1)), rewriting again: 0.5n2(n2 — 1)(n1^2 — 1), which is clearly greater than 0, so the number of comparisons made in the first equation is larger than those made in the second equation.
 » For problem C, can it be solved by sorting the vouchers by r-l+1. Then iterate through every single voucher and take it as the first voucher selected, the second one is chosen through a binary search(look for the value x-(the first selected voucher r-l+1). If it's found check if there are more x-r-l+1 values to the left and right. Check if any of them is valid and it minimizes the money needed.My submission It's a messy solution.
 » Can someone tell me how to solve a variation of Problem C, i.e., if more than two disjoint trips are allowed? (Select T trips covering duration K) All I can think of is a recursive approach. For N trips and duration K, choose min(cost[i] + Trip(disjoint_trips(i), K - dur[i]), Trip(remove_i_from_list(i), K)) Any other approaches would be nice. Thanks
 » I understood the problem D. However, how can we come up with the idea "all di should be prime" ? Thanks you.
•  » » Observing.Try to calculate f(16), f(20)...If u had experience in olympiad maths it would be easier, because in maths many times you need to observe something, to see a pattern. So, just calculate few f-values and you will see that optimal is to choose di as smallest possible, but since they need to divide total number of people in current stage, they must be primes. Its important to mention that i solved a problem without this observation, only bottom up DP. Thats why solution passed in 1450 ms while 1500 ms was limit, so i was lucky.
 » 3 years ago, # | ← Rev. 2 →   Can anyone teach me how to prove "you can prove the fact that we should split the girls into groups by prime numbers in the order of their increasing" in problem D.Thanks a lot :)
•  » » 3 years ago, # ^ | ← Rev. 2 →   just suppose a and b are two distinct prime factors of n. The number of comparisions that you want to minimize is given by the recursion formula: By this you can imagine the expansion for all the factors of n. For two different prime factors a and b you get to choose if a is bigger or smaller than b. will be the same no matter the choice. So just analise the first part of the expression, the . Imagine all pairwise choices for a and b among all prime factors of n, by proving that choosing a 0 which is true because b>a and both a and b are bigger than 1 because they are primes so, for sure |ab(b - a)| > |(a - b)(a + b)| because ab > (a + b) which concludes the proof.
•  » » » Thank you. Maybe I fail to get the point... I thought you only prove that if the pair a,b is given (a
•  » » » » You are right. I did not prove why the solution must be greedy and, in fact, I do not know how to do that. An ideia to why this works is, since the next values will be divided by ab (the part) what is most important to minimize is the current value not divided.
•  » » » » » Anyway thank you:)
 » can someone please post a noob's solution for problem E? really couldn't understand a thing...
•  » » You can refer to my submission here. Tried to make it as clear as possible. (:http://codeforces.com/contest/822/submission/28289280
•  » » » by noob's solution I meant, noob's explanation :P... can you help with that? really having a hard time to figure out how to proceed...
•  » » » » Okay so you need to find if string S of length l1 can be broken by maximum x cuts into pieces that can be joined together to form string T of length l2. Assume that the strings are 1-indexed. dp[i][j] stores the maximum prefix of T that can be obtained from length j of string S after i cuts. So obviously, we need to see if there exists a value of i that is less than or equal to x such that dp[i][l1]=l2. Now assume that you have dp[i][j]=t1. That means after i cuts and length of j from string S, we can obtain the first t1 characters of string T. Now, two transitions are possible. Either the j+1'th character of string S matches with t1+1'th character of string T, resulting some length of their prefixes matching, or those characters are not equal. If the characters are equal, we can binary search + hashing to find the LCP (Longest Common Prefix) of string S from j+1...l1, and string T from t+1...l2. Suppose the LCP is t2. Then, the transition dp[i+1][j+t2]=max(dp[i+1][j+t2],dp[i][j]+t2). (i+1, j+t2 must lie within bounds)If the characters aren't equal, then dp[i][j]=max(dp[i][j],dp[i][j+1]) because the first j+1 characters of string S can give the same answer as the first j characters. Hope this explains it. (:
 » I notice that some of the current AC solutions for Problem E use greedy strategy and I think it is wrong. For example, 28272853. I was wondering if there is a chance to open hack and rejudge. Hope the solutions won't mislead future coders. I got a test case to turn these solutions into WA. 19 xmmmabcdmmmabcdbmmm 7 xabcdbc 3 The answer should be YES but these solutions output NO. Thanks.
 » guys can someone gives me a simplified test case according to test case 7 in Div2 C problem :( my code fails and has got WA on test case 7 :/ this is my code here
•  » » On codeforces we do not have access to the full test case, but what you can do is when you detect the problematic test case (that is, in your case when n == 200000 and x == 114451) you print whatever parameter you need to debug. Your code is outputing a value smaller then the answer from the jury, so your two choices for the 2 vouchers shoud be invalid, that is, they intersect or something like this, just print it to check.
 » In the author's solution for 822C - Hacker, pack your bags!, why do we have to add two types of queries? Isn't the first type enough to handle all cases?
 » For those who use hash for E and got wrong answer in test case 172unsigned long long is hacked, u have to modulo something else.
 » I use an O(r*log(r)) algorithm and get Accepted as well. Instead of enumerating all primes, I use all factors to update the answer.
 » i am getting runtime error for case 2 but when i am running my code on my pc for case 2, i am getting correct answer. Here is the link to my submission: http://codeforces.com/contest/822/submission/28796938
 » 3 years ago, # | ← Rev. 2 →   Very strange TL in div2 D, I wrote solution with the same idea as in editorial, but it got TLE with 1.8 sec in worst case ( l = 2, r = 5·106). I replace some long long variables with int (it always helps a bit), but got 1.575 sec in worst case.So it would be smarter just to make TL = 2 sec and not to make people find small extra optimizations for their code (main solution idea is enough, isn't it?).
 » http://codeforces.com/contest/822/submission/34284404 can anyone tell me why i am getting WA on test case 19? it seems okay to me
 » 2 years ago, # | ← Rev. 2 →   Can anyone explain the dp states along with transitions of problem E div2, unable to get it from editorial.
 » In Div2 C problem, Why we can't sort the vouchers by their right borders?
 » Div2 C , isn't the standard algorithm used in editorial actually known as 'line sweep algorithm' ?