We're running experiments to retest old unrated rounds to see how the latest improvements perform. There might be a testing queue in the next few hours. ×
Please read the new rule regarding the restriction on the use of AI tools. It applies starting from round 972. ×

negetive_iq's blog

Can someone help me with this problem C1. Message Transmission Error (hard version)?
By negetive_iq, history, 2 weeks ago, In English

I have solved the easy version of the problem. But I have no idea how to solve this one. Do I require any new algorithms? Can someone please help me solve this problem?

  • Vote: I like it
  • +1
  • Vote: I do not like it

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

Auto comment: topic has been updated by negetive_iq (previous revision, new revision, compare).

→ Reply
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Learn pattern searching algorithms like Z function, KMP, etc. I used Z function to solve this question.

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

    Can you explain a bit more in detail on how to solve this after learning pattern matching algorithms?

    → Reply
    • »
      »
      »
      2 weeks ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      The problem after this will turn into "for string $$$s$$$ of length $$$n$$$, find any index $$$i$$$ ($$$2 \le i \le n$$$) such as $$$s(i, n) = s(1, n-i+1)$$$ and $$$i \le n-i+1$$$".

      (Here, $$$s(i, j)$$$ means a contiguous substring of $$$s$$$ from index $$$i$$$ to index $$$j$$$, inclusively).

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

Can you give me the link to the problem?

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

    https://codeforces.net/problemset/problem/2010/C1

    → Reply
»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

To solve the problem, analyze the string t to determine if it can be the result of merging two identical consecutive messages. Compute the length of the longest prefix that is also a suffix of the string. If this length is at least half the length of t plus one, it indicates a possible merging error, and you should print "YES" along with the prefix. If not, print "NO". For this, you can use the KMP algorithm’s LPS (Longest Prefix Suffix) array to efficiently find the longest prefix which is also a suffix.

→ Reply