NOSEQ - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: still_me
Testers: the_hyp0cr1t3, rivalq
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given N, K, S, find a sequence B = [B_1, \ldots, B_N] such that:

  • B_i \in \{-1, 0, 1\}
  • \sum_{i=1}^N B_i\cdot K^{i-1} = S

EXPLANATION:

Let’s try to build B from its first position to its last.

Notice that we can rewrite \sum_{i=1}^N B_i\cdot K^{i-1} = S as S = B_1 + \sum_{i=2}^N B_i\cdot K^{i-1} = B_1 + K\cdot x for some integer x.

So, B_1 \equiv S \pmod{K}.
Notice that this (almost) uniquely determines what B_1 should be:

  • If S \equiv 0 \pmod{K}, choose B_1 = 0
  • If S \equiv 1 \pmod{K}, choose B_1 = 1
  • If S \equiv -1 \pmod{K}, choose B_1 = -1
  • If none of the above hold, no S-good sequence can exist.

The only edge case here is when K = 2, in which case 1 and -1 are equivalent and you can choose either one.

Now that we know B_1, let’s try to find B_2.
A bit of simple algebra tells us that \displaystyle S = \sum_{i=1}^N B_i\cdot K^{i-1} is equivalent to \displaystyle \frac{S-B_1}{K} = \sum_{i=2}^N B_i\cdot K^{i-2}.

Notice that the last equation is simply asking us to compute a good array for \frac{S-B_1}{K} of length N-1.
So, all we need to do is replace S with \frac{S-B_1}{K} and repeat the above process.

This allows us to compute the values of every B_i.
At the end of the process, if S \neq 0 or we couldn’t compute some B_i, the answer is -2; otherwise print the B array computed.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Setter's code (C++)
//	Code by Sahil Tiwari (still_me)

#include<bits/stdc++.h>
#define still_me main
#define endl "\n"
#define int long long int
#define all(a) (a).begin() , (a).end()
#define print(a) for(auto TEMPORARY: a) cout<<TEMPORARY<<" ";cout<<endl;
#define tt int TESTCASE;cin>>TESTCASE;while(TESTCASE--)
#define arrin(a,n) for(int INPUT=0;INPUT<n;INPUT++)cin>>a[INPUT]

using namespace std;
const int mod = 1e18;
const int inf = 1e18;

long long power(long long a , long long b , long long mod){
    if(b==0)
        return 1;
    long long res = power(a , b/2 , mod);
    res = res*res % mod;
    if(b%2)
        res = res*a % mod;
    return res;
}
int t = 0;

void solve() {
    t++;
    int n , k , s;
    cin>>n>>k>>s;
    vector<int> b(n);
    int i = 0;
    bool flag = 1;
    while(i < min(n , 61ll)) {
        if(s % k == 0) {
            s /= k;
        }
        else if((s-1) % k == 0) {
            s = (s-1ll) / k;
            b[i] = 1;
        }
        else if((s+1) % k == 0) {
            s = (s+1ll) / k;
            b[i] = -1;
        }
        else {
            flag = 0;
            // assert(false);
            // cerr<<t<<endl;
            break;
        }
        i++;
    }
    // cout<<s<<endl;
    if(!flag || s != 0) {
        cout<<"-2"<<endl;
    }
    else {
        print(b);
    }
}


signed still_me()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    // freopen("3.in" , "r" , stdin);
    // freopen("3.out" , "w" , stdout);
    tt{
        solve();
    }
    cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
    return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
    n, k, s = map(int, input().split())
    ans = []
    for i in range(n):
        if s%k == 0:
            ans.append(0)
            s //= k
        elif s%k == 1:
            ans.append(1)
            s = (s-1)//k
        elif s%k == k-1:
            ans.append(-1)
            s = (s+1)//k
    if s > 0: print(-2)
    else: print(*ans)
2 Likes

Good problem to practice Horner Algorithm.

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

#define FAST() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

#define mod 998244353
#define pb push_back
#define ll long long


/* Sorting on column basis */

bool sortcol(vector<ll>& v1,vector<ll>& v2 ) {
 
if(v1[0] == v2[0])
    return v1[1] < v2[1];
else
    return v1[0] < v2[0];
 

}


/*  declaring an array of size n

ll n;
cin>>n;
ll a[n];
for(ll i=0;i<n;i++)
{
cin>>a[i];
}

*/

/* declaring string of length n 

ll n;
cin>>n;
string s;
cin>>s;
ll len=s.length();

*/

/* Computing x^y mod p */

// ll power(ll x, ll y, ll p)
// {
//     ll res = 1;
 
//     x = x % p;
 
//     while (y > 0) 
//     {
//             if (y & 1)
//             res = (res * x) % p;
 
//         y = y >> 1; 
//         x = (x * x) % p;
//     }
//     return res;
// }



/* To check whether a number is prime or not */

bool isPrime(int n)
{
   
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    if (n % 2 == 0 || n % 3 == 0)
        return false;

    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}

// ll power(ll x, ll y, ll M)
// {
// if (y == 0)
// return 1;

// ll p = power(x, y / 2, M) % M;
// p = (p * p) % M;

// return (y % 2 == 0) ? p : (x * p) % M;
// }

// ll mI(ll A, ll M)
// {
// return power(A, M - 2, M);
// }

// ll gcd(ll a, ll b)
// {
// if (a == 0)
// return b;
// return gcd(b % a, a);
// }

// ll lcm(ll a,ll b)
// {
// return (a*b)/__gcd(a,b);
// }

void Rush()
{
unsigned ll n,k,s;
cin>>n>>k>>s;

vector<ll> a(n);    


unsigned ll sum = 0;

ll idx = -1;

for(ll i = 0; i < n;i++)
{
    a[i] = (ll)pow(k,i);
    sum += a[i];

    if(sum >= s)
    {
        idx = i;
        break;
    }
}


if(idx == -1)
{
    cout<<"-2"<<"\n";
    return;
}
else if(sum == s)
{
   for(ll i = 0; i < n;i++)
   {
        if(a[i] > 0)
            cout<<"1"<<" ";
        else
            cout<<"0"<<" ";
   }

    cout<<"\n";
    return;
}
else
{


    for(ll i = idx ; i>= 0;i--)
    {
        if(sum - a[i] >= s)
        {
            if(sum - 2ll*a[i] >= s)
            {
                sum -= 2ll*a[i];

                a[i] = -1;
            }
            else
            {
                sum -= a[i];
                a[i] = 0;
            }
        }
        else
        {
            a[i] = 1;
        }
    }

    if(sum != s)
    {
        cout<<"-2"<<"\n";
        return;
    }
    for(ll i = 0; i < n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<"\n";
}

}

int main()
{
    FAST(); 

    #ifndef ONLINE_JUDGE 
    freopen("Ip.txt", "r", stdin);
    freopen("Op.txt", "w", stdout);
    #endif

   // ll test = 1;
    
    ll test;
    cin>>test;
  
    while(test--)
    {
        Rush();    
    }

    return 0;
}

I am not able to get why this code fails on test 2 , any idea what’s wrong ?

I solved it using a different approach.
I build the array from last to first.

First we pre calculate what maximum number we can make using first ‘i’ indexs
Max number that can be made using first i index is 1 + k + k^2 +… k^i-1 .
But we got to take care of overflow, and only store for those i, such that maximum number that we can make till i <= s.
Then we greedily try to construct the number ‘s’.
We know that some index are way too big, so they will never be used.
For example n=4, k=5, s = 19 ,
index 3, could give us these number 125, 0, -125. We can observe that we should leave index 3 as 0.
So we would recusively try to construct number ‘s’ using some indexes (0,1,…idx).
That what function find(s, idx) does in my code.
So, in find(s, idx) :
We need to set b[0,1,…idx] such that the corresponding number is s. Or we need to set the possible variable false, if it is not possible.

We start by seeing maximum number that can be formed by previous powers,
which is 1 + k + k^2 … k^(idx-1). (We already precomputed that)

If the number can be formed by using only index [0…idx-1] then we don’t use idx, and set b[idx]= 0.
Otherwise we need to use b[idx], we set it 1 .
Now we have current sum = k^idx.
required sum is s, so we would need req = s - sum to be build from indexes[0…idx-1].

if req >= 0 we just call find(req, idx-1).
else we need negative sum from [0…idx-1.
Then we just call find(req, idx-1) and then reverse sign of all b[0,1…idx-1].

Its hard to prove, and you have to be very careful about the overflows, base cases in the implementation. But this is the overall idea.

Code : https://www.codechef.com/viewsolution/84386333

2 Likes

I have an easy intuitive solution for that.
Just take a var = 0 and check for decreasing powers of K(from n-1 to 0), whether adding/subtracting this to/from var will result in bringing var closer to s. Fill suitably 1 or -1 at this index in the answer array, and modify var.
After traversing all powers of K, if var != s, then print -2, else print the answer array.
My submission
Note why this works is because of the fact that K^N will always be greater than sum of K^(N-1) + K^(N-2) + … + K + 1, so K^N will have the greatest hand in determining the closeness of var to required s.

4 Likes

I think the real contest started this problem onwards, the first 3 were fairly trivial. This problem was just so good!

Nice approach.

1 Like

Hello @iceknight1093 and thank you for this challenging problem but I would need a little help here because I can’t understand why I’m wrong when I have the same algorithm as the solution

During the contest I used the same algorithm as your solution but I always got it wrong, and I would like to understand why
Thank you in advance for your help
here are the submission links

contest submission 2
pratice submission

there, a snippet of ma pratice submission, which still gave me wrong

        bool flag = false;
        vi BB(N, 0);
        for(int j=0; j < N; j++){

            if(  S%K == 0 ){
                BB[j] = 0;
                S = S/K;
            }else if( (S-1)%K ==0){
                BB[j] = +1;
                S = (S-1ll)/K;
            }else if( (S+1)%K ==0 ){
                BB[j] == -1;
                S = (S+1ll)/K;
            }else{
                flag = true;
                break;
            }

        }

        if( flag || S != 0){
            cout << "-2" << endl;
        }else{
            trav(elt, BB){
                cout << elt << " ";
            }
            cout <<  endl;
        }

nevermind, my bad :sleepy:
i got stuck here for 1 hour because of (comparaison) ‘==’ instead of ‘=’ (affectetion) in the second ‘else if’
and lost all my chances to get :star::star::star::star: STARS :sob::sob::sob:
still have a lot to learn…

Why the 61ll in while(i < min(n , 61ll)) in the Setter’s code?