CHFINVNT - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Souradeep Paul and Daanish Mahajan
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

Basic Math

PROBLEM

Given N, K and p, there are N gases numbered from 0 to N-1. Chef tries all gases one by one, first trying all gases x with x \bmod K = 0 in increasing order, then all gases with x \bmod K = 1 and so on, trying one gas on each day.

Given an integer p, determine the day on with gas numbered p shall be tried.

QUICK EXPLANATION

  • Grouping gases x having the same value of x \bmod K, we get K groups, where groups are processed one by one.
  • We can find the group in which p is present simply by computing p \bmod K.
  • First N \bmod K groups shall have \frac{N}{K}+1 elements, and rest K - N \bmod K groups shall have \frac{N}{K} elements
  • We need to count all elements in the first p \bmod K groups and then count the number of gases in the group same as p which are tried before p.

EXPLANATION

Let’s consider an example first. Say we have N = 27, K = 5. The gases would be processed in following order
0 5 10 15 20 25 1 6 11 16 21 26 2 7 12 17 22 3 8 13 18 23 4 9 14 19 24
We can divide above into groups bases on x \bmod K. We have

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

We can see that before processing any element in row r, all elements in rows before r are processed.

Let’s assume given p is in row r. So we need to find the number of elements in rows before row indexed r.

Observation: First N \bmod K rows contain \frac{N}{K}+1 elements, and rest K - N \bmod K rows contain \frac{N}{K} elements.

It is intuitive to see it this way. Let’s find C as the largest multiple of K such that C \leq N. In above example, C = 25 = K *\lfloor \frac{N}{K}\rfloor. We can see that dividing the first C gases into K groups contribute \lfloor \frac{N}{K}\rfloor gases in each group evenly. Now, only N \bmod K gases are left, each of which is divided into the first N \bmod K groups.

Hence, first N \bmod K groups have \lfloor \frac{N}{K}\rfloor +1 elements, and rest K - N \bmod K rows have \lfloor \frac{N}{K}\rfloor elements.

For computing the number of elements in the first r rows, we can see that

  • if r \leq N \bmod K, then all rows have \lfloor \frac{N}{K}\rfloor+1 elements, leading to \displaystyle r * \left(\left\lfloor \frac{N}{K}\right\rfloor+1\right) elements.
  • Otherwise first N \bmod K rows have \lfloor \frac{N}{K}\rfloor+1 elements, and r - N \bmod K rows have \lfloor \frac{N}{K}\rfloor elements, leading to \displaystyle (N \bmod K)* \left (\left \lfloor \frac{N}{K} \right\rfloor+1 \right) + (r - N \bmod K) * \frac{N}{K}
Simplicifation

We can write number of elements in first r rows as r * \left\lfloor\frac{N}{K}\right\rfloor + min(r, N \bmod K), as Each row contributes \left\lfloor\frac{N}{K}\right\rfloor and first min(r, N \bmod K) rows may contribute an additional element.

Hence, if we know row containing p, we can count the number of elements in rows before that row. Also, based on our grouping, we have p appearing in row indexed p \bmod K.

Now, within the current group r, First, r is processed, then K + r is processed, and so on. We want to find the index of p in the current row, which can be computed in the same way as computing the index of a term in AP. Specifically, p is processed at index n, such that n = (p-r)/K+1.

Summarizing, the day on which gas p is processed can be written as \displaystyle (p \bmod K) * \frac{N}{K} + min(p \bmod K, N \bmod K) + \frac{p-p \bmod K}{K} + 1 which can be computed in O(1) time.

TIME COMPLEXITY

The time complexity is O(1) per test case.

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds; 
#define int long long int
#define ordered_set tree<int, nuint_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
mt19937 rng(std::chrono::duration_cast<std::chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
#define mp make_pair
#define pb push_back
#define F first
#define S second
const int N=2005;
#define M 998244353
#define BINF 1e9
#define init(arr,val) memset(arr,val,sizeof(arr))
#define MAXN 501
#define deb(xx) cout << #xx << " " << xx << "\n";
const int LG = 22;


 
void solve(){

    int n, i, k;
    cin >> n >> i >> k;

    int ex = n % k, ind = i % k;

    int ans = 0;
    if(ind > 0){
        int p = n / k;
        ans += p * ind;
        if(ex > 0){
            ans += min(ex, ind);
        }
    }

    i++;
    ans += (i + k - 1) / k;

    cout << ans << endl;

}

 
 
#undef int 
int main() {
#define int long long int
ios_base::sync_with_stdio(false); 
cin.tie(0); 
cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("optput.txt", "w", stdout);
#endif
    
 
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    
    
 
return 0;  
 
}
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
    #include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

int solver(int N, int P, int K)
{
    --N;
    int Z = P % K;
    int S = N % K;
    int res = 0;
    if (Z <= S)
    {
	    res += Z * ((N + K) / K);
	    res += (P - Z) / K + 1;
    }
    else
    {
	    res += (S + 1) * ((N + K) / K);
	    res += (Z - S - 1) * ((N + K) / K - 1);
	    res += (P - Z) / K + 1;
    }
    return res;
}

int solverBF(int N, int P, int K)
{
    vector<pair<int,int> > v(N);
    forn(i, N)
	    v[i] = { i % K, i };
    sort(v.begin(), v.end());
    int res = 0;
    forn(i, N)
    {
	    if (v[i].second == P)
		    res = i;
    }
    return res;
}

int main(int argc, char** argv) 
{
#ifdef HOME
    if(IsDebuggerPresent())
    {
	    freopen("../in.txt", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    }
#endif
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    forn(tc, T)
    {
	    int N, P, K;
 		cin >> N >> P >> K;
 		int res = solver(N, P, K);
 		cout << res << endl;
    }
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class CHFINVNT{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), p = ni(), K = ni();
        int pInd = p%K;
        
        int G1 = N%K, G2 = K-G1;
        int S1 = N/K+1, S2 = N/K;
        int ans = -1;
        if(pInd < G1){
            ans = pInd*S1 + p/K;
        }else{
            ans = G1*S1 + (pInd-G1)*S2 + p/K;
        }
        pn(ans+1);
        hold(G1*S1 + G2*S2 == N);
    }
    //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 CHFINVNT().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:

2 Likes

spent 5 days to think about how to solve this, but couldn’t solve it
looks likes I need more practice . :slightly_smiling_face:

8 Likes

Same lol. First round and could solve only 2 questions :frowning:
But ig grinding is the only way :slight_smile:

1 Like

same bro two questions

yeah bro :neutral_face:

Solution: 49899026 | CodeChef
Why my solution is giving runtime error ?

Can’t we solve using binary search @taran_1407 ?I tried but due to floting point I was not getting correct answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const unsigned int M = 1000000007;


void solve()
{
    ll n,p,k;
    cin>>n>>p>>k;
    ll days=0;
    if(k==1||k>=n){
        days=p+1;
    }
    else if(p%k<=(n-1)%k){
        days=((n/k)+1)*(p%k)+(p/k)+1;
    }
    else{
        ll last=(n/k)*k;
        days+=n-last;
        ll x=n/k;
        days+=x*(p%k)+(p/k)+1;
    }
    cout<<((days==0)?1:days)<<"\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

Can someone explain why it is giving WA?

#include<iostream>
using namespace std;
int main() {
    int t;
    cin>>t;
    while(t--) {
        int n,p,k;
        cin>>n>>p>>k;
        if(n%k==0) {
            cout<<(p%k)*(n/k)+(1+(p/k))<<endl;
        }
        else {
            if(n%k>=p%k) {
                cout<<(p%k)*((n/k)+1)+(1+(p/k))<<endl;
            }
            else {
                cout<<(n%k)*((n/k)+1)+(p%k-n%k)*(n/k)+(1+(p/k))<<endl;
            }
        }
    }
    return 0;
}

How did you find out that ? It is observation ? or It is a specific math concept ?
Thank You

Continuing the discussion from CHFINVNT - Editorial:

Can any one please answer why are we taking minimum of (N mod K , P mod K)
i tried solution video but not satisfied with the explanation same with editorial
if someone can help me please reply to this comment

It can be explained using Pigeonhole principle.