NOPAL2 Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Jeevan Jyot Singh
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

2279

PREREQUISITES:

None

PROBLEM:

A string S is called good if none of the substrings of S of length \ge 2 are palindromic.

For e.g. S = \texttt{hello} is not good but S = \texttt{world} is good.

You are given a string A of length N (containing lowercase Latin letters only). Rearrange A to form a good string or determine it is not possible to do so.

Recall that a string is called palindromic if it reads the same backwards and forwards. For example, \texttt{noon} and \texttt{level} are palindromic strings.

EXPLANATION:

Observation: If in a string there are no palindromic sub-strings of length 2 or 3, then there are no palindromic sub-strings in the string(except for sub-strings of length 1).

Keeping this observation in mind, we divide the entire string into three containers c_1,c_2,c_3 where, c_i = \{j,\;such\;that\;j \;mod\; 3 = i, 1 \leq j \leq n\}. In order to avoid palindromic sub-strings of length 3, we must keep a distance of at least 2 between each same character or we must keep them in same containers. Thus for each character we have a limit of its frequency as:

limit = \lceil \frac{n}{3} \rceil

If frequency of any character exceeds this limit then it won’t be possible to make it a good string.

Now let’s talk about the case when there are multiple characters that have frequency equal to limit. Taking another variable afford as (n \;mod\; 3).

  • afford = 0: All containers are of length \lceil \frac{n}{3} \rceil.
  • afford = 1: Only one container is of length \lceil \frac{n}{3} \rceil.
  • afford = 2: Two containers are of length \lceil \frac{n}{3} \rceil.

Let us define bad as number of characters having frequency equal to limit. If bad is more than the number of containers having length equal to \lceil \frac{n}{3} \rceil, then it won’t be possible to construct a good string.

If none of such cases arise then we can confidently say that we can create a good string.

Now we loop through each characters in descending order of their frequency and if its frequency is equal to limit, then we fill it in all the positions of container whose size is equal to that of limit else we can fill its characters in the containers in the order c_3->c_2->c_1

TIME COMPLEXITY:

O(Nlog(N)), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

2

Can someone please tell me for which test case my code is not working
https://www.codechef.com/viewsolution/67406979

2 Likes
3

I also do it with taking a gap of 2 between the two same char
But my code doesn’t work for all test case
Plzz anyone check
{
map<char,ll>mp;
for(int i=0;i<n;i++){
mp[s[i]]++;
}

vector<pair<ll,char>>A;
for(auto it:mp){
    A.pb({it.second , it.first});
}
sort(all(A)); // in reverse 

vector<char>ans(n , '?');

ll k=0;
for(auto it:A){
    ll start =k;
    if(ans[start]!='?'){
        cout<<"NO"<<endl;
        return;
    }
    while(it.first--){
        if(start>=n){
            cout<<"NO"<<endl;
            return;
        }
        ans[start] = it.second;
        start+=3;
    }
    while(k<n && ans[k]!='?') k++;
}

cout<<"YES"<<endl;
for(auto it:ans){
    cout<<it;
}
cout<<endl;

}

4

Here’s my solution for the problem:

Using the observation that there should be no repeated characters within a substring of length 2 or 3, we try making the final string, let’s call it ans. Keep a count of all remaining characters in a set of {count, letter} pairs. Also keep two variables which note down the letter in the previous and second-previous position.

While the set is not empty, run the following loop - At each step, we’ll choose the letter with the highest remaining count. However, if this letter occurs in one of the previous two positions, we’ll check the letter with second highest count, and if that occurs too, we’ll check the third highest letter. Whichever letter is suitable, we append it to the ans string and decrement its count by 1.

If the final length of ans is N at the end of the loop, then the answer exists, else it doesn’t.

Submitted code : https://www.codechef.com/viewsolution/67352016

7 Likes
5

@xaier310

1
10
abcabcacdb

Your test case gives “cbacbacadb” as output, in which “aca” is a palindromic sub-string. One of the possible correct outputs for this would be “abcabcabcd”.

2 Likes
6

Can someone please tell me what I am doing wrong in my solution:
https://www.codechef.com/viewsolution/67417686

Also I am not getting the proof of correctness of the last part of the editorial about how to create the good string.

7

Proof?

8

For everyone who is struggling with the editorial, I want to claim that the last line of the editorial is incorrect (thanks @foxy7 for a faulty editorial :slight_smile: )

Screenshot_20220623_025003
Screenshot_20220623_025003734Ă—107 15.4 KB

According to the editorial we can fill the remaining characters in any position of a container as long as a position is available in any particular order of containers.

Well I was doing the same thing in my solution but was not getting an AC. It took me 3 hours to realise that we cannot take containers in any order.

I just used the Editorialist’s Solution, in which he has used this order c3 → c2 → c1 of containers to fill the characters whose count is not equal to limit , and changed the order to c1 → c2 → c3 (the order I was using in my code).
And guess what, hIs solution was also not accepted.
Check for yourself : CodeChef: Practical coding for everyone

Now, I don’t know if the test cases are wrong or the approach is incorrect.
Also there is no proof of correctness mentioned in the editorial that we can take the containers in any order.

I request the problem setter @jeevanjyot to present a correct approach with proof of correctness.

9

I thought of a similar approach, with one tiny difference that I check by looping(in the order of highest frequency) on the current set if we can append a character to our answer or not.
But’s its giving WA.
WA Code: https://www.codechef.com/viewsolution/67421135
Can someone tell where It’s wrong

10

taking the highest frequency character while making sure it is not equal to last two previous characters

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

11

Can someone please tell me what’s wrong in my approach or please give some test case where i am getting WA

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

13

In this question my approach is that i will main count of each character in a vector of pair and sort it on basis of their count in decreasing order. I will take top 3 characters and decrease their count and sort vector again. At last only one or two or possibly zero characters will remain. I will check them seperately

14

We cannot fill the chains in the order c1 → c2 → c3
Here is the counter case : “aabbccd”
If you try to fill in the above order you would get “abcacdb” which is incorrect. Although there is a workaround in this logic. If you just swap the incorrect index with its previous index then also it will get AC. Proof is slightly harder, let me move to my approach.

Lets say all the characters have frequency < ceil(n/3). (If any character has freq=ceil(n/3) we can assign it a full chain and continue solving the problem).
Now I will start filling in the decreasing order of frequencies in the chains c3->c2->c1.
What is special in this ordering?
Basically if you change chain from c3 to c2 or c2 to c1 you have space of one extra character as compared to moving from chain c1 to c2 or c2 to c3.
Also since we are filling in decreasing order of frequencies (i.e. if current character has frequency x then next character has frequency <=x), if we do the calculation we can see that we have atleast x characters to fill the next character too without violating the palindromic conditions if we are filling in order from c3->c2->c1.
You can once do the calculations. Let me know if you get stuck.

2 Likes
15

I made a video editorial for the problem. You can check it out here.

1 Like
16

Thank you !
I got your approach

17

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

can someone plz tell me why my code is giving WA for some test cases

18

Can someone please help me why my code is not working for all test cases ??
For which test case my code is not working ?
https://www.codechef.com/viewsolution/67430674

19

Any one plz tell me where i m getting wrong answer CodeChef: Practical coding for everyone

20

sir can u plz help me with my solution plz CodeChef: Practical coding for everyone

21

Can anyone tell me why my code is not working. I did same thing from the editorial (Keeping distance of atleast 2)
My submission