XCODE02 - Editorial

Problem Link

[Contest][1]

Practice

Author: Sahil Rajput

Tester: Sahil Rajput

Editorialist: Sahil Rajput

Difficulty

EASY-MEDIUM

Prerequisites

Maths, binary search, array

Problem

Given N, C, E representing no. of towers, coins and elixers, and next N lines represent cost, power, and money (coin or elixer), task is to choose a way to build towers with maximum total power.

Explanation

We can tackle this problem with multiple ways.
  1. Lala builds one tesla tower for coins and other for elixirs

  2. Lala built both tesla tower for coins.

  3. Lala build both tesla tower for elixirs.

Our task is to choose a way with maximum total power.

Simple Approach (Gives WA or TLE):
Choose one tesla tower for each type with maximum power on which is enough coins and elixirs which Lala has. So, we can easily iterate through all given tesla towers.

Two Best Approachs:
First approach is that consider the way when Lala built both tesla towers for coins.
Make an array and write out all the tesla towers for a coins. We will store them as pairs (cost and power). After that sort the array in ascending order of the cost.

Let Lala will build tesla tower with cost v1 and v2 coins and v1<=v2 and v1+v2<=c.

We also need an array (let maxB), where maxBi equals to maximum tesla power on the prefix of sorted towers for coins which ends in position i. v1 equals to v2 should be considered separately, so it can be done in one iteration through the tesla towers (from towers with same cost we just need to choose two with maximum power and update the answer with result).
It is only left case when v1 < v2. So brute the towers with the cost equal to v2 and after that Lala will have c - v2 coins. So with the help of binary search we need to find the tower prefix which Lala can build for the remaining coins. from array maxB we can determine the maximum power of the tesla tower which Lala should build.

Similarly, third way is solved when both towers will be build for elixers.

Solution Link

[Setter's solution][6]

Tester’s solution

1 Like