You are not logged in. Please login at www.codechef.com to post your questions!

×

CLFIBD - Editorial

3
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 \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.

asked 16 Apr, 00:35

meooow's gravatar image

6★meooow ♦
7.0k717
accept rate: 48%

edited 23 Apr, 22:46


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

link

answered 16 Apr, 01:02

debjitdbb's gravatar image

4★debjitdbb
534
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★

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

link

answered 03 May, 13:02

sivayempalli's gravatar image

2★sivayempalli
1
accept rate: 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.

link

answered 13 May, 22:54

leshlo's gravatar image

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★

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

link

answered 21 May, 22:00

kanishk_27's gravatar image

3★kanishk_27
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)

link

answered 25 May, 13:42

kprogrammer's gravatar image

2★kprogrammer
1
accept rate: 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<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

link

answered 08 Jun, 01:28

venkat270593's gravatar image

1★venkat270593
1
accept rate: 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

link

answered 08 Jul, 10:25

shubham732's gravatar image

3★shubham732
1
accept rate: 0%

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

(08 Jul, 18:29) aryanc4035★

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

answered 11 Jul, 18:55

patadi123's gravatar image

0★patadi123
1
accept rate: 0%

It is written for Pyth 3.5

(11 Jul, 18:56) patadi1230★

include<iostream>

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;

}

link

answered 20 Jul, 21:30

venky521's gravatar image

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

}

link

answered 02 Aug, 21:51

gaurav1508's gravatar image

3★gaurav1508
11
accept rate: 0%

edited 02 Aug, 22:15

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?

link

answered 01 Nov, 22:31

rael007's gravatar image

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★

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?

link

answered 01 Nov, 22:32

rael007's gravatar image

0★rael007
1
accept rate: 0%

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

(01 Nov, 23:22) rael0070★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

question asked: 16 Apr, 00:35

question was seen: 4,349 times

last updated: 02 Nov, 03:31