Need help in PALPAL string problem

Link for the problem is :
https://www.codechef.com/LTIME93B/problems/PALPALS

A string is called a Palpal string if it can be divided into contiguous substrings such that:

  1. Each character of the whole string belongs to exactly one substring.
  2. Each of these substrings is a palindrome with length greater than 1.

xyxyxy - It is one of the sample test cases provided.
Here goes the explanation provided:
(The string “xyxyxy” is already a Palpal string, since it can divided into “xyx” and “yxy”.)

Now the que is,
In case of “xyx” and “yxy”, it violates the1st condition(because of x and y being used in both substrings while they must be in exactly one), so how “xyx” and “yxy” is a possible answer?

I think it should be “xxx” and “yyy”.
Note: Codechef is considering answers as wrong if 1st condition is followed.

3 Likes

I also faced the same issue. Anyone please explain it.

The first statement can be rephrased as: Each of the characters present in the original string should be part of exactly one substring, which means a character once used can not be assigned to multiple substrings.

For example: Let String - “abcd”, then if we form substrings “ab” and “cd” then you can use ‘a’ in exactly one substring, the substrings “ab” and “acd” are invalid. But if we had multiple copies of ‘a’ like for string “aabcd” then the latter one works fine.

Though i was not able to solve it, but in the last some minutes i was able to figure out that it says:- “same character of the string can’t be the part of two sub-strings… It is not saying that same alphabet can’t be the part of two sub-strings”. So, there can be copies of same alphabets which will be considered as different characters of the string.
P.S. :- I wasted 45 minutes during contest thinking about the same".

1 Like

@its_me_ss The question is bit complicated. Someone asked the same during the contest. Please see the comments ( Div 2). It is explained what it actually means.

1 Like

Nice question Chef😄
But question actually meant that each character of the string is used once.

1 Like

The first condition here says:
Each character of the whole string(original string) belongs to exactly one substring(partitions made by you to construct palpal string).

This means that when you partition your re-arranged string then there should not be any overlapping characters. In other words, each character of the original string must be a part of only one substring from many made by you. :smile:

1 Like

It means you are considering two or more same characters as different bcz they are present at diiferent indices.

Btw ,I understand what you mean.
Thanks for clarifying.

same here bro

In my opinion,1st condition should have been removed bcz it made no sense.

@admin
please review the Question once before giving in contest .

Actually this problem is due to 2 start and 3 star people contributing to questions.
#serious_issue
@admin @admin

Thats why the sample cases are provided if there is something you are not able to understand by seeing the problem statment you can have a look at sample, when it is said you can reorder the character and divide them into palindromic strings its straightaway reflecting what it want to ask.

This is what creates a problem. Problem descriptions and test case interpretations are vice versa, so which should be considered correct?