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

×

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.

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.3k415
accept rate: 47%

edited 5 hours ago

admin's gravatar image

0★admin ♦♦
18.4k348492529


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
314
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:

×13,928
×1,345
×479
×49
×4

question asked: 16 Apr, 00:35

question was seen: 334 times

last updated: 5 hours ago