PALSUM - Editorial

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. :slight_smile:

1 Like
#include <bits/stdc++.h>
#define ll long long int
#define vchk(v) for(auto i:v)cout << i << " ";
#define p(a) cout << a << endl;
#define MOD 1000000007
using namespace std;

void solve()
{
    int n; cin >> n;
    vector<int> v;
    int mask=1;
    int tmp=0;
    for(int i=0; i<12; i++)
    {
        tmp = n & (mask << i);
        if(tmp>=1)
        {
            v.push_back(tmp);
        }
    }
    cout << v.size() << endl;
    for(auto i:v)cout << i << " ";
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
	
	//sieve(10000001, isPrime);
	int t; cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Why is it wrong? My approach was every bit value like 1, 2, 4, 8, 16, 32, 64, … and so on. These are good numbers and also they can sum up to make value n.
Where I went wrong?

2,4,8,16,32 in bitwise form are 10,100,1000,10000,100000 which are not palindrome.

1 Like

My approach was to go through all bits of the required value N, starting from the highest bit. If the x-th bit is set, then use either 2^x-1 or 2^x+1 as the next good number. The uses of -1 and +1 are interleaved, so they nicely cancel each other if the total amount of good numbers in the answer is even. If not, then it’s possible to just append an extra 1 to the answer.

2 Likes

But we can write 2 as both 10 and 010, tell me if we 010 doesn’t mean 2? same for every pow of 2.

Leading zeroes are ignored unless explicitly mentioned.

Okay. Thanks for replying.

as you are saying this ae the list 1,3,5,9,17,33,65,129,257,513
my question is 7,15,… also gives palindromic as 7’s binary is 111 and 15’s is 1111

can someone explain why they are only considering above list ??

1 Like

same question

We are not required to provide the optimal solution to solve this problem. For example, a large palindromic number, such as 765 (or 1011111101 in binary format), can be just represented by itself. But the solution from the editorial will decompose it into a sum of multiple numbers. And this is perfectly fine, because it does not exceed the 12 numbers limit.

I know that any number n >= 1 can be expressed as a sum of power of 2.
But here how can we know that n can be expressed as sum of no’s whose binary string format is palindrome ?

7 and 15 aren’t of the format 10…01. If you observe he did a +1 to 0,2,4,8…,512 to get 1,3,5,9…513 which would result in every number being a palindrome

#include <bits/stdc++.h>

using namespace std;

void solve(){

int n;cin>>n;

vector<int> ans;

int bits = (int)log2(n)+1;

for(int i=bits-1;n>0 and i>=0;--i){

    int t = (1<<i);

    if(t>1) t--;

    if(n-t>=0){

        ans.push_back(t);

        n-=t;

    }

}

while(n) {ans.push_back(1);n--;}

cout<<ans.size()<<endl;

for(auto i:ans) cout<<i<<" ";

cout<<endl;

}

int main()

{

int t;cin>>t;

while(t--) solve();

return 0;

}

could you provide edge cases for this approach?

Here is my code based on ssvb’s idea and submission

/* Use the observation  that 2^x - 1 and 2^x + 1 are 
 * palindrome. 
 * For example, 2 = (10), 3 = (11) 1 = 1 
 * 				8 = (1000), 9 = 1001, 7 = 111
 * We do not include leading zeroes. 
 * 
 * 
 * Then, since we know N = 1000 < 2^10, 
 * iterate from 1...10 
 * and check (1 << i) & n. 
 * If (1 << i) & n   is true, then 
 * add (1 << i) to a vector. 

 */ 
void palindromic_binary_sum() {
	int n;
	cin >> n;
	vector<int> good_numbers;
	// Variable used to add close to even amounts of 2^x + 1 and 2^x - 1
	int parity = 0; 
	// O(1)
	for (int i = 1; i < 10; i++) {
		int bitmask = (1 << i); 
		if ((bitmask & n)) {
			if (parity) {
				good_numbers.push_back(bitmask + 1);		
			} else {
				good_numbers.push_back(bitmask - 1); 
			} 
			parity ^= 1; 
		} 
	}
	
	 /* The number of good numbers is proportional to log N, as
	  * n can have at most log(N) bits set to 1. 
	  * Therefore, O(log_N + a), where a is the number of 1's that we add. 
	  */  
	int sum_so_far = accumulate(begin(good_numbers), end(good_numbers), 0); 
	/* Since the sum of the good numbers is not guaranteed to be equal to n, 
	 * for example, 
	 * if n = 2, the only good number is 1, so sum_so_far = 1
	 * if n = 5, the only good number is 3, so sum_so_far = 3. 
	 * , so print n - sum_so_far amount of 1's.
	 * Time complexity: O(a) where a is the number of 1's that we have to add. 
	 */ 
	while (sum_so_far < n) {
		good_numbers.push_back(1); 
		sum_so_far++;
	} 
	//Print answer
	cout << good_numbers.size() << endl;
	// O(log N) 
	for_each(cbegin(good_numbers), cend(good_numbers), [](int good_number) {
		cout << good_number << " ";
	}); 
	cout << endl;
	// Total time complexity per test case: O(log N)
	// The number of 1's that are being added is trival as N gets bigger. 	 
} 

we consider only the numbers, whose binary representation are of the form 100…001

does the palindromes in 10…01 form only counts to good numbers ?
what about these :- {7,15,21,27,31,45,63,…}
?

does 7 , 15 ,… are not palindrome ?

21,27 ,45 is palindrome , rit ? and it doesnt come to 2^x - 1 or 2^x + 1

21,27 ,45 is palindrome , rit ? and it doesnt come to 2^x - 1 or 2^x + 1

Everyone knows that 21 (which is 10101 in binary format) can be represented as 2^0 + 2^2 + 2^4. Now in order to turn it into a sum of palindromes, this expression can be changed to (2^0 - 1) + (2^2 + 1) + (2^4 - 1). This became a sum of 3 palindromic numbers. Except that there’s one minor problem: -1 is used twice, +1 is used once and they don’t compensate each other. But this may only happen when we have an odd amount of numbers in the answer. And can be easily resolved by just appending 1 to the answer: (2^0 - 1) + (2^2 + 1) + (2^4 - 1) + 1

BTW, this particular solution may output a useless 0 as a part of the sum (if bit 0 is set). But this is fine, because the judge system happens to consider 0 as a valid palindrome too (if this wasn’t the case, then 0 could be filtered out). Here’s a link to my C++ submission in practice mode: Solution: 54231109 | CodeChef

It’s also easy to prove that this solution never produces a sum of more than 10 numbers in the answer, so the problem’s constraints are very generous.

Just rate my approach.Solution is being accepted.
I just used the logic to use the numbers which are 1 less than the numbers which can be expressed as the power of 2 ,for example 0,1,11,111,1111 etc. I stored all such numbers (less than 1000) inside a vector v1. Jumping to the approach I searched a number less than equal to the ‘n’ in the vector v1 using upper bound approach.and subtracted it from n .Continuing this process till n!=0 .

#include<iostream>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
int main ()
{
    int i=0,t,k;
    vector <int>v1;
    
     while(1)
     {
         if((1<<i)>1000)
         break;
        v1.push_back(1<<i);
        v1[i]=v1[i]-1;
          
          i++;
     }
    k=v1.size();
    
    cin>>t;
    while (t--)
    {
        
        int n,i,nearest,count=0;

        vector<int> v2;
        cin>>n;
       
    while(n!=0)
    {
        auto j=upper_bound(v1.begin(),v1.end(),n);
        j--;
        n=n-*j;
        v2.push_back(*j);
        count++;
    }
    cout<<count<<"\n";
    for(i=0;i<count;i++)
    cout<<v2[i]<<" ";
        
     cout<<"\n";
    }
    return 0;

}

easy to understand>>

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

string decimalToBinary(int n)
{
string s = bitset<32> (n).to_string();

const auto loc1 = s.find('1');
 
if(loc1 != string::npos)
    return s.substr(loc1);
 
return "0";

}

bool isPalindrome(string str)//for strings only
{
int l = 0;
int h =str.size() - 1;

while (h > l)
{
    if (str[l++] != str[h--])
    {
        return false;
    }
}
return true;

}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);

vector<int>pal;
for (int i = 1; i <=1000 ; ++i)
{
	if(isPalindrome(decimalToBinary(i)))pal.push_back(i);
}
reverse(pal.begin(),pal.end());

int t;
cin >> t;
while(t--){
	int n,i=0;
	cin >> n;
	vector<int>ans;

	while(n && pal.size()>i){
		if(pal[i]<=n){
			ans.push_back(pal[i]);
			n-=pal[i];
		}
		else i++;
	}
	cout << ans.size() <<"\n";
	for(int i=0;i<ans.size();i++)cout << ans[i] <<" ";
	cout << "\n";
}

}

1 Like