CHFHEIST - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

Arithmetic Progression

PROBLEM

Chef is planning a heist in the reserve bank of Chefland. They are planning to hijack the bank for D days and print the money. The initial rate of printing the currency is P dollars per day and they increase the production by Q dollars after every interval of d days. For example, after d days the rate is P+Q dollars per day, and after 2d days the rate is P+2Q dollars per day, and so on. Output the amount of money they will be able to print in the given period.

QUICK EXPLANATION

  • Ignoring the last D \bmod d days, all days are divided into D/d groups of d days each where first d days Chef receives P dollars, next d days Chef receives P+Q dollars, and so on.
  • Each group contains d values, so we can calculate the sum of dollars for 1 person in each group and multiply by d.
  • The sum of values in each group is d times the sum of Arithmetic Progression with initial term P, common difference Q, and number of terms D/d.
  • Last D \bmod d days, the Chef receives the same amount, calculated by computing the nth term of a similar Arithmetic Progression.

EXPLANATION

For subtask 1, we can iterate up to D, maintaining track of the number of dollars earned and current earning per day, so I’ll focus on complete solution.

Let us see what the sequence looks like with D = 11, d = 4 for some P and Q

Day			Dollars
1			P
2			P
3			P
4			P
5			P+Q
6			P+Q
7			P+Q
8			P+Q
9			P+2*Q
10			P+2*Q
11			P+2*Q

We can see that the same value appears in groups of d days, except the last group which may have less than d elements. Let’s ignore those now.

Let’s consider these groups, we can see that the terms P, P+Q, P+2*Q form an arithmetic progression.

We need to compute d*P+d*(P+Q)+d*(P+2*Q) \ldots ... = d*(P+(P+Q)+(P+2*Q)+ \ldots )

What is the number of groups? In the above example, we had two groups, one with value P and one with value P+Q (Remember that we are ignoring the last group, which has less than d elements).

In the general case, we can see by basic maths that there are exactly N = D/d complete groups, and additionally, if D is not a multiple of d, there would be an incomplete group with D \bmod d elements.

Hence, ignoring last D \bmod d days, we can write sum of dollars earned as d * APsum(P, Q, D/d) where APsum(a, d, n) denotes the sum of first n terms of arithmetic progression with first term a and common difference d, given by formula \displaystyle \frac{n*(2*a+(n-1)*d)}{2}.

For the last D \bmod d days, the amount earned would be the same value, which is P+N*Q, since that is a part of (N+1)-th group. Hence, we can add (D \bmod d) * (P+N*Q) to account for dollars earned in last D \bmod d days.

In case of any doubt, refer to the implementations below.

TIME COMPLEXITY

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

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;
  
const int maxt = 1e5, maxD = 1e6, maxp = 1e6;
const string newln = "\n", space = " ";

int main()
{   
	int t; cin >> t;
	ll D, d, P, dP;
	while(t--){
	    cin >> D >> d >> P >> dP;
	    ll ans = P * D + dP * (d * (D / d - 1) * (D / d) / 2 + (D % d)  * (D / d)); 
	    cout << ans << endl;            
	}
} 	
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;


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) {
			assert(cnt > 0);
			if (is_neg) {
				x = -x;
			}
			assert(l <= x && x <= r);
			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, ' ');
}

int main(int argc, char** argv) 
{
#ifdef HOME
	if(IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	int T = readIntLn(1, 100'000);
	forn(tc, T)
	{
		int64_t D = readIntSp(1, 1'000'000);
		int64_t d = readIntSp(1, D);

		int64_t P = readIntSp(1, 1'000'000);
		int64_t dP = readIntLn(1, 1'000'000);

		//d*P+d*(P+dp)
		//D*P 
		//a=d*dp
		//b=D/d
		//a+2*a+3*a+..(b-1)*a = a*b*(b-1)/2
		//rem = D%d
		//rem*dp*b
		int64_t a = d * dP;
		int64_t b = D / d;
		int64_t rem = D % d;
		int64_t res = D * P + a*b*(b-1)/2 + rem * dP * b;

		printf("%lld\n", res);
	}
	return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class CHFHEIST{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    long D = nl(), d = nl(), P = nl(), Q = nl();
	    long rem = D%d;
	    long N = D/d;
	    long sum = d * apSum(P, Q, N);
	    sum += rem * nth(P, Q, N+1);
	    pn(sum);
	}
	long apSum(long a, long d, long n){
	    return (n*(2*a+(n-1)*d))/2;
	}
	long nth(long a, long d, long n){
	    return a+(n-1)*d;
	}
	//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 CHFHEIST().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

what’s wrong with these :-

void solve3(){
    ll D,d,P,Q;
    cin>>D>>d>>P>>Q;
    ll remainder = D%d;
    ll n = (D-remainder)/d;
    ll ans = d * (2*P + (n-1) * Q) * n * 0.5 + (P + n*Q)*(remainder);

    cout<<ans<<endl;  }
1 Like

bro it took me time to find out the issue and I figured out why it is not giving the correct ans was that you are multiplying it with 0.5. just change it to division
ll ans = (d * (2P + (n-1) * Q) * n ) / 2+ (P + nQ)*(remainder);

2 Likes

You are trying to multiply ‘int’ value with ‘float’.
Instead of multiplying by 0.5, try dividing by 2.

Can anyone tell me what’s wrong with this?
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main()
{
int t;
cin >> t;

while (t--) {
	ll D, d, P, Q;
	cin >> D >> d >> P >> Q;

	ll res = 0;
	ll n = D / d;
	ll rem = D % d;


	double f = (double) n / 2;
	res = d * (f * (2 * P + (n - 1) * Q));
	if (rem != 0) {
		res = res + (rem * (P + (n * Q)));
	} 
	cout << (ll) res << "\n";
}

}

I got wa for the second subtask, I even tried some test cases with a correct solution and I was getting correct output.

thanks @corack and @nimesh_04

Here i my solution. what is wrong ?

#include
#include <stdio.h>

int main()
{
unsigned short hijack_days,interval_for_increment,test_cases;
unsigned int printing_rate,new_printing_rate;
unsigned char hijack_days_short;

scanf("%d",&test_cases);


for(int i=0;i<test_cases;i++)
{
	scanf("%hd%hd%d%d",&hijack_days,&interval_for_increment,&printing_rate,&new_printing_rate);

	hijack_days_short=hijack_days;

	unsigned short next_interval_for_increment=interval_for_increment;
	unsigned int printed_amount=0;

	for(int i =0;i<(int)hijack_days_short;i++) //Even by using short type int it was not accepting
	{
		if(i+1>next_interval_for_increment)
		{
			next_interval_for_increment += interval_for_increment;

			printing_rate+=new_printing_rate;
		}
		printed_amount+=printing_rate;
	}

	printf("%d \n",printed_amount);
}

return 0;

}

There seems to be a type conversion error. If your ’ n ’ is completely divisible by 2, then it will work.
If, however, n/2 leaves a remainder, then ’ res ’ will lose value.

Try making 2 equations, one for each case.

1 Like

This problem can be solved without loops, try avoiding them as much as possible because they will increase time complexity. If TLE is your issue, try making a formula and doing it without loop.

If it is something else, please mention the issue. Also, please try to post the solution link instead of actual code as it makes it much easy to read and debug.

#include
using namespace std;

int main() {
// your code goes here
long t;
cin>>t;
for(int i = 0; i<t; i++){
long D,d,P,Q;
cin>>D>>d>>P>>Q;
long sum1 , sum2, sum3;
sum1 = DP;
long l,n,r;
l = D-d;
n = l/d;
r = l%d;
sum2 = Q
d*(((n+1)*n)/2);
sum3 = (n+1)Qr;
cout<<sum1+sum2+sum3<<endl;
}

return 0;

}

It was showing WA (wrong Answer )

My logic is -

  1. take user inputs
  2. A loop will go till the number of days bank is hijacked “D”
  3. if the day as soon as becomes greater to the interval “dCopy” (which is initially initialized as “d” when they are going to increase production -
    a)next interval date gets calculated by doing it dCopy=dCopy+d
    b)printing rate gets updated p=p+q
  4. In the bottom of loop total printed money is getting calculated by - amount = amount + rate"p"

It gave correct result for the sample inputs …and even for my custom inputs …

Sorry for the late reply, I tried what you said still couldn’t figure out what is wrong, anyway, thanks for the help.

Can someone please tell me …what is wrong with this code?
t = int(input())
while t:
D,d,P,Q = map(int,input().split())
div = D//d

num1 = (d*div)/2

num2 = 2*P + (div-1)*Q

num3 = D - (div*d)
num4 = P+(div*Q)
num5 = num3 * num4
num6 = num1 * num2
sum1 = num6 + num5
    
        
print(int(sum1))
t = t - 1

Can anyone tell me the error in this code.

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

Can someone tell me what is the problem in this code.

int D,d,p,q;;
cin>>D>>d>>p>>q;
long long money = 0;
int days = 0;
int n = D/d;
int extra_days = D%d;
money = d*((n*((2p)+((n-1)q)))/2);
money+=extra_days
(p+(n
q));
cout<<money<<endl;

Thanks in advance

Bro you are missing "" in "extra_days * (p+(nq));