You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFSPL - Editorial

PROBLEM LINK:

Contest
Practice

Author: Prateek Gupta
Tester: Roman Furko
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

DIFFICULTY:

Simple

PREREQUISITES:

String processing

PROBLEM:

Given a string $S$, can you remove at most one character so that the remaining string is a double string? A double string is a string of the form $W + W$ for some non-empty string $W$.

QUICK EXPLANATION:

The answer is YES iff $|S| \ge 2$ and one of the following is true:

  • The first $\lfloor \frac{|S|}{2} \rfloor$ characters is a subsequence of the last $\lceil \frac{|S|}{2} \rceil$ characters, or
  • The last $\lfloor \frac{|S|}{2} \rfloor$ characters is a subsequence of the first $\lceil \frac{|S|}{2} \rceil$ characters.

EXPLANATION:

Subtask 1

Let's first try using the simplest solution possible: Try all possible characters to remove (possibly none), and see whether any resulting string is a double string. There are only $|S|+1$ cases to try, because there are only $|S|$ locations to remove a character from, plus $1$ for the "do nothing" scenario. For this to work, we need code that checks whether a string is a double string. Here's a pseudocode that does that:

def is_double_string(s):
    n = s.length
    if n == 0 or n % 2 != 0:
        return false
    h = n / 2
    for i = 0..h-1:
        if s[i] != s[i+h]:
            return false
    return true

(Note: We also return false when n == 0 because $W$ must be nonempty from the definition!)

With this function, we can now answer a single test case by trying all $|S|+1$ cases. The following is a pseudocode for this:

def solve(s):
    n = s.length
    good = is_double_string(s)
    if not good:
        for i = 0..n-1:
            let t be s with the i'th character removed
            if is_double_string(t):
                good = true
                break
    print (if good then 'YES' else 'NO')

Unfortunately, checking whether a string is a double string takes $O(|S|)$ time, so this runs in $(|S|+1)O(|S|) = O(|S|^2)$ time, too slow for the second subtask.

Subtask 2

Here are a few observations that will help us find a faster solution:

  • Double strings are of even length, and
  • Removing a letter from a string changes its parity.

This gives us the following clues on what we must do:

  • If $|S|$ is even, then we must not remove any letter.
  • If $|S|$ is odd, then we must remove exactly one letter.

In the first case, since we can't remove any character, we simply need to check whether $S$ is already a double string to begin with. This takes $O(|S|)$ time so we're good.

In the second case, we still have a problem because we don't know which letter to remove. However, we can use the fact that in a double string, the first half is the same as the second half (by definition). Since we can only remove one character to turn $S$ into a double string, the first "half" of $S$ must already be nearly the same as the second "half" to begin with. (The word "half" here is a bit ambiguous because $|S|$ is odd, but you sorta get the idea.) Specifically, the first and second "halves" must differ from each other by exactly one deletion. This means that the shorter "half" must be a subsequence of the longer "half". Thus, we have reduced the problem to simply checking whether some string is a subsequence of another string!

Now, we still have a problem because we don't know which "half" must be the shorter one. But there are only two possibilities to check (either the first or second half is the shorter one), so it's no problem.

Finally, how do we quickly check whether some string, say $A$, is a subsequence of another string, say $B$? A simple greedy algorithm such as the following will do:

def is_subsequence(a,b):
    j = 0
    for i in 0..a.length-1:
        // find where a[i] appears in b[j..]
        while j < b.length and a[i] != b[j]:
            j++
        if j == b.length:
            return false
        j++ // "consume" b[j]
    return true

This code runs in $O(|A| + |B|)$ time, and since in our case $|A| + |B| = |S|$, and there are only two cases to check, our algorithm runs in $2\cdot O(|S|) = O(|S|)$.

To summarize, here is our algorithm:

def solve(s):
    n = s.length
    good = false
    if n % 2 == 0:
        good = is_double_string(s)
    else if n > 1: // n == 1 is bad
        h = n / 2
        good = is_subsequence(s[0..h-1], s[h..n-1]) or is_subsequence(s[h+1..n-1], s[0..h])
    print (if good then 'YES' else 'NO')

Time Complexity:

$O(|S|)$

AUTHOR'S AND TESTER'S SOLUTIONS:

setter
tester
editorialist

This question is marked "community wiki".

asked 13 Mar '16, 14:17

kevinsogo's gravatar image

7★kevinsogo
1.7k469127
accept rate: 11%

edited 27 Mar '16, 22:30

1

Nice editorial. Breaking and showing all the operations in the form of functions will definitely inculcate better coding practices among the newbies

(16 Mar '16, 23:01) nickzuck_0073★

Answer is hidden as author is suspended. Click here to view.

answered 15 Mar '16, 18:54

an2609's gravatar image

3★an2609
(suspended)
accept rate: 22%

It was so easy to miss the obvious with this problem. It is unsurprising that the test cases were initially inadequate. The note from the editorial made my error apparent to me:

"Note: We also return false when n == 0 because W must be nonempty from the definition!"

link

answered 15 Mar '16, 17:00

adavis444's gravatar image

2★adavis444
111
accept rate: 0%

Simple string processing....MySolution

link

answered 15 Mar '16, 15:45

s_verma's gravatar image

3★s_verma
562
accept rate: 18%

@s_verma

What logic did you use.

(20 Mar '16, 15:43) arpit7282★

I did exactly the same... Dont't know what went wrong?? Please have a look...

https://www.codechef.com/viewsolution/9574300

link

answered 15 Mar '16, 15:45

abhiroj786's gravatar image

2★abhiroj786
819
accept rate: 22%

edited 15 Mar '16, 15:47

1

did you consider the case where all characters are same? like a, aa, aaa. answer should be: NO YES YES

(15 Mar '16, 16:59) shadek3★

it fails for a. I guess tis is where I went wrong. Thank you, Shadek

(15 Mar '16, 19:50) abhiroj7862★

thought the same way nice question https://www.codechef.com/viewsolution/9578821

link

answered 15 Mar '16, 15:48

c0dew0rm's gravatar image

3★c0dew0rm
1
accept rate: 0%

Can someone please help me and tell where is the problem in my code?

http://ideone.com/RRF7tE

I am getting WA for last test cases of both sub tasks.

link

answered 15 Mar '16, 18:29

megha_agg007's gravatar image

2★megha_agg007
1
accept rate: 0%

same logic but got wrong answer!!! https://www.codechef.com/viewsolution/9674515

link

answered 15 Mar '16, 18:35

akash_kumar96's gravatar image

4★akash_kumar96
1
accept rate: 0%

Try this

1

cxccc

Answer - YES

(15 Mar '16, 23:32) dushsingh19955★

corrected the error https://www.codechef.com/viewsolution/9685962 still not working

(16 Mar '16, 22:19) akash_kumar964★

https://www.codechef.com/viewsolution/9678465

can anyone tell me for what testcase this fails ?? because it works for every testcase i can think of and get only the last testcase of second subtask wrong

link

answered 15 Mar '16, 20:20

saad_adeeb's gravatar image

2★saad_adeeb
11
accept rate: 0%

edited 15 Mar '16, 20:22

can any one please tell me where My Solution is failed

link

answered 15 Mar '16, 23:28

prasadram126's gravatar image

2★prasadram126
11
accept rate: 0%

Very easy problem. Consider all the possible cases. Check out my sol https://www.codechef.com/viewsolution/9655225

link

answered 16 Mar '16, 11:01

manishvirodhia's gravatar image

2★manishvirodhia
1
accept rate: 0%

Getting a wrong answer for my solution :https://www.codechef.com/viewsolution/9683501...dono for what it fails! Can someone look at it?

link

answered 16 Mar '16, 14:23

ACR's gravatar image

1★ACR
11
accept rate: 0%

Shouldn't it be subsequence instead of substring since we are checking for the same ordered sequence of characters rather than the contiguous characters?.

link

answered 16 Mar '16, 19:01

kishu18_agar's gravatar image

3★kishu18_agar
21
accept rate: 0%

Yes, that's right. I forgot that it should be subsequence. I have updated the editorial. Thanks for pointing it out!

(16 Mar '16, 19:04) kevinsogo7★

I tried all test cases given in the comments.. My code gives correct answer for all of them, but it fails for last test case in both sub tasks. Can someone please check what the error is in my code.? https://www.codechef.com/viewsolution/9688335

Thanks in advance...

link

answered 17 Mar '16, 10:27

sriramdesai's gravatar image

3★sriramdesai
1
accept rate: 0%

can someone plz post the testcases . i have written the code but ans is always showing to be wrong!! here is the link to my code ! http://ideone.com/Q5Wyyw

i dont get why codechef submission is always wrong!!

link

answered 17 Mar '16, 20:23

jragarwal's gravatar image

2★jragarwal
11
accept rate: 0%

edited 17 Mar '16, 20:25

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Tags:

×10,491
×737
×341
×189

Asked: 13 Mar '16, 14:17

Seen: 3,038 times

Last updated: 27 Mar '16, 22:30