MELTGOLD - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: notsoloud
Tester: abhidot
Editorialist: iceknight1093

DIFFICULTY:

835

PREREQUISITES:

None

PROBLEM:

Chef’s kiln is at Y degrees, and he has an ore that melts at X degrees.
In the i-th second, the kiln’s temperature increases by i degrees.
Find the time needed for the ore’s melting temperature to be reached.

EXPLANATION:

It’s enough to directly simulate the process!

That is, start with the temperature at Y, and in the i-th step, increase it by i.
Stop once you reach \geq X.

This is fast enough because the temperature grows quickly: after i seconds, the temperature is exactly Y + \frac{i\cdot (i+1)}{2}, so it will take about 2\sqrt{X-Y} seconds for us to reach X, which is pretty small.

TIME COMPLEXITY

\mathcal{O}(\sqrt{X-Y}) per test case.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    x, y = map(int, input().split())
    ans = 0
    while y < x:
        y += ans + 1
        ans += 1
    print(ans)
2

i iterated in for loop till N and got right answer shouldn’t that give tle due to constraints?

1 Like
3

I got TLE (performing while loop). So I saw editorial python code (probably same code) still gives TLE I don’t know what is the problem

1 Like
4

Please read the editorial, it’s mentioned that the complexity of your loop is actually \mathcal{O}(\sqrt{X-Y}) and not \mathcal{O}(X). That’s fast enough to get AC.

I see you’ve submitted in Python. Python is almost always much slower than Pypy.
If you submit the editorial code in Pypy, you’ll see that it passes in ~0.55 seconds, which is almost 10 times faster than Python!

If you’re planning to use python for competitive programming, I heavily recommend submitting in pypy. The syntax is the exact same so you don’t need to change anything.

1 Like
5

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

My solution got TLE. My code logic is similar to editorial code logic. I’m not able to understand where did this error happen

6

As I mentioned in my previous comment, if you’re using Python, submit the code in Pypy instead.
The same code will run much faster.