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
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
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