When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

kpw29's blog

By kpw29, 4 years ago, In English

Thank you very much for taking part in the contest!

Contest timeline

1447A - Добавьте конфет

Tiny hint
Hint
Solution

1447B - Коробка с числами

Hint
Solution

1447C - Рюкзак

Hint
Solution
Alternative solution

1447D - Ловя мошенников

Hint
Key observation
Solution

1447E - Ксор дерево

Small hints
First step
Hint
Next step
Solution

1447F1 - Задача о частотах (простая версия)

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 - Долгое выздоровление

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

1446F - Расстояние до прямой

Stupid hint
Geometric insight
Proof of observation
Final details
  • Vote: I like it
  • +515
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +127 Vote: I do not like it

This editorial was created... 3 months before the contest? That might be the fastest editorial ever on Codeforces.

»
3 years ago, # |
  Vote: I like it +93 Vote: I do not like it

The Contest timeline section is pretty nice and active. I like it.

»
3 years ago, # |
  Vote: I like it +53 Vote: I do not like it

Best editorial ever, HOLY!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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...

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    In most cases, as long as $$$n < 10^4,$$$ $$$O(n^2)$$$ solution can pass

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok, thanks. Actually, I ran program with two cycles that were doing 5000 iterations each, and it was running ~10 seconds ¯_(ツ)_/¯.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You are right. Thank you so much!

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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)$$$?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    And there is another small typo under that line (but it's not a big deal)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes, I believe it should be max instead of min.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same and got AC during the contest.

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Great explanation for Problem D

»
3 years ago, # |
  Vote: I like it +159 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Nice solution! (I ranted about my bad nlogn solution, but this one is much cleaner so nvm)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Good catch, my wording could have been more precise. As loan 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

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

1447D time limit is too tight that bottom-up implementations are accepted but not top-down with same time complexity.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    mine is O(2 * N^2) top down and it's Accepted in 592ms.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Generally recursive implementation will spend more time There is a very good comparision between those two ways

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry if this is a stupid question but what is the "standard algorithm" of computing longest subarray with sum 0?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Subarray $$$[a, b)$$$ has sum 0 <=> $$$prefsum(a) = prefsum(b)$$$

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      So store an array of minimum position with given prefix sum?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

        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.

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

301A Similar Hard version of problem B for practise

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me identify why my solution is wrong ? https://codeforces.com/contest/1447/submission/98488500

I 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!

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    $$$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$$$.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can Div 2C be solved with DP? Cause mine got TLE

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +60 Vote: I do not like it

F is too easy and standard for 3000... and E deserves 4000.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      A, C and D was nice and I enjoyed them a lot! Thank you for providing the problem set.

»
3 years ago, # |
Rev. 3   Vote: I like it -6 Vote: I do not like it

[Deleted]

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1447D — Catching Cheaters

In 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 j

Is it because the value will be at least zero?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

tnx for fast & complete editorial

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

loved the idea of "contest timeline"

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

98501736

Very interesting questions indeed!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know about test case 1023 in C ? All the solutions failed on that one.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    keep a counter of the number of testcases, print input if counter = 1023, check testcase in the checker log.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for a great contest!!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ohh shit i forgot about that ,thanks man

»
3 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Can anyone tell me why my submission 98492742 for Div2D fails for test case 6?

I'm using pair<int,pair<int,int>> 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.
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Your solution will most likely fail for the case:

    1 3 1

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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

»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

What is the actual proof for div1F? The pictures make it intuitive but I'm not sure how to rigorously prove.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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$$$.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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).

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think indexof() function will take O(n) time inside the for loop so it's O(n^2)

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 way

In my way, I just binary search the seperate position in every step 98511888

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Never mind, I understand it is actually Trie

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Very much fancy the step-by-step tutorial which guides one to think more and more deeply. :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Thanks! I wish all the editorials were done this way :)

»
3 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Very high quality contest and tutorial! Thanks!!!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Solution for problem Knapsack. https://codeforces.com/contest/1447/submission/98518206

this failed on test 2. Can somebody tell me why this solution is wrong.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

OMG! THE BEST EDITORIAL EVER in the history of cf !!! wow, great job ! Community appreciates your awesome work

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

'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!

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    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!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem C as per the alt solution if i sort the elements, how do i keep track of the original indices?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Sort pairs of the form (element, initial index).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For div1 D2

After 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 6

then 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 them

it somehow passed. 98560373

Can someone help me prove it right or hack me ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any Greedy solutions for div2 D?

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :(

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

"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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div 2 F, i've come up with an approach with the complexity of $$$O(nlogn)$$$ , But it fails on test #5

Here's my submission. anyone can tell me where i'm going wrong?

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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/2

Now we have all elements < w/2 if sum of all remaining elements <w/2 that means we can't make req. config output -1

now there is always a way to make sum>=(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 :)

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Thank you for your amazing explanation! Better than editorial

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    My alternative math proof for problem C
»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

kpw29 can you please explain the formula 1 + max(F(S0),F(S1)) for the problem div2E .

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution for problem D case1 is DP[i][j] = max(DP[i][j], DP[i- 1][j- 1] + 2)