Help in A. Acacius and String - codeforces

Problem
If anyone passed pretests for this problem, please explain your approach. I tried bruteforce but got WA in pretest 2. This was perhaps the hardest div 2 round ever. Only ~3.8k people solved A and B (which may fall after system testing) whereas it’s usually > 10k and ~6k.

check for TC abac?bacabaca?a.

1 Like

I did not pass test case 2.
Looking at the editorial, my approach was same as explanation. I am not able to figure out whats wrong in my code.
If anyone could help.

    t = int(input())
    MAIN = ["a","b","a","c","a","b","a"]
    while(t):
        n = int(input())
        si = str(input())
        s = []
        for i in range(n):
            s.append(si[i])

        count = 0
        interval = []

        for i in range(n-6):
            sub = s[i:i+7]
            if (sub == MAIN):
                count+=1
        
        if (count==1):
            for i in range(n):
                if (s[i]=="?"):
                    s[i] = "z"
            print("YEs")
            print("".join(s))
            #si.replace("?", "z")
        elif (count>1):
            print("NO")
        elif (count == 0):
            for j in range(n-6):
                sub = s[j:j+7]
                flag = True
                for i in range(7):
                    if (i==0):
                        if (sub[i] != "a" and sub[i] != "?"):
                            flag = False
                            break
                    elif (i==1):
                        if (sub[i] != "b" and sub[i] != "?"):
                            flag = False
                            break
                    elif (i==2):
                        if (sub[i] != "a" and sub[i] != "?"):
                            flag = False
                            break
                    elif (i==3):
                        if (sub[i] != "c" and sub[i] != "?"):
                            flag = False
                            break
                    elif (i==4):
                        if (sub[i] != "a" and sub[i] != "?"):
                            flag = False
                            break
                    elif (i==5):
                        if (sub[i] != "b" and sub[i] != "?"):
                            flag = False
                            break
                    elif (i==6):
                        if (sub[i] != "a" and sub[i] != "?"):
                            flag = False
                            break
                if (flag):
                    count += 1
                    interval.append(i-6)
                    interval.append(i+1)

            if (count==1):
                l,r = interval[0],interval[1]
                s[l:r] = MAIN
                print("yes")
                print("".join(s))
            else:
                print("No")
        t-=1
1 Like

https://codeforces.com/contest/1379/submission/87312835
You may refer this

Always check that your new arrangement of string does not make the count of required string more than 1

2 Likes

I am aware of the fact that my code fails for this. But I know people who got “NO” for this but still managed to fail system pretests. It may be hard to come up with test cases with insufficient information like this, but do you have any idea about the test cases for which their code failed?

see…at first go through all substrings of length 7
if count of abacaba>1 ans is no
if it is 1, fill all ? in given string by d and print it
if it is 0(this is the tricky part)
iterate through all strings of length 7
check if abacaba can be formed using it
if yes, form new string as previous(till the beginning of this substring)+this abacaba+remaining string[fill the question marks with d, even if u dont it wont matter]
check count of abacaba in this newly formed string, if its 1, this is your answer
if there isnt any such string, ans is no

this is my logic used and it has been accepted…u can check editorial for detailed explanation

1 Like

It’s probably this. I didn’t go through your code though.

I haven’t solved the problem…but maybe you could go with something like this.

STEP 1:

Ignore all the question marks.
It is obvious if the cnt of the string abacaba >=2, then the answer is NO.

If the cnt of the string abacaba == 1, then just fill all the question marks with z and the output will be YES

STEP 2:

The only case left here is cnt = 0.
For this, you make a string temp = abacaba, and whenever you encounter a question mark, check the prefix of the string you have encountered just before this position.

For example, if the string given is abaca?a, then the letters matching the prefix of the position of the question mark is abaca. So we fill this with b. If you have found the string, set f = 1 to avoid the repetitive occurrence of abacaba

If f = 0, the output is NO, else YES

1 Like

thanks @sebastian.

1 Like

All types of yes are accepted in CF

2 Likes

This was the mistake. Thanks a lot!

1 Like

Thanks! I was dumb enough to not check if there are multiple occurrences of “abacaba”. It was such a simple question smh.

I think your algorithm may fail in abac?bacaba

1 Like

One thing to note is that a lot fewer people gave this contest because of unusual timing, that is one reason why so few people solved A and B.

I disagree. There were 20k registrants before the contest began. Also, there was no extra registration. You can see the comments section of the blog to get an idea about the relative difficulty. A was easy tbh, but it required a lot of implementation (which isn’t normal).

Oh ya, lol…you really need to check the substrings XD