vovuh's blog

By vovuh, history, 7 weeks ago, In English,

All ideas except the problem C belong to MikeMirzayanov. The author of C is Rox.

Special thanks to opukittpceno_hhr for the invaluable help with the round preparation!

1272A - Three Friends

Tutorial
Solution

1272B - Snow Walking Robot

Tutorial
Solution

1272C - Yet Another Broken Keyboard

Tutorial
Solution

1272D - Remove One Element

Tutorial
Solution

1272E - Nearest Opposite Parity

Tutorial
Solution

1272F - Two Bracket Sequences

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +61
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +35 Vote: I do not like it

Not hard, but still nice problems with nice solutions.

»
7 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Missing a '$$$|$$$' in the tutorial of 1272A. It should be $$$|na-nb|+|na-nc|+|nb-nc|$$$. Thanks for the nice problems and a neat editorial.

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

    It's good when your eye doesn't put extra symbols while reading. It would be really helpful when debugging. :))

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

    Thank you, fixed.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to solve modified version of D i.e. if we can Remove at most K element. problem_link

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

        Firstly, try to find the longest increasing subarray without removing any of the element from the array. assign the maximum to variable ans. After that find the length of the longest increasing subarray ending at position i(from 0 to i), and length of the longest decreasing subarray from ending i.e. n-1 position to position i. store the lengths in two seperate arrays dp1,dp2 respectively. Then try to delete elements one by one from i = 1 to n-2 (we won't try deleting element at i = 0 or i = n-1 because it will not increase the length if we did so). If, we delete element at position i then we check if(a[i-1] < a[i+1]) then ans = max(ans,dp1[i-1]+dp2[i+1]) which basically means we are joining the maximum increasing left subarray ending at position i-1 to the maximum increasing right subarray starting at position i+1 subarray. EDIT : I did not read the problem carefully.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          He is asking for the modified version, ie, suppose if we can remove at most K elements.

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

        Can this solution here be generalised by maintaining k+1 arrays?

        Solution link Can you look and get something? alokjnvl41

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          During the contest I have solved this problem by exactly same method you have discussed here_mine_one.
          And you know maintaining k+1 arrays sounds difficult/lengthy if K is of range 1000 or more.
          Actually I am having an idea just wanted to know others opinion.....

          My thought(might be wrong/modification might be needed)

          following with our previous method(I.e. maintain two arrays dp1 and dp2. Here dp1[i] denotes the length of longest subarray(without any deletion) ending at ith index and ith element inclusion is must, and dp2[i] denotes the length of longest subarray ending at ith index with at most k deleted element ith element inclusion is must. In previos case k was 1)
          Now just create an additional 3rd array say dp3 s.t dp3[i]= no of element deleted till now for dp2[i] result. And by this result we can construct for dp2[i+1] by looking at dp3[i] I.e. if no of deleted element at ith position is less than k then we still can delete otherwise not.

          I think we can do this by this method. or correct me if something else/extra needed.

»
7 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

I didn't get the idea of why inversing the graph works

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it +12 Vote: I do not like it

    Okay, so let us put it this way. Let's consider the normal graph where you can go from an index $$$i$$$ to an index $$$j$$$. And you add an edge between $$$i$$$ and $$$j$$$ only if the values at those indices are of same [CORRECTED] parity, right, else you could simply put the answer for index $$$i$$$ as 1 and proceed for the other indices. Now we have a graph with out-going edges (from $$$i$$$ to $$$j$$$ means an out-going edge). It is clear that answer for index $$$i$$$ will be one more that the answer for index $$$j$$$, as $$$i$$$ and $$$j$$$ house the same parity elements, and you can go from $$$i$$$ to $$$j$$$ (if you can also go from $$$j$$$ to $$$i$$$ that's a different scene, not considering it here).

    For answer to exist for indices $$$j$$$ and $$$i$$$, there should be a path from $$$j$$$ to some index (maybe through a series of other same parity elements) with the opposite parity as $$$a[i]$$$, (this has to hold for a possible solution, i.e. two opposite parity reachable in one step values of array should exist). Say that index is $$$k$$$ and it came after traversing a path from $$$i$$$ to $$$j$$$ to some series of other indices of same parity as $$$a[i]$$$. This index $$$k$$$ goes to the queue as it is the source for all the elements coming to it.

    So, if you build the normal graph, that is add edge to k, not from k, during bfs, you won't go anywhere from $$$k$$$ (atleast not towards the indices $$$i$$$, $$$j$$$ and others on path from them to $$$k$$$). Hence building the normal graph fails to give a solution. (One may think of using DFS with the normal graph, but DFS doesn't guarantee a shortest path, and dealing with cycles will become very terrible)

    Thus building the inverted graph ensures that you start from a source (here $$$k$$$), and go back to the nodes you used to reach the source (here $$$k$$$)

    Spoiler

    Hope this helps !!

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you

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

      Or more simply put ; updation of ans[node] happens via dfs only in the back-track move of the dfs.

      It looks something like :

      for ( auto to : graph[node] ) 
      {
           if ( vis[to] == false ) 
                dfs ( to ) ; 
           ans[node] = min ( ans[node] , ans[to] + 1 ) ; 
      }
      

      So whatever we do ; we update answer only in the backtrack move of dfs. And if now we need to do something via BFS ( And keeping in mind that BFS is not a recursive algo ) ; its tough even to write a back-track.

      Hence its better to inverse the graph first ; and then proceed with BFS for the same purpose...

      This is highly informal way to explaining ; hope it helps biannaib

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

        Since you're mentioning dfs here, I am curious as to whether it can be solved using dfs or any modification of that? ritesh1340

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
          Rev. 4   Vote: I like it 0 Vote: I do not like it

          No I don't think that this problem can be solved via dfs ; because dfs is what I tried in the actual contest ; but I failed to receive an AC.

          Then actually I was confused as to why was I going wrong. By that time the editorial was not out ; so we were discussing the problems on the announcement page.

          Why I thought of dfs and how I came to know that it will not work can be found HERE. Special thanks to hellomoto

          After hellomoto explained that what is the problem in the logic ; I took several other attempts trying to make something out of dfs only ; however all of them failed...

          Some of those attempts I can share — My contest submission

          My first attempt after realizing mistake

          Attempt 2

          Attempt 3

          So after trying enough ; most probably ; I think it can't be solved via dfs ( Or maybe some cool person reads this and suggests some better way on dfs itself ).

          So then I finally shifted to learn the concept provided in editorial ; and it gave me AC

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

            The main issue with the DFS was that there might be back-edges in the dfs-trees ( or essentially, cycles) and hence the updates would probably be impossible.

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

              Yes ! And thus in my remaining attempts ; when I understood what was happening ; I tried to re-run dfs on the nodes that were not relaxed ( on nodes for which ( ans[i] = inf ).

              I had the intution before-hand that there can be many such nodes ; and it was highly probable that such solution could time out ( As it did on test case 12 ) ; but still it was worth a try.

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

            $$$DFS$$$ works but will result in a TLE verdict. The problem is, in $$$DFS$$$ we may have to update each vertex more than one time (refer to $$$dp[u]$$$ in my code). This is not true in $$$BFS$$$, since its property is to expand the calculated vertices step by step, each $$$dp[u]$$$ is calculated only once and thus achieving $$$O(n)$$$ complexity.

            My DFS submission got TLE on test 19

            My BFS submission got AC

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

              Yeah... an already relaxed vertex using some dfs can be relaxed more...

              Hence we will return to the same node more than once...

              But in BFS ; only one relaxation is enough to update dp[u] ; hence BFS ensures a strict O(n) time ; whereas time of DFS will depend on the structure of the graph ; it will pass a few graphs... but will time out !

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

      Nice explanation. By the way, do you know similar problems where you need to invert the graph to solve it? :)

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

        Finding strongly connected components in a directed graph :)

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

      Thank you for such a detailed explanation. But I dare to assume there is a mistake: "And you add an edge between i and j only if the values at those indices are of opposite parity, right, else you could simply put the answer for index i as 1 and proceed for the other indices." Should it be "if the values at those indices are of same parity" instead of "opposite"?

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

        Ah right, didn't realize the mistake earlier. Edge will be between indices having same parity elements. FIXED !!

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

    Yet another pattern of reasoning for this might be the following one: We do not know what the shortest distances from, e.g. even-to-odd nodes are (we are asked to find them), but we know for sure that the shortest distances from odd nodes to odd nodes are all 0s.

    Based on that we traverse the graph backwards to get the final answers for even nodes. Repeat the same for odd-to-even nodes. Took me a while to understand this.

»
7 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

In F problem in the tutorial its written that bal can have max length 200 , ok no problem but then in code why have we taken bal as 2*N shouldnt it be just N or say to be on a safe side N+5

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

    It can be $$$N$$$, I just wrote the solution earlier than editorial and didn't notice that I used $$$2N$$$ instead of $$$N$$$ in the code.

»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

In problem A answer is just max(|A-B|+|A-C|+|B-C|-4, 0). I don't know why, but it's true.

Also problem D could be solved with dynamic programming. Let dp[i][0] be the answer for prefix i, and the element wasn't erased. dp[i][1] — the answer for prefix i, element was erased. Formula is:

1) if (a[i-2]<a[i]) dp[i][1]=max(dp[i][1],dp[i-2][0]+1); (if element i-1 was deleted).

2) if (a[i-1]<a[i]) dp[i][0]=max(dp[i][0],dp[i-1][0]+1), dp[i][1]=max(dp[i][1],dp[i-1][1]+1); (everything is good, answer is growing).

3) if (a[i-1]>=a[i]) dp[i][0]=max(dp[i][0],1LL), dp[i][1]=max(dp[i][1],1LL);

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

    Do you mean dp[i][1] is the maximum length of subarray of the prefix until index i, after an element between 0 and i inclusive has been deleted?

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, but not between 0 and i inclusive, but between 0 and i-1 inclusive.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ah, I understand the solution now, thanks.

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

    For problem a, let's assume that a <= b <= c, so |A-B|+|A-C|+|B-C| is equal to 2 * |A-C|.

    so we just need to consider the value of |A-C|.

    If |A-C| <= 2 then you can always move point a, b, c to a same point, temp answer is 0.

    If |A-C| >= 3 then the minimun temp answer is |A-C|-2.

    temp answer times 2 is the answer.

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

    It is because |A-B|+|B-C|+|C-A| represent twice the length of the line joining the three points on number line. You can think of this problem as trying to shorten the length of the line. Since you can move the endpoints at most 1 unit towards each other, you can at at most shorten the length by 2 units. Now, since the answer asks for twice of length of the new line segment, the answer is basically oldLength — 4, which is equal to |A-B| + |B-C| + |C-A| — 4. But we are missing one case, when the length is less than or equal to 2, we can simply reduce the line to a single point. So the answer simply becomes max(2 * oldLength — 4, 0).

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

    In problem A, assume a<=b<=c, the pairwise sum=(|b-a|+|c-b|+|c-a|). Now since a<=b<=c, we can open the absolute/mod signs, therefore sum=(b-a+c-b+c-a)=2*(c-a). Now we have to minimize 2*(c-a), so we increase a by 1 and decrease c by 1, therefore minimized sum=2*((c-1)-(a+1))=2*(c-a-2). Now we have to handle 2 cases, when (c-a)=1 and c=b=a, in both the case answer will be 0. My submisiion: 66774673

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wind_Yatagarasu i solved it using iterative approach . But How to solve using recursive dp ?? i've been getting stuck while thinking how many state i've to assume in recursive approach .. Please help . It would be the best if you provide a code of recursive approach . Thanks .

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

I am not able to understand problem F's solution i know dp will be used but still Can somebody please give a well comented solution describing each step , why its done please

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

    Vovuh please reply to this as well
    ༼ つ ◕_◕ ༽つ

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    I can try explaining,

    Let's forget about bracket sequences and just construct a string $$$A$$$ that is a supersequence of these two strings $$$S$$$ and $$$T$$$ ($$$A$$$ contains both $$$S$$$ and $$$T$$$ as a subsequence). This problem can be solved with following DP: compute shortest supersequence for all possible pairs of prefixes $$$S'$$$ and $$$T'$$$. Instead of storing explicit strings we store lengths of matched prefixes and length of resulting sequence. Let $$$dp_{i,j}$$$ be minimum possible length of supersequence for prefix $$$S'$$$ with length $$$i$$$ and prefix $$$T$$$ with length $$$j$$$. For empty prefixes empty string matches both $$$dp_{0,0} = 0$$$. Suppose we have have calculated $$$dp_{i,j}$$$, now we can append new character $$$c$$$ to the end of this string, length of the string will be increased by $$$1$$$, and size of matched prefixes also can be increased by $$$1$$$, it depends whether new character is equal to first unmatched character in strings: $$$i$$$ will increase if $$$S_i = c$$$ and $$$j$$$ will increase if $$$T_j = c$$$. This works in $$$\mathcal{O}(|S| \cdot |T|)$$$.

    Now coming to the fact that we have bracket sequences instead of arbitrary strings. Bracket sequences have a concept of balance, I will call it depth. This is actually amount of opened but not yet closed brackets (difference of opened and closed brackets). For some bracket sequence to be correct, balance of any prefix must be non-negative (we cannot put more closing brackets than opening) and must be $$$0$$$ at the end (each opening bracket must have a pair of closing one). Sequence properties as a prefixes only depend on it's depth. So we can add one more parameter to our DP, let $$$dp_{i,j,d}$$$ be length of shortest correct supersequence for prefix $$$S'$$$ with length $$$i$$$ and prefix $$$T$$$ with length $$$j$$$ with depth equal to $$$d$$$.

    So we actually need to store this information about prefixes and be able to continue any prefix with either opening bracket or closing bracket (if it is possible). Generally we say that empty string has depth $$$0$$$ and matches empty prefixes: $$$dp_{0,0,0} = 0$$$. All other states are not calculated yet. Then we can extend all states with ( and ) possibly getting to new states and updating these states. About order of calculations: each extension increases length of sequence by $$$1$$$, and as we are seeking for minimum there is no point trying to update some states that already have a lower value than current state. So we can do this process in BFS-style. Firstly use $$$0$$$-result state to find all states that can have result of $$$1$$$. Then use all $$$1$$$-result states to get all possible $$$2-$$$result states, etc. Depth parameter $$$d$$$ can be safely capped at $$$max(|S|, |T|) = 200$$$, if we just concatenate sequences we can get sequence with depth $$$|S| + |T|$$$, but when both strings have large amount of opening (or closing) brackets they will be matched simultaneously.

    Answer will be stored in $$$dp_{n,m,0}$$$. Minimum-length supersequence that has zero bracket depth and completely matches both sequences $$$S$$$ and $$$T$$$.

    Also we need to actually restore the answer: for each state we can save last character and another DP state that was preceding for current state (last state that was successfully extended to current one), then restore string one character at a time: add last character to the answer and move to previous state until you get to $$$dp_{0,0,0}$$$.

    So we get $$$\mathcal{O}(|S| \cdot |T| \cdot \max(|S|, |T|))$$$

    Here is my solution 66725721 . All the logics of state extension is incapsulated into state struct.

    Firstly, it prepares all the DP states to have not-reached-yet status and $$$dp_{0,0,0}$$$ to be the starting point and the only state with $$$0$$$ result. Then it starts the process, at step $$$k$$$ of the process all states with result equal $$$k$$$ are extended forming list of states that are $$$(k+1)$$$-result states and putting them into next list. When all states are processed target state $$$dp_{n,m,0}$$$ must be reached. We can start recovering answer starting at the end and moving to a previous state character by character.

    Hope it helps.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot (∩_∩)

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

      What is S = 228 in your code? And why 228? Also, there are mentions of using BFS in DP, and of backtracking also. Could anyone explain what they are referring to here?

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

        Constant S is actually shorthand for Size and refers to general size of arrays in solution. So, it is used as three dimensions of $$$dp$$$ array. Constant SL stands for SizeLarge and represents amount of waves in BFS-like algorithm.

        Why exactly $$$228$$$ and what is it? I don't think that this number is somewhat specific. I've used this just as a number that is not much greater than $$$max(|S|, |T|)$$$. Just added some reserved elements to make sure that I can use some prefix of $$$\{n, n+1, n+2, \dots\}$$$ indexes if some of them are needed. Why not usual (at least for me usual) $$$200+5$$$? That was chosen at very early stages of solution, when I wasn't sure in all the details. For some non-important reason I've chosen to have more additional elements than usual and $$$228$$$ was the first number that come to my mind. Just as $$$SL = 10 \cdot S$$$ is much greater than actually needed: $$$3 \cdot S$$$ or even $$$2 \cdot S$$$ would've been enough. Overall solution turned out to be memory-hungry, so these extra limits put it dangerously close to MLE (480+ MB, but it is easy to optimize if needed).

        Short story of 228, not related to programming at all

        BFS part of the solution is loop that starts in line $$$102$$$:

        for (int len = 0; len+1 < SL; len++) {
        

        It passes layer by layer forming next layers, where each layer contains all DP states that have result equal to len.

        Backtracking part comes right after BFS part, starting at line $$$148$$$. It starts from position $$$dp_{n,m,0}$$$. And uses backtracking information of $$$dp$$$ states:

        state::last
        state::prev_pa
        state::prev_pb
        state::prev_depth
        

        These are used to put one bracket into answer and move to previous state that allows to put one last character to the answer and move further backwards.

        Hope it helps.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In the tutorial for problem D, the explanations for array l and r seem to be swapped. li records the max length of increasing sequence ending at i and ri records the max length of increasing sequence starting at i. This way the explanations would be coherent with the code.

Otherwise, the final update can be changed into li+1 + ri-1

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, the code and explanation differ. The remove at ith index part needs to be swapped.

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

Can we do E with DFS? I tried solving it but getting wrong answer 66719636. My approach:-
Suppose dp[i][odd/even] represents the distance of odd/even bit from the ith element.
Do dfs and update the result.


if(child is even){ dp[parent][even]=1; } else if(dp[child][even]!=INT_MAX) dp[parent][even]=min(dp[parent][even],dp[child][even]+1); if(child is odd){ dp[parent][odd]=1; } else if(dp[child][odd]!=INT_MAX) dp[parent][odd]=min(dp[parent][odd],dp[child][odd]+1);

But the problem is with the case when there is loop, like A->B->A. First I go from A to B. Then since I have already visited A, then I try to update my results for B. But since I have not got the final answer for A(as it is still in the stack), my answer for B will be wrong.
Can anyone help me how can I overcome this problem??

»
7 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

My CF predictor was showing +10..But after the hacking in my rank decrease -10... :( Can anyone tell me what is the problem...Is CF predictor is wrong??

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

My solution over problem 'A' was a bit different. I think it will be proved that the amount we are trying to minimize is being lowered only '4' units for each query and we only need to output max (0 , |a-b| + |b-c| + |a-c| — 4) p.s:This solution passed the test data :)

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved it the same way although it took me some time to find it. Thats why I think the best solutions is bruteforce.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain a DP approach to problem D. PLZZ

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I had a slightly different approach for question D. I had first calculated the array dp[n] where dp[i] holds the longest increasing subarray ending at i. The next thing I did was to find all the endpoints of the blocks of increasing subarrays. One can prove that the answer to the question is the max of the following two cases: 1. The maximum value in dp. 2. The maximum value of dp[endpts[i]]+dp[endpts[i+1]]-1. There are two possibilities in this case,removing the last element of the current block and joining the current block with the next, or doing the same by removing the first element of the next block. Of course we must run the check that the pair of elements crossing the two resultant blocks after removal of an element are still strictly increasing. Submission for reference: Submission #66717570.

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

An alternative solution for D, using DP, is as follows : Store two arrays subs and subs_rem, indexed with 0. Here subs[i] denotes the length of longest subarray ending at ith index, and subs_rem[i] denotes the length of longest subarray ending at ith index with a deleted element, whose index <= i-1.

subs[0] = 1; subs_rem[0] = 0;

Also, subs[i] can be calculated easily using dp. For subs_rem[i] do the following: Knowing subs[i], we know the index j from which the longest subsequence ending at i begins.

Giving some thought, we realise that the only two elements which can be deleted and the length of sequence would grow, is either jth element or (j-1)th element.

Two cases arise:

  1. Suppose j-1 and j-2 are both indexes of the array(j-2 >= 0), this means that a[j] <= a[j-1] , where a array is 0 indexed, if a[j] > a[j-2] then we could remove the a[j-1] and then val1 = subs[i]+subs[j-2]; , since we have already deleted a[j-1] element no other element can be deleted.

  2. Again suppose j-1 and j+1 are both indexes of the array(j+1 <= i and j-1 >= 0), this means again that a[j] <= a[j-1], if a[j-1] < a[j+1] then we could remove the a[j] element and then val2 = subs[i]-1+subs[j-1]; , since we have already deleted a[j] element no other element can be deleted.

Now, subs_rem[i] = max(val1,val2,1); 1 because we could simply delete the a[i-1] element. The final answer is the max of all values of subs array and subs_rem array.

My implementation here : 66725589

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And I missed the second case during the contest and hence messed up :(

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

66806946 for D is incorrect, and it's giving me some funny errors (I understand my WA error, but not the uninitiaized value usage on the line 32) Can anyone explain what's going on?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In the writer's solution of F, he/she restores the answer string by the memo when he/she calculated DP table. can I restore the answer string only by its recurrence's transition? For example, dp[i][j] = min(dp[i — 1][j] + x, dp[i][j — 1] + y) is the target. Only using its recurrence's transition means that finding the before situation of dp[i][j] is by checking both dp[i — 1][j] + x == dp[i][j] and dp[i][j — 1] + y == dp[i][j], and decides the correct before situation(satisfied the either equals). If both of them are OK, I can choose any of them. In this way to restore, can I accept problem F?

»
7 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone explain problem E??

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

    To find the minimum number of moves of opposite parity. We construct a graph(g) in the following manner.

    g[i] is a vector containing all indexes which reaches to position i in one move only. Now we traverse the graph(for odd and even values separately).

    For instance, traversing with odd values.

    First push all the nodes in a queue. Now while traversing the graph if any even value node is encountered. Then the number of moves required = number of moves required by the parent + 1 and then push it into the queue. In this process all the even nodes with moves required 1 is encountered first, then 2,3,4.....

    Same is done for the even value nodes.

    For better understanding refer to my solution. link

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me the issue with my code for PROBLEM C . I used a similar logic but implementation is a bit different from the editorial. Submission : 66825640 It gives a wrong answer for test case 12 ( n = 2*10^5 ) .

int main() {

#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif

int l,k ;      cin>>l>>k;
string s;      cin>>s;

map <char,int> m ;
char a= 'a';
for(int j=0;j<26;++j)
{  
    m[a] =0;
    a++;
}

for(int i=0;i<k;++i)
{
    cin>>a;
    m[a]=1;
}

ll n=0 ; // max useful substring length 
ll ans =0;
for(int i=0;i<l;++i)
{
    if( m[s[i]]  )
       n++;
    else
    {
       ans += n* 1ll * (n+1) /2 ;
       n=0;
    }

}
ans += n* 1ll * (n+1) /2 ;
cout<<ans<<endl;

return 0;

}

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem A, why the answer (|A-B|+|A-C|+|B-C|-4, 0) is true? How come the solution is this? I dont understand how it's deduced?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to solve problem E using DP (DP is not there in the problem tags) ?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I guess the tutorial for problem D has a mistake. Where it's said "The array l can be calculated in order from right to left ". I think array l should be calculated from left to right and array r vice versa.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, it is correct. Think once again. Unless, you see the elements on the right side of the index i, you can't compute l[i] that is why you compute l[i] by traversing the array from the right to the left.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the working of D.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem F is very good in the sense that this was the first time i calculated dp using bfs.

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

I am getting wrong answer in test case 4 in problem D Here is my code, What am i doing wrong?

include<bits/stdc++.h> typedef long long int ll; typedef unsigned long long int ull; define fast ios_base::sync_with_stdio(false);cin.tie(NULL); using namespace std; int main() { fast; // your code goes here ll n; cin>>n; vector v(n); for(ll i=0;i<n;i++) { cin>>v[i]; } vector dp(n,0); dp[n-1]=1; if(v[n-2]<v[n-1]) dp[n-2]=2; else dp[n-2]=1; ll maxi=max(dp[n-1],dp[n-2]); for(ll i=n-3;i>=0;i--) { dp[i]=(v[i+1]>v[i])?dp[i+1]+1:1; dp[i]=max(dp[i],(v[i+2]>v[i])?dp[i+2]+1:dp[i]); maxi=max(maxi,dp[i]); } cout<<maxi; return 0; }

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, I have traversed the list and found out the length of the subsequence by removing at most 1 element and at end of the subsequence, started to search for another subsequence from the element which i removed in the previous iteration. Here is the code https://ideone.com/xL5oax. Can someone please help me understand the fault in my logic?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In c problem, the time complexity is O(n*k) right???

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

In the problem C — Yet Another Broken Keyboard

The solution is correct but memory limit keeps exceeding. I don't think it should.

My Submission

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

    The problem is in this part: // Generate substrings for(int i=0; i<n; i++){ for(int j=1; j<=n-i;j++){ subs.PB(s.substr(i,j)); } }

    According to the task, n can be as large as 2*10^5. The total number of substrings is n*(n+1)/2. Thus, you need to generate about 10^10 of substrings. Even if one substring takes 1 byte of memory, you need 10^10 bytes which is about 10 gigabytes.

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

      Thanks for the answer. I solved the question using the approach mentioned in the tutorials. But I didn't knew the reason behind my submission exceeding memory limit. Thanks for explaining.

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

Can anyone provde solution for problem D with dp? :)

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

Need dp idea for Problem C.

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

Thanks for a definitive editorial!

Minor problem E note: I was confused by a variable name in bfs function: for (auto to : g[v]). Shouldn't it be from instead of to? Since we are dealing with the inverse graph here. So mentally you would read it as iterate over vertices _from_ which we can go to vertex v