# DATE1 - Editorial

Author: Daanish Mahajan
Testers: Shubham Anand Jain, Aryan
Editorialist: Nishank Suresh

Cakewalk

None

# PROBLEM:

Chef has 1 lit candle, and infinitely many unlit candles. Each second, he can take one lit candle and use it to light x unlit ones. y seconds after a candle is lit, it runs out of wax and is extinguished. What is the maximum number of candles which can be lit at time t?

# QUICK EXPLANATION

The answer is x\cdot y if t\geq y and x\cdot t+1 otherwise

# EXPLANATION:

When t\geq y, the only active candles at time t are the ones which lit up time t, t-1, t-2, \dotsc, t-y+1; y seconds of time in total. Any candle which was lit before that will also be extinguished before time t. In particular, because t\geq y, t-y+1 \geq 1; which means that the candle Chef started out with at time 0 will also be extinguished. Thus, we have y seconds, in each of which x candles are lit. This gives us x\cdot y candles in total.

t\geq y can be solved as above. Now we also have to worry about the case when t < y. However, t < y just means that no candle which is lit up will extinguish before time t - so all we need to do is count the number of candles which are lit.
x candles light up at each of the seconds 1, 2, \dotsc, t; and the candle Chef starts out with isnâ€™t extinguished either.
This gives us x\cdot t + 1 candles at time t.

# TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

# SOLUTIONS:

Setter's Solution (C++)
    #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, minv = 1, maxv = 1e9;
int main()
{
int t; cin >> t;
while(t--){
ll time, y, x; cin >> time >> y >> x;
ll ans = 0, cnt = 0;
if(time - y + 1 <= 0){
cnt = cnt + 1;
ans = 1 + time * x;
}else{
ans = x + (y - 1) * x;
}
cout << ans << endl;
}
}

Tester's Solution (C++)
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)

int main(){
fastio;

int tests;
cin>>tests;

while(tests--){
long long int t, y, x;
cin>>t>>y>>x;

if(t >= y){
cout<<x*y<<endl;
}
else{
cout<<1+x*t<<endl;
}
}

return 0;
}

Editorialist's Solution (Python)
import sys

t = int(input())
for _ in range(t):
t, y, x = map(int, input().split())
if t >= y:
print(x*y)
else:
print(x*t+1)

3 Likes

Damn, I used for loop and got tle NIce explanation. I should have given more time for this.

can anyone please tell me what is wrong with this code? Showing WA while submitting.

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0) {
long a,y,x ;
a = sc.nextLong();
y = sc.nextLong();
x = sc.nextLong();
if(a>=y)
System.out.println(y*x);
else
System.out.println(1 + (a*x));
}
}
}

Why did we take long long int for t, x and y. If constraints for them are 1â‰¤A,Y,Xâ‰¤10^9, then shouldnâ€™t taking int for it be sufficient enough?

Use long instead of int, for large a, y, x integer overflow is occuring

you can check my code i have used long type for a,y,x

I submitted that code without any changes and got AC: here.

1 Like

t,x,y will fit in int. However the output is either xy or tx+1, and those wonâ€™t necessarily fit in int.

There may be some bugs because smae code submitted by one person gives WA and by other person gives AC.

I can see that happening with TLE if the server has a load issue, or if the tests were changed between submissions.
Do you have an example of this happening (where the tests werenâ€™t changed between submissions)? Even though the code posted here uses long, all of roshan803â€™s actual submissions use int, and thatâ€™s obviously wrong.

You can see that the problem LUNCHTIM gives TLE in 2nd subtask if I submit the code in Python and TLE in 1st Subtask if I subit same code in PyPy3
Python Code: CodeChef: Practical coding for everyone
PyPy3: CodeChef: Practical coding for everyone

Can you explain me why this things happen in Codechef?

Honestly, I have no idea what is happening here.
Python TLE-ing on the second subtask is not too surprising, even though the tests were weak.
The pypy submission however is quite weird - if I modify it slightly to count the sum of n over all tests, it passes magically; and I donâ€™t really know enough about pypy to tell whatâ€™s happening, unfortunately.

after completion of competition i tried my code using both int and long after wathcing editorial . but it was either showing WA or server error. so i didnâ€™t know where was my actual error. so today i posted it here before submitting it again. i should have submitted it again before asking it here.
Thanks for testing my code.
i have 1 more question. I knew the 3 values can be 10^9. But i thought as i donâ€™t need to store the result i can directly print the result without long datatype. it will just print the string. i thought if i store the the value in a variable then only i need a long variable otherwise not required. so even i use int datatype for variables should i use type conversion to (long) in print statement?

No we canâ€™t manually typecast an int to long manually because long is bigger in size. you cannot type cast like this . You can learn about this topic internet.