DATE1 - Editorial

PROBLEM LINK:

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

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

DIFFICULTY:

Cakewalk

PREREQUISITES:

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:

Subtask 1
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.

Subtask 2
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
input = sys.stdin.readline
 
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 :disappointed_relieved: 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
	{
		// your code goes here
		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.