PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Jeevan Jyot Singh
Tester: Lavish Gupta and Abhinav Sharma
Editorialist: Taranpreet Singh
DIFFICULTY
Easy
PREREQUISITES
Observation, Greedy
PROBLEM
We call a number x good if its binary representation is palindromic. For e.g. 107 is good because its binary representation is 1101011 which is palindromic while 10 is not good because its binary representation is 1010 which is not palindromic.
You are given a number n. Express it as a sum of at most 12 good numbers. If there exist multiple answers, print any one of them.
QUICK EXPLANATION
- Build a list of integers in the range [1, 1000] such that their binary representation is of the form 100\ldots001 and store it in decreasing order.
- For a given n, we can repeatedly pick the largest element in the list and subtract it from n.
- Since, at each subtraction, the number is halved, the process takes only O(log_2(N)) operations.
EXPLANATION
In this solution, we consider only the numbers, whose binary representation are of the form 100\ldots001 and are in the range [1, 1000]. We can see that the binary representation would be a palindrome. The list comes out to be [1,3, 5, 9, 17, 33, 65, 129, 257, 513].
Let’s try to answer a query, only using these numbers greedily. For current n, pick the largest number in this list \leq n, and add it to the answer list and subtract it from n.
The crucial observation here is that n is reduced by at least n/2. Ignoring element 1, we can see that consecutive elements are of the form x and 2 * x-1. If x is the largest element \leq n, then x \leq n \lt 2*x-1. Dividing all terms by 2, we have x/2 \leq n/2 \lt x - 0.5. Focusing on n/2 \lt x-0.5, we can see that n/2 \leq x, hence n is reduced by half every time.
This way, halving at each step, the number of operations does not exceed log_2(N), which is less than 12.
Note: Solutions used by testers used the DP approach, which essentially boils down to the above thing. They used all good numbers, unlike setter.
TIME COMPLEXITY
The time complexity is O(M*log(M) + T*log(N)) where M = 1000
SOLUTIONS
Setter's Solution
#ifdef WTSH
#include <wtsh.h>
#else
#include <bits/stdc++.h>
using namespace std;
#define dbg(Z...)
#endif
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
#define endl "\n"
#define sz(w) (int)(w.size())
using pii = pair<int, int>;
const double EPS = 1e-9;
const long long INF = 1e18;
const int N = 1e6+5;
void solve()
{
int n; cin >> n;
int temp = n;
vector<int> ans;
for(int i = 10; i >= 0; i--)
{
if(n == 1)
{
ans.push_back(1);
break;
}
if(n >> i & 1)
{
int remove = (1 << i) + 1;
if(n - remove >= 0)
ans.push_back(remove), n -= remove;
else
{
int small_remove = 1 << i-1;
if(small_remove > 1)
small_remove += 1;
ans.push_back(small_remove), n -= small_remove;
}
}
}
cout << sz(ans) << endl;
for(int x: ans)
cout << x << " ";
cout << endl;
}
int32_t main()
{
IOS;
int T; cin >> T;
for(int tc = 1; tc <= T; tc++)
{
// cout << "Case #" << tc << ": ";
solve();
}
return 0;
}
Tester's Solution 1
#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++;
assert('a'<=g and g<='z');
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 = 1000;
const int MAX_N = 1000 ;
#define ll long long
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int sum_len = 0;
int max_n = 0;
int max_k = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
int n;
vector<ll> pal ;
bool is_pal(int k)
{
string str ;
int curr = 1 ;
while(k)
{
if(k&curr)
{
str += '1' ;
k -= curr ;
}
else
{
str += '0' ;
}
curr *= 2 ;
}
string rev = str ;
reverse(str.begin() , str.end()) ;
return str == rev ;
}
void pre()
{
for(int i = 1 ; i <= MAX_N ; i++)
{
if(is_pal(i))
{
pal.push_back(i) ;
}
}
reverse(pal.begin() , pal.end()) ;
return ;
}
void solve()
{
n = readIntLn(1 , MAX_N) ;
vector<int> ans ;
int ind = 0 ;
while(n && ind < pal.size())
{
if(pal[ind] <= n)
{
ans.push_back(pal[ind]) ;
n -= pal[ind] ;
}
else
{
ind++ ;
}
}
cout << ans.size() << endl ;
for(int i = 0 ; i < ans.size() ; i++)
{
cout << ans[i] << ' ';
}
cout << endl ;
return ;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("inputf.txt", "r" , stdin);
freopen("outputf.txt", "w" , stdout);
#endif
// fast;
int t = 1;
t = readIntLn(1,MAX_T);
pre() ;
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
// cerr<<"maxN : " << max_n << '\n';
// cerr<<"maxK : " << max_k << '\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';
}
Tester's Solution 2
#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 = 4100;
const int MAX_LEN = 1e5;
const int MAX_SUM_LEN = 1e5;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
int sum_len = 0;
int max_n = 0;
int max_k = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
int n,k;
string s;
vector<int> v(1001);
vector<int> pal;
bool is_palindrome(int x){
vector<int> z;
while(x){
z.push_back(x&1);
x>>=1;
}
int l=0, r=z.size()-1;
while(l<r){
if(z[l]!=z[r]) return 0;
l++;
r--;
}
return 1;
}
void pre(){
for(int i=1; i<1001; i++){
if(is_palindrome(i)){
v[i] = i;
pal.push_back(i);
}
else v[i]=-1;
}
for(int i=1;i<1000; i++){
assert(v[i]!=-1);
for(auto h:pal){
if(i+h<=1000 && v[i+h]==-1) v[i+h] = h;
}
}
}
void solve()
{
n = readIntLn(1,1000);
vector<int> ans;
while(n){
ans.push_back(v[n]);
n-=v[n];
}
assert(ans.size()<=12);
max_k = max(max_k, (int)ans.size());
cout<<ans.size()<<'\n';
for(auto h:ans) cout<<h<<" ";
cout<<'\n';
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;
pre();
int t = 1;
t = readIntLn(1,MAX_T);
assert(1<=t && t<=1000);
for(int i=1;i<=t;i++)
{
solve();
}
assert(getchar() == -1);
cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
// cerr<<"maxN : " << max_n << '\n';
cerr<<"maxK : " << max_k << '\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 PALSUM{
//SOLUTION BEGIN
List<Integer> special;
void pre() throws Exception{
special = new ArrayList<>();
for(int i = 0; i< 12; i++)special.add(1<<i|1);
//Adds numbers of form 1000....01
}
void solve(int TC) throws Exception{
int N = ni();
List<Integer> ans = new ArrayList<>();
for(int i = special.size()-1; i>= 0; i--){
while(N >= special.get(i)){
ans.add(special.get(i));
N -= special.get(i);
}
}
hold(N == 0);
hold(ans.size() <= 12);
pn(ans.size());
for(int x:ans)p(x+" ");pn("");
}
boolean isPalindrome(int x){
String S = Integer.toBinaryString(x);
for(int i = 0, j = S.length()-1; i< j; i++, j--)
if(S.charAt(i) != S.charAt(j))
return false;
return true;
}
//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 PALSUM().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. 