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

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

3★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%

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&lt;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");="" }="" <="" pre="">
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:27

venkat270593's gravatar image

1★venkat270593
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%

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<str.length();k++) freq[str.charAt(k)-97]++; Arrays.sort(freq); int f=1; for (int p=0;;p++) {if(freq[p]!=0) {for(int j=p+2;j<26;j++)
if(freq[j]!=freq[j-1]+freq[j-2]) {f=0; break; }

        break;
       }
       }       
       if(f==0)
        System.out.println("Not");
        else
        System.out.println("Dynamic");

  }  
    }          
}
link

answered 13 Jun, 19:39

yashendrarawat's gravatar image

0★yashendrarawat
11
accept rate: 0%

edited 13 Jun, 19:40

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

link

answered 15 Jun, 20:15

niks0763's gravatar image

2★niks0763
1
accept rate: 0%

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:

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

question asked: 16 Apr, 00:35

question was seen: 2,488 times

last updated: 15 Jun, 20:15