CREAHUN - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You have N weapons. The i-th needs S_i seconds to charge and does D_i damage.
1 \leq S_i \leq 2.

Find the minimum time needed to do at least H damage using these weapons, if only one weapon can be used at a time.

EXPLANATION:

Each weapon has a charge time of either one second or two second.
Since our aim is to do at least H damage (and not exactly H), it’s always a good idea to use higher-damaging weapons.

Specifically, only two weapons really matter: the weapon with maximum damage among those with a 1 second charge time, and the weapon with maximum damage among those with a 2 second charge time.

Let X be the maximum damage of a 1-second weapon, and Y be the maximum damage of a 2-second weapon.
We then have three options: use only the first weapon, use only the second weapon, or use both.

Using only the first weapon is easy enough: keep doing X damage till H damage is done.
This takes \left\lceil \frac{H}{X} \right\rceil attacks, and so the same number of seconds.
Similarly, using the second weapon is easy: Y damage is done each attack, so \left\lceil \frac{H}{Y} \right\rceil attacks are needed; and hence 2 \left\lceil \frac{H}{Y} \right\rceil seconds.

What about using both weapons?
There, observe the following:

  • If 2X \geq Y, it’s never optimal to use the second weapon: we could just use the first weapon twice and do more damage in the same time instead.
  • If 2X \lt Y, it’s never optimal to use the first weapon twice: we could use the second weapon once and do more damage in the same time.

So, either we’ll use only the first weapon (which has already been calculated), or we’ll use the first weapon at most once.
Using the first weapon zero times has also been calculated (it’s equivalent to only using the second weapon); so we only need to check for using the first weapon once.
This is easy: the first hit does X damage and needs 1 second; and after that we do Y damage every two seconds, so the total time needed is 1 + 2\left\lceil \frac{H - X}{Y} \right\rceil.

The answer is just the minimum of the three quantities computed.
Be careful when dealing with cases where all weapons are of the same type (so one of X or Y doesn’t exist), and also be careful when computing 2\left\lceil \frac{H - X}{Y} \right\rceil: in particular, when H-X \lt 0 this should resolve to 0 and not a negative number (so technically the real expression is 1 + \max(0, 2\left\lceil \frac{H - X}{Y} \right\rceil)).

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
def ceildiv(h, d):
    if h <= 0: return 0
    return (h + d - 1) // d

for _ in range(int(input())):
    n, h = map(int, input().split())
    one, two, ans = 0, 0, 2*h + 1
    
    for i in range(n):
        s, d = map(int, input().split())
        if s == 1: one = max(one, d)
        else: two = max(two, d)
    
    # only s = 1
    if one > 0: ans = min(ans, ceildiv(h, one))
    # only s = 2
    if two > 0: ans = min(ans, 2 * ceildiv(h, two))
    # both: s = 1 gets used at most once
    if one > 0 and two > 0: ans = min(ans, 1 + 2 * ceildiv(h - one, two))
    print(ans)
2

I’ve used the same logic as given in editorial but am getting wrong ans on last test case. heres my code:

int n, h;
        cin >> n >> h;
        vector < long long > s(n), d(n);
        long long max1 = 0, max2 = 0;
        for (int i = 0; i < n; i++) {
            cin >> s[i] >> d[i];
            if (s[i] == 1) {
                max1 = max(max1, d[i]);
            }
            else {
                max2 = max(max2, d[i]);
            }
        }
        if (h <= max1) {
            cout << 1 << endl;
        }
        else if (h <= max2) {
            cout << 2 << endl;
        }
        else if (max2 >= 2 * max1) {
            if (max1){
                cout << min((2 * h / max2 + ceil((h % max2) / (double) max1)), 2 * ceil(h / (double) max2)) << endl;
            }
            else{
                cout << 2 * ceil(h / (double) max2) << endl;
            }
            
        }
        else {
            cout << ceil(h / (double) max1) << endl;
        }

Can someone please point out what am i missing?

1 Like
3

i get similar error don’t know where i did wrong