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

Автор isaf27, история, 4 года назад, По-английски

The problems A, C, D, G are authored and prepared by isaf27.

The problems B, E, F are authored and prepared by 300iq.

Tutorial is loading...

Jury solution: link

Tutorial is loading...

Jury solution: link

Tutorial is loading...

Jury solution: link

Tutorial is loading...

Jury solution: link

Tutorial is loading...

Jury solution: link

Tutorial is loading...

Jury solution: link

Tutorial is loading...

Jury solution: link

Let's discuss your ideas and solutions in the comments. Thanks for your participation!

Разбор задач Codeforces Global Round 7
  • Проголосовать: нравится
  • +315
  • Проголосовать: не нравится

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

Thanks for the fast editorial ! :)

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

Thanks for Editorial giving so fast

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

For the jury solution of D, on line 41, shouldn't the substring be from L to size — L, not from L to size — 2 * L?

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

    In the C++ substring function, the arguments are (start index, length), not (start index, end index). Since we trim a prefix and a suffix of length L from the string, the length should in fact be size — 2 * L.

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

can anyone give me detailed explanation of E?
Thanks in advance!!

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

    I get the conclusion in the tutorial by Hall Theorem during the contest.

    This is my understanding: To check whether answer is $$$x$$$, we consider the largest $$$n-x$$$ number, and link edges to the bombs on it right, so we need to check whether there is a perfect match. According to Hall Theorem, every subset of these number $$$A$$$, and it links bombs set $$$B$$$, $$$|A| \le |B|$$$. Actually, we do not need to check all the subset, we only need to check all the suffixs, and this is the conclusion in the tutorial. And you can see, if all the suffixs satisfy this condition, all the subset also satisfy it.

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

      Can you please give some detail into how actually segment trees can be used to check the condition? I mean what are we actually maintaining in the nodes and how are we using it?

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

        The check condition is:

        There is at least $$$1$$$ bomb after the rightmost value which is $$$\ge n - x$$$.

        There are at least $$$2$$$ bombs after the next rightmost value which is $$$\ge n - x$$$.

        ...

        There are at least $$$x$$$ bombs after the $$$x$$$-th rightmost value which is $$$\ge n - x$$$.

        So each of the key position $$$p$$$ whose value is $$$\ge n-x$$$ should satisfy that the number of suffix key position is larger than the number of suffix bombs. We minus these two suffix sum, and in each node of segment tree, we actually maintain the number of suffix bombs minus the number of suffix key position.

        When we add a bomb at $$$q$$$, all the value in $$$[1, q]$$$ should $$$+1$$$. When we try to add a key position $$$p$$$, all the value in $$$[1,p]$$$ should $$$-1$$$. And if some position's value is negative, check failed. So we only need to maintain global minimum.

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

Can anyone please give a detailed explanation of D? Thanks.

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

    I divided question into two parts

    1.Till how much prefix and suffix are same

    2.Using manchers algorithm find longest palindrome at each point

    Then for each index check if it touches with common prefix points and it's your solution.

    My Solution — 74734509

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

Can someone explain the given solution for 1326D2 — Prefix-Suffix Palindrome (Hard version). For example, if the input string is "xkcddckyyx", the answer should be "xkcddckx" a="xkcddck" and b="x", can somebody explain how you will reach the value of 'k' ( k is given in the solution above) here?

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

    First try understanding that for every $$$x <= k$$$, the string $$$s[1..x]$$$ is equal to reverse of string $$$s[n-x..n]$$$, and for any other $$$x > k$$$ the string $$$s[1..x]$$$ is not equal to reverse of string $$$s[n-x..n]$$$. So that lets iterate over $$$i$$$ from 1 to $$$n/2$$$, if the strings were equal, then $$$k >= i$$$, otherwise $$$k < i$$$, it can be done in $$$O(n)$$$, if $$$s_i == s_{n-i+1}$$$ then just continue iterating, otherwise break the loop, $$$k$$$ will be the biggest $$$i$$$ before breaking.

    Now we have $$$k$$$, try finding maximum palindrome prefix and maximum palindrome suffix using prefix-function(or hashing) on string $$$w = s[k+1..n-k] + "*" + rs[k+1..n-k]$$$, where $$$rs$$$ is the reverse of string $$$s$$$.

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

      And would you please explain the prefix function?

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

        For this algorithm, i really recommend cp-algorithm, the site is very useful in lots of competitive programing topics, specially it's prefix-function. I used the same code as cp-algorithm in my solution.

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

          Same;)

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

          Thanks for the link ! but there is no explanation for why the complexity is O(n). Would you explain it ?

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

            I did the same question with Z-function, you can see its asymptotic behavior (proof) of O(n) in this blog — https://cp-algorithms.com/string/z-function.html

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

            Let me explain why its $$$O(n)$$$, first you should know that the prefix-function wont increase more than 1 each time, i mean there is no $$$i$$$ such that $$$pi_{i+1} > pi_i+1$$$, the value names came from cp-algorithms implementation. So $$$pi$$$ will increase at must 1 in each step, so the maximum number of increases we can have is $$$n$$$, so we cant decrease our value more than $$$n$$$ times at most, because we have to keep them non-negative and $$$pi_1$$$ is zero and also $$$pi$$$ increase at most 1, then for $$$i$$$ such that $$$pi_i$$$ is grater or equal to $$$pi_{i+1}$$$, we have to perform 1-2 action(s), but for $$$i$$$ such that $$$pi_i > pi_{i+1}$$$, we have to perform more than 2 actions(at most $$$pi_i - pi_{i+1}$$$ actions), as i said above, we cant decrease more than $$$n$$$ times(i.e sum of $$$pi_i - pi_{i+1}$$$ over every $$$i$$$ in range $$$1..{n-1}$$$ is at must $$$n$$$. So we have to perform at most $$$O(n)$$$ actions.

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

          Could you please tell where my code fails i am not able to debug it :( https://codeforces.com/contest/1326/submission/73832292

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

        You can find an extensive explanation for prefix function here : https://youtu.be/nJbNe0Yzjhw

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

      w = s[k+1..n−k] + "∗" + rs[k+1..n−k]

      What is the use of "*"?

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

        Split the string into two part, after the operation, there will not exist a palindrome cross two independent parts.

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

      How to prove that it is optimal to take such k and then find longest palindromic prefix on remaining string. I don't understand statement from editorial.

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

      deleted

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

        For example: string s: "aybxpbtdtbya" if you choose prefix:"ay" and suffix:"ya" then take the suffix string:"btdtb" from the remaining string:"bxpbtdtb"

        then you can see that if you choose prefix:"ayb" and suffix:"bya" then take the suffix string "tdt" from the remaining string:"xpbtdt"

        the results are same. so you can simply choose the same character from the prefix and suffix and it has no effect to the answer

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

      can you tell me why doesn't it works if we set w = reverse(s) and why it works when we set w = s + "#' + reverse(s) ?

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

        For example when $$$s = "aaaaaa"$$$, then we use a character(like '#' or '*') to limit the prefix-function.

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

          what do you mean by limit the prefix function? what my understanding is we are using delimiter to reset the matching count to 0 and start matching on the reversed part of string. so can't we just set s to reverse(s)?

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

In the third question, the explanation for the third test case seems to be wrong which was quite confusing.

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

May be its too basic, but I couldn't understand the mathematics behind solution of problem A. Can anyone explain how this works? I know this solution will work but unable to know how to come up with this solution

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

    We will form the number with just 2s and 3s, For a number to be divisible by 2, it should have 2 at the end. So we will keep 3 at the end. Thus it is not divisible by 2 now. For a number to be divisible by 3, its digit's sum should be divisible by 3. So sum of digits of our number is of the form 3k + 2, which can never be divisible by 3 for any value of k.

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

    It's probably just some guess work. The way I thought about it is that instead of thinking of a lot of digits, why can't we just have a lot of digits which keep repeating? This highly simplifies your solution space. So suppose your number has only one digit, let's say a; then your number is aaaa....aaa but in that case, it is divisible by a. That means, we should think of having two digits in the number. Clearly 1 can't be a digit. What else do we have? If we take 2 as one of the digits, the other digit can be 3(as in the solution) or 5 or 9. I hope this gives you some form of intuition in regard to the problem.

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

    233...33, is not divisible by 2 as number must end with 2 to be divisible by 2 and number is also not divisible by 3 as the sum of digits is never gonna divisible by 3 as it always short by 1 number.

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

    There is another AC solution. We just need to write n-1 times ‘9’ and at the end we should write ‘8’. Why this works? Because of rule of divisor 8 (find it yourself, my English level not good enough to explain my thoughts).

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

    I intuitively think it's OK to just choose an odd number and an even number. For example, "2.... 3" or "4.... 3" or "5.... 8" or "8.... 9". Can anyone prove it?

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

      3 out of the 4 you gave are counterexamples lol

      2223 % 3 = 0, 4443 % 3 = 0, 8888888889 % 9 = 0

      ending in 3, 6, and 9 all don't work cus of the same reason :(

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

        They aren't counter examples 23333 43333 89999 Just repeat the other digit.

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

          Yes, I think so. But I don't have enough mathematical knowledge to prove that it's right, so it's my guess.

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

            oh my bad, then ending in 3, 6, and 9 will always work, since the sum of digits will have a nonzero remainder mod 3, unless the first digit is also divisible by 3

            ending in 1, 2, 4, 5, and 8 don't work and idk about 7

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

              ending with 4 also works. Divisibility Test of 4:

              Let a number $$$N$$$ represent in digits as follows: a[1] a[2] a[3].... a[k-1] a[k];

              then $$$N$$$ is divisible by 4 if and only if 10*a[k-1] + a[k] is divisible by 4

              Thus Numbers ending with 14, 34, 54, 74, and 94 are not divisible by 4. Now repeat any odd digit and that's the answer.

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

Can someone pls explain how the second part of problem C is done?? i mean why ai+1-ai works here in finding number of segments?

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

    Let's denote the places of the largest elements by stars, and the other elements by dashes. For example, it might look like:

    --*--**--*-
    

    Then our goal is to count the number of ways to add dividers that split up all the stars. For example:

    --*-|-*|*--|*-
    

    The i-th divider must be between $$$a_{i}$$$ and $$$a_{i+1},$$$ so it has $$$a_{i+1}-a_i$$$ places it can go. The choices for all dividers are independent, so we multiply all these numbers together.

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

      Hey Monogon, thanks for the solution, that is pretty intuitive! Would you suggest similar problems as Div2C for the above one?

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

        Look at problems with the combinatorics tag and difficulty 1000-1500.

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

    Lets first solve the following problem, you have $$$n$$$ different eggs in a row, you want to take a prefix from eggs(probably empty or all eggs), how many ways you can choose the prefix?, lets say that we want to choose a border and then our prefix is the eggs in the left of the border(border is just a stick between two eggs or before or after all eggs), you can choose the border in $$$n+1$$$ ways.

    Now go back to the problem $$$C$$$, its easy to see that every segment must have exactly one number bigger than to $$$n-k$$$, so lets change it a little bit, we want to find exactly $$$k-1$$$ borders, such that first border is between $$$a_1$$$ and $$$a_2$$$, second border is between $$$a_2$$$ and $$$a_3$$$ and so far, what you think the answer will be?($$$a_i$$$ is $$$ith$$$ number in the array which is bigger than $$$n-k$$$), choosing border are independent, there is exactly $$$a_{i+1} - a_i$$$ ways to choose $$$ith$$$ border.

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

I don't understand why, but problems B, C and D1 were much more intuitive to me than A was.

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

    Yeah! about that, the more one thinks the harder it gets. These first questions are really surprising these days.

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

I have slightly different approach for problem E which does not use observation in the editorial. First how to check that the answer is at least $$$x$$$? Let $$$a_i = 1$$$ if $$$p_i \ge x$$$ and $$$0$$$ otherwise. To check it in linear time go from left to right maintainng $$$cnt_1$$$ — current number of ones. If $$$a_i=1$$$ increment $$$cnt_1$$$ by one. If there is a bomb in the $$$i$$$-th cell do $$$cnt_1 = max(cnt_1 - 1, 0)$$$. If $$$cnt_1 > 0$$$ at the end then the answer is at least $$$x$$$. To solve original problem maintain current answer which equals to $$$n$$$ at the beginning, and you have two type of events : assign $$$a_i = 1$$$ and put a bomb in some cell. You can do it with segment tree storing for each node $$$cnt_1$$$ — the number of ones left at the end if we will go through this segment and $$$cnt_0$$$ — the number of times there was a bomb but there was not a one($$$cnt_1 = 0$$$). With this data we can calculate desired $$$cnt_1$$$ at the end. And as answer never increases at the beginning of each iteration decrease current answer until $$$cnt_1 > 0$$$ at the end and at the end of each iteration do an update of the bomb.

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

    Your solution is very intuitive. Thanks a lot.

    I noticed that bombs could be modeled as ')' and numbers greater than current ans i.e 1s as '('. Now this question is similar to regular bracket sequence.

    I was getting WA earlier as I was using -1 for bombs earlier. But this bomb cancels even numbers on the right. Hence we needed to maintain two values in the segment tree.

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

    ABalobanov, can you provide a link to your submission? I'm having trouble understanding how the segment tree is maintained. Specifically, what information is stored at each index?

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

      Here's my submission 73741605. To calculate amount of ones left at the end we should also store another value — the number of times there was a bomb but there was not a one. We should do it because we do not decrease number of ones if there are no of them. So we store these two values in every node of the segment tree. And with this information we can calculate these values in the node using values in it's left and right child. You can see how to do it in my code. Ask if you have questions.

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

There is a beautiful solution to problem E using partial retroactive priority queues. In a partial retroactive priority queue, it is allowed to perform five types of operations:

  • Insert / Delete a Push(x) operation at time t;
  • Insert / Delete a Pop() operation at time t;
  • Get the smallest element inside the priority queue at present time.

Demaine describes in the following article how to implement a partial retroactive priority queue in $$$O(\lg n)$$$ time per operation.

So, you can Push all values $$$p_i$$$ inside the data structure at time $$$i$$$ and, after each bomb, insert a Pop operation at time $$$q_i$$$.

If you want more details, you can see my code here

Ps. Thanks to Kallaseldor for the idea to solve the problem using retroactive priority queue

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

    despite of partial retroactive priority queue, can you tell me which algo i need to know to solve E as a beginner

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

Wy this submission My submission to problem D2 gives TLE if the complexity is O (n)

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

    Instead of doing this

    p = p + s[i];
    pp = s[j] + pp;
    

    Try doing this :

    p += s[i];
    pp += s[j];
    reverse(pp.begin(),pp.end());
    

    Cuz the above operations takes O(|p|) each time you add a character, but the this method appends the characters into string taking O(1) each time you add a character to string.

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

      I thought the operation y = s [j] + y was O (1). Thank you very much I still did not find the error and it cost me 13 TLEs in the competition and in the end I could not accept it.

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

Could someone point out the idea behind solving F1 (that won't work for the harder version)? Thanks.

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

    For example this 73757219 naive recursion with memoization. calc(mask, last) calculates the answer for the rest of the men (given by mask) with last being currently the last man in the sequence. Complexity seems to be O(n*2^(2n)) with a good constant.

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

      I guess it is more like $$$\sum\limits_{k=0}^n {n \choose k}2^n$$$ which adds up to $$$3^n$$$, or at least this is number of states (for each $$$k$$$ there are $$${n \choose k}$$$ sets of $$$k$$$ men and $$$2^k$$$ possible sequences so far), time complexity might be times $$$n$$$ because transitions are in $$$O(n)$$$

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

    I ran through all of the partitions of the people by two (almost) equal groups (there are C_14^7 of them, it's around 3500).

    For the first half of every partition I pre-counted d[fin][res] – the number of ways to go through this half stopping in fin and getting a result mask equal to res.

    For the second half of every partition I pre-counted d[start][res].

    Now you can go through all of the partitions, but also through all of the end and start points and all of the result masks in every half. It works in #(partitions) * 7 * 7 * 2^6 * 2^6.

    It's too long. So we also need to pre-count d[start_mask][res] for the second half of every partition. Here start_mask is a set of vertices where you can start.

    Now once you fixed a fin you don't need to go through every start. You just need to look at the set of adjacent to fin and the set of all others. This will work in #(partitions) * 7 * 2 * 2^6 * 2^6 and gets AC.

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

In Question D2

"In order to find the longest palindrome which is a prefix of some string, a, let's find p from the prefix function of the string a+ '#' +a¯, where a¯ represents the reverse of a."

Could someone please explain what this means.

Thanks

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

    We want to find the longest prefix which is also a palindrome, lets call it string $$$a$$$(the longest palindrome prefix). What do we do now?, we use prefix-function(prefix-function is an algorithm which can find the longest prefix of a string, which is also a suffix of the string and is not equal to the string itself, in $$$O(n)$$$, you can find it in cp-algorithms). Then lets run prefix-function on string $$$s[k+1..n-k]+"|"+rs$$$, where $$$rs$$$ is reverse of string $$$s[k+1..n-k]$$$.

    Why the prefix-function's return is the longest palindrome prefix?, you can understand it yourself!!

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

KMP O(n) solution (Longest palindromic prefix)

https://discuss.interviewbit.com/t/kmp-o-n-solution-longest-palindromic-prefix/29112

Can someone please explain the logic behind the code. Thanks!!

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

    Suppose the string $$$S=AB$$$, where $$$A$$$ is a palindrome. Then the code computes the KMP array for $$$S\text{#} S'=AB\text{#} (AB)'=AB\text{#} B'A.$$$ Note that $$$A$$$ is both a prefix and a suffix of the string, and the KMP array computes the longest proper prefix that is also a suffix. That is, the last KMP array value will be at least the length of $$$A$$$.

    Conversely, suppose we have the longest prefix that is also a suffix of the string $$$S\text{#}S'.$$$ Clearly, it cannot contain the $$$\text{#}$$$, because it does not appear elsewhere in the string. So, we have the longest prefix of $$$S$$$ that is a suffix of $$$S'$$$. But these are just the same characters in reverse order, so we must have a palindrome!

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

How does CF compile c++14?

I submited problem D

On test2:

case input: q

Real Ouput: qq

my ouput: q$q.

But on my pc my output was like the real output "qq"

I didn't realize that mistake 'til, I saw the real test after contest

Help me pls.

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

    Probably your solution on your machine didn't output just "qq", but "q<some control character, which is invisible in terminal>q" and did the same on the server, which is not considered a correct answer. And if not then you have some type of undefined behaviour.

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

Can somebody tell me all the various ways of solving D2? I used string hashing, editorialist used prefix function, did anyone use any other method too?

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

Isn't 2222...29 also a possible solution for Ugly Bad Numbers?

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

Case 3 of G: Furthermore, the last edge on the path from $$$i_x$$$ to $$$i_{x+1}$$$ must equal to the first edge on the path from $$$i_{x+1}$$$ to $$$i_{x+2}$$$.

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

I don't know why a manacher alogrithm for D2 which should be O(n) get TLE. Does anyone know the reason or got AC by using it? Thank you.

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

    Could the problem be:

    memset(f,0,sizeof f);
    

    since it is resetting the entire array for every single test case?

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

Sorry to bother, but why my O(n) solution in problem B got TLE in the system test but got AC just now when I submitted exactly the same code? Could somebody please tell me the reason? Thx a lot. 73666334 73748630

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

    There isn't much difference between 982ms and 1000ms. Expect ~30ms difference. It may be due to overload on servers at that moment etc.... You soln is O(n) but input/output takes too much time here. It's close to 2MB (2^21 chars). I added this line for fast input output in your code and it runs in 124ms. 73749515

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

      Yeah thx now I get it and will be careful next time. Hope they could rejudge this submission but it's kind of unrealistic. SO SAD :(

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

    My code is similar to yours, but mine runs fast at the forth test case 73756081. Why your solution runs so slow is mainly because input/output takes too much time, as @aryanc403 said. In my code, output here is independent:

    rep(i, 1, n) cout << a[i] << " ";
    

    This will take advantage of IO buffers, which makes the compiler happy. To verify my conclusion further, I edited your code to become four versions. The first is your original code:

    cin >> n;
    rep(i, 1, n) {
    	cin >> x;
    	ll now = x + ma;
    	ma = max(now, ma);
    	cout << now << " ";
    }
    cout << endl;
    

    It costs 826 ms at the test#4. 73757350

    I add flush after cout << now << " "; in the second one. It costs 857 ms at test#4. 73757273

    I extract the output part to make it independent in the third version, like my code. It costs 529 ms at test#4. 73756448

    In the fourth version, I flush the IO stream after each outputs, in the basis of the third version. It costs 841 ms at test#4. 73756516

    It is found that independent IO without flush runs fast, but with flush runs slowly; the in-independent IO without explicit flush runs slow, as well as the in-independent IO with explicit flush runs slowly.

    It is shown that the in-independent IO runs flush implicitly, the independent IO does not run flush unless you specified explicitly. I guess the reason for the former is that there are both input and output in the for-loop, which makes the IO stream flush quickly.

    Could someone who is familiar with the internal working mechanism about iostream in C++ tell me more? Thanks a lot.

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

      flushing the buffer is slow, so you shouldn't use endl for newlines (if there are a lot of them) because they flush. Instead use '\n'. Also adding ios::sync_with_stdio(0); cin.tie(0); at the beginning of your main function will make input faster. I think the input is the problem in your code because mine looks similar and it runs in <200ms.

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

The largest bloody lesson I learned from this contest is to use two primes to hash instead of just one prime.

My D2 get WA during system test due to hash collision.

I was able to be in 500th and join the T-shirt lottery but now my rating even drops...

So sad Orz

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

    I don't think so. You use 30 and 30 is not a prime.

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

      Because I treat every character as a digit, made the string a base 30 number. 30 is not the prime I use for hashing.

      The hash trick is $$$h(i)=num(s_1...s_i)\%MOD$$$, where $$$MOD$$$ is a prime.

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

        I have never seen someone use a non-prime as base for string hash...

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

      BTW I got AC using double hashing.

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

        You can use a prime as base, it will AC: https://codeforces.com/contest/1326/submission/73752592

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

          I think using any number as base is basically the same, as long as you don't use a base that smaller than 26. Since every string converts to number is a unique value, using a prime as base or not shouldn't affect the probability of collision.

          I think I'm just unlucky that can't get passed with single hashing...

          Still, your code seems better than mine. I could learn a lot from your code. Thanks a lot anyway :)

          UPD: got AC using single hash and I personally think its prettier: https://codeforces.com/contest/1326/submission/73767232

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

          I have one doubt.

          I tried to submit by using primes as base, but I was surprised to se that taking bases as 29 and 31 failed system tests, but prime no. like 53, 103 and others were passing.

          Is it entirely based on luck if we use single hashing.

          Also if we take mod as 1e9+7 with base 31, it fails but if we take mod as 1e9+9 it passes

          It will be very helpful if you can clarify this to me

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

          It will... With about 80-90% chance(depending on how the tests are made). That 10-20% chance made me get WA in contest which made me miss out on top 30...

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

A Permutationforces round.

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

why is the editorial of D2 not given?

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

My solution for C was failing on pretest 5. Has any1 faced the same problem?

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

    maybe you forgot to module 998244353?

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

      No, I did it.

      Here is my code.

      #include <bits/stdc++.h>

      using namespace std;

      #define MOD 998244353

      int mul(int x, int y){ return (x*1ll*y)%MOD; }

      int main() { int n,k; cin>>n>>k; int a[n]; for(int i=0; i<n;i++) cin>>a[i]; int sum= n*k — (k*(k-1))/2; cout<<sum<<" ";

      int num=1;
      
      for(int i=0, j=0,count=0; j<k; i++){
          if(a[i]>=(n-k+1)){
             if(j>0) num=mul(num,count+1);
             j++;
             count=0;
          }
          else
             count++;
      }
      cout<<num;
      

      }

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

Useless editorials

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

I like this editorial. It's great.

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

Why do they give mod = 998 244 353 instead of 1e9 + 7 ?? Got 3 wrong submissions because of that !!! And if they do ...they should have highlighted that !!

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

    The number 998 224 353 appears three times in the problem and it is long and strange enough for you to discover it.

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

    By doing this, if some problem of the contest uses NTT, the modulo won't give it away.

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

Trie Solution for D1
Link to solution
Approach :- Insert all suffixes in Trie and iterate over all prefixes and search if whole prefix or some part of it is present in Trie and return it's length. If length of suffix is equal to length of prefix then you find one solution and update answer. If it's not then for the remaining part of the prefix which is not found in the suffix of Trie check whether it it is palindrome or not. If it is update the answer.
Same you do with suffixes and insert all prefixs in another Trie. Do the same thing.
Complexity :- O(n^2) (For every prefix or suffix you will iterate at max it's length.)

Though a little long solution but it just clicked in the contest so I wrote it and was accepted.

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

If someone can explain approach of question D2 in simple words it would be great help

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

    Summary

    • Find the longest matching prefix and suffix, where suffix = palindrome(prefix)
    • Find the longest inner substring that is a palindrome and touches the prefix or suffix (or both)
    • Combine these as final answer

    Steps

    1. From both ends of the string, find a prefix and suffix that are mutual palindromes. Store that for the final answer
    2. Strip off these matching prefix and suffix (if any) so you're left with just the inner string
    3. Run Manacher's algorithm on the inner string
    4. Using the output from step 3, find the max value (i.e. max palindrome length in inner string) that touches the prefix or the suffix (or both).
    5. Return [prefix] + [longest internal palindrome that touches either prefix or suffix] + [suffix]

    Manacher's Algorithm

    • This algorithm finds all palindromes in the string in O(N). It treats each index as a "center" and finds the "radius" (or half length) of the palindrome around that center. It stores this radius for each index in the string. For instance, for "aba", the values returned would be [1, 2, 1]
    • The algorithm starts off with a brute force palindrome search (i.e. from the first point, expand linearly in both directions to see how far the palindrome stretches). Then for the next point, first re-use pre-computed information, if that exists. Then continue linearly expanding to see how much further the palindrome stretches. Store this palindrome length ("radius") for that index.
    • The key observation that's used here is that if the current index lies to the right of a known palindrome and falls within that palindrome's range, then you can simply copy over the pre-computed values from the left half to the right half, and then continue expanding on the right to see how much longer the palindrome on the right stretches. This is because the left half is an exact mirror image of the right.
    • For eg. if the string is "abcdcba", then since we have a palindrome around "abc[d]cba" and both b's fall within its radius, palindrome_len("abcdc[b]a") = palindrome_len("a[b]cdcba") + {any additional palindromic text to the right}
    • Side observation: it's sort of a DP equivalent approach where for any index, you first read what has been partially pre-computed (by virtue of the current index falling under the radius of a prior index), then manually expand beyond that, then save that value, then repeat for next index.

    References

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

      Thanks a lot buddy ! Really it was amazing video and tutorial provided by you was quite helpful!!! :)

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

        Sure thing! I've edited it further with an example, and some more clarifications.

        I had a tough time with the last contest (misinterpreted C and spent all my time trying to oversolve it), so I made it a point to try and upsolve a few of the other problems that I wasn't able to get to. D2 required a fair bit of reading to understand how Manacher's algorithm worked, so thought I'd share my notes here for the benefit of anyone who has not heard of this algorithm before. If anyone sees a more efficient way of doing this, I welcome your feedback.

        I've skipped a few details for readability. for eg. there's multiple approaches to it too — you could compute both manacher_odd and manacher_even indexes and use that, or you could modify the input string to insert a special character (for eg. "*") before and after every character in the string, and then do a single manacher run on it (which is what I have used in my input).

        I'm sure there are other ways to find the longest palindrome for D1/D2 (for eg. someone suggested a prefix method?) When I went through submissions of many of the top contestants, they had used manacher, but obviously the other approaches work just as well.

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

      can you please help me understand why this (https://codeforces.com/contest/1326/submission/73942810) is giving wrong answer?

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

        I'm not familiar with the prefix function (I used manacher's algorithm instead), but the editorial uses that, and it says:

        In order to find the longest palindrome which is a prefix of some string, a, lets find p from the prefix function of the string a + "#" + reverse(a)

        Are you setting the string accordingly before you send it to the prefix function? Note that you'll need to repeat this for the suffix (per the editorial).

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

      Helped me a lot, thanks brother!!

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

      if(i-radius[i]+1 <= 0 || i+radius[i]-1 >= n-1)

      can u plz explain this line?? thank u

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

        This is when you're trying to find the longest inner string that is a palindrome and also touches the outer string. Let's say the original string was abcdedxcba. Here the outer string will be abc...cba. Then you want to find the largest inner string that touches either the initial abc part or the latter cba part. So we run manacher's on dedx and find that ded is the longest inner palindrome that touches the abc portion of the outer string. This is because at i=1 (i.e. at the character 'e'), radius[i]=2 (and hence i-radius[i] + 1 = 0).

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

Can somebody please explain the perfix function in problem D2??

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

can someone help me finding the mistake in my logic for problem E. I did similar thing as mentioned in editorial.

After putting ith bomb 'ans' will be valid if for every index 'j' after 'position[ans] in array p' the number of bombs in prefix(starting from position[ans]) <= # elements greater than 'ans' till j — #elements greater than 'ans' till the previous bomb position just before poition[ans].

I implemented it but got WA on TC-4. Can someone please find the mistake? Code: https://codeforces.com/contest/1326/submission/73769004

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

It's really sad to get the result that I failed on System Test 32 in D2 using hashing.

I use base=233,mod=998244353 in my hashing. I tried to modify the base or mod, both can get accepted. It seems that the test kills the hashing with base=233,mod=998244353. :(

Anyway D is really a great problem. I was writing a messy code using manacher algorithm in contest before I realized it can be solved with hashing. It takes me a long time.

Sorry for my poor English.

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

Can anyone share similar problems to D1/D2 related to string searching? It would be really helpful for beginners to practice on this topic.

Thank you!

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

For 1326A — Bad Ugly Numbers, as the solution of the editorial if n = 13 then the output comes 2333333333333. But it is divisible by 3, which doesn't fit those conditions. Then isn't the solution wrong?

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

    How can a number ending on $$$3$$$ in decimal representation be divided by $$$2$$$?

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

      Sorry, typing mistake. It was "divisible by 3". Just edited it now.

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

        $$$2333333333333$$$ isn't divisible by $$$3$$$.

        A number is divisible by $$$3$$$ if the sum of its digits is divisible by $$$3$$$. So, according to editorial, the sum of the digits of the answer will be $$$2+3*(N-1)$$$ and it's clear that this sum is never divisible by $$$3$$$.

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

How to Solve problem D1 and D2, Please tell the complete approach.

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

Can someone please explain D easy version? The approach that I used is as follows:- first check if the given string is a palindrome, if yes, print given string and go for next test case else do the following. 1. set L=1 2. remove all possible substring of length L, one by one and each time check that the remaining string is a palindrome or not. If it is a palindrome then print it, break the loop and go for the next test case. Else continue to check rest substring removals. 3. After checking all substring removal, increase L, that is L++ 4. go to step 2 until you get a palindrome in step 3

The code is as follows:-

t=int(input()) for _ in range(t): s=input() if s==s[::-1]: print(s) else: n=len(s) l=1 flag=True while flag: for i in range(n-l+1): p=s[:i]+s[i+l:] print("p =",p) if p==p[::-1]: print(p) flag=False break l+=1

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

For the problem D1, I used the following approach: Suppose the answer is the string t = a + b, length(a) > length(b), a is prefix, b is suffix, then there is a prefix of a that is same as string b and the remaining part of a is a pallindrome in itself. Similar approach can be used length(**a**) < length(**b**), with the change being that there exist a suffix of b that is the same as a. I'm getting wrong answer on test case 16. Can anyone point out the flaw in this approach? It'll be really helpful.73818028

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

PROBLEM C DOUBT can someone explain me the definition of partition, segment and partition value(in this problem) in layman's term (first a non — mathematical followed by a mathematical)?

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

    partitioning — divide the complete array into continuous ranges. segment — a continuous range of the array or a portion of the array. partition value — sum of maximum values in each partition.

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

...

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

I am a python user and it's been almost 24 hours since I have been trying to solve the D1 problem of codeforces global round 7. My code works fine in all the test cases I can think of and can easily handle a string of length 5000. But, I am getting time limit exceeded error in test case 5 of codeforces. Here is my code; if there's any python user out there, please, help me out.

SOURCE CODE:
def palindrome(s,si,ei):

l=len(s)
if si>=ei:
    return True
elif(s[si]==s[ei]):
    return palindrome(s,si+1,ei-1)
else:
    return False

n=int(input())

li=[]

for i in range(n):

li.append(input())

for ele in li:

stm=palindrome(ele,0,len(ele)-1)
if stm:
    print(ele)
else:
    longest=1
    final_str=ele[0]
    for i in range(len(ele)):

        prefix=ele[0:i:1]
        for j in range(i+1,len(ele)+1):

            suffix=ele[j:len(ele):1]
            new_str=prefix+suffix                
            lll=len(new_str)
            stm_1=palindrome(new_str,0,lll-1)
            if stm_1:                    
                if lll>longest:
                    final_str=new_str
                    longest=lll
                    break

    print(final_str)

Again, this code is working for all the test cases the human brain can think of but fails to pass test case 5 of codeforces for reasons which have been tormenting me for a while, since I don't know the reason at all.

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

    Unfortunately there is no way of downloading the full test data, but your implementation is O(n^3) so is likely to be slow for large test cases. Also recursion is quite slow in Python, and best avoided as far as possible.

    This can be reduced to O(n^2) by breaking the problem into parts:

    1. find how much of the start of the input string matches the reversed end of the string, this will be the start and reversed end of the result.

    2. find the longest palindrome at the start or end of the middle section of the string and put it in the middle of the result string.

    My solution following this strategy is here

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

Can anyone elaborate explanation of E problem ? Thanks in Advance

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

Who likes parsing — like

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

In C, where did n-k+1 come from?

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

    So you want the k largest numbers to be in separate partitions so the total partition value is the greatest. Because a is a permutation of numbers from 1 to n, the k largest numbers are n, n-1, n-2 ... n-k+2, n-k+1 (n-k is the k+1th largest number as n-1 is the second largest)

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

isaf27 Can you please share the test generation strategy for Problem D. I was trying to generate test cases during the contest for stress testing and it turned out that even a random string comprising of Just two character say just 'a' and 'b' for $$$N$$$ = $$$2*10^5$$$ had answer almost around 30-50. I was curious to know about the strategy you used to create test cases for actual task because they were really strong.

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

    It is true, that for random strings the length of the answer isn't big, because you have a very very small probability to get the long string in the answer (there are many pairs of symbols that should be equal). So, in the generation of the random strings, you will never get some extreme test cases.

    About test generation strategy: it's hard to share it because I had some generators, which are not obvious to understand. But some idea of how to generate the string with the long string in the answer: just generate some palindrome first, after that split it randomly and add some symbols between the parts.

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

https://www.youtube.com/playlist?list=PLl4Y2XuUavmsf8Os2QTsRgi6Gn5M1dWO8

Uploaded solution videos of problems A — D2 on this link.

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

I got TLE in (D2) 73954184 . I use string hashing. help pls. thanks in advance xd

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

In Problem F2, is there another choice besides using FWT to calculate the convolution of g_ai quickly?

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

74680175 Why I am getting TLE in Problem 2 complexity of my soln is O(n^2) I have used += everywhere using string operation and the code is working fine of TC 2 on my laptop but it is giving TLE on cf why?

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

For problem D my code is failing on TEST 16 can someone find the test_case for which its failing. My code :https://codeforces.com/contest/1326/submission/80047216

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

Please can someone tell me why I am getting TLE in Prefix — Suffix Palindrome (HARD) I have maintained to hash array one for forward and one for backward Then I first used two — pointers to get the common elements from first and end. Then I checked the largest palindrome that is in prefix and in suffix in the remaining string (after I removed the common elements ) using forward and reverse hash. This is the link to my solution

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

I don't understand why D2 solution is true. Can anyone prove it?

Mybe we have a smaller k but a longer palindrome that makes answer bigger.

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

    I have the same doubt , if you figured it out by now , please explain

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

      I understood it!

      If we have m<k then we can increase l , r by 1 and remove the last(or first) character of a. then the length of our string increase by 1.

      So if we choose m<k then we have a longer string.

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

seems like editorial solution of D2 didn't include hashing which I used to solve

»
11 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
def func(s) :
    n = len(s)
    lps = [0] * n   # lps[0] is always 0
  
    # length of the previous
    # longest prefix suffix
    l = 0
     
    # the loop calculates lps[i]
    # for i = 1 to n-1
    i = (n+1)//2;
    while (i < n) :
        if (s[i] == s[l]) :
            l = l + 1
            lps[i] = l
            i = i + 1
         
        else :
 
            # (pat[i] != pat[len])
            # This is tricky. Consider
            # the example. AAACAAAA
            # and i = 7. The idea is
            # similar to search step.
            if (l != 0) :
                l = lps[l-1]
  
                # Also, note that we do
                # not increment i here
             
            else :
 
                # if (len == 0)
                lps[i] = 0
                i = i + 1
  
    res = lps[n-1]
  
    # Since we are looking for
    # non overlapping parts.
    return s[:res];
def main() :
    for t in range(int(input())):
        s=input()
        
        n=len(s)
        s1=s[::-1]
        i=0
        for i in range(n//2):
            if s[i]!=s[n-1-i]:
                break
        s1=s[i:n-i]
        s2=s1[::-1]+"#"+s1
        s1=s1+"#"+s1[::-1]
        
        ans1=s[:i]+func(s1)+s[n-i:]
        ans2=s[:i]+func(s2)[::-1]+s[n-i:]
        if len(ans1)>len(ans2):
            print(ans1)
            continue
        
        print(ans2)
main()

Can someone help with this code? It is failing some test cases!!