### 300iq's blog

By 300iq, 2 years ago, translation,

Thank you for your participation, see you soon (I hope)!

• +167

 » 2 years ago, # |   0 In english?
 » 2 years ago, # |   0 Please link the editorial to the English version of the contest 300iq
 » 2 years ago, # |   0 Excuse me, where can I read about dp? Thanks.
•  » » 2 years ago, # ^ |   0 just surf on the internet ,you will get a whole bunch of stuff to learn...
•  » » » 2 years ago, # ^ |   0 I've found a lot of dp: https://en.wikipedia.org/wiki/DP What exactly should I look for?
•  » » » » 2 years ago, # ^ |   +8 Dynamic Programming
•  » » » » 2 years ago, # ^ |   -34 REALLY!!!!!ARE YOU KIDDING OR WHAT ....
•  » » 16 months ago, # ^ |   0 Topcoder Tutorial DP IOI training herethese are two good resources
 » 2 years ago, # | ← Rev. 3 →   +8 Here are my solutions to the problems of this contest that I could do. I have written an editorial about D here, in case anybody requires further explanation. :) I have also written a post about the O(n) solution to A here. P.S. — What is the bonus solution to Problem D ?
•  » » 2 years ago, # ^ |   0 Awesome explanation !!!
•  » » » 2 years ago, # ^ |   0 Thanks a lot :). I appreciate the encouragement :)P.S. — Are you refering to A or D ?
•  » » » » 2 years ago, # ^ |   0 I was refering to problem D, again awesome explanation !!! I'm adding you to my friends list :)
•  » » » » » 2 years ago, # ^ |   0 Please follow me on Quora and read my answers there. I've written a few posts :)
•  » » » » » » 2 years ago, # ^ |   +7 No. Who cares about your Quora?
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 The people I was talking to do :)The real question you need to be asking yourself is who cares about your imaginary dragons and weird, snarky comments from a fake account ?
•  » » » » » » » » 2 years ago, # ^ |   0 Lol. Making a personal attack doesn't change the fact that you are a shameless advertiser.
•  » » » » » » » » » 2 years ago, # ^ |   +1 I am writing posts so that it clarifies my concepts and can share my knowledge to help others. That's my only intention. When you have a cheap mentality, everything looks cheap. Advertisement for what ? Quora doesn't give me any money if people read my answers.Moreover, I'm on CF so that I can learn and increase my knowledge, not get drawn into random fights. My suggestion is that if you don't like my posts, don't read them. :)I wish you well and have no intention in interacting further with you. :)
•  » » » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Lol. Learn and increase your knowledge? I am seriously curious about what you have learnt. Writing unreadable code and cranking out solutions to unrealistic problems? Stop bluffing yourself!
 » 2 years ago, # |   +1 For bonus question of C, Call a vertex a root if it's degree > 2. Case 1 : There is atleast one vertex with degree > 2If there is more than one root, then the solution stays the same as a decomposition is not possible. If there was exactly one root, then we have to make it the root and the solution stays the same. Making any other vertex the root will not satisfy the given conditions.Case 2 : All vertices have degree <= 2To minimise the number of paths, we must choose a leaf vertex since it has only one child and it will result in 1 simple path from one leaf to another.For maximising the number of paths, we will have to pick any non-leaf vertex which has a degree of 2. There will be two paths, one to each leaf.
 » 2 years ago, # | ← Rev. 2 →   -7 problem E is clearly visible from D&C ...how to solve by DP in an easy way..
 » 2 years ago, # |   +6 I'm really curious about how to solve F in O(n⋅logn). Could someone tell me the method?
•  » » 2 years ago, # ^ |   0 Think about randomized binary search in O(log(n2))
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 I tried to do binary search in O(log(n2)) which equals O(logn), but I failed. If a number doesn't equal any |ai - bj|, it can't be the answer. So there are O(n^2) numbers which can be the answer. But I don't know how to find the k-th of them quickly. What does "randomized binary search" mean?
•  » » » » 2 years ago, # ^ |   +20 You can choose random distance  ≥ l and  ≤ r, (just find good interval for each element, and take random element from these intervals), because if you will take random element (not n/2-th) it will work in O(log(n2)) too.
•  » » » » » 2 years ago, # ^ |   0 I'll use |ai - bj| to indicate the shortest distance bewteen ai and bj. Do you mean if we know the answer is in [l, r]，then we randomly select a number from numbers which are in [l, r] and are equal to some |ai - bj|?If so, is there any convenient way to randomly select a number? It's not uniform that randomly select an i , then randomly select a number from |ai - bj|. In fact for a fixed i, there may be no such j. A solution is calculating how many j satisfying l ≤ |ai - bj| ≤ r for each i using two pointers, then selecting an i using weighted random. But I think this is too complex.
•  » » » » » » 2 years ago, # ^ |   +1 I don't know any other way ╮(╯▽╰)╭
•  » » » » » » » 2 years ago, # ^ |   0 OK, thanks. It's a very interesting idea!
•  » » » » » » » » 2 years ago, # ^ |   0 yeah, it's a fascinating ideal，So good, :D
 » 2 years ago, # |   +26 Can someone explain last paragraph of editorial of problem F, as I can't understand which segments we are talking about and why the intersection of segments is the validation for possible matching for that specific answer.
•  » » 20 months ago, # ^ |   0 I can't understand it,too.Do you know the ans now?
 » 2 years ago, # | ← Rev. 2 →   0 For problem F"So we can solve the problem in O(n * L) — fix the cut, and match i-th bridegrom (in increasing order) with i-th bride (if we will order brides in the traversal order starting from border), and relax answer with current inconvenience."Why this solution is always optimal?
 » 2 years ago, # |   0 In problem E(DP solution), I am unable to crack the logic behind size of DP array(size = N = 1e4+7). Can you explain. Also the case of taking random number to avoid hacking.Why??
 » 2 years ago, # |   0 For problem F Round Marriage.I find a solution in O(n * log_2(L)) with the key idea in the tutorial.What I do is just optimizing the progress of finding the range of x.We can use two-pointers to work out it.More in the code: 39254791
 » 2 years ago, # | ← Rev. 4 →   0 Can someone please explain why this DP in pD is wrong : dp[i][j][k] as maximum value obtained by distributing books in segment [i, j] into k shelves? Complexity O(n^3.n^2) ? 300iq ghoshsai5000 Can you help me out?
•  » » 2 years ago, # ^ |   0 Can you share your logic or your program ?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 ps[] prefix sum Base case : dp[i][j][0] = ps[j] — ps[i-1] all books in segment are in same shelfTransition : dp[i][j][k] = max(dp[i][j][k], (dp[i][be][x] & dp[be+1][j][k-x]))Ans : dp[0][n-1][k-1]Complexity : O(n^3) for states and O(n^2) for each transition
•  » » » 2 years ago, # ^ |   -8 Any success ghoshsai5000
•  » » » » 2 years ago, # ^ |   -8 I think the main problem is AND-ing may not necessarily have optimal substructure !What I mean is ... If we want to know the best AND of a segment [1, 4] into 2 segments, it might not necessarily be the best [1, 2]&[3, 4]. I'm not able to come up with a good counter example. I hope you understood my point. You make one segment [3, 4] ... Now to know the maximum AND with the last segment [3, 4], you might not necessarily need the best AND of [1, 2]. You might need something less than best in that segment.
•  » » » » » 2 years ago, # ^ |   0 Thank you :)
•  » » » » » » 2 years ago, # ^ |   0 I hope you understood. I tried my best. Wasn't able to come up with a counter example :)That's why the intended solution greedily sets as many higher order bits as possible.
 » 2 years ago, # |   0 Can someone explain me problem C?
 » 14 months ago, # |   0 For problem F, is the following correct : First, binsrch on ANS, now we will check whether such answer exists using hall's theorem. So we want to count for each 1 <= L <= R <= N whether number of brides reachable from grooms of [L,R] is atleast R-l+1. So start with [1,i] for all 1<=i<=N. Get the count for these. Now, we update our values for [2,i], then [3,i] and so on using Lazy propagation on Segment tree. Basically, when we remove some element, we invalidate a range of brides for the segment [j,i]. Note that since its cyclic, we wont update all i from j <= i <= n when updating from [j-1,i] to [j,i], because some of them might be accessed for say i = n. Thus, we need Lazy range addition and min. Overall, logL * nlogn.Is this correct though? I am not confident in applying Hall's theorem.
 » 6 months ago, # |   +10 I think I have a simpler solution for problem E:Sort the queries in increasing $r_i$. Then mantain $dp[i]$ which is the rightmost index in the array which we can achieve a maximum of $i$ in. Iterate through the queries, initially setting $dp[0]=r_i$ and then iterating backwards like the knapsack DP trick (I think this is covered in Errichto's AtCoder DP video in the knapsack problem) to update all the $dp[i]$. Complexity $O(nq)$.73507542