4
\$\begingroup\$

Remains

You've recently stumbled upon the remains of a ruined ancient city. Luckily, you've studied enough ancient architecture to know how the buildings were laid out.

The city had \$n\$ buildings in a row. Unfortunately, all but the first two buildings have deteriorated. All you can see in the city are the heights of the first two buildings. The height of the first building is \$x\$, and the height of the second building is \$y\$.

Your studies show ancient traditions dictate for any three consecutive buildings, the heights of the two smaller buildings sum up to the height of the largest building within that group of three. This property holds for all consecutive triples of buildings in the city. Of course, all building heights were nonnegative, and it is possible to have a building that has height zero.

You would like to compute the sum of heights of all the buildings in the row before they were ruined. You note there can be multiple possible answers, so you would like to compute the minimum possible sum of heights that is consistent with the information given. It can be proven under given constraints that the answer will fit within a 64-bit integer.

Input Format

The first line of the input will contain an integer \$T\$, denoting the number of test cases.

Each test case will be on a single line that contains 3 integers \$x, y, n\$.

Output Format

Print a single line per test case, the minimum sum of heights of all buildings consistent with the given information.

Constraints

For all files
\$1 ≤ T ≤ 10\,000\$
\$0 ≤ x, y\$
\$2 ≤ n\$

File 1 -- 61 pts:
\$x, y, n ≤ 10\$

File 2 -- 26 pts:
\$x, y, n ≤ 100\$

File 3 -- 13 pts:
\$x, y, n ≤ 1\,000\,000\,000\$

Sample Input

3
10 7 5
50 100 50
1000000000 999999999 1000000000

Sample Output

25
1750
444444445222222222

Explanation

In the first sample case, the city had 5 buildings, and the first building has height 10 and the second building has height 7. We know the third building either had height 17 or 3. One possible sequence of building heights that minimizes the sum of heights is {10, 7, 3, 4, 1}. The sum of all heights is 10+7+3+4+1 = 25.

In the second sample case, note that it's possible for some buildings to have height zero.

Environment

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

TLDR;

Heights of first two buildings and the total number of buildings are given. For any three consecutive buildings, the heights of the two smaller buildings sum up to the height of the largest building within that group of three. This property holds for all consecutive triples of buildings in the city.

Buildings of size 0 are allowed.

Compute the minimum sum of heights of all the buildings.

Runtime Per Input = 5 sec

My Code:

#include <iostream>
#include <cmath>
#include <vector>
#include <cstdio>
using namespace std;

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    long long int t;    // t = number of test cases
    cin >> t;
    long long int x, y, n;   
           //x, y = Height of first & second building. n = number of buildings
    long long int sum;  //sum of the height of buildings


    int arr[3];     //Not required as pointed out by Juno

    long long int z;   //Temporary variable to store the height of next building
    for (long long int foo = 0; foo < t; foo++)
    {
        cin >> x >> y >> n;      //Takes the input 

        sum = x + y;    //Adds to sum the height of the first two buildings


        for (long long int i = 2; i < n; i++)
        {
            z = abs(x - y); 
            sum += z;
            x = y;
            y = z;
        }
        cout << sum << endl;
    }
}

Input 1: x, y, n ≤ 10

Input 2: 26 pts: x, y, n ≤ 100

Input 3: 13 pts: x, y, n ≤ 1,000,000,000

My code works for the first two inputs but goes on time limit exceeded on the third input. enter image description here

Can anyone help in thinking a better algorithm for solving this question?

During the last input, the program's execution was not complete.

\$\endgroup\$
  • 2
    \$\begingroup\$ Honestly, I think the challenge is simply poorly worded. The following is deceiving: "You would like to compute the sum of heights of all the buildings" since they really want to know "the minimum sum of heights of all buildings consistent with the given information". I'm fairly sure it can be done with less iteration by ignoring the first line and focussing on what they actually want. \$\endgroup\$ – Mast Mar 14 at 19:31
  • 2
    \$\begingroup\$ I found the seed for an analytical solution to this problem with a bit of messing around. Preliminary results are available around here in our main chatroom. Unless I get to it (and delete this commment) everyone is welcome to use what I found out to write their own answer :) \$\endgroup\$ – Vogel612 Mar 14 at 20:44
  • \$\begingroup\$ @Vogel612 Can you please confirm that the question that I posted is relevant to this site so that I can post more such questions. Also thanks for the link. \$\endgroup\$ – harshit54 Mar 15 at 4:30
3
\$\begingroup\$

There are a few observations we can make about the nature of the problem.

The first and most obvious observation is that the building heights will keep decreasing until the first building hits 0. As soon as that happens, the building heights will follow the form \$h, 0, h, h, 0, \ldots \$, repeating the last non-zero height twice before adding in a zero again.
Note that the same is true for equal building heights (though that much should've been obvious).

The next observation is the following: When the first building is smaller than the second, the output of cumulative_heights(a, b, n) is a + cumulative_heights(b, b - a, n - 1)

Now that we handled "special cases", we should take a look at the properties of the "general case". In the following, \$a > b\$

Now let's examine the behaviour of four simple sequences:

$$ \begin{align} (1) & 20, 5, 15, 10, 5, 5, 0, \ldots \\ (2) & 20, 9, 11, 2, 9, 7, 2, 5, 3, 2, 1, 1, 0, \ldots\\ (3) & 20, 4, 16, 12, 4, 8, 4, 4, 0, \ldots\\ (4) & 20, 6, 14, 8, 6, 2, 4, 2, 2, 0, \ldots \end{align} $$

Note how in all of these sequences the smaller building height keeps repeating.

I've chosen these for certain additional properties they exhibit. It's important to understand how the divisibility of the building heights comes into play here. Using \$(\lfloor \frac{a}{b} \rfloor, a \mod b)\$ to classify these sequences gives us an insight:

The sequences where \$a \mod b = 0\$ very quickly result in a repeating pattern. Because the repeated subtraction returns 0 at some point, these sequences (namely (1) and (3)) "end" the descent of the building heights.

The other two sequences are somewhat more interesting.
When we look at them somewhat differently we get the following picture:

$$ 20, 9, 11, 2, 9\\ 2, 9 \\ 9, 7, 2, 5, 3, 2, 1\\ 2, 1, 1, 0 \\ ... \\ 20, 6, 14, 8, 6, 2\\ 6, 2, 4, 2, 2, 0 $$

Now when you see this I hope you notice that there's multiple subsequences here. I repeated the "start" of each subsequence to make it easier to notice.

The deciding factor about what exactly happens when the first subsequence ends is whether \$\lfloor \frac{a}{b} \rfloor \$ is even or not. If it is, that's equivalent to the first case (sequence (2)). If it isn't we get the somewhat cleaner and easier to reason about result of sequence (4).

Note how upon reaching \$a \mod b\$ the even case "adds another \$b\$", which will always be larger than \$a \mod b\$. The sequence then continues with \$(b, b - (a \mod b))\$.

The odd case however just "starts sooner" and follows a sequence based on \$(b, a \mod b)\$.

The only remaining puzzle piece to turn this into a working analytical (and possibly recursive) solution is to understand how many steps elapse before the "next subsequence" begins and to encapsulate this behaviour into a separate function that takes the two starting heights and the number of buildings as arguments.

I leave the hammering out of that detail to you :)

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. I was thinking that since there is always a 3 integer sequence repeating, I can start out with 6 variables instead. Also I can check for the condition if the first three variable equals to the last three then add their sum (n-current iteration) number of times and exit the loop. I think this should improve the run time drastically. \$\endgroup\$ – harshit54 Mar 16 at 5:29
  • \$\begingroup\$ I would not be able to code for all the special cases because it was just a 30 min contest \$\endgroup\$ – harshit54 Mar 16 at 5:34
4
\$\begingroup\$

This is not going to be the answer you want, but it might help you figure it out on your own. There are (at least) two problems here. The first is in the challenge description, the other one is in your code being a mess.

  1. Honestly, I think the challenge is simply poorly worded. The following is deceiving: "You would like to compute the sum of heights of all the buildings" since they really want to know "the minimum sum of heights of all buildings consistent with the given information". I'm fairly sure it can be done with less iteration by ignoring the first line and focussing on what they actually want.

  2. Your code. There's a lot of things in there that don't have to be in there and the naming could be much better. I'm not a star at it myself, but I've taken a shot at cleaning it up.

A more readable version:

#include <iostream>
#include <cmath>

int main(void)
{
    long long int amount_cases;
    long long int first, second, n;
    long long int sum;
    long long int carry;

    std::cin >> amount_cases;

    for (long long int i = 0; i < amount_cases; i++)
    {
        std::cin >> first >> second >> n;
        sum = first + second;
        for (long long int j = 2; j < n; j++)
        {
            carry = std::abs(first - second);
            sum += carry;
            first = second;
            second = carry;
        }
        std::cout << sum << std::endl;
    }
}

Your timeout problem is in this part:

for (long long int j = 2; j < n; j++)
{
    carry = std::abs(first - second);
    sum += carry;
    first = second;
    second = carry;
}

That's not the most optimum method for this problem and the only part of the program you'll have to improve to make it happen fast enough.

\$\endgroup\$
  • 1
    \$\begingroup\$ Two suggestions: first, you don't need to write int main(void) (remove void). Second, it's quite C-like to declare variables at the beginning of scope. With C++, I'd stick to declaring them as late as possible (and you can make a good bunch of them const here as well). \$\endgroup\$ – Juho Mar 14 at 20:04
  • \$\begingroup\$ @Juho You are absolutely right. Feel free to write an answer based on mine, improving it even further. \$\endgroup\$ – Mast Mar 14 at 20:07
  • 1
    \$\begingroup\$ If you're going to use std::cin >> like that without checking, make it throw exceptions instead: start with cin::exceptions(std::ios_base::fail | std::ios_base::eof); before any reading. \$\endgroup\$ – Toby Speight Mar 14 at 21:50
  • \$\begingroup\$ @TobySpeight Usually, absolutely. Would you still do that for guaranteed to be sanitized input, which is the case here? \$\endgroup\$ – Mast Mar 14 at 22:13
  • 1
    \$\begingroup\$ @Mast, I probably would, given it's only one line at the beginning - it helps us diagnose any misunderstanding of, or change to, the spec. BTW, giving good names to the variables was my first thought, and the largest single improvement to be made! \$\endgroup\$ – Toby Speight Mar 15 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.