### Melnik's blog

By Melnik, 4 years ago, translation,

Hello everyone!

This Sunday July 2, 19:05 MSK rated Codeforces Round #422 (Div. 2) will be held.

This time I'm the only one author in contradistinction to the Round 415. Many thanks to coordinator Alex netman Vistyazh for help in preparations of the round, Vladislav winger Isenbaev, Alex AlexFetisov Fetisov, Nikolay KAN Kalinin and Ildar 300iq Gainullin for testing the problems and also to Mike MikeMirzayanov Mirzayanov for Codeforces and Polygon platforms.

As in the Round 415, the main characters of the tasks will be the stunning girl Noora and hacker Leha.

Participants will be given six problems and two hours to solve them. As always, participants from the first division can take part out of competition. Scoring will be announced before the round.

I hope you'll enjoy my round. I wish everyone good luck and high rating!

UPD1: Note that the number of tasks which would be proposed for the solution has been changed.

UPD2: The scoring for this round is: 500 — 750 — 1250 — 1750 — 2250 — 2500.

UPD3: Congratulations to the winners! Editorial will be posted soon.

Div. 2:

Div. 1:

Special congratulations to natsugiri, who is the only one among all the participants who coped with all six tasks!

UPD4: Editorial.

• +428

 » 4 years ago, # |   -48 Really looking forward to this round! //Why always stunning girl Noora and hacker Leha... (codeforces round 415)
•  » » 4 years ago, # ^ |   +18 N** coincidence, why not? You'll feel like making "Tommy" do all sorts of interesting/ridiculous things if you do more problemsetting.
 » 4 years ago, # |   +21 Is it rated?
•  » » 4 years ago, # ^ |   -9 Not for you bro
•  » » » 4 years ago, # ^ |   0 why? why? why? T-T
•  » » » 4 years ago, # ^ |   +41 Why do you talk to yourself? Are you so lonely?
•  » » 4 years ago, # ^ |   +13 till now yes.
•  » » 4 years ago, # ^ |   -20 В связи с последними событиями очень актуальный вопрос
•  » » 4 years ago, # ^ | ← Rev. 2 →   +2 I want to ask it too.The past two contests are both unrated!
•  » » » 4 years ago, # ^ | ← Rev. 3 →   -6 I'm so tired.
•  » » » » 4 years ago, # ^ |   +14 don't worry this time it will be rated and try to learn some new things from each and every contest instead of thinking about ratings and all.
•  » » » » » 4 years ago, # ^ | ← Rev. 4 →   +8 I'd like to go to sleep if this is unrated.Then I will have a virtual contest.
•  » » » » » » 4 years ago, # ^ |   +2 The virtual contest can let me learn some new things too.
•  » » » » » » » 4 years ago, # ^ |   +3 Me too.
•  » » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 But,in virtual contest,there is no hacks,no points.
•  » » » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   -8 It's a little boring.
 » 4 years ago, # | ← Rev. 7 →   -9 UPD: I miscalculated it. I'm so sorry for inconvenience.I think the time and date link is incorrect as it differ from the remaining time.] written in contests page.
 » 4 years ago, # |   0 Hopefully this time it will be rated ;D
 » 4 years ago, # |   +66 tourist is registered and everyone is excited!
•  » » 4 years ago, # ^ |   +13 He unregistered!
•  » » » 4 years ago, # ^ |   +47 tourist you're such a troll!
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 He unregistered now, or he isn't registered basically his last visit was 6 hours ago before which is before the registration opened. Looks like you just want contributing points :D
•  » » » 4 years ago, # ^ |   +22 snowden.exposedNice try detective, but that "Last visit" thing doesn't work well.
•  » » » 4 years ago, # ^ |   +16 why would a fake account wants contributing points though?
•  » » 4 years ago, # ^ |   0 Then why I can't see tourist in the registration list?
•  » » 4 years ago, # ^ | ← Rev. 2 →   -64 ...
•  » » » 4 years ago, # ^ | ← Rev. 3 →   -23 He is fond of contribution, I think he comments from this account then upvote his comment form other accounts, as I realized immediately when he write a comment he got +3 or something like this, which gives more chance to upvote him after seeing that tourist is registered and the comment took +22 before checking if he if really registered.
•  » » » » 4 years ago, # ^ |   +100 Yes, I upvote my own comments and I also did 9/11.
•  » » 4 years ago, # ^ |   +9 He ranked 5 in SnackDown 2017 Finals today the 3 top are 1-Um_nik's team 2-anta's team 3-jcvb's teamcheck Ranklist here
 » 4 years ago, # |   -13 we hope it be rated and no issues during the round after two consecutive unrated round
•  » » 4 years ago, # ^ |   +2 It's three
 » 4 years ago, # |   -33 Is it unrated?
•  » » 4 years ago, # ^ |   +3 the answer is after the contest :D :D
 » 4 years ago, # |   +184 Schrödinger's round: it's both rated and unrated until it ends
•  » » 4 years ago, # ^ |   +64
 » 4 years ago, # |   +58 Two consecutive rounds unrated, i think codeforces should be more cautious！
•  » » 4 years ago, # ^ |   -15 The last round was just the author's luck though, nothing could have been done to help.
•  » » » 4 years ago, # ^ |   +14 what? having a false solution to a problem is luck? I am not saying the that it is the author's fault, but being cautious does help in such situation, so why do you think that it is luck?
•  » » » » 4 years ago, # ^ |   0 Yes.I think it is a luck because you can learn from it.
 » 4 years ago, # |   +69 I can only imagine the pressure on author.
 » 4 years ago, # |   -280 Round #422=Registration x422
•  » » 4 years ago, # ^ |   +78 Soon it will be Round #422=Downvote x422
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -10 Soon the blog post rating will be 422! Great! UPD: It's now +416. Soon it will be 422 or more!
 » 4 years ago, # |   +16 Hope this time nothing to be happened to make this round unrated !I participated in the last two rounds, in spite of Eid occasion. One of them was at the night before Eid day in our country and another was one day after the Eid day. Though my friends and relatives were enjoying and gathering by themselves with other stuffs, I participated in the contest in stead of joining with them, because I love to do contest. But unfortunately both of them became unrated !
 » 4 years ago, # |   +202 I speak through memes.
•  » » 4 years ago, # ^ |   +64
•  » » » 4 years ago, # ^ |   +121
•  » » 4 years ago, # ^ |   -28 .
 » 4 years ago, # |   -13 No mistakes in jury's solutions, please
 » 4 years ago, # | ← Rev. 2 →   +34 For the First time, i am Not Excited for Hat-trick .
 » 4 years ago, # |   0 after the round :D
•  » » 4 years ago, # ^ |   0 Mike Cameron
 » 4 years ago, # | ← Rev. 2 →   0 Hope that this contest will be bugfree and rated even after contest unlike last twos.
 » 4 years ago, # |   +12 My plan for evening: Mexico — Portugal Contest Germany — Chile
 » 4 years ago, # |   -14 Hope there will be no problem with any of the problems. :-)
 » 4 years ago, # | ← Rev. 3 →   -9 GL & HF ?
 » 4 years ago, # |   -13 Hopefully history won't repeat itself...throwback to unrated #420 and #421 :(
 » 4 years ago, # |   +78 Hmmm.. This doesn't look legit :DFrom today's contest registration:
•  » » 4 years ago, # ^ |   +26 Attack on acloser season 1++
•  » » 4 years ago, # ^ |   +12 Ban everyone!
•  » » 4 years ago, # ^ |   0 Is it possible to make User-Id using loop?
•  » » » 4 years ago, # ^ |   +5 If not then that guy had all the time in the world to create these lmao
•  » » » 4 years ago, # ^ |   +4 Codeforces has CSRF and XSS protection which supposedly should prevent anyone from running a script to send data to the server from the outside, so that lad must've had gone through lots of trouble to make those accounts XD Or he's really smart and he could turn around the system and find some sort of a vulnerability that let him do that. Either way it took him some serious effort :3
•  » » » » 4 years ago, # ^ |   0 What about selenium?
•  » » » » » 4 years ago, # ^ |   0 What about captcha?
•  » » » » » » 4 years ago, # ^ |   0 don't think codeforces has captcha to make account.
•  » » » » » » » 4 years ago, # ^ |   0 there is a captcha you have to solve immediately after confirming your email.
•  » » 4 years ago, # ^ |   0 What's the gain on creating multiple dummy accounts ? Altering the quantity of people that have submitted something wrong, and in that way boosting your rating income?
•  » » 4 years ago, # ^ |   0 76 likes, it seems all the acloser liked this.
•  » » » 4 years ago, # ^ |   0 They are more than 76, you never know.
 » 4 years ago, # |   0 Hopefully no more server slow problems.
 » 4 years ago, # |   +33 Many thanks to coordinator Alex netman Has KAN resigned?
•  » » 4 years ago, # ^ |   +42 No :)
 » 4 years ago, # |   +22 Exciting score distribution :D
 » 4 years ago, # |   +11 My first contest in a long time.. good luck to everyone!
 » 4 years ago, # |   0 I have faith in pedrodelyra... he is a monster
 » 4 years ago, # |   -8 wow great,after a long time six problems. Hopefully all problem statement will be shortly. Thanks.
 » 4 years ago, # |   0 Problem A: I shed a tear :'(no emoji)
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Me too.
•  » » » 4 years ago, # ^ |   -6 At most one of the numbers a,b is greater than 12.
 » 4 years ago, # |   0 I am not able to see the source code for hacking.
•  » » 4 years ago, # ^ |   -21 You should use glasses Maybe You can see !! :D
 » 4 years ago, # |   -23 WA #3 preliminary test set C. C seems so easy!
•  » » 4 years ago, # ^ |   -22 So there is a blue rating contestant with four wrong answer verdict submissions in my room and three green rating with five WA's. Seems that the problem is very dangerous. I will wait for the explanation very hard.
•  » » 4 years ago, # ^ |   0 It's not the whole test
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Test case3 21 1 102 2 1003 3 1000Answer — 110
•  » » » 4 years ago, # ^ |   0 On my local machine output is 110.
•  » » » 4 years ago, # ^ |   0
 » 4 years ago, # |   0 Is there something wrong with hacks of A?
•  » » 4 years ago, # ^ |   0 Just lost 50 points due to this.
 » 4 years ago, # |   +8 Pretest 2 D is killing everybody
•  » » 4 years ago, # ^ |   0 dp f(i)%=MOD before calculating f(i)*t^(i-l)
 » 4 years ago, # | ← Rev. 2 →   0 How to solve C? I had a O(n*log(n)*log(n)) approach using segment tree and binary search, but I thought it wouldn't pass. Is there a better approach?
•  » » 4 years ago, # ^ |   +13 I used adjacency list + BS.
•  » » » 4 years ago, # ^ |   0 Can adjacency list be used to answer rmq?
•  » » » » 4 years ago, # ^ |   +6 actually in my approach suffix minimum was sufficient.
•  » » » 4 years ago, # ^ |   0 me too!
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 EDIT: failed systests. two pointers
•  » » 4 years ago, # ^ |   +3 You can sort by difference between l and r (sort by cost in case of equality) and then use two pointers to iterate your array .(runs in O(nlog(n)) )
•  » » » 4 years ago, # ^ |   0 could you elaborate on your approach . I tried this way only . the sorting logic also exactly same but i got WA on pretests.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 EDIT: This failed systests. this might help http://ideone.com/BU1KjQ
•  » » » » 4 years ago, # ^ |   0 well, after sorting , you start with i=0 and j=n-1, and while(idiff(j)) you decrement j and if (diff(i)>diff(j) you increment i. here's my code: https://ideone.com/avXw3e
•  » » 4 years ago, # ^ |   0 Use a segment tree with min query and you can do it in O(n*log(n)). You don't need the binary search.
•  » » » 4 years ago, # ^ |   0 I was using Binary search to find the elements which do not overlap, and segtree to find the minimum in them, I don't know how do I avoid Binary search here?
•  » » » » 4 years ago, # ^ |   0 Use a segment tree with MAX_SIZE positions and put the item on its L. You'll get the ranges (0, current L — other size) and (current R + current size, MAX_SIZE — 1).
•  » » 4 years ago, # ^ |   0 I used array of priority queues
 » 4 years ago, # |   0 What is the hack for div2B?
•  » » 4 years ago, # ^ |   +4 many people code like thisthey don't limit i+n-1<=m for (int i = 1;i <= m;i++) for (int j = 1;j <= n;j++) { } so hack is 4 4 abcd eeab 
•  » » » 4 years ago, # ^ |   +1 I wish someone had hacked me :(
 » 4 years ago, # |   +6 How to solve E ??
 » 4 years ago, # |   +1 How to solve D? O(nlogn) would be TLE :(
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Apparently not. I used a prime sieve and submitted at 1:59 and got pretest passed. (if only I had gotten it earlier though...)
•  » » » 4 years ago, # ^ |   0 WT!!? I thought it will get TLE and didn't submit :((
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 http://codeforces.com/contest/822/submission/28233115actually, I think it's O(N), not n log n, my bad. (because the number of primes less than any N approaches 1/N for large N)Since the prime sieve only has to go from 0 to 3000 (about root 5000000), it doesn't take a long time
•  » » » » » 4 years ago, # ^ |   0 Now that I think about it, I have no clue how to calculate the complexity of my code.
•  » » » » 4 years ago, # ^ |   +5 A prime sieve is O(nloglogn).
•  » » » » 4 years ago, # ^ |   0 also, even if it was N log N instead of N, it would probably still pass because it only works out to ~120m operations
•  » » 4 years ago, # ^ |   +3 Mine passed in 1240 ms. Hope it passes system tests too.
•  » » » 4 years ago, # ^ |   0 Mine too, but it didn't pass systests :(
•  » » 4 years ago, # ^ |   0 Mine passed in ~700 ms.. So guess it will run..
•  » » 4 years ago, # ^ |   +8 F[n] = F[n / x] + (x — 1) * n / 2; Where x is smallest prime factor of n.
•  » » » 4 years ago, # ^ |   0 Why is the smallest prime factor optimal ?
•  » » » » 4 years ago, # ^ |   +1 Idk, maybe because of comparisons sorts you try to split it into less parts and try to get to nlogn rather than n^2.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Let's prove that if you can get p or q such that p * q is a divisor of n you want to get the smallest one. If you get the cost of the p and q operations you'll get://pairs(p * q) * n / (p * q) = n * (p — 1) * (q — 1) / 2 this is making p * q//pairs(p) * n / p + pairs(q) * n / (p * q) = n * ((p — 1) + (q — 1) / p) / 2 this is making p and later making qAfter one of those you'll use the best of n / (p * q) so you can ignore it. It is easy to see that (p — 1) * (q — 1) >= (p — 1) + (q — 1) / q always so from this you see that you'll always take prime factors. Now, if p <= q, (p — 1) + (q — 1) / p <= (q — 1) + (p — 1) / q because q — p >= (q — 1) — (p — 1) >= (q — 1) / p — (p — 1) / q so you want to get the lowest.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +4 What?I got f(a) = (f(a/sf) + a/sf * f(sf))where sf is the smallest prime factor of a.You accomplish this by breaking it into a/sf groups of size sf.EDIT: Never mind, these both end up giving the same expression.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 I got pretests passed for O(nlogn) in 545 ms, hope it passes system tests too...EDIT: Passed system tests. Phew.EDIT EDIT: Never mind, looks like my solution wasn't O(nlogn)
 » 4 years ago, # |   0 When u get problem C and then rejoice but then with 15 mins left get hacked and get sent plummeting down :'(
 » 4 years ago, # |   0 Hack for C:2 4 1 2 1 2 3 2For A, one person in my room explicitly tried to compute the factorials of both A and B. I was unable to hack him for (N, M) = (12, 10^9), because overflow probably led M! to be equal to 0 at the end, but I got him with (N, M) = (11, 30)
•  » » 4 years ago, # ^ |   +1 Answer should be -1 right?
•  » » » 4 years ago, # ^ |   0 Yes.
•  » » » » 4 years ago, # ^ |   0 http://codeforces.com/contest/822/submission/28230967What is wrong with this? Gave WA on Pretest 3.
•  » » 4 years ago, # ^ |   +12 Also, I hacked 1 brute force solution, and one solution with inf = 1e9(max answer can be 2e9).
•  » » » 4 years ago, # ^ |   0 Oh I think we should use inf like 0x3f3f3f3f......thruongh this figure,or up to the problem itself.
 » 4 years ago, # |   +4 Start system tests quickly this time please!
 » 4 years ago, # |   +1 May somebody please explain how to solve Problem C without getting "time limit exceeded?" Thanks in advance!
 » 4 years ago, # |   0 Since the round is done, would anyone mind sharing how they solved C? :(
•  » » 4 years ago, # ^ |   +1 Loop through all the sorted start and end points and if it's an end point, add the length and cost to your set, and if it's a start point then check all the end points before the current coordinate (in the set) to match the 2 lengths together.
•  » » » 4 years ago, # ^ |   0 Can u check my solution using Binary Search link: http://ideone.com/hC25Oz
•  » » 4 years ago, # ^ |   +1 For every length store costs and left border in vector. Then sort these vectors by left side and cost. And for every element do binary search. 28224027
•  » » » 4 years ago, # ^ |   0 Damn! I never thought to use binary search! That's pretty neat
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 EDIT: This failed systests. sort by duration of voucher and use two pointers method. works in O(nlogn) due to sorting. it passed pretests, hope it will pass systests as well. http://ideone.com/BU1KjQ
•  » » 4 years ago, # ^ |   +6 Create arrays for vacations of each length. Write all vacations into corresponding arrays (l, r, cost) Sort each array by vacation start date. For each array create a corresponding array of the same size and write minimal vacation cost for all vacations which start from x or later. Now iterate from 1 to x (length of your first vacation). Length of corresponding vacation would be x-i. On each step you have to find minimal price of second vacation (of length x-i). Because you sorted your array you can find it using binary search (also note that we use calculated suffix minimums here). On the end of each step update your answer.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 O(n) solution for C: 28224212 It passed pretest. But it didn't passed System test :(
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 What is your approach?EDIT: I don't think it could be solved in O(n) you gotta atleast sort man.EDIT2: Ok I guess it could be done in O(n)
•  » » » » 4 years ago, # ^ |   0 You can sort in O(n) btw.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Yes, but with a very large Constant. I mean ok my bad.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Here is mine O(MAX) solution.
•  » » » » » 4 years ago, # ^ |   0 Can you explain it a bit?
 » 4 years ago, # |   0 Problem D: Was there anyone getting wrong answer in pretest 2 ?? I don't know what's wrong with my code :(
•  » » 4 years ago, # ^ |   0 You should check for 32-bit integer overflow
•  » » » 4 years ago, # ^ |   0 Yes I am using long long int
•  » » 4 years ago, # ^ |   0 Have you done the operations MOD 1e9 + 7 ?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Yep, I am also doing the modulo operation. I think I have figured out the problem. Actually , I was miscalculating he f(n) for odd numbers. I was using f(n) = (n*(n-1))/2 for odd numbers. But it seems the correct value is f(n) = f(n/x) + ((n/x) * ((x*(x -1))/2) , where x is the smallest prime factor of n.
•  » » » » 4 years ago, # ^ |   0 It is the same for even numbers
•  » » » » 4 years ago, # ^ |   0 For prime numbers in range, is the only possibility (n*(n-1))/2 ?? (where n is prime number)
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 let z = small[n], is the smallest prime factor of n, let h = n/z, then ans will be SpoilerF(n) = ((h*(z*(z-1)/2)%mod)%mod + F(h))%mod
•  » » 4 years ago, # ^ |   0 Mod the value of dp[i] or F(i).
•  » » 4 years ago, # ^ |   0 I also fell down on the second test. Then I noticed that I forgot my answer by modulo after each addition.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 If you are updating f[i] from f[i / p] (where p is the smallest prime divisior of i) and i >= l and i / p < l , f[i] would update incorrectly.
 » 4 years ago, # |   0 Can anyone explain the solutions of E and F?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Hi, I had an idea with hashings, with some greedy steps for problem E. The general idea is to keep the matched segments in some stack and remove those segments when a better one appears. Below the steps:*Let's say "size" is equal to the sum of length of your segments in every step. *For every character "i" in string "t", and with current position pos = 0 in "s" do this:(1)Look for the ith character of "t" in s[pos... n], take the first ocurrence, let's call this position "k" in s.(2)Check if the largest common suffix of s[1,2,...k] and t[1, 2, ...size + 1] can replaced some stored segments on your stack. (3)Remove segments of the stack that can be replaced by the largest suffix.(4)Updated pos, size, Repeat until pos = nFinnaly if you got the whole string "t" in "s", you will need one aditional check if some substring at the right position of "pos" can be a better suffix for t.
 » 4 years ago, # |   +2 Is suffix array required in E?
•  » » 4 years ago, # ^ |   0 suffix array is not necessary
 » 4 years ago, # |   +15 2 minute silence for all those(including me) who initialize maximum answer to 1e9 in C
 » 4 years ago, # |   0 Idea behind D ?
•  » » 4 years ago, # ^ |   +3 It can be proved (I simply bruteforced), that at it stage it was optimal to take the smallest group possible.Given this, you simply computed the answer with help of memoization and a prime sieve to prevent TLE.
•  » » » 4 years ago, # ^ |   0 Yeah. That is what I want to know. How to prove this ?
•  » » » » 4 years ago, # ^ |   0 I computed 50000 values and it worked. You can easily proof that taking 2 prime numbers is better than taking their product, and then generalize. I haven't written any strict proof but someone might help.
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 Okay, maybe because we want to keep numerator small, we will greedily choose smallest prime
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +1 I haven't written any strict proof but someone might help. That's exacty what I said
•  » » » » » 4 years ago, # ^ |   0 You have to notice that one prime will never be in divisor. So which prime should this be?
•  » » » » 4 years ago, # ^ |   0 Lets compare it with comparisons sort :D When you do smaller groups you achieve O(nlogn) rather than O(n^2) :D
•  » » » » » 4 years ago, # ^ |   +9 This is intuition, not proof
•  » » » » 4 years ago, # ^ |   0 Lets say what n=p1p2...p_n. We need to show what we choose p_i in order of i.
•  » » 4 years ago, # ^ |   +5 I did like this. For any n, the optimal choice is always a prime factor. To prove this, it's enough to prove that its better to choose X for N and then Y for N/X rather than choosing X*Y for N.F(N) = X*(X-1)/2 * N/X + Y*(Y-1)/2 * (N/X)/Y + F(N/XY) in the first way.F'(N) = XY*(XY-1)/2 * N/XY + F(N/XY) in the second way.Its simple to prove F'(N) > F(N) for any X,Y > 1 (Just rearrange the terms, do some math).
•  » » » 4 years ago, # ^ |   0 But it's not necessary that X and Y will be chosen one after the other. Yes, all of this is very intuitive, but nothing solid.
 » 4 years ago, # |   +56 #include using namespace std; int main() { bool uDoWell, isRated; cin >> uDoWell; if (uDoWell) { isRated = false; } else { isRated = true; } cout << isRated << endl; } 
 » 4 years ago, # |   +6 just in case Rank predictor
•  » » 4 years ago, # ^ |   +14
 » 4 years ago, # |   +3 Can anyone help me with my code on C...I was getting WA on pretest 5. But I used exactly same logic as people have discussed here. Thank you..
 » 4 years ago, # |   +32
 » 4 years ago, # |   0 So, in D, is the optimal f(n) simple greedily doing N/2 * [ p1-1 + p2-1 / p1 + p3-1/p1*p2 + ..... + pk-1/(n/pk-1) ] ? I can't formally prove why it will be lowest, although seems like it can be.
•  » » 4 years ago, # ^ |   0 F[n] = F[n / x] + (x — 1) * n / 2 Where x is smallest prime factor of n. Lets say n is composite: n=p*q. When F[n] = min(F[n / pq] + (pq — 1) * n / 2,F[n / p] + (p — 1) * n / 2, F[n] = F[n / q] + (q — 1) * n / 2) When F[n/p] = F[n / pq] + (q — 1) * n / 2 When F[n/q] = F[n / pq] + (p — 1) * n / 2 From this you somehow prove that you need to choose first smaller of p, q.
•  » » » 4 years ago, # ^ |   0 -_-
•  » » » 4 years ago, # ^ |   0 Actually, number of primes is small enough to take the sum. NlogN. Then you do the multiplication with t^k, 10^6logN.
 » 4 years ago, # |   +4 What a Thrilling Contest!
 » 4 years ago, # |   0 Anyone with O(n) solution for C?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 Mine, if we replace sort with counting sort: 28224166
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I belive mine is: 28236057 Edit: although technically it's O (200000+n) I guess
•  » » » 4 years ago, # ^ |   0 200000+n is still O(n)
 » 4 years ago, # |   -11 i commented and asked why are we not getting ratings and contests added up in our graph ?? and my contributions went to -1
•  » » 4 years ago, # ^ |   +4 I'm not sure, but if your comment rating is in [-5; 0], cf will show this rating as 0, but will count real rating when calculates contribution
 » 4 years ago, # |   0 I submitted an nlogn solution for D(I know it can be improved), but currently it doesn't appear on the standings and on the status page, my submission got TLE on test1(wtf). Is there someone else facing a similar problem?
•  » » 4 years ago, # ^ |   0 Your solution's complexity doesn't depend on l, r. If your solution runs like 1400-1500 ms it can get tle when rejudged I think.
•  » » » 4 years ago, # ^ |   0 I think almost in the same way, but it is unfair if you receive tle on test 1, because it shouldn't pass pretest(it would give the possibility to modify my solution, instead of switching to other problem). As you said, my solution doesn't depend on l, r. So, if it pass pretests, it must pass systest, because the computations are almost the same.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 It's only a prediction. But if you choose to write solution that runs on edge, I think you are relying on your luck.
•  » » » » » 4 years ago, # ^ |   +5 Why do they run our code on pretests again?
 » 4 years ago, # |   +3 what is the time needed to calculate the rate?
 » 4 years ago, # |   0 keeping small numbers as an input in pretests would have given a chance of successful hacking attempt on Question A
 » 4 years ago, # |   +7 No plagiarism detection between DIV 1 participants and DIV 2 participants??.Saw a few same codes.
 » 4 years ago, # | ← Rev. 2 →   +1 Although got WA in C due to initializing of maximum answer to 1e9 and D due to some silly mistake but still best contest in last 1 month ,waiting for more rounds by author
 » 4 years ago, # |   +18 Actually, anyone mind sharing what E's test 24 or its general idea is? A lot people get WA'd but the case is too long to be read or copied.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +19 I think this. Note that dp[pref1][ans][flag] doesn't work
•  » » » 4 years ago, # ^ |   0 That's pretty unexpected. I originally thought about some edge cases, but did not ponder too much on the algorithm. Thanks a lot!
 » 4 years ago, # |   0 can anyone pls share solution of D?? (I was getting wrong ans on pretest 2 inspite of using the prime numbers concept to form groups)
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Didn't see where you're using t. You count not t^0 * f(l) + ..., but 2^0 * f(l) + ...
•  » » » 4 years ago, # ^ |   0 thanks for pointing that out i will try and resubmit in practice section..
•  » » 4 years ago, # ^ |   0 Check your code if there is overflow because of int. At first , I got WA on the pretest 2 too. But after changing "int" into "long long int" , I got AC.
•  » » 4 years ago, # ^ |   0 Actually, you can see the test cases here for yourself.
•  » » 4 years ago, # ^ |   +1 http://codeforces.com/contest/822/submission/28234001 My solution for D, developed minutes after finish of contest (spent whole time trying to solve C). Idea is: to calculate, for example, f[40], maybe optimal is to have 5 groups of 8 people, so using just prime numbers does not work. Firstly, lets set f[x] = x*(x-1). Thats always a solution. Then, lets iterate from i = 2 to i = r/2 + 1. Inside that loop, iterate from j = 1 to j = i. Update f[i*j] : f[i * j ] can be solved in two ways: 1. way either you have i groups and j people in every group, then f[i*j] = i* f[j] + f[i]( if you cant understand: i times you solve groups of j people, and then you will have i "winners", so you solve one group of i people). Since i and j are smaller than i*j, i and j will be computed by this time. 2. way similar, just opposite, j groups of i people. So f[ i * j ] = max ( i*f[j] + f[i], j*f[i] + f[j], f[i*j] ) Third way if f[i*j] is already better than going with i or j. So you just calculate all values, and then sum from l to r, and must be careful about modulo.
 » 4 years ago, # |   0 So.. Does D could be solved in C#? It seems I've used asimptotical optimal solution, but it still gets TL.http://codeforces.com/contest/822/submission/28234265
•  » » 4 years ago, # ^ |   0 O(r * min(pr)) not optimal really. O(r) or O(rloglogr) are optimal.
•  » » » 4 years ago, # ^ |   0 You are right. I should use Eratosfen Sieve, I'm stupid. But I see — on C++ approach that I've used works 1.2 — 1.4 sec, so on C++ the solution of this task is little more obvious.
 » 4 years ago, # |   +10 I can share my divide and conquer approach for E if someone'd like me to :)
•  » » 4 years ago, # ^ |   +5 Please do :)
•  » » » 4 years ago, # ^ |   +29 ok :DLet's calculate dp[m][x]: the minimum possible position in S such that it's possible to obtain [0..m] of T using no more than x cuts. If there's no such position, it's equal to -1.How would we calculate this in a straightforward way? Let's try to brute this optimal position. For a fixed i in S we wanna know the maximum possible length K such that S[i — K + 1..i] == T[m — K + 1..m]. If we can add it without intersections (i.e distance between dp[m — K][x — 1] and j is greater or equal than K), it means we found the answer. This gives us an O(xnmlogn) solution provided we use hashing :)Let's try to speed it up. It can be easily seen that for a fixed x the dp values are monotonic (till they reach -1). Moreover, if for some i dp[i][x] is equal to -1, that means that for all j >= i dp[j][x] will be -1 aswell.From these points we obtain the following idea: if there are some given segment bounds (l/r for the dp positions and L/R for the dp values), we take the median m = (l + r) / 2 and check all possible i's in range L..R. If we find the optimum, we call (l, m — 1, L, opt) and (m + 1, r, opt, R). If no, it's no use checking the right part of the segment, so we proceed with (l, m — 1, L, R). This gives us log(n) levels or recursion and no more than m operations per level. Since every check is performed in O(logn) time (binary search + hashing) and there are x calls or divide & conquer, this gives us the total complexity of O(x * m * log(n) * log(n)).http://codeforces.com/contest/822/submission/28235167
•  » » » » 4 years ago, # ^ |   0 Last part of solution is one of the DP optimizations from next link, right? http://codeforces.com/blog/entry/8219 More precisely, It is divide and conquer optimization? Also, can u explain more briefly how do we use hashing here?
•  » » » » » 4 years ago, # ^ |   0 It's similar, right, and uses the same idea, but applied in a bit simpler case since I know that my dp is monotonic and bounded by [0..m — 1] at the same time. This allows me to turn O(mn) into O(mlogn) as described above.How do we use hashing? Denote lcs(i, j) as largest common suffix of prefixes [0..i] of T and [0..j] of S and use binary search :)
•  » » » » » » 4 years ago, # ^ |   +5 You can actually shave off a factor of log(n), by simply using the observation you mentioned — on the monotonicity of the dp values for a fixed x. We can simply run 2 pointers — one for S from 1..n and the other for T from 1...m. The xth row in the dp table will be computed in (n+m)*(time for computing the latest common suffix) which is log(n) using hashing.
•  » » 4 years ago, # ^ |   0 Yes please!
•  » » » 4 years ago, # ^ |   0 Check the comment above :)
 » 4 years ago, # |   0 Is there anyone with TLE in C. My complexity was O(nlogn).
•  » » 4 years ago, # ^ |   0 yes same here, but i think some corner cases were not being handled by that approach
 » 4 years ago, # |   +3 I solved D without prime factors or anything like that. Just bottom up DP :/ Anyway, anyone thinks that D is far easier than C? I tried to solve C for ages, and I couldnt, but I solved D in pretty short amount of time.
•  » » 4 years ago, # ^ |   0 +1 , took me quite some WAs (and a few < instead of >=) and time to get C right, D was in one go, if only I saw D first :(
•  » » 4 years ago, # ^ |   0 You approach isn't 100% correct. You use dp[j] that sometimes won't have the best answer at the moment you use it so if the relation was diffent your solution would be WA. It's correct for this problem because of the fact that you need to use the minimal prime factor so you'll end up getting the correct answer.
•  » » » 4 years ago, # ^ |   0 No. You always calculate in right order. When you want to calculate f [i*j] you will always have f[i] and f[j] because its bottom up approach. Its nothing to do with smallest prime.
•  » » » » 4 years ago, # ^ |   0 Nah... there's more than 1 way of writing i * j. You'll for example get 120 using 1 * 120, 2 * 60, 3 * 40 etc but when i = 3 and j = 40 did you consider the case when i = 10 and j = 4 (that results in 40 and is the j on 3 * 40)?
•  » » » » » 4 years ago, # ^ |   0 tfg No. You dont understand my solution, now please try to understand it. My first loop goes from i= 2 to i = r/2 + 1. Loop inside it goes from j = 1 to j = i ! So NEVER it can be that j > i . Because of that, when I come with first loop on some number, it is surely calculated. j is never bigger than i, so I will not have problems like you mentioned.Im 100% that this is OK.
 » 4 years ago, # |   0 Can somebody explain me E solution without hashes?
 » 4 years ago, # | ← Rev. 7 →   0 Is it possible to get a particular testcase? I need case 46 of C. WA. http://codeforces.com/contest/822/submission/28232052. Otherwise, if someone helped figuring out why, it would do too!
•  » » 4 years ago, # ^ |   0 Got my bug :) But... is it possible to see a whole particular testcase, say, as a .txt file?
•  » » » 4 years ago, # ^ |   0 Hey, what was the idea of fixing the bug? I'm also using binary search and getting WA at 46:)
•  » » » » 4 years ago, # ^ |   +1 Actually I messed up checking upper bound. Check line no 57 there and here. See a difference?
•  » » » » » 4 years ago, # ^ |   0 I see, thanks
 » 4 years ago, # |   0 Any help plz ? C solution
 » 4 years ago, # |   0 Does anyone else think that the time limit for D was too strict.My solution TLEd on pretest 1 in spite the logic was perfect. :(
•  » » 4 years ago, # ^ |   +5 Actually, I think it was opposite. I got AC without even proving that it is best to choose smallest prime. I just had DP[x] and bottom up approach, didnt even care about prime factors. It could be more strict so only if you prove optimal strategy you get AC. Still, I think that would be too hard for D tbh.
•  » » 4 years ago, # ^ |   0 You did O(n^2)... You should do about O(n) or O(nloglogn)
•  » » » 4 years ago, # ^ |   0 How is my solution O(n*n) bro?2 nested loops don't always mean its O(n*n)
•  » » » » 4 years ago, # ^ |   +3 Your solution about O(nlogn): for each i = [1..N — 4] you do (N — 4) / i iterations.As it's said above, you need O(n) solution or O(nloglogn).
•  » » » » » 4 years ago, # ^ |   0 Yeah my solution is O(nlogn).But even that passes.If I take minimum then everytime its TLE,else its AC. See these two solutions,u can see that just 1 line is commented and that line is making difference.TLE solution: (http://codeforces.com/contest/822/submission/28235754)AC solution: (http://codeforces.com/contest/822/submission/28235976)
•  » » » » » » 4 years ago, # ^ |   +3 I always think that if my solution goes for little quicker then TLE, that there is not perfect logic:DThough if solution passes, who cares? But this solution wouldn't pass in Python or C#. Maybe there must be 1s TLE?
•  » » 4 years ago, # ^ |   0 I think the TL is loose. Some solutions with O(N3 / 2) passed (which is precisely your solution).
•  » » » 4 years ago, # ^ |   0 My solution is O(n log n) just like balalaika said.Its like let x=N-4, x/1+x/2+x/3+.... which is O(x log x).
 » 4 years ago, # |   0 I keep Getting WA on test 58 on problem C, and i couldn't understand what i did wrong, can anyone please check this submission for me :( 28235829
 » 4 years ago, # | ← Rev. 2 →   0 I used two pointers in C. I had created a pair in map mp[{l,r}]=cst which stores the minimum value of cost from l to r. I had created an array of sets where i inserted l,r as a pair in the r-l+1 th set. After that i used two pointers in the following way : I ran a loop from i=1 to x and i had a pointer pointing to the ith and x-i th set itr and itl respectively. I will check whether the L value of itl is less than or euqal to the R value of itr ,then i will increase itl,else i would compute the answer and increment itr by 1. This is my logic with a few corner cases handled . I trie to run the code on every possible small input in the test file but it passed all of them. Please have a look at it, and let me know my mistake. I am unable to find the mistake in my code. Here is the link to my code. Thank you !
 » 4 years ago, # |   0 unlucky contest ....
•  » » 4 years ago, # ^ |   0 Oh my god , you must be so angry. You have 1899 rating. So close to div1. Man so sorry for you. I am 5 points away from specialist but you are 1 point away from div1.
•  » » » 4 years ago, # ^ |   0 I had 1898 at some point and now 1899 .... Maybe I'm cursed...
•  » » » » 4 years ago, # ^ |   0 Yeah :D, but it's time for sure you become a div1, you have lots of experience, also during virtual contests you are performing really well.
 » 4 years ago, # |   0 In problem D, I get wrong output for case 2 in codeforces but right output in home pc and ideone, can anyone point out my mistake . code ideone
•  » » 4 years ago, # ^ |   +1 I had same problem few times on Codeforces. Trick is, on codeforces, default value for int isnt 0. Maybe on home pc your default value is 0, like on mine. So your array prime[x] is maybe problem. Just set everything to 0 on start. That will fix it, I am 99% sure! (also for other arrays that you have)
•  » » » 4 years ago, # ^ |   0 fixed wasn't the default value problem , changed type of i from int to long long in solve().
 » 4 years ago, # |   0 Liked the contest very much, but i don't like when a contest becomes a fast typing one. I knew how t osolve B insantly but i didn't write it fast enoguh and that's why i lost some points. Also why where the pretests for A so easy and for C. I understand that you're giving other contestants posibility to hack but that's not cool. There where people who solved 3 problems and others who solved 2 problems and they where on the same rank just because of hacking. Not cool. But contest was nice in general.
 » 4 years ago, # |   0 I am really not able to find bug in my code :'(. Can someone please help me! Submission link
•  » » 4 years ago, # ^ |   +9 I don't know if this is the only problem, but you shouldn't divide an expression by 2 after taking its modulo. Do the division before taking modulo in line 13.
•  » » » 4 years ago, # ^ |   0 Thanx! I m really tired of doing such mistakes! I think i am going to stay in Div 2 my whole life!Well, thank you very much!
 » 4 years ago, # | ← Rev. 2 →   +14 That moment when you did well last two rounds but fail to do well this time:Is this gonna be unrated as well? xD
 » 4 years ago, # |   0 Why am i getting runtime error but i am not getting it in my compiler. Thanks in advance. http://codeforces.com/contest/822/submission/28236678
 » 4 years ago, # | ← Rev. 2 →   0 regarding this submission:http://codeforces.com/contest/822/submission/28235877as you see it gives me time limit, isn't this rlogr ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 the nested loops work in a manner like this: r + r/2 + r/3 + r/4 + ..... + r/r, take r common factor, this gives : r(1 + 1/2 + 1/3 + 1/4 + ..... + 1/r), for very large r this summation is just approximately 2.7, so complexity will be approximately 2.7r, do you know why it gives time limit ?EDIT: the summation is near to log not 2.7
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 (1 + 1 / 2 + 1 / 3 ... + 1 / n) is harmonic series. Its sum isn't equal to e. It grows like log n. So, as we have 5*10^6, r log r solution may not pass.
•  » » » » 4 years ago, # ^ |   0 yes sorry it is not equal to e i mixed it with another thing, but still at 5 million this series sums up to just 16, why 80 million would not pass ?
•  » » » 4 years ago, # ^ |   0 It is actually . You solution should pass after removing some unnecessary things, as the Time Limit is tight.
•  » » » » 4 years ago, # ^ |   0 yes i accidentally mixed it with the summation of 1/factorial(i) as i tends to infinity
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Just removing some unnecessary mod (it is too costly) and using long long only where it is needed gave AC :P Bad Luck :(Changed Code — 28237999Diff: Diffchecker
•  » » » 4 years ago, # ^ |   0 yes but with 1497 ms which is too dangerous :D
 » 4 years ago, # |   +29 Div2 C test 59 is a stdlib qsort() killer!Learned my lesson today: shuffle before using quicksortMy solution without shuffle: 28226684 (TLE 59) My solution with shuffle: 28235814 (Accepted)Not only me, other C (without plus-plus) user (rainboy) is also affected:rainboy's solution without suffle: 28219544 (TLE59) rainboy's solution with suffle: 28233646 (Accepted)Then I search for source code for qsort() gnu implementation and found this: https://code.woboq.org/userspace/glibc/stdlib/qsort.c.htmlIt choose the pivot element using a median-of-three decision tree. After I read this: https://stackoverflow.com/questions/7559608/median-of-three-values-strategy the median of tree is pivot selection strategy to prevent worst case performance on easy to make case like "almost sorted data".So I think it's not easy to make this qsort work in O(n2), but this test 59 prove that it's something common (although this is first time I encounter this problem after ~3.5 years experience in competitive programming).How to make testcase that make this stdlib qsort() run in worst case O(n2)?I trusted this function for years and now... he betrayed me :p
•  » » 4 years ago, # ^ | ← Rev. 2 →   +17 Why use qsort instead of sort? is there any advantage?EDIT: oops, my mistake, misread.
•  » » » 4 years ago, # ^ |   0 sort has a better worst case time complexity. sort has a worst case runtime of O(nlgn) whereas qsort has a worst case runtime of O(n^2).
•  » » » 4 years ago, # ^ |   +8 Because there is no sort() function in C, only qsort().
 » 4 years ago, # | ← Rev. 3 →   0 I get "Wrong answer on test 2" (E: on problem D) when I submit and it evaluates wrong answer, but when I do custom invocation it evaluates to the correct answer. What is the difference between "custom invocation" and normal submission? E: The submission: 28237592
•  » » 4 years ago, # ^ |   0 Don't mind me — there is a mistake in my code and I checked the wrong numbers...
 » 4 years ago, # | ← Rev. 2 →   0 My code(28230274) for DIV2 — D gave TLE when submitted in GNU C++ 14. Exact same code(28238828 ), when submitted with GNU C++ got accepted. Why is this happening( due to compilation overhead maybe) and isn't this unfair ? Should I start submitting in GNU C++ from now on ?
•  » » 4 years ago, # ^ |   +7 Accepted code has max execution time 1497 ms with TL=1500ms. It was lucky to pass.You shouldn't start submitting in GNU C++, just write faster solution and don't forget that compilation time isn't counted as execution time of your solution.
•  » » » 4 years ago, # ^ |   0 Thanks for pointing out :) And I just realized that the same solution passes in 1497 ms in GNU C++ 14 when I wrote the code directly main() instead of making a function solve() and calling it from main() Code : 28239178
•  » » » 4 years ago, # ^ |   0 can you please share your approach to solve E...
 » 4 years ago, # |   0 Is it possible to do problem D in python? My solution in python is close to the editorial one( but failed) and I implemented one of the AC solution in C++ by others and rewrite it in python but still can't get pass testcase 8. Anyone help? Thanks a lot!
•  » » 4 years ago, # ^ | ← Rev. 4 →   +1 I think you can try to use a better algorithm to solve the problem. If your C++ program runs more than 1000ms,your solution in Python is hard to get accepted, and I think my idea of problem D is better than the editorial
•  » » » 4 years ago, # ^ |   0 Thank you for your advice. I will take a look of your solution and see what happen if I implement it in python.
 » 4 years ago, # |   0 Can anyone check my solution to C using Binary Search link: http://ideone.com/hC25Oz
 » 4 years ago, # |   0 Can Someone explain me the solution of problem C ? Thank You.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +2 I have used 4 vectors in my solution. vector > > deal : This stores all the packages. vector > pack[k] : An array of vector in which pack[i] will store the {starting day,cost} of a package which extends over 'i' days. During input itself I ignored all packages which had a length of 'k' days or more since I could not use them with some other package (would have exceeded the constraint of EXACT k days). So, in vector 'deal' I pushed the {cost,{start,end}} and in the vector pack[end-start+1] I pushed the {start,cost}. Once the input part was done, I sorted the pack vectors one by one from (0,k). Now i created 2 more vectors : vector pack_day[k] vector pack_cost[k] I created these 2 new vectors because if not, then I had to write a binary search function separately. So I basically kept the pack[i].first portions in pack_day[i] and pack[i].second.portion in pack_cost[i] so that I could use the lower_bound function. Let me illustrate this with an example.Suppose I had 3 packages: (k=4)1 3 52 3 46 7 2Then deal would store this : { {5,{1,3}} , {4,{2,3}} , {2,{6,7}} }Then pack would store this :pack[0] : {}pack[1] : {}pack[2] : { {2,4} , {6,2} }pack[3] : { {1,5} }Then pack_day would store this :pack_day[0] = {}pack_day[1] = {}pack_day[2] = { 2 , 6 }pack_day[3] = { 1 }Then pack_cost would store this :pack_cost[0] = {}pack_cost[1] = {}pack_cost[2] = { 4 , 2 }pack_cost[3] = { 5 }So now, if I am provided a package starting from L, ending at R and costing W, then I will have to search for another package of length LEFT = K — (R-L+1) days. So will have to search the pack_day[LEFT] vector and find the position from where the packages start further from (R+1). So if for example,L=3R=6W=5K=10DAYS IN CURRENT PACKAGE = 6-3+1 = 4DAYS REQUIRED IN OTHER PACKAGE = 10-4 = 6So search in pack_day[6] for the position from where packages start from (R+1=7) 7 so that disjointness is satisfied. Once you have got this position, all you require is the minimum cost from THAT POSITION to the end of the pack_cost[LEFT] vector.Finding the position aspect is taken care of by lower_bound : IDX= lower_bound(pack_day[LEFT].begin(),pack_day[LEFT].end(),R+1) - pack_day[LEFT].begin() Now you require minimum cost in pack_cost[LEFT] vector in range (IDX,end of that vector). So for the minimum cost finding part, we shall take minimum from the end of the vector to beginning. for(int i=0;i=0;j--) { mini=min(mini,pack_cost[i][j]); pack_cost[i][j]=mini; } } So the minimum in pack_cost[i] vector from position IDX to end is = pack_cost[i][IDX]So, iterate through the DEAL vector and for each package find its optimum partner package and keep taking a global minimum of the costs : mini=min(mini,W+pack_cost[i][IDX]) My AC Code Complexity : O(Nlog(N))
•  » » » 4 years ago, # ^ |   +3 Thank You So Much! I understood very well..
 » 4 years ago, # |   0 can anyone tell y my soln to C is giving RTE 28228552 . Thanks in advance.
 » 4 years ago, # |   0 Can anyone find my bug please :/ problem: Dhttp://codeforces.com/contest/822/submission/28252419
 » 4 years ago, # |   0 Div 2 C giving WA on Test Case 25. Can anyone help me in finding the error?http://codeforces.com/contest/822/submission/28250623Man this is the third time I'm commenting. After commenting, I'm not able to find the previous comments. Why does this happen ?
•  » » 4 years ago, # ^ |   0 Bro..Your code is extremely lengthy to look at. Let me explain you my logic. I hope it will help you.I have a map,int> mp-stores the minimum value of range {l,r},an array of set > st[N]-store the value {l,r} in the r-l+1 th set.So you have a map in which you can get the minimum cost from range l to r and an array of set in which st[i] has all the ranges stored in increasing order whose distance is i. So now lets run a loop from i=1 to i
•  » » » 4 years ago, # ^ |   0 Thank you very much for the explanation. That helped !
 » 4 years ago, # |   0 I would really appreciate it if someone could help me figure out why the following submission ended up with WA on testcase #7. I'll try to explain each of my steps in this post if anyone is confused with what I was trying to do :^)http://codeforces.com/contest/822/submission/28232461So I have an array arr that has dimensions n x 4. The first column was meant to store r — l + 1 and I was planning on doing a sort based off first column with my own comparator. Up till this point my code was successful (I'm 100% sure). However, I feel the mistake lies somewhere in the way I applied the binary search to find the other value in the array such that both sum to x. Any advice is appreciated greatly!Thanks for the great contest Melnik :)
 » 4 years ago, # |   -22 IS IT RATED IS IT RATEDDDDDDDDDDDDDDD
 » 4 years ago, # | ← Rev. 2 →   0 Can someone tell me how to solve a variation of Problem C, i.e., if more than two disjoint trips are allowed? 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 approach to implement this would be nice. Thanks
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I only can think about DP... O(NK^2) DP[i][k] stores min cost ending at i with length k. Initially DP[i][k]=inf, DP[i][0]=0 for every vacation (sorted by r) (l, r, c) DP[r][k]=min (DP[l-a][k-r+l-1]+c). Also you can do O(N^3) by compressing intervals in O(NlogN).
•  » » » 4 years ago, # ^ |   0 You can do it in O(n^2logn) using RMQ.
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   0 You don't need rmq, just prefix minimum. Its O(n*x)