CLFIBD - Editorial

editorial
, , , ,
21

I couldn’t find any issues here in the code!
It’s working fine with all possible test cases I can think of !
Can you please help in finding out the problem?? It’s showing wrong answer (WA).

def clfibd(occ):
    for i in range(len(occ)-1):
        for j in occ[i+1:]:
            if (occ[i] + j) in occ:
                return "Dynamic"
    return 'Not'

for _ in range(int(input())):
    s = input()
    alpha = set()
    for i in range(len(s)):
        alpha.add(s[i])
    if len(alpha) < 3:
        print('Dynamic')
    else:
        occ = list()
        for i in alpha:
            occ.append(s.count(i))
        occ.sort()
        print(clfibd(occ))
22

At line 7 checking index 2 does not make any difference. You need to check it for index 3 (considering index from 0). For example-- if your sorted list looks like 3 4 7 10 then you have to swap 3 and 4 to satisfy the condition of being dynamic for 10 ( as 7+4=11 and 7+3=10). But on the other hand if you swap 3 and 4 for 7 it does not really make any difference.

1 Like
23

What is problem in my code?
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t; cin>>t;
if(t>=1 && t<=10)
{
while(t–)
{
char str[100002];
cin>>str;
int arr[26],flag=0;
memset(arr,0,sizeof(arr));
for(int i=0;str[i]!=’\0’;i++)
arr[str[i]-97]++;
for(int i=0;i<26;i++)
{
if(arr[i] && arr[i+1] && arr[i+2])
{
if((arr[i]==(arr[i+1]+arr[i+2]))||(arr[i+1]==(arr[i]+arr[i+2]))||(arr[i+2]==(arr[i]+arr[i+1])))
flag++;
}
}
if(flag>0)
cout<<“Dynamic”<<endl;
else
cout<<“Not”<<endl;
}
}
return 0;
}
please tell me!!!

24

why this will give not
f(a)=1
f(b)=1
f©=2
f(d)=12
f©=f(b)+f(a)
at least one this this condition should hold true to be dynamic so it must be dynamic

25

what you found where was the error ?

26

The below code is giving a bad result but getting accepted as Correct answer:

For input “ppppmmnnooooppqq” we should expect “Not”. But this code will print “Dynamic” which is not correct. Looks like there are no tests that have only last few frequencies following fibonacci sequence while the rest are not, in the sorted frequencies. Please check. Thanks!

def fibFound(x):
    found = True
    if (x[-1] != (x[-2] + x[-3])):
        found = False
    return found

def dyn(s):
    res = False
    u = [s.count(x) for x in set(s)]
    if ((len(u) < 3) or (fibFound(sorted(u)))):
        return True
    else:
        return False

try:
    t = int(input())
    for i in range(0, t):
        s = input()
        if (dyn(s)):
            print("Dynamic")
        else:
            print("Not")
except EOFError as e:
    pass