PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Tejas Pandey
Tester: Abhinav sharma
Editorialist: Taranpreet Singh
DIFFICULTY
Easy
PREREQUISITES
None
PROBLEM
Find the smallest binary string S having exactly N hills and M valleys, where a hill is defined as a position 1 \lt p \lt |S| such that S_p \gt S_{p-1} and S_p \gt S_{p+1}, and a valley is defined as position p such that S_p \lt S_{p-1} and S_p \lt S_{p+1}.
QUICK EXPLANATION
- For N = M, alternating binary string with of length N+M+2 is the answer.
- Otherwise, if we have N \gt M, we can simply build the smallest string with N hills, and reduce the number of valleys to M.
EXPLANATION
Let’s handle base case first.
N = M
We need the same number of hills and valleys. We can start the string with either 0 or 1, and keep alternating, as each 1 creates a hill except at the border, and each 0 creates a valley except at the border.
We can see that string 01010101 has exactly 3 hills and 3 valleys
N \gt M
Let’s try applying the above approach here. Build a string with exactly N hills. For N = 4, the string looks like 010101010. We can see that it also created N-1 = 3 valleys. Since we have M \lt N, which implies M \leq N-1, hence we do not need to create more hills or valleys, just need to reduce the number of valleys to M.
Reducing the number of valleys
The position p formed a valley only because 1 is present on both sides of p. If we insert another 0 adjacent to that 0, neither of the two zeros forms a valley.
For example, 010101010 is a string with 4 hill and 3 valleys, while 0101010010 is a string with 4 hill and 2 valleys, 01010010010 is a string with 4 hills and 1 valley, and 010010010010 is a string with 4 hills and no valley.
Hence, we have a way to build a string with N hills and M valleys.
N \lt M
We can swap N and M, solve for N \gt M and flip the final answer.
How is the length minimized in the above solution
I’d assume N \gt M here.
- Since N hills are needed, at least N occurrences of 1 and N+1 occurrences of $0$s are needed so that N hills are formed. But now we have N-1 valleys as well. The length of the string is 2*N+1
- The two zeros at either end do not form a valley, but the rest all do. The only way to reduce the valley is to have at least two zeros consecutive. Since the length of the string has to be minimized, exactly two zeros are used whenever we need a non-valley between two hills. There are (N-1)-M such places, leading to string length being 2*N+1 + (N-1)-M = 3*N-M when N \gt M.
TIME COMPLEXITY
The time complexity is O(N+M) per test case.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
int sm = 0;
while(t--) {
int n, m;
cin >> n >> m;
assert(n > 0 && m > 0 && n <= 500 && m <= 500);
vector<bool> ans;
if(n < m) {
ans.push_back(1);
for(int i = 0; m; i++) {
if(i&1) {
ans.push_back(1);
if(n < 1) ans.push_back(1);
n--;
} else {
ans.push_back(0);
m--;
}
}
ans.push_back(1);
} else if(n > m) {
ans.push_back(0);
for(int i = 0; n; i++) {
if(i&1) {
ans.push_back(0);
if(m < 1) ans.push_back(0);
m--;
} else {
ans.push_back(1);
n--;
}
}
ans.push_back(0);
} else {
ans.push_back(0);
for(int i = 0; m; i++) {
if(i&1) {
ans.push_back(0);
m--;
} else {
ans.push_back(1);
n--;
}
}
ans.push_back(1);
}
cout << ans.size() << "\n";
sm += ans.size();
for(int i = 0; i < ans.size(); i++) cout << ans[i];
cout << "\n";
}
assert(sm <= 200000);
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
/*
------------------------Input Checker----------------------------------
*/
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
/*
------------------------Main code starts here----------------------------------
*/
const int MAX_T = 2500;
const int MAX_N = 1e6+5;
const int MAX_SUM_LEN = 1e5;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
void solve()
{
int n,m;
n = readIntSp(1, 500);
m = readIntLn(1, 500);
int swapped = 0;
if(n<m){
swap(n,m);
swapped = 1;
}
vector<pair<int,int> > v;
int sz = 0;
for(int i=0; i<n; i++){
v.push_back({0,1});
v.push_back({1,1});
sz+=2;
}
v.push_back({0,1});
sz++;
int cnt_val = n-1;
if(n==m){
v.push_back({1,1});
sz++;
cnt_val++;
}
int j = 2;
while(cnt_val>m){
v[j].second++;
sz++;
j+=2;
cnt_val--;
}
cout<<sz<<"\n";
for(auto h:v){
sum_len+=h.second;
for(int i=0; i<h.second; i++){
cout<<(h.first^swapped);
}
}
cout<<"\n";
return;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;
int t = 1;
t = readIntLn(1,MAX_T);
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_len << '\n';
// cerr<<"Maximum length : " << max_n << '\n';
// cerr<<"Total operations : " << total_ops << '\n';
//cerr<<"Answered yes : " << yess << '\n';
//cerr<<"Answered no : " << nos << '\n';
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class VANDH{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni(), M = ni();
StringBuilder ans = new StringBuilder();
if(N == M){
for(int i = 0; i<= N; i++)ans.append("01");
}else if(N > M){
for(int i = 0; i<= M; i++)ans.append("01");
for(int i = M+2; i<= N; i++)ans.append("001");
ans.append("0");
}else{
for(int i = 0; i<= N; i++)ans.append("10");
for(int i = N+2; i<= M; i++)ans.append("110");
ans.append("1");
}
pn(ans.length());
pn(ans.toString());
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new VANDH().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 