×

# 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 ♦
6.5k517
accept rate: 49%

 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%

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 could anyone help me understand what is the purpose of sorting a[0] and a[1] and performing the same checks again in the next for loop answered 08 Jun, 01:27 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 import java.util.*; class FiboString { public static void main(String args[]) {Scanner in = new Scanner(System.in); int test_cases=in.nextInt(); in.nextLine(); for (int i=1;i<=test_cases;i++) { String str = in.nextLine(); int[] freq=new int[26]; for (char k=0;k
 0 My code's not working. What's wrong with it? int main() { int n; cin>>n; for(int i = 0 ; i < n ; i++) { long int cCount[26]; for(int j = 0; j < 26; j++) cCount[j] = 0; string aa; cin>>aa; for(long int ss = 0; ss < aa.size(); ss++) cCount[aa[ss]-'a']++; sort(cCount, 26); int ii = 0; while(cCount[ii] == 0) ii++; bool fib = true; if(ii < 24) { ii+=2; for(; ii < 26 ; ii++) { if((cCount[ii-2] + cCount[ii-1]) != cCount[ii]) { fib = false; break; } } } if(fib) printf("Dynamic\n"); else printf("Not\n"); } return 0; } void sort(long int *a, int size) { for(int i = 1; i < size; i++) { long int key = a[i]; int j = i-1; while(j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; } a[j+1] = key; } } answered 15 Jun, 20:15 2★niks0763 1 accept rate: 0%
 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:

×14,362
×1,409
×540
×52
×9