CREATEBINSTR - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

The score of a binary string is defined as follows:

  • Each 0 has a value of A.
  • Each 1 has a value of B.
  • Each 01 subsequence has a value of C.
  • Each 10 subsequence has a value of D.

Given N, A, B, C, D, find the maximum possible score of a binary string of length N.

EXPLANATION:

The score depends on the number of zeros and ones in the string, so let’s fix these counts: suppose there are K zeros and N-K ones.
This will contribute A\cdot K + B\cdot (N-K) to the score.
We now need to figure out how to arrange these zeros and ones to maximize the score coming from the 01 and 10 subsequences.

Let x_{01} and x_{10} denote the number of 01 and 10 subsequences in the string.
Our goal is to maximize C\cdot x_{01} + D\cdot x_{10}.

Now, observe that each subsequence that’s of the form 01 or 10 must come from a pair consisting of one 0 and one 1.
Conversely, each pair of 0 and 1 in the string will correspond to either a 01 or a 10 subsequence too.
So, the number of 01 subsequences plus the number of 10 subsequences, equals the total number of pairs of a 0 and a 1.
That is, x_{01} + x_{10} = K\cdot (N-K), since we know there are K zeros and (N-K) ones.

With this, we can write x_{10} = K\cdot (N-K) - x_{01}, so that the quantity we’re trying to maximize now becomes

C\cdot x_{01} + D\cdot (K\cdot (N-K) - x_{01}) = x_{01}\cdot (C - D) + D\cdot K\cdot (N-K)

Here, the second term, D\cdot K\cdot (N-K) is a constant, so we’re really just trying to maximize x_{01}\cdot (C-D).

Looking at this quantity:

  • If C \geq D, ideally x_{01} should be as large as possible.
    The best we can do is to have x_{01} = K\cdot (N-K).
    It’s not hard to see that it’s always possible to achieve this, by simply constructing a sorted binary string, i.e. \underbrace{00\ldots 00}_{K} \ \underbrace{11\ldots 11}_{N-K}.
  • If C \lt D, the opposite is true and x_{01} should be as small as possible.
    The best we can do is x_{01} = 0, and again this is always possible by using reverse sorting:
    \underbrace{11\ldots 11}_{N-K} \ \underbrace{00\ldots 00}_{K}

An alternate way of looking at this is that once K is fixed, there are K\cdot (N-K) pair-subsequences, and we’re either making all of them 01 or all of them 10 depending on which of C or D is larger.
This gives us a simple way of writing the score:

A\cdot K + B\cdot (N-K) + \max(C, D)\cdot K\cdot (N-K)

The answer is the maximum of this across all 0 \leq K \leq N.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, a, b, c, d = map(int, input().split())
    ans = 0
    for x in range(n+1):
        ans = max(ans, a*x + b*(n-x) + max(c, d)*x*(n-x))
    print(ans)
1 Like
2

include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int t;
cin >> t;
while(t–)
{
int n;
cin >> n;
int a,b,c,d;
cin >> a >> b >> c >> d;
int ans=0;
if(n%2==1)
{
int count0=0;
int count1=0;
for(int i=1 ; i<=n-1 ; i+=2)
{
int w=2b + count0c2;
int x=2a + count1d2;
int y=a+b+ count0c + count1d + d;
int z=a+b+ count0c + count1d + c;

            if(x>=y && x>=z && x>=w)
            {
                ans=ans+x;
                count0+=2;
            }
            else if(y>=x && y>=z && y>=w)
            {
                ans=ans+y;
                count1++;
                count0++;
            }
            else if(z>=x && z>=y && z>=w)
            {
                ans=ans+z;
                count0++;
                count1++;
            }
            else if(w>=x && w>=y && w>=z)
            {
                ans=ans+w;
                count1+=2;
            }
        }
        
        int x= b + count0*c ;
        int y= a + count1*d ;
        
        if(x>y)
        {
            ans=ans+x;
        }
        else{
            ans=ans+y;
        }
    }
    else
    {
        int count0=0;
        int count1=0;
        for(int i=1 ; i<=n ; i+=2)
        {
            int w=2*b + count0*c*2;
            int x=2*a + count1*d*2;
            int y=a+b+ count0*c + count1*d + d;
            int z=a+b+ count0*c + count1*d + c;
            
            if(x>=y && x>=z && x>=w)
            {
                ans=ans+x;
                count0+=2;
            }
            else if(y>=x && y>=z && y>=w)
            {
                ans=ans+y;
                count1++;
                count0++;
            }
            else if(z>=x && z>=y && z>=w)
            {
                ans=ans+z;
                count0++;
                count1++;
            }
            else if(w>=x && w>=y && w>=z)
            {
                ans=ans+w;
                count1+=2;
            }
        }
    }
    
    cout << ans <<endl ;
}

}
“what is wrong with this code”