CLFIBD - Editorial

PROBLEM LINK:

Practice
Contest

Author: Avijit Agarwal
Tester and Editorialist: Soumik Sarkar

DIFFICULTY:

CAKEWALK

PREREQUISITES:

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.

3 Likes

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

1 Like

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.

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

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.

I had an indexing error in line 7, for anyone wondering and seeing this post

Getting a WA with this solution. It should pass all the test cases, will be of great help if someone can figure it out.

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)

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<k;i++)
             {
                 if(a[i]!=( a[i-1]+a[i-2]))
                 {
                    f1=1;
                    break;
                 }
             }
             x=a[0];
             a[0]=a[1];
             a[1]=x;
             for(i=2;i<k;i++)
             {
                 if(a[i]!=( a[i-1]+a[i-2]))
                 {
                    f2=1;
                    break;
                 }
             }
        }
        if(f1==0 || f2==0)
        System.out.println("Dynamic");
        else
        System.out.println("Not");
    }

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

https://www.codechef.com/viewsolution/19067870
https://www.codechef.com/viewsolution/19073896
these two are accepted but showing dif answers for the string mnnooopppppq

@vijju123 @meooow @admin Test Cases are still weak for this problem.

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

It is written for Pyth 3.5

#include
#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;

}

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<stdio.h>
#include<string.h>
#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;

}

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?

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?

I clearly misread that the above solution had been accepted when in fact it has not. My apologies.

I believe I see the error now, sorry for the confusion…

note that abbcccdddd is dynamic with (b,a,c,d) ordering, counts (2,1,3,4)