### kpw29's blog

By kpw29, 8 months ago,

Thank you very much for taking part in the contest!

Contest timeline

1447A - Add Candies

Tiny hint
Hint
Solution

1447B - Numbers Box

Hint
Solution

1447C - Knapsack

Hint
Solution
Alternative solution

1447D - Catching Cheaters

Hint
Key observation
Solution

1447E - Xor Tree

Small hints
First step
Hint
Next step
Solution

1447F1 - Frequency Problem (Easy Version)

Hint
First steps
Proof of the observation above
Consequence of the observation
Why the simplification works
Solution for the easy version
Hint for the subproblem
Solution of the subproblem

1446E - Long Recovery

Setup
The upper bound
When does the organism remain sick?
Solution
Proof

1446F - Line Distance

Stupid hint
Geometric insight
Proof of observation
Final details

• +515

 » 5 months ago, # |   +127 This editorial was created... 3 months before the contest? That might be the fastest editorial ever on Codeforces.
•  » » 5 months ago, # ^ |   +27 Time is relative. How it moves for one may be very different for how it moves for another :p
•  » » 5 months ago, # ^ |   0 That time is very strange...
•  » » 5 months ago, # ^ |   0 Someone just got inspired after watching Dark
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 .
 » 5 months ago, # |   +93 The Contest timeline section is pretty nice and active. I like it.
 » 5 months ago, # |   +53 Best editorial ever, HOLY!
 » 5 months ago, # |   0 Why O(nm) is enough for D? 5000^2 = 25000000 is a very big number. As for me, I was searching for smth like O(nlogn) the whole contest...
•  » » 5 months ago, # ^ |   +21 In most cases, as long as $n < 10^4,$ $O(n^2)$ solution can pass
•  » » » 5 months ago, # ^ |   0 Ok, thanks. Actually, I ran program with two cycles that were doing 5000 iterations each, and it was running ~10 seconds ¯_(ツ)_/¯.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +3 Probably you've run your program in Debug mode (if we are talking about c++), try to switch your mode to Release and test again.
•  » » » » » 5 months ago, # ^ |   0 You are right. Thank you so much!
•  » » 5 months ago, # ^ |   0 In one of the educational codeforces round problems it was said that around 10^8 operations can pass in less than 0.5 seconds in fast languages like C++ so now you can imagine here it will even pass in less than 0.25 seconds using C++
 » 5 months ago, # |   +13 I might be wrong, but for Div 2 D, shouldn't it be $dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 2)$?
•  » » 5 months ago, # ^ |   +3 And there is another small typo under that line (but it's not a big deal)
•  » » 5 months ago, # ^ |   +1 Yes, I believe it should be max instead of min.
•  » » 5 months ago, # ^ |   0 I did the same and got AC during the contest.
 » 5 months ago, # |   +4 Great explanation for Problem D
 » 5 months ago, # |   +159 Nice $O(n)$ solution to D (or at least $O(n \log n)$)In problem D we can test two values $A$ and $B$ in time $O(occ(A) + occ(B))$, where $occ(x)$ means how many times $x$ appears. We should fix A as a mode and loop over all values of $B$ in order to get solution for D1. But if we can somehow bound number of interesting occurences of $A$ to $O(occ(B))$ than we would be able to solve that problem in linear time, right? And that is what we are gonna do now.We will mark some occurences of $A$. Let us go through values of $B$ from left to right. For each value of $B$ let us mark closest unmarked occurence of $A$ on the left and on the right (note that closest occurences may already be marked). We keep only marked occurences of A and there are at most $2occ(B)$ of them, so that suits us.What is left to do is to prove that answer doesn't change if we discard the rest of unmarked occurences (which I left as an exercise) and to implement that quickly. It is very easy to implement that in $O(n \log n)$ what I did during testing, but it probably is doable in $O(n)$, but I haven't given it much thought.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 Nice solution! (I ranted about my bad nlogn solution, but this one is much cleaner so nvm)
•  » » 5 months ago, # ^ |   +25 Consider this array: $[1,2,1,1,1,2,1]$. In this case $A=1$. When $B=2$, we mark the $1$s occurring at indices $1,3,5,7$ and the new array is $[1,2,1,1,2,1]$. Note that $[2,1,1,2]$ is a valid solution in the new array but this corresponds to $[2,1,1,1,2]$ in the actual array, which is not a valid solution. Could you clarify this? @Swistakk
•  » » » 5 months ago, # ^ |   +21 We are not removing unmarked occurences of $A$ from the array, we are just stating that those unmarked occurences can't be the first time or the last time $A$ appears in the solution, so you can just skip over them.
•  » » » » 5 months ago, # ^ |   0 Yes, it makes sense. Thanks!
•  » » » 5 months ago, # ^ |   +18 Good catch, my wording could have been more precise. As Gioto explained, I don't consider them as contained in optimal interval, but I still remember for each occurence of A where is the next/previous original occurence that tells me how much I can expand this interval without containing more of its occurences
 » 5 months ago, # |   +11 1447D time limit is too tight that bottom-up implementations are accepted but not top-down with same time complexity.
•  » » 5 months ago, # ^ |   0 mine is O(2 * N^2) top down and it's Accepted in 592ms.
•  » » 5 months ago, # ^ |   0 Generally recursive implementation will spend more time There is a very good comparision between those two ways
•  » » 5 months ago, # ^ |   0 I don't think it's recursion or the TL. I think it's your implementation. Looking at 98495013, you use binary search in your dp, adding an additional log factor.
•  » » » 5 months ago, # ^ |   0 No, I was talking about my previous submission https://codeforces.com/contest/1447/submission/98483575. As per my analysis, it should be O(3*N^2).
•  » » » » 5 months ago, # ^ |   0 Using big O notation, your time complexity is O(nm). However, you don't have a great constant. Intended solution's dp returns an int while yours returns a tuple. Also, I'm not sure why you're comparing top down and bottom up. Does your solution pass if you write it iteratively?
•  » » 5 months ago, # ^ |   0 Yes, even my bottom-up python solution is getting TLE. 98682330
 » 5 months ago, # |   0 Sorry if this is a stupid question but what is the "standard algorithm" of computing longest subarray with sum 0?
•  » » 5 months ago, # ^ |   0 Subarray $[a, b)$ has sum 0 <=> $prefsum(a) = prefsum(b)$
•  » » » 5 months ago, # ^ |   +4 So store an array of minimum position with given prefix sum?
•  » » » » 5 months ago, # ^ |   +22 Exactly. Take a note this prefix sum may be negative, but it is within interval $[-n, n]$, so you may use a static array of length $2n+1$ with offset $n$. And remember about first empty prefix sum.
•  » » » » » 5 months ago, # ^ |   +6 Thank you for answering!
 » 5 months ago, # |   +4 301A Similar Hard version of problem B for practise
 » 5 months ago, # |   0 Can someone help me identify why my solution is wrong ? https://codeforces.com/contest/1447/submission/98488500I do normal LCS, then reconstruct the positions where the LCS exists into two arrays. Now I go through all possible substrings that contain an LCS and maximize value across all. Check the code, it'll make more sense there.Any help is apprecited!
 » 5 months ago, # |   +11 In every case, we can refer to DP[i][j−1] or DP[i][j−1] to extend one of the previous substrings, but not the LCS, so: DP[i][j] = max(DP[i-1][j], DP[i][j-1]) — 1.Can anyone explain this point in Solution of problem D along with an example? I could not understand this part of the solution.Btw Great contest kpw29! Loved the concept of A.B and C!
•  » » 5 months ago, # ^ |   +17 $A = ababaa$ $B = abbabb$Consider the above 1-indexed strings. Since $A[4] \neq B[4]$, both of them can't be included in the LCS at the same time. So, $dp[4][4]$ must be the same LCS as $dp[4][3]$ ($B[4]$ is not included in the LCS) or $dp[3][4]$ ($A[4]$ is not included in the LCS). To get from $dp[4][3]$ to $dp[4][4]$, we extend $B$'s substring by $1$, leaving $A$'s substring and the LCS the same. This results in subtracting $1$ from the similarity score. Similarly, to get from $dp[3][4]$ to $dp[4][4]$, we extend $A$'s substring by $1$, leaving $B$'s substring and the LCS the same. This also results in subtracting $1$ from the similarity score. So, $dp[4][4] = max(dp[3][4]-1, dp[4][3]-1) = max(dp[3][4], [4][3]) - 1$. This generalizes to $dp[i][j] = max(dp[i-1][j], dp[i][j-1]) - 1$.
•  » » » 5 months ago, # ^ |   +5 Thank you for such a good explanation 2020akadaver. I usually do not understand DP editorials but this was one of the rare excellent ones! Kudos
•  » » » 5 months ago, # ^ |   0 it's important to informally notice that we never get a greater LCS this way so wrong calculations only lead to the worse score, and that our code will always find a sequence of transitions which finds the true LCS as well. Can you elaborate on this as well ? 2020akadaver
 » 5 months ago, # |   0 After 35 minutes trying to get some property out of problem A, i checked if I was not in div1 contest by mistake, next contest I will start with problem C.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 yeah it was tricky
 » 5 months ago, # |   +3 Hi, I don't understand why in problem C doesn't matter if the matrix has a zero.If the matrix has a zero, i can transform all negatives in positives, taking the negatives with the zero.
•  » » 5 months ago, # ^ |   +3 Yes! You can but in that case minimum abs value would be 0 only!
•  » » » 5 months ago, # ^ |   +3 Oh! I see! Thanks
 » 5 months ago, # | ← Rev. 2 →   0 Can Div 2C be solved with DP? Cause mine got TLE
•  » » 5 months ago, # ^ |   0 No. Also, its not DP but rather straight up recursion/backtracking. In the worst case, you will never find a valid sequence and you will have 2^n iterations making the complexity O(2^n). I did the same and got TLE on system check.
 » 5 months ago, # |   +60 F is too easy and standard for 3000... and E deserves 4000.
•  » » 5 months ago, # ^ |   +18 We honestly didn't expect so many wrong answers on E. The proof is a bit tricky, but analyze the setup and exclude two quite obvious cases where you can't use the cheap operation didn't sound significantly harder for us.We hope you've enjoyed solving the problems anyway!
•  » » » 5 months ago, # ^ |   +29 A, C and D was nice and I enjoyed them a lot! Thank you for providing the problem set.
 » 5 months ago, # | ← Rev. 3 →   -6 [Deleted]
 » 5 months ago, # |   0 i made a divide and conquer solution for C but it's missing cases on tc 1023 pretest 2 if anyone can see what's wrong with my approach 98480163
•  » » 5 months ago, # ^ |   0 One thing I can clearly see is that u have used w/2 but u must use (w+1)/2. Rest you have done hell lotta extra things which complicates the code and they need not be done. You should refer editorial :)
•  » » » 5 months ago, # ^ |   +1 ya that's for sure
 » 5 months ago, # |   0 1447D — Catching CheatersIn this problem why we not considering starting index of any substring; dp[i][j] just indicates that first substring ends at i and second at jIs it because the value will be at least zero?
•  » » 5 months ago, # ^ |   0 Yes. Just like in the normal longest common substring problem we are looking for the best possible answer while moving in the backward direction .That's why not letting the value stored at any position in dp matrix decrease beyond 0. Anytime the value goes beyond 0 we restart by making it 0 .
 » 5 months ago, # |   0 tnx for fast & complete editorial
 » 5 months ago, # |   +6 this is the most kind and elegant editorial i've ever seen. step by step hints made me understand better and think more by myself. thanks a lot.
 » 5 months ago, # |   +4 loved the idea of "contest timeline"
 » 5 months ago, # |   +11 Div-2D Had a very hazy understanding of how the +2, -1 tracking would address the fact that the actual substrings chosen must have both start and end characters to be part of the LCS. The solution I was trying for was tracking the starting matched characters along with traditional LCS to calculate score at each step. So at (i,j) I would know the LCS and the (i_, j_) where this LCS started. Of course, cases like <2 and <0 scores must be handled appropriately.Ran into the issue that I can't really have 5000x5000x3 integers, got memory limit exceeded in testcase 12. The trick to that I discovered from one of the successful submissions as I was looking for one which matched my approach and I found one where the MLE was tackled by the fact that we need the previous and current row only as we aren't answering queries that would need these previous values.98501736Very interesting questions indeed!
 » 5 months ago, # |   0 Does anyone know about test case 1023 in C ? All the solutions failed on that one.
•  » » 5 months ago, # ^ |   0 keep a counter of the number of testcases, print input if counter = 1023, check testcase in the checker log.
 » 5 months ago, # |   0 Thank you for a great contest!!
 » 5 months ago, # |   0 Is there any way to know for which test case my solution failed , I have done div2 C using 2-pointer method, but got WA on pretest 2.
•  » » 5 months ago, # ^ |   0 Test case — 1027, pretest 2, hope there was some way to download the test case file..
•  » » 5 months ago, # ^ |   0 Try this input 1 4 7 1 6 1 1 
•  » » » 5 months ago, # ^ |   0 thanks, there was a silly mistake..
 » 5 months ago, # |   0 Can anybody please tell me what's wrong in using ceil in div2C after contest i tried by replacing ceil with (w+1)/2 and it gave AC
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 I think you tried ceil(w/2). Here w/2 will be performed first and it is integer division so it will floor. Basically for example if w=5, then ceil(5/2) -> ceil(2) -> 2. You need to work with floating point there if you want ceil to work.
•  » » » 5 months ago, # ^ |   0 ohh shit i forgot about that ,thanks man
•  » » » 3 months ago, # ^ |   0 what if someone uses ceil(w/2.0)
 » 5 months ago, # | ← Rev. 5 →   0 Can anyone tell me why my submission 98492742 for Div2D fails for test case 6?I'm using pair> DP[i][j] where: dp[i][j].first stores max. LCS length in s[0....i] and t[0....j] dp[i][j].second.first stores the index where current LCS began in s dp[i][j].second.second stores the index where current LCS began in t.
•  » » 5 months ago, # ^ |   0 I'm not sure because your code is quite complicated. But usually people failed on test 6 when they didn't consider the possibility to restart the substrings (setting dp[i][j] = max(dp[i][j], 0) in the editorial)
 » 5 months ago, # |   0 Guys, i am not sure why my solution of problem C is wrong. Can anyone help me debug it? That would be much appreciated! 98506202
•  » » 5 months ago, # ^ |   +5 Your solution will most likely fail for the case:1 3 1
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 the result my code (and my understanding of the problem) is: 1 1. Can you tell me the correct result pls. And thank you for responding.EDIT: oh crap, i realized now, i misread the symbol in the orignial problem
•  » » » » 5 months ago, # ^ |   +5 Item of $1$ is not enough to fill more than half of the knapsack. Your if w/2 is incorrect, should be (w+1)/2
•  » » » » » 5 months ago, # ^ |   0 Tks for responding dude, i misread the symbol in the problem statement. Such a stupid mistake
 » 5 months ago, # |   +13 What is the actual proof for div1F? The pictures make it intuitive but I'm not sure how to rigorously prove.
•  » » 5 months ago, # ^ |   +38 One fun way to prove it is to use a bit of Euclidean Geometry. The intersection $X$ of $A_1A_2$ and $B_1B_2$ and the projection $Y$ of $O$ onto $AB$ are inverses with respect to the circle, so $OX \cdot OY = r^2$ and one of the points lies inside the circle if and only if the other one lies outside.The reason this is true is that the red lines are the polar lines of $A$ and $B$ with respect to the circle, so $AB$ is the polar line of $X$ and $OX$ cuts $AB$ at the inverse of $X$.
•  » » 5 months ago, # ^ |   +3 There is an older version of the editorial which was rewritten by _h_ so that it's a bit clearer, but in the process the more rigorous proof was lost. I wanted to revert to that revision, but forgot, and since Ari's answer is really good, I will allow myself to just rely on that :)
•  » » 5 months ago, # ^ |   +18 Here's a proof close to the pictures in editorial.Let's imagine the circle is a solid "obstacle". I claim that A and B "see" each other -- i.e. the segment AB does not intersect the circle -- iff they both see some point on the circle. This then proves the observation, since the points on the circle seen by A are precisely those between A_1 and A_2.Suppose A and B see each other. If the line AB intersects the circle, then A and B both see one of the intersection points, so done. Otherwise A and B both see the point on the circle closest to the line AB, so again done.Now suppose A and B both see some point X on the circle. So the circle does not intersect AX or BX. So A and B both lie on the same side of circle tangent at X. So done.For what it's worth, this argument doesn't use any property of the circle other than the fact that it's convex (for second implication).
•  » » » 5 months ago, # ^ |   +21 Sorry, I got confused about what we wanted to prove. The above is correct, but not strong enough to prove the observation... let me try again.Note that B "sees" A1 if and only if B and O lie on opposite sides of the tangent line A A1. Consider the four different cases of whether B sees A1, A2, both, or none. If B sees A1 but not A2, then the chords B1 B2 and A1 A2 must intersect, since the segment B1 B2 contains A1 but not A2. In this case, it should also be clear that the line AB does not intersect the circle. The cases where B sees A2 but not A1 is of course the same.If B sees neither A1 nor A2, then B lies on the same side as O of both tangents A1, A2, and from this it should be clear that AB intersects the circle. Similarly of B sees both A1 and A2.
 » 5 months ago, # |   0 Hi, My solution gives TLE for pretest 3 for div2 C problem. Plz help why cause imo it takes O(nlogn) and it follows the same way as suggested in alternative soln of the editorial. 98491654
•  » » 5 months ago, # ^ |   0 I think indexof() function will take O(n) time inside the for loop so it's O(n^2)
 » 5 months ago, # | ← Rev. 2 →   0 I saw many people who get accepted on Div2E/Div1C uses a 2d structure to store data, which are very similar to this one 98462641. What is the name of this method? It seems a common wayIn my way, I just binary search the seperate position in every step 98511888
•  » » 5 months ago, # ^ |   0 Never mind, I understand it is actually Trie
 » 5 months ago, # |   0 May be it's a stupid question, but I still can't understand for DIV2-B. Why the X means the number of the non-zero numbers in the grid. I think may be X can be the number of the zero and the negative numbers.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Well, the number of zeroes doesn't change the answer. Why? if X is odd, u can easily make all numbers positive except for the smallest and that is 0(if exists). Subtracting 0 doesn't change the answer. if X is even, u can make all numbers positive. So adding 0 also also don't change the answer. // I think u have understood
•  » » » 5 months ago, # ^ |   0 Thak you very much for your reply! I have understood it.
•  » » » 13 days ago, # ^ |   0 i thought we could perform operations only on adjacent cells like left right top bottom why is that they have mentioned that we can perform operation on any two cells?
 » 5 months ago, # |   +25 Very much fancy the step-by-step tutorial which guides one to think more and more deeply. :)
•  » » 5 months ago, # ^ |   +16 Thanks! I wish all the editorials were done this way :)
 » 5 months ago, # |   +26 Very high quality contest and tutorial! Thanks!!!
•  » » 5 months ago, # ^ |   0 We're glad to hear that!
 » 5 months ago, # | ← Rev. 2 →   0 Can someone give me advice regarding my code on Div2C to avoid TLE? It has the same approach with the alternative solution and received a pass in pretests, but got TLE on test 20 after the contest :(
•  » » 5 months ago, # ^ |   0 This was because I used pop(0) of O(N) instead of pop() of O(1)...
 » 5 months ago, # |   0 How would the solution change in Div2 D if it was also said to output the selected 2 substrings for which we are getting the best similarity? Any clues or suggestions are appreciated.
•  » » 5 months ago, # ^ |   0 Let pos[i][j] be a number from 1 to 4. if we have maximum answer when we start substrings from A[i] and B[j] and end the in A[i] and B[j] the pos = 1. if we have it when we are using DP[i — 1][j — 1] then pos = 2. we can have pos = 3 or 4 when we are using DP[i — 1][j] or DP[i][j — 1]. Now all we need is to find maximum DP[i][j] and start finding the substrings using pos[i][j]. It wouldn't take much time and we can handle it in O(n.m) in worth case.
 » 5 months ago, # |   +3 That was really a fantastic editorial. The way they provided hints and moved towards the solution was great. Maybe just adding a sample solution code will be more great. We will be waiting for these types of editorials everytime.
•  » » 5 months ago, # ^ |   0 Sure. The usual solution is to wait after the end of systests, submit model solutions in practice mode and then link them. I just forgot to do that :)
 » 5 months ago, # | ← Rev. 2 →   0 Solution for problem Knapsack. https://codeforces.com/contest/1447/submission/98518206this failed on test 2. Can somebody tell me why this solution is wrong.
•  » » 5 months ago, # ^ |   0 I believe you have not checked whether your capacity is at least [W/2] or not as mentioned in the question
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 try using this test case 1 5 100 1 1 1 1 1
•  » » » 5 months ago, # ^ |   0 i got 1 1 2 3 4 5 
•  » » » » 5 months ago, # ^ |   0 hope u get your mistake the anwer should be -1
 » 5 months ago, # |   0 Hey , I am quite confused with Problem D, what actually dp[i][j] mean, I am a tyro in dp and not able to comprehend how dp[i][j] is related to substrings and longest common subsequence. someone, please explain
 » 5 months ago, # |   0 Can we have a DP solution for Div2 C?
 » 5 months ago, # | ← Rev. 2 →   0 div-2 c can anyone tell whats wrong with this code https://ide.codingblocks.com/s/373982
 » 5 months ago, # |   0 Consider the following input 2 3 ab bab Now in our table i.e. dp[N][N]when we calculate for i=3 and j=1 i.e we calculate S(a,bab) which should be 2 as the longest common subsequence is a thus similarity score should be 2 as substrings to be considered are a and a(from bab) but according to editorial it should be 1. Can someone please explain this
 » 5 months ago, # |   0 OMG! THE BEST EDITORIAL EVER in the history of cf !!! wow, great job ! Community appreciates your awesome work
 » 5 months ago, # |   +5 'For the other elements, for all the appearances of V we'll consider only at most |V| + 1 neighboring occurrences of D to search for the optimal interval.'Can someone explain this part of the explanation for problem F2? Thanks in advance. Great contest btw!
•  » » 5 months ago, # ^ | ← Rev. 2 →   +5 You're looking for a segment with sum $0$, if you take at least $|V| + 1$ consecutive elements for number $1$ then there's no way that something including the last element be in the optimal solution, as there are at least $|V|$ other elements before you reach any $-1$, and there are $|V|$ elements in total.I hope it helps!
 » 5 months ago, # |   0 in problem C as per the alt solution if i sort the elements, how do i keep track of the original indices?
•  » » 5 months ago, # ^ |   +5 Sort pairs of the form (element, initial index).
 » 5 months ago, # | ← Rev. 2 →   0 Mr.Miyukine, can you please confirm if what i understood from reading the "why the simplification works" section (of problem F1, div 2) correct or not?What i understood,That we might be wrong in finding the longest subarray length regarding a particular pair (D,V), but when we check all the pairs we end up on the right answer that too on a right pair or say one of the right pairs as the optimal oneUPD: I think what i understood was correct, the code got accepted which is in accordance with my understanding. I'm so happy that I solved F1 (after the contest) for the first time. I thank Mr.Miyukine and his team for designing such an amazing tutorial which made be believe that I can solve F with good enough hints (ofcourse not involving complex data structures).
 » 5 months ago, # |   0 For div1 D2After reading the editorial for D1, I was wandering if the property "Most frequent element will be in optimal solution" can be extended to "Most frequent element and second most frequent element will be in optimal solution"WA on test 6then I try some random stuff. I sort every element by their frequency.let's call the most frequent value by $V$ I do the similar thing in D1, just that except for enumerating all of the other element that could have the same frequency as $V$, I took the first 750 of themit somehow passed. 98560373Can someone help me prove it right or hack me ?
•  » » 5 months ago, # ^ |   0 Hmm, this is quite strange. I recall writing a solution which did something very similar and failing the tests. In theory, if you have all elements but one appear 2 times then by taking 750 random values which appear 2 times you should have quite a slim chance of finding the right pair to use.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 I actually tried smaller number after that submission, it turns out that setting 750 to 100 will pass too.Maybe it's not necessary to have the right pair to find the optimal solution.(I cannot prove it though .. qq
 » 5 months ago, # |   0 https://codeforces.com/contest/1447/submission/98559797 why my code fails
 » 5 months ago, # |   0 Can someone help me optimizing my solution for 1447-C Knapsack problem (got tle on test case 5 (DP Approach)) Here is the link: https://codeforces.com/contest/1447/submission/98505502
 » 5 months ago, # |   0 div-2 c can anyone tell whats wrong with this code https://ide.codingblocks.com/s/373982
 » 5 months ago, # |   0 Any Greedy solutions for div2 D?
 » 5 months ago, # |   0 please Can Any explain help me with the problem D
 » 5 months ago, # |   +3 IN div 2D,can anyone explain what does this line means If a substring has a negative score, we can throw it away and start from scratch- 1.
•  » » 5 months ago, # ^ |   0 This is similar to kadane's algorithm for the maxiumum subarray sum problem. If we ever get a negative value for the maximum subarray sum ending with the previous element in the array, it is best to "throw that away" than to add that "maximum sum" to the next value in the array. I hope this helps!
•  » » 5 months ago, # ^ |   0 Adding more to this question, can someone please tell how defining the dp for every combination of prefixes of the two strings(that is, dp[i][j] = ans for prefix i from A, and prefix j from B), in itself answers for all possible combinations of 'substrings' under i and j, and not just the prefixes. I really am not able to get this :(
 » 5 months ago, # |   0 Can we do D with help of recursion?
 » 5 months ago, # | ← Rev. 5 →   0 I didn't understand how to convert problem D into DP. can anyone explain in detail? thanks in advance.
 » 5 months ago, # |   +3 "DP[i][j] be the maximum similarity score if we end the first substring with Ai and the second substring with Bj"In 1447D - Catching Cheaters we used the above assumption. But wouldn't this only give us the possible Similarity Scores, when the last characters of the string are trimmed? Thus the first characters of the strings A and B will always be used.Since Ai would always contain the first i characters, so for instance if the first characters in A is not necessary for the substring since we always take the first i elements, it will still consider it.
 » 5 months ago, # |   0 For Div 2 F, i've come up with an approach with the complexity of $O(nlogn)$ , But it fails on test #5Here's my submission. anyone can tell me where i'm going wrong?
 » 5 months ago, # |   0 Problem C div 2, https://codeforces.com/contest/1447/submission/98644637 can anyone say me why my code fails.
•  » » 5 months ago, # ^ |   0 you cant just simply use (w+1)/2, it works only if w is even not when w is odd.
 » 5 months ago, # | ← Rev. 4 →   0 I know a lot of people solved C. But for Those who are unable to think why greedy works or unsatisfied with editorial can read this :)so we have to fill our knapsack such that sum(wt)<=w and sum(wt)>=(w+1)/2. let say there is one element which is satisfying above condn output that. otherwise elements are present in combo of ai < w or ai > w now do you want to include an item which has size > w in knapsack?? no because taking that in any situation will deny our requirements so let's shrink the array to only those elements which has size=(w+1)/2 and sum<=w how?? sort it. iterate in reverse manner. stop where sum>=w/2.now why let define number line as ----region1-----w/2----region2------w---region3------- now if we are on region 2 we are ok output now many of you are thinking it may be possible we are at end of region 1 and some number comes and we promoted to region 3 right?? so my dear friend promoting from region 1 to region 3 requires w/2+something value which is not present in our array. because if it was there we can output that :)If something is still unclear let me know :)
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 Thank you for your amazing explanation! Better than editorial
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 My alternative math proof for problem CObservation [0] Removing number larger $w$ doesnt affect the result [1] If sum of all element is smaller than $\frac{w}{2}$ then there is no way [2] If there is a number satisfy $\frac{w}{2} \leq x \leq w$ then output it Now we have to prove there is always exist such $sum$ satisfy the condition. Let $sum$ is sumation by keep adding numbers from large to smaller and $x$ is the next element to add to our $sum$ [3] If current sum satisfy $\frac{w}{2} \leq sum \leq w$ then output it Since [2] is not satisfy, then $0 \leq x \leq \frac{w}{2}$ Since [3] is not satisfy, then $0 \leq sum \leq \frac{w}{2}$ Since [2], [3] are both not satisfy, we have $0 \leq sum + x \leq w$ Since [0], [1] are both not satisfy, there is exist atleast one way to add $x$ to $sum$ until $sum \geq \frac{w}{2}$ So by keeping adding largest to smaller elements, we meet the case $w \geq sum \geq \frac{w}{2}$ before $sum + x \geq w$ or there is no left $x$ to add
 » 5 months ago, # |   0 Hi, Can anyone please tell me why my 1447C solution is failing for testcase 3? (https://codeforces.com/contest/1447/submission/98686992)
 » 5 months ago, # |   0 I'm wondering the solution of Problem E. If we divide the numbers in to two Set S1 and S0. then the case 7 6 9 8 7 3 5 2 will be S0:2 3 5 6 7 S1:8 9 both aren't empty ans = 1 + max(S0, S1) and the answer will be 6. but if we divide number into groups by their highest bit S0 : empty S1 : 2 3 S2 : 5 6 7 S3 : 8 9 we will know we must delete one from S1 and one from S3. Do I have a wrong understanding at the tutorial? Thanks.
 » 5 months ago, # |   -7 How to translate "triforce" into Chinese? I wrote a blog at https://www.cnblogs.com/jz-597/p/14008291.html but I don't know how to show the concept concisely.
 » 5 months ago, # |   0 kpw29 can you please explain the formula 1 + max(F(S0),F(S1)) for the problem div2E .
 » 5 months ago, # |   0 why for 1446F2 random_suffle is working solution to reduce search space? I have seen it in some of programs, very elegant but unclear for me
 » 2 months ago, # |   0 For Problem F, I'm really puzzled.I try to solve it using binary search. In my opinion, when I cannot find an answer while the most occurences freq of an element in the longest subarray is x, there won't be answer for x' (x' > x). Therefore, I use binary search to find the largest x and record the answer using ans. However, I can't pass Test Case 5. Can someone please point out where the flaw is? https://codeforces.com/contest/1446/submission/106463443
 » 6 weeks ago, # |   0 In A problem can't we use below mentioned method In the second case, firstly you use first three operations to add 1+2+3=6 candies in total to each bag except of the third one, which gives you [7,8,3]. Later, you add 4 candies to second and third bag, so you have [7,12,7], and 5 candies to first and third bag — and the result is [12,12,12].m =3 3 2 1Y is this not being accepted
 » 4 weeks ago, # |   0 Solution for problem D case1 is DP[i][j] = max(DP[i][j], DP[i- 1][j- 1] + 2)