×

# CLFIBD - Editorial

Author: Avijit Agarwal
Tester and Editorialist: Soumik Sarkar

CAKEWALK

Strings, Sorting

# PROBLEM:

Given a string $S$ find the frequency of each character in the string and check whether they can be rearranged into a sequence $F$ where $F_i = F_{i-2} + F_{i-1}$ holds for all $i \ge 3$.

# EXPLANATION:

Finding the frequency of each character can be done in linear time. One possible way is below

m = empty map
for each character c in S:
if c in m:
m[c] = m[c] + 1
else:
m[c] = 0
F = empty list
for each key, value in m:
append value to F


Next we can say that because $F_i = F_{i-1} + F_{i-2}$ and $F_{i-2}$ cannot be $0$, $F_i > F_{i-1}$ for all $i \ge 3$. So it makes sense to sort the array $F$.

Then we can check if $F$ satisfies the given condition for all $i \ge 3$. If it does, then the string is dynamic otherwise it is not, right? ......But hold on, there is a catch. Indeed $F_i > F_{i-1}$ for all $i \ge 3$, but what about $F_2$? The relation between $F_2$ and $F_1$ is not specified. So it maybe that $F_4 \ne F_2 + F_3$ in the sorted order but $F_4 = F_1 + F_3$. In that case if we can simply swap $F_1$ and $F_2$ to get the required sequence and the string is dynamic.

For example: $F = (1, 2, 3, 4)$. Here $3 = 1 + 2$ but of course $4 \ne 2 + 3$. If we swap $1$ and $2$ we will get $(2, 1, 3, 4)$ where $3 = 2 + 1$ and $4 = 1 + 3$.

sort F
N = length of F
if N >= 4 and F[4] != F[2] + F[3]:
swap(F[1], F[2])
ok = True
if N >= 3:
for i in [3..N]:
if F[i] != F[i - 1] + F[i - 2]:
ok = False
if ok:
S is dynamic
else:
S is not dynamic


# AUTHOR'S AND TESTER'S SOLUTION:

Author's solution can be found here
Tester's solution can be found here.

6★meooow ♦
7.0k717
accept rate: 48%

 1 I think there were weak test cases in this question. This solution gets AC by only checking the first 3 distinct elements and ignoring the rest. For example, 1 abccddddddddddd should give "Not" as output where in the above mentioned code it is giving "Dynamic". answered 16 Apr, 01:02 53●4 accept rate: 0% You are right, this was not anticipated by us and we are sorry for that. The test cases have been fixed in the practice section. (23 Apr, 22:48) meooow ♦6★
 0 import java.util.*; class StringFact{ public static void main(String[] args) { Scanner sc = new Scanner(System.in);  //test cases int t = sc.nextInt(); while(t > 0){ String str = sc.next(); int[] count = new int[256];//ASCII int len = str.length(); //for(int i = 0 ; i < 256 ; i++ ){ // count[i] = 0; //} //counting each character int arrlen = 0; for(int i = 0 ; i < len ; i++ ){ if(count[str.charAt(i)] == 0){ arrlen++; count[str.charAt(i)]++; } else{ count[str.charAt(i)]++; } //System.out.println(count[str.charAt(i)]); //System.out.println((int)str.charAt(i)); } //System.out.println(count[100]); int[] arr = new int[arrlen]; //int i = 0; int j = 0; //while(count[i++] != 0){ // arr[j++] = count[i-1]; // System.out.println(count[i-1]); //} //if count have some value then i put in array for(int i = 0 ;i < 256;i++){ if(count[i] != 0){ arr[j] = count[i]; j++; } } //sort the array Arrays.sort(arr); //System.out.println(arr.length); //System.out.println("j="+j); //for(int i = 0 ; i < arrlen ; i++){ // System.out.println(arr[i]); //} //for(int k = 0 ; k < count.length ; k++){ // System.out.println(count[i]); //} int fib = 0; //if(arrlen < 2 ){ // System.out.println("Dynamic"); //} //checking condition for(int i = 2 ; i < arrlen ; i++){ if(arr[i] == arr[i-1] + arr[i-2]){ fib++; } } if(fib != 0 || arrlen < 2){ System.out.println("Dynamic"); } else{ System.out.println("Not"); } t--; } }  } What was the mistake??? Showing Wrong Answer.Please explain answered 03 May, 13:02 1 accept rate: 0%
 0 enter code here def dynamic_string(string): count_list = [string.count(x) for x in set(string)] count_list.sort() check = 1 if len(count_list) < 3: return 'Dynamic' if count_list[2] != count_list[1] + count_list[0]: count_list[0], count_list[1] = count_list[1], count_list[0] for i in range(len(count_list)-1, 1, -1): if count_list[i] != count_list[i-1] + count_list[i-2]: check = 0 break if check == 1: return 'Dynamic' else: return 'Not' output = "" user_input = int(input()) for i in range(user_input): to_check = input() output += dynamic_string(to_check) + ' \n' print(output)  I do get the Wrong Answer notification, but im really lost and stuck on what cases my code can't handle properly. Any help or hints would be appreciated. answered 13 May, 22:54 0★leshlo 1 accept rate: 0% I had an indexing error in line 7, for anyone wondering and seeing this post (15 May, 05:11) leshlo0★
 0 Getting a WA with this solution. It should pass all the test cases, will be of great help if someone can figure it out. answered 21 May, 22:00 1 accept rate: 0% note that abbcccdddd is dynamic with (b,a,c,d) ordering, counts $(2,1,3,4)$ (02 Nov, 03:31) joffan5★

If anyone needs to understand the problem in python code(Please do not copy: understand and reflect) import sys

def fibs(d: list):

sorts = sorted(d)
for i in range(len(d)-1, 2, -1):
if sorts[i] - sorts[i-1] != sorts[i-2]:
if sorts.count(sorts[i] - sorts[i-1]) == 0:
return False
else:
sorts[i-2] = sorts[sorts.index(sorts[i] - sorts[i-1])]
return True
#for i in range(2, len(d)):
#    if (len(d) >= 4) and (sorts[i] != sorts[i-1] + sorts[i-2]):
#        try:
#            sorts[i-3], sorts[i-2] = sorts[i-2], sorts[i-3]
#        except:
#            continue

#    if (sorts[i-2] + sorts[i-1]) != sorts[i]:
#        return False
#return True


def solve(s): sets = set(s) #print(sets) a = [] for i in sets: a.append(s.count(i))

if len(sets)<3:
return "Dynamic"
else:
if(fibs(a)):
return "Dynamic"
else:
return "Not"


T = int(sys.stdin.readline().strip()) ans = [] for i in range(T): x = sys.stdin.readline().strip() ans.append(solve(x)) for j in range(T): print(ans[j])

# solve(SI)

1
accept rate: 0%

 0 Hi, In the editorial section of author's solution the following block is there(https://gist.github.com/meooow25/fea592474e33b0817d3d0f4ad55685af) if(k>2) { for(i=2;i
 0 https://www.codechef.com/viewsolution/19067870 https://www.codechef.com/viewsolution/19073896 these two are accepted but showing dif answers for the string mnnooopppppq answered 08 Jul, 10:25 1 accept rate: 0% @vijju123 @meooow @admin Test Cases are still weak for this problem. (08 Jul, 18:29)
 0 Why is this wrong. I used an extra flag variable to maintain a single occurence of True to replace the need of swapping. Which test cases does my code fail? for t in range (int(input())): s = list(input().strip()) r = sorted(s) x = set(r) a = [] flag = 0 count = 0 for n in x: a.append(r.count(n)) val = sorted(a) for k in range(2, len(val)): if val[k] == val[k-1]+val[k-2]: fib = True if fib: flag = 1 else: fib = False if fib or flag or len(x)<3: print("Dynamic") else: print("Not")  answered 11 Jul, 18:55 1 accept rate: 0% It is written for Pyth 3.5 (11 Jul, 18:56)

# include <bits stdc++.h="">

using namespace std; int main() { int t; cin>>t; while(t--) { string s; cin>>s; int l = s.length(); char a[l]; strcpy(a, s.c_str()); int sum[123]; for(int i=0;i<123;i++) sum[i]=0; for(int i=0;i<l;i++) { int v = (int)a[i]; sum[v]=sum[v]+1;

    }
int temp;
int n=123;
for(int i = 97;i < n;i++)
{
for(int j = i+1;j < n;j++)
{
if(sum[i] > sum[j])
{
temp = sum[j];
sum[j] = sum[i];
sum[i] = temp;
}
}
}
int c1=0,c2=0;
for(int j=99;j<123;j++)
{
if(sum[j]==0)
continue;
else if(sum[j]!=0 && c2<2)
{
c2++;
continue;
}
else if((sum[j-1]+sum[j-2])!=sum[j])
{
c1=1;
break;
}
else
continue;
}
if(c1==1)
cout<<"Not"<<endl;
else
cout<<"Dynamic"<<endl;
}
return 0;


}

1★venky521
1
accept rate: 0%

I think this problem can be solved using logic of AP Series.But our series will star from second element of series which is sort.Correct me if i am wrong. please suggest were i am wrong

enter code here

# include<ctype.h>

char a[1000001];

int main() { register int i,j,k,cnt,max,sum,sum2,l,n; int t,b[27]; float s; scanf("%d",&t);

while(t--)
{
k=0;
sum=0;
scanf("%s",a);
l=strlen(a);
for(i=0;i<l;i++)
{
cnt=1;
if(a[i]!='#')
{
for(j=i+1;j<l;j++)
{
if(a[i]==a[j])
{
cnt++;
a[j]='#';
}
}
b[k++]=cnt;
sum=sum+cnt;
}
}


n=k; do{ cnt=0; for(j=0;j<n-1;j++) {="" if(b[j]="">b[j+1]) { max=b[j]; b[j]=b[j+1]; b[j+1]=max; cnt++; } } n--; }while(cnt!=0);

   if(k<3)
printf("Dynamic\n");
else
{
if(k==3)
{
if(b[2]==b[1]+b[0])
printf("Dynamic\n");
else
printf("Not\n");
}
else
{
s=k;
sum2=(((s-1)/2)*((2*b[1])+(s-2)*(b[2]-b[1])))+b[0];
if(sum==sum2)
printf("Dynamic\n");
else
printf("Not\n");

}
}

}
return 0;


}

11
accept rate: 0%

 0 This solution is marked as accepted: https://www.codechef.com/viewsolution/21357782 However, given this input: aaabcdeeeeeeefghhhhijjjkkkklmnooooopppqrszzzzzzzzzzzzzzzz which has counts of: 16 7 5 4 4 3 3 3 1 1 1 1 1 1 1 1 1 1 1 1 Clearly 5 = 4 + 1 is a permutation that makes this input Dynamic. However, the above solution is returning "Not" for this input. Also for the input: ab which has counts of: 1 1 The string should be Dynamic, as the rules state: "Note that if the number of distinct characters in the string is less than 3, i.e. if |C|<3, then the string is always dynamic." However, the above solution is returning "Not" for this input, which appears to be incorrect. What am I missing? answered 01 Nov, 22:31 0★rael007 1 accept rate: 0% I clearly misread that the above solution had been accepted when in fact it has not. My apologies. (01 Nov, 22:52) rael0070★
 0 I submitted a solution that was marked as accepted, here: https://www.codechef.com/viewsolution/21356653 However, it incorrectly determines that the string "aaaabcccxxxxxxxxxxyyyyyyyyzwp" is NOT dynamic. However, the non-zero counts for this string are, in sorted order, 1 1 1 1 3 4 8 10. Clearly 1 + 3 == 4 here, so it appears this should be dynamic. Am I missing something, or is your test data simply not complete? answered 01 Nov, 22:32 0★rael007 1 accept rate: 0% I believe I see the error now, sorry for the confusion... (01 Nov, 23:22) rael0070★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,182
×1,579
×619
×53
×16