TCO 2017, Round 1B, 250-Pointer (WaterAndOxygen)

James S. Plank

Mon Apr 10 22:10:03 EDT 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: April, 2017
Competitors who opened the problem: 435
Competitors who submitted a solution: 401
Number of correct solutions: 262
Accuracy (percentage correct vs those who opened): 60.2%
Average Correct Time: 16 minutes, 15 seconds.

I'm afraid that I find this problem boring. It's algebra, plain and simple.

Now that you know it's algebra, give it a try. If you want more hints or you get stuck, see below.

Let's give some simple variable names to these quantities:

Amount of water that you have: W.
Amount of oxygen that you have: X
Cost of water: Y
Cost of oxygen: Z
Amount of water that you convert to oxygen: A.

The number of days that you can live, given the amount of water that you have left after converting A units to oxygen is:

(W - A) / Y

And the number of days that you can live, given the amount of oxygen that you have left after converting A units to oxygen is:

(X + A/2) / Z

To maximize the number of days that you live, set these equal to each other, and then solve for A. You have to check for impossibility:

If A < 0, then you simply set A equal to 0. This is what happens when you start out being able to live longer on oxygen than on water.
If A > W, then you simply set A equal to W. I doubt this ever happens theoretically, but this is topcoder, so look for boundary conditions that will hurt you.

Once you have A, convert it back to the number of days that you will live, but do it for both water and oxygen, in case the values differ, and take the minimum. Done.

My Solution

This one is straightforward - do the algebra, check the boundary conditions, done. The file is Solution.cpp.

/* Topcoder TCO 2017 Q1B 250-Pointer
 * James S. Plank
 * Mon Apr 10 22:27:22 EDT 2017
 */

#include <string>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class WaterAndOxygen {
  public:
    double maxDays(int remainH20, int remainO2, int costH2O, int costO2);
};

double WaterAndOxygen::maxDays(int remainH20, int remainO2, int costH2O, int costO2)
{
  double Y, W, X, Z, B, A, Days_W, Days_O;

  W = remainH20;
  X = remainO2;
  Y = costH2O;
  Z = costO2;

  /* Do the algebra to calculate A which makes the 
     number of days that you live on water equal 
     the number of days you live on oxygen. */

  B = W / Y - X / Z;
  A = B * ( 2.0 * Z * Y ) / ( Y + 2.0 * Z );
  
  /* Make A legal. */

  if (A > W) A = W;
  if (A < 0) A = 0;

  /* Now, from A, calculate the number of days you live on water,
     and the number of days you live on oxygen, and return the minimum. */

  Days_W = (W - A) / Y;
  Days_O = (X + A/2.0) / Z;
  return (Days_O < Days_W) ? Days_O : Days_W;
}