CLFIBD - Editorial

cakewalk
clfibd
cole2018
editorial
string

#1

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 e 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 e 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* != 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.


#2

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


#3

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* = 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* != 0){
			   arr[j] = count*;
			   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*);
	      //}

	      //for(int k = 0 ; k < count.length ; k++){
	      //	System.out.println(count*);
	      //}
    
          int fib = 0;
          //if(arrlen < 2 ){
          //  System.out.println("Dynamic");
          //}
          //checking condition
	      for(int i = 2 ; i < arrlen ; i++){
		     if(arr* == 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


#4

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* != 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) + ' 

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.


#5

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


#6

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* - sorts[i-1] != sorts[i-2]:
        if sorts.count(sorts* - sorts[i-1]) == 0:
            return False
        else:
             sorts[i-2] = sorts[sorts.index(sorts* - sorts[i-1])]
return True
#for i in range(2, len(d)):
#    if (len(d) >= 4) and (sorts* != 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*:
#        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)


#7

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*!=( 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*!=( 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


#8

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


#9

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

#10

#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*=0;
for(int i=0;i<l;i++)
{
int v = (int)a*;
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* > sum[j])
			{
				temp = sum[j];
				sum[j] = sum*;
				sum* = 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;

}


#11

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*!='#')
        {
            for(j=i+1;j<l;j++)
            {
                if(a*==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

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

   }
   }

}
return 0;

}


#12

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?


#13

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?


#14

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.


#15

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


#16

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


#17

It is written for Pyth 3.5


#18

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


#19

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


#20

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