CHFING - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Ritesh Gupta

Tester: Radoslav Dimitrov

Editorialist: Teja Vardhan Reddy

DIFFICULTY:

Easy

PREREQUISITES:

Math

PROBLEM:

Given n consecutive positive number which are k,k+1,k+2,...,k+n-1 respectively. Find the count of numbers that cannot represented as \sum\limits_{i=0}^{n-1}a_i* (k+i) where a_i>=0 \forall i and \sum\limits_{i=0}^{n-1}a_i \gt 0.

EXPLANATION

Firstly, we can never get numbers which are less than k.

Now using only one of the numbers we can get k,k+1,k+2,....k+n-1.
Using two numbers,we can get 2*k,2*k+1,2*k+2,....2*(k+n-1).
Similarly using x numbers , we can get x*k,x*k+1,.....x*(k+n-1).

Now , the other numbers we miss will be between k+n-1 and 2*k
similarly 2*(k+n-1) to 3*k
And x*(k+n-1) to (x+1)*k

Now since n-1>0 (from contraints), after a certain value of x, x*(k+n-1)+1 \geq (x+1)*k.
So after that onwards, all the numbers can be attained.
x*(n-1) \geq k-1 or x \geq ceil(\frac{k-1}{n-1}) (lets call this val).So for x \lt val, we need to take sum of (x+1)*k - x*(k+n-1).

which will be nothing but \sum\limits_{x=1}^{val-1}(k-x*(n-1)).

= k*(val-1)-(n-1)*\sum\limits_{x=1}^{val-1}x

= k*(val-1) - (n-1)*val*(val-1)/2.

Hence, total answer will be k-1 + k*(val-1) - (n-1)*val*(val-1)/2.

TIME COMPLEXITY

The above value can be computed in O(1) time per test.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
 
#define int long long
#define mod 1000000007
 
using namespace std;
 
int32_t main()
{
    int t;
    cin >> t;
 
    while(t--)
    {
        int n,k;
        cin >> n >> k;
 
        int total = (k-1)/(n-1);
        int first = k-1;
        int last = first - total*(n-1);
 
        int ans = first + last;
        total++;
 
        if(ans%2 == 0)
            ans /= 2;
        else
            total /= 2;
 
        ans = ((ans%mod) * (total%mod))%mod;
 
        cout << ans << endl;
    }
} 
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'
 
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
 
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
 
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int64_t mod = (int64_t)1e9 + 7;  
const int64_t inv2 = (mod + 1) / 2;
 
int64_t n, k;
 
void read()
{
    cin >> n >> k;
}
 
void solve()
{
    if(k <= n)
    {
        cout << (k - 1) % mod << endl;
        return;
    }
 
    int64_t cnt = ((k - n) / (n - 1)) % mod, answer = ((((k - n) % (n - 1)) % mod) * (cnt + 1)) % mod;
    cnt = cnt * 1ll * (cnt + 1) % mod;
    cnt = cnt * 1ll * inv2 % mod;
    cnt = (cnt * 1ll * ((n - 1) % mod)) % mod;
    answer = (answer + cnt) % mod;
    answer = (answer + k - 1) % mod;
    cout << answer << endl;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int T;
    cin >> T;
    while(T--)
    {
        read();
        solve();
    }
 
    return 0;
}
Editorialist's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
 
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define int ll
 
main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        n--;
        int wow,gg,val=(k-1)/n;
        if(val%2){
            wow=val+1;
            wow/=2;
            wow%=mod;
            wow*=(val%mod);
        }
        else{
            wow=val;
            wow/=2;
            wow%=mod;
            wow*=((val+1)%mod);
        }
        val%=mod;
        wow%=mod;
        gg=(k-1)%mod;
        val%=mod;
        gg*=val;
        gg%=mod;
        wow*=n;
        wow%=mod;
        gg-=wow;
        gg%=mod;
        gg+=mod;
        gg+=k-1;
        gg%=mod;
        cout<<gg<<endl;
    }
    return 0;   
}

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

8 Likes

Can you explain how the following condition is satisfied?

x ∗ ( k + n − 1 ) + 1 ≥ ( x + 1 ) ∗ k
2 Likes

Isn’t it the case that, there are in total
(x + 1) * k - x * (k + n - 1) - 1 unreachable number between (x + 1) * k and x * ( k + n - 1) . Arent you forgetting subtracting 1?

7 Likes

yes, i also have the same confusion. I did -1 means ((x + 1) * k -x * (k + n - 1)) - 1 during the contest and got wrong answer.

1 Like

For given numbers 9,10 the number of numbers missing is 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 , for given numbers 9,10,11 the number of missing numbers are 8 + 6 + 4 + 2 , for given numbers 9,10,11,12 the number of missing numbers are 8 + 5 + 2 . If we observe carefully we can observe a pattern, They are in A.P. The last number being : K - 1 and the common difference of the A.P. being N-1. So you need to just find the first term of the A.P and the number of terms of the A.P and then use the formula for sum of the terms of an A.P. i.e.
codechef
where : n = number of terms of the A.P.
a = first term of the A.P.
d = common difference of the A.P.

Here is the implementation and link for my solution: For solution click here

12 Likes

I think correct formula is ,considering what xyz_000 suggessted is (x+1)(k-1)-(x)*(x+1)(n-1)/2 where x=(k-1)/(n-1) except when k==n , answer=k-1;

https://www.codechef.com/viewsolution/24869725

Could you tell me why one sub-task of the second task is failing. i am using the same approach as you.

Thanks in Advance.

Overflow issue. Retype the same code in Python and the issue will be solved else use mod conditions properly .
Here this will help you understand better . Code in C++

https://www.codechef.com/viewsolution/24790923

https://www.codechef.com/viewsolution/24809818
Can anyone tell me why one sub-task of the second task is failing.

Thanks in Advance.

why my solution is not giving correct answer?
it paseed first subtask of 20 pts and 2 sub tasks of 80 pts. even after seeing the solution i didn’t find any bug in my code. please help…
here is link to my code…

https://www.codechef.com/viewsolution/24841033

I think because of overflow. This term n2(k-1) in ur code may exceed long long range so u need to use modulo here too.

C++::
I think the final solution posted is a bit wrong as the forgot to subtract one in subsequent cases

I got the answer as (k-1)(c+1)- (c(c+1)/2)*(n-1) . where c = (k-1)/(n-1). N = 1000000007

Just guide me where to put modulo N.
Attempts : -

  1. ( ( (c + 1 )%N )* ( ( k - 1 )% N ) ) % N this for first term
    ( ( ( ( c %N) * ( (c + 1) %N) / 2) % N) * ( (n - 1) %N) ) %N for second term and finally (first - second ) % N.
    I got WA in some Subtasks. Please tell why this is wrong.
    Full Code for Reference :
    #include
    using namespace std;
    int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long int t, N=1000000007;
    cin>>t;
    while(t–){
    unsigned long long int n, k;
    cin>>n;
    cin>>k;
    unsigned long long int c = ((k-1)/(n-1));
    unsigned long long int a = (((c+1)%N)((k-1)%N))%N,
    b =((((c%N)
    ((c+1)%N)/2)%N)*((n-1)%N))%N;
    if(a>=b)
    {
    cout<< a-b<<"\n";
    }
    else
    {
    cout<< a - b + N<<"\n";
    }
    }
    return 0;
    }

Can someone please let me know what’s wrong with my formula and the way I have implemented it.
I tried some test cases and it was giving me the correct answer. Can you please give a test case so that I can understand my mistake?
https://www.codechef.com/viewsolution/24876496

when you are multiplying by the modular inverse of 2 i.e. 500000004 , the number may be greater than the range of unsigned long long int, so i advice using python as python as unlimited range for calculating multiplication.

The python implementation of your exact same code given correct answer AC !
https://www.codechef.com/viewsolution/24876736

The link posted is showing access denied

updated the link, check now

You need to work on your modular arithmetic rather than just using python.

1 Like

Alright, here’s my method. It gives WA for one test case. Either my logic or my program is flawed, help me figure out my mistake.

Let’s say k=6 and n=3. We have 6, 7, 8. Divide the whole numbers into 6 sets as follows-

0, 6, 12, 18, 24…
1, 7, 13, 19, 25…
2, 8, 14, 20, 26…
3, 9, 15, 21, 27…
4, 10, 16, 22, 28…
5, 11, 17, 23, 29…

Note that if one member of any of these set is achieved the ones ahead of that would be achieved as well, by simply adding 6. For example if we get 14, then we can keep on adding 6 to get 20, 26, 32 and so on.

From the first set we can’t get 0 (which is not to be counted).
From the second set we can’t get 1 (+1)
From the third set we can’t get 2 (+1)
From the fourth set we can’t get 3, 9 (+2)
From the fifth set we can’t get 4, 10 (+2)
From the sixth set we can’t get 5, 11, 17 (+3)

So our answer is 1+1 + 2+2 + 3.

Try this method yourself for various cases and you’ll notice the pattern.
For example if k=9 and n=4, then the answer will be 1+1+1 + 2+2+2 + 3+3
For k=14 and n=5 answer is 1+1+1+1 + 2+2+2+2 + 3+3+3+3 + 4
For k=13 and n=4 answer is 1+1+1 + 2+2+2 + 3+3+3 + 4+4+4

The number of terms in the series is k-1 and the number of times each number repeats is n-1 (except the last one which does not necessarily appear n-1 times, see examples above).

Based on that we can create a formula (try it yourself, it’s easy) which is-

(n-1) × (1+2+3…+ x) + (x+1) × (k-1)mod(n-1)

Where x is the GIF of (k-1)/(n-1)

Check my solution here.

Edit : I compared my program with the official solution and they matched in few random inputs, but it’s some specific test case (as seen here) where I’m going wrong (which I’m unaware of), any help will be appreciated.

with numbers from [a, b]. assume a = k, b = k + n -1
Minimum Number = a, Maximum Number = b.
So Minimum number which can be formed is a + a = 2a. This means all the numbers from (b + 1) to (2a - 1) can’t be formed. continuing this process-
(2 * b + 1 to 3 * a - 1 (3 *a is excluded as 3 * can be expressed a + a + a)
3 * b + 1 to 4 * a - 1.
we have to continue this until for some x there range x * b + 1 is lesser than (x + 1) * a;
That means x * b + 1 >= (x + 1) * a.

1 Like

The numbers that are gonna miss is between x*(k+n-1) to (x+1)k EXCLUSIVE FROM BOTH SIDES!!! We can construct both x(k+n-1) and (x+1)*k, hence, the number of numbers that we cannot generate in that EXCLUSIVE INTERVAL is (x+1)k - x(k+n-1) - 1, NOT JUST (x+1)k - x(k+n-1) .