Valleys and Hills VANDH Solution Codechef

Valleys and Hills VANDH Solution

Chef built a binary string SS that has exactly NN hills and MM valleys.

  • hill is any index 1<i<|S|1<i<|S| such that both its neighbors are strictly smaller than it, i.e, Si−1<SiSi−1<Si and Si+1<SiSi+1<Si.
  • valley is any index 1<i<|S|1<i<|S| such that both its neighbors are strictly larger than it, i.e, Si−1>SiSi−1>Si and Si+1>SiSi+1>Si.

Chef thinks that his string SS is the shortest among all binary strings with NN hills and MM valleys. You don’t quite trust his words, so to verify his claim you would like to find the shortest binary string with exactly NN hills and MM valleys.

If there are multiple possible binary strings of the least length satisfying the given condition, you may print any of them.

Input Format

  • The first line of input will contain a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains two space-separated integers NN and MM, the required number of hills and valleys respectively.

Output Format

For each test case, output two lines.

  • The first line contains the length of the binary string you constructed to satisfy the given conditions.
  • The second line contains the string itself.

Constraints

  • 1≤T≤25001≤T≤2500
  • 1≤N≤5001≤N≤500
  • 1≤M≤5001≤M≤500
  • The sum of lengths of the answer strings across all test cases does not exceed 2⋅1052⋅105

Subtasks

Subtask 1 (10 points):

  • 1≤N≤501≤N≤50
  • 1≤M≤501≤M≤50
  • You may output any string of length not exceeding 320320 containing exactly NN hills and MM valleys: it need not be shortest by length. It is guaranteed that at least one such string with length ≤320≤320 exists.

Subtask 2 (90 points):

  • Original constraints
  • The binary string you construct must be shortest by length.

Sample Input 1 

3
3 2
2 3
3 3

Sample Output 1 

7
0101010
7
1010101
8
01010101

Explanation

Test case 1: The given string has hills at indices 2,4,62,4,6 and valleys at indices 3,53,5. It can be verified that there is no string of length 66 or less with 33 hills and 22 valleys. Note that for subtask 11, a binary string like 001010100001010100 will also be accepted as a valid output, even though it is not shortest by length.

Test case 3: Apart from the given string, another possible string of length 88 that has 33 hills and 33 valleys is 1010101010101010. You may print any of them.

SOLUTION

Program Python: Valleys and Hills VANDH Solution in Python

for i in range (int(input())):
    n,m = map(int,input().split())
    x = ''
    if m==n:
        for i in range (n+1):
            x+="01"
    elif m>n:
        for i in range(n+1):
            x+="10"
        for i in range(m-n-1):
            x+="110"
        x+="1"
    else:
        for i in range(m):
            x+="01"
        for i in range(n-m):
            x+="010"
    print(len(x))
    print(x)

Program C++: Valleys and Hills VANDH Solution in C++

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
       int n,m;
       cin>>n>>m;
       string ans = "";
       if(m==n)
       {
           for(int i=0;i<n+1;i++)
           {
               ans+="01";
           }
       }
       else if(m>n)
       {
           for(int i=0;i<n+1;i++)
           {
               ans+="10";
           }
           for(int i=0;i<m-n-1;i++)
           {
               ans+="110";
           }
           ans+="1";
       }
       else
       {
           for(int i=0;i<m;i++)
           {
               ans+="01";
           }
           for(int i=0;i<n-m;i++)
           {
               ans+="010";
           }
       }
       cout<<ans.size()<<endl;
       cout<<ans<<endl;
    }
    return 0;
}

December Long Challenge 2021 Solution

Leave a Comment