Valleys and Hills solution codechef December Long Challenge - TechTalkBot

Contents

• Valleys and Hills solution codechef
• For Solution
• Click Here!
  • • Input Format Valleys and Hills solution codechef
    • Output Format
    • Valleys and Hills solution codechef Constraints
    • Subtasks
    • Sample Input 1  Valleys and Hills solution codechef
    • Sample Output 1 
    • Valleys and Hills solution codechef Explanation
• 
  

Valleys and Hills solution codechef

• For Solution

  
  

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

• A 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.

• A 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 Valleys and Hills solution codechef

• 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.

Valleys and Hills solution codechef 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  Valleys and Hills solution codechef

3
3 2
2 3
3 3

Sample Output 1 

7
0101010
7
1010101
8
01010101

Valleys and Hills solution codechef Explanation

Test case 11: 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 33: 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.

• For Solution

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int t; cin>>t;

    while(t--)

    {

        int m,n;

        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;

}