adplus-dvertising

Binary String Happiness CodeChef Solution

We Are Discuss About CODECHEF SOLUTION

Binary String Happiness CodeChef Solution

Binary String Happiness CodeChef Solution

For a binary string¬†SS, define its¬†beauty¬†to be the maximum number of¬†substrings¬†SS¬†can be partitioned into, such that each substring has strictly more ones than zeroes. For example, the beauty of¬†1101111011¬†is¬†33, as it can be partitioned as¬†[110][1][1][110][1][1]. If such a partition doesn’t exist, the beauty is defined to be¬†00.

Also, define the happiness of a binary string to be the maximum beauty over all its substrings. For example, the happiness of the string S=010011011S=010011011 is 33, which is the beauty of its substring 1101111011.

You are given NN binary strings S1,S2,…,SNS1,S2,…,SN. You have to process QQ queries:

  • Each query consists of two integers¬†L,RL,R, where¬†1‚ȧL‚ȧR‚ȧN1‚ȧL‚ȧR‚ȧN.
  • The result of the query is the¬†maximum¬†possible happiness of¬†Sp1+Sp2+‚ĶSp(R‚ąíL+1)Sp1+Sp2+‚ĶSp(R‚ąíL+1), where¬†pp¬†is some permutation of¬†{L,L+1,‚Ķ,R‚ąí1,R}{L,L+1,‚Ķ,R‚ąí1,R}¬†and¬†++¬†denotes the concatenation operation.

Input Format

The first line of input contains two space-separated integers NN and QQ, the number of strings and the number of queries. Then, 2N+Q2N+Q lines follow:

  • For each¬†1‚ȧi‚ȧN1‚ȧi‚ȧN,¬†SiSi¬†is represented by two lines. The first line contains the length of¬†SiSi¬†and the second line contains¬†SiSi¬†itself.
  • Each of the next¬†QQ¬†lines contains two integers,¬†LL¬†and¬†RR, denoting the query parameters

Output Format

For each query, print the maximum possible happiness of the concatenation of some permutation of the given interval on a new line.

Binary String Happiness CodeChef Solution

Constraints

  • 1‚ȧN,Q‚ȧ1051‚ȧN,Q‚ȧ105
  • |Si|‚Č•1|Si|‚Č•1¬†for each valid¬†ii.
  • Every string consists of characters which are either ‘0’ or ‘1’.
  • The sum of the lengths of all the input strings doesn’t exceed¬†106106.

Subtasks

  • Subtask 1 (30 points):¬†The sum of¬†R‚ąíL+1R‚ąíL+1¬†over all queries doesn’t exceed¬†106106.
  • Subtask 3 (70 points):¬†No further constraints.

Sample Input 1 

4 1
1
0
2
11
3
010
4
0110
2 4

Sample Output 1 

3

Explanation

Binary String Happiness CodeChef Solution

It is optimal to concatenate as S3+S4+S2S3+S4+S2 to get 010011011010011011 with a happiness value of 33.

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.

If You Want To Learn Something New Then Visit Our Official Channel YOUTUBE

Related Posts

Leave a Reply

Your email address will not be published.