Блог пользователя vovuh

Автор vovuh, история, 4 года назад, перевод, По-русски

Все идеи, кроме задачи C, принадлежат MikeMirzayanov. Автор задачи C — Rox.

Отдельное спасибо _overrated_ за неоценимую помощь в подготовке раунда!

1272A - Три друга

Разбор
Решение

1272B - Робот-cнегоход

Разбор
Решение

1272C - Очередная сломанная клавиатура

Разбор
Решение

1272D - Удалите один элемент

Разбор
Решение

1272E - Ближайшая противоположная четность

Разбор
Решение

1272F - Две скобочные последовательности

Разбор
Решение
Разбор задач Codeforces Round 605 (Div. 3)
  • Проголосовать: нравится
  • +61
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

Not hard, but still nice problems with nice solutions.

»
4 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Thank you, fixed.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        Solution link Can you look and get something? Trgt_2021_explosion

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

          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

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится

              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.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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 !

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      1272E - Nearest Opposite Parity ->

      Could you please tell where am i going wrong in this question

      80077469

      Thanks in advance.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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?

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

    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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +22 Проголосовать: не нравится

    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.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can anyone explain problem E??

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Блин, я не допёр, что в 1272E мало рёбер и можно было запускать обычную Дейкстру, а не вспоминать ускоренную. Спасибо за разбор. Реально помогает

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В разборе задачи D, мне кажется что вы перепутали, кое — что: "Массив l может быть посчитан слева направо со следующим условием: ...", наоборот, массив l мы считаем справа налево, ведь это длина максимальной возр. подпосл. которая начинается в позиции i , а массив r слева направо.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    И ответ мы обновляем r[i — 1] + l[i + 1], а не наоборот. Исправьте, если я не прав.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В задаче E можно просто смотреть какое наибольшее количество сначала ( идёт у обоих строк с начала этих строк до первой ) и то же самое с ). Затем найти максимум их этих двух величин и вывести ( и) соответствущее количество раз и обрезать эти две строки до указателей которыми мы прошлись. Итого O(|s|+|t|)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Dp solution of D ( recursive ) submission

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain, why we can not apply recursion in problem E. I have tried applying it but got wrong ans at testcase 2. I am not able to understand what is happening. If someone can give a shorter testcase which proves my submission is wrong. That would be really helpful. Thanks Here is my submission:- https://codeforces.com/contest/1272/submission/82418760

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can E be solved with DP? https://codeforces.com/contest/1272/submission/88624220 Can't figure out what is wrong, even if there is a cyclic dependency (idx i depends on idx A and A depends on i), I think this should work