Miyukine's blog

By Miyukine, 3 months ago, In English

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
 
 
 
 
  • Vote: I like it
  • +480
  • Vote: I do not like it

»
11 days 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.

  • »
    »
    11 days ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Time is relative. How it moves for one may be very different for how it moves for another :p

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That time is very strange...

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Someone just got inspired after watching Dark

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's so because the author wrote an editorial 3 months ago (at the same time with setting problems), saved it as a draft but didn't post it. It doesn't mean that editorial was publicly available for three months.

»
11 days ago, # |
  Vote: I like it +93 Vote: I do not like it

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

»
11 days ago, # |
  Vote: I like it +53 Vote: I do not like it

Best editorial ever, HOLY!

»
11 days 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...

  • »
    »
    11 days 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

    • »
      »
      »
      11 days 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 ¯_(ツ)_/¯.

      • »
        »
        »
        »
        10 days 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.

        • »
          »
          »
          »
          »
          10 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You are right. Thank you so much!

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
11 days 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)$$$?

  • »
    »
    11 days 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)

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

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

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same and got AC during the contest.

»
11 days ago, # |
  Vote: I like it +4 Vote: I do not like it

Great explanation for Problem D

»
11 days 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.

  • »
    »
    11 days 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)

  • »
    »
    10 days 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

    • »
      »
      »
      10 days 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.

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

      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

»
11 days 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.

  • »
    »
    11 days 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.

  • »
    »
    11 days 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

  • »
    »
    11 days 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.

    • »
      »
      »
      11 days 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).

      • »
        »
        »
        »
        11 days 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?

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, even my bottom-up python solution is getting TLE. 98682330

»
11 days 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?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

      • »
        »
        »
        »
        11 days 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.

»
11 days ago, # |
  Vote: I like it +4 Vote: I do not like it

301A Similar Hard version of problem B for practise

»
11 days 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!

»
11 days 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 Miyukine! Loved the concept of A.B and C!

  • »
    »
    11 days 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$$$.

    • »
      »
      »
      10 days 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

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
11 days 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.

»
11 days 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.

»
11 days 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

  • »
    »
    10 days 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.

»
11 days ago, # |
  Vote: I like it +60 Vote: I do not like it

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

  • »
    »
    11 days 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!

    • »
      »
      »
      11 days 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.

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

[Deleted]

»
11 days 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

  • »
    »
    11 days 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 :)

»
11 days 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?

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

tnx for fast & complete editorial

»
11 days 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.

»
11 days ago, # |
  Vote: I like it +4 Vote: I do not like it

loved the idea of "contest timeline"

»
11 days 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!

»
11 days 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.

  • »
    »
    11 days 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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for a great contest!!

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
11 days 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

  • »
    »
    11 days 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.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ohh shit i forgot about that ,thanks man

»
11 days 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.
  • »
    »
    11 days 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)

»
11 days 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

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

    Your solution will most likely fail for the case:

    1 3 1

    • »
      »
      »
      11 days 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

      • »
        »
        »
        »
        11 days 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

        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Tks for responding dude, i misread the symbol in the problem statement. Such a stupid mistake

»
11 days 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.

  • »
    »
    11 days 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$$$.

  • »
    »
    11 days 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 :)

  • »
    »
    11 days 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).

    • »
      »
      »
      11 days 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.

»
11 days 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

  • »
    »
    10 days 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)

»
11 days 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

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Never mind, I understand it is actually Trie

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    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

»
11 days 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. :)

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

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

»
11 days ago, # |
  Vote: I like it +26 Vote: I do not like it

Very high quality contest and tutorial! Thanks!!!

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

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

Python) https://codeforces.com/contest/1447/submission/98488848

  • »
    »
    10 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This was because I used pop(0) of O(N) instead of pop() of O(1)...

»
10 days 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.

  • »
    »
    10 days 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.

»
10 days 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.

  • »
    »
    10 days 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 :)

»
10 days 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.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we have a DP solution for Div2 C?

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

div-2 c can anyone tell whats wrong with this code https://ide.codingblocks.com/s/373982

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 days 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

»
10 days 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!

  • »
    »
    10 days 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!

»
10 days 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?

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

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

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

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 one

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

»
10 days 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 ?

  • »
    »
    10 days 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.

    • »
      »
      »
      10 days 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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

div-2 c can anyone tell whats wrong with this code https://ide.codingblocks.com/s/373982

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Any Greedy solutions for div2 D?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

please Can Any explain help me with the problem D

»
10 days 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.

  • »
    »
    10 days 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!

  • »
    »
    10 days 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 :(

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we do D with help of recursion?

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

I didn't understand how to convert problem D into DP. can anyone explain in detail? thanks in advance.

»
10 days 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.

»
10 days 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?

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C div 2, https://codeforces.com/contest/1447/submission/98644637 can anyone say me why my code fails.

  • »
    »
    9 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you cant just simply use (w+1)/2, it works only if w is even not when w is odd.

»
9 days 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 :)

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

    Thank you for your amazing explanation! Better than editorial

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

Hi, Can anyone please tell me why my 1447C solution is failing for testcase 3? (https://codeforces.com/contest/1447/submission/98686992)

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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