PROBLEM LINK:Author: Avijit Agarwal 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_{i2} + F_{i1}$ holds for all $i \ge 3$. EXPLANATION:Finding the frequency of each character can be done in linear time. One possible way is below
Next we can say that because $F_i = F_{i1} + F_{i2}$ and $F_{i2}$ cannot be $0$, $F_i > F_{i1}$ 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_{i1}$ 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$.
AUTHOR'S AND TESTER'S SOLUTION:Author's solution can be found here asked 16 Apr, 00:35

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". answered 16 Apr, 01:02
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)

import java.util.*; class StringFact{ public static void main(String[] args) { Scanner sc = new Scanner(System.in);
} What was the mistake??? Showing Wrong Answer.Please explain answered 03 May, 13:02

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. answered 13 May, 22:54

If anyone needs to understand the problem in python code(Please do not copy: understand and reflect) import sys def fibs(d: list):
def solve(s): sets = set(s) #print(sets) a = [] for i in sets: a.append(s.count(i))
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)answered 25 May, 13:42

Hi, In the editorial section of author's solution the following block is there(https://gist.github.com/meooow25/fea592474e33b0817d3d0f4ad55685af)
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 answered 08 Jun, 01:28

https://www.codechef.com/viewsolution/19067870 https://www.codechef.com/viewsolution/19073896 these two are accepted but showing dif answers for the string mnnooopppppq answered 08 Jul, 10:25

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?
answered 11 Jul, 18:55

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;
} answered 20 Jul, 21:30

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);
n=k; do{ cnt=0; for(j=0;j<n1;j++) {="" if(b[j]="">b[j+1]) { max=b[j]; b[j]=b[j+1]; b[j+1]=max; cnt++; } } n; }while(cnt!=0);
} answered 02 Aug, 21:51

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? answered 01 Nov, 22:31
I clearly misread that the above solution had been accepted when in fact it has not. My apologies.
(01 Nov, 22:52)

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 nonzero 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? answered 01 Nov, 22:32
