CODEWITHSUNDEEP
c#algorithm
webwurm
webwurm

Reputation: 89

Kattis-problem: Building Pyramids - why is this not correct?

I'm trying to solve this problem here in C#: https://open.kattis.com/submissions/8340306 (edit: Full question below)

So, in short: Give is a number of bricks. The aim is to figure out, how high I can build a 3D-pyramid with these blocks. The top-level has 1 brick, the 2nd level from the top 9 bricks, the 3rd 25 bricks and so on.

I thought I solved it and with the given example it is correct. It is also correct in all the calculations I did. Yet: From the 5 sample-runs, in it only excepted in 3.

Edit - the full question: When initiating a larger project, like building a pyramid, it’s best to think twice. Your task today is to write a program that computes how high a pyramid can be built given a certain number of blocks of stone.

We assume that the pyramid to be built is compact, i.e. there are no cavities inside. Furthermore, we assume it is built according to the principle in Figure 1. Each layer is square, with a side length that is two less than the one below it. The top layer always consist of a single block.enter image description here

It is fine if you have leftover blocks, as long as you build a complete pyramid.

Input The first and only line of input contains an integer N (1≤N≤100000000), the number of blocks you have available.

Output Output a single integer – the maximum height of a pyramid that can be built with at least N blocks. enter image description here

The result of my solution: enter image description here

Here is my code - please be gentle, I am just learning :)

    public static void Main()
    {
        int bloecke = int.Parse(Console.ReadLine());
        int neueBloecke = 1; // Bloecke, die für die neue Ebene benötigt werden
        int sumBloecke = 1; // Blöcke in Summe
        int seitenLaenge = 1; // Seitenlänge der Ebene
        int ebene = 1; // Auf welcher Ebene wir uns aktuell befinden

        while (sumBloecke < bloecke)
        { 
            // Wenn wir weniger als 10 Blöcke haben, brauchen wir gar nicht anzufangen > wir haben 1 Ebene
            if (bloecke < 10)
            {
                ebene = 1;
                break;
            }

            // Andernfalls legen wir los
            seitenLaenge += 2;
            neueBloecke = seitenLaenge * seitenLaenge;
            sumBloecke += neueBloecke;

            if (sumBloecke>=bloecke)
            {
                break;
            } else
            {
                ebene++;
            }

        }

        Console.Write(ebene);

    }

Upvotes: 1

Views: 777

Answers (3)

mendax1234
mendax1234

Reputation: 13

For your not-working solution, one of the case I found that doesn't make sense is when your input is 10. In this case, if you step through your program, you will find your output is 1, but the correct output should be 2. This is also why you don't pass the secret test case for group 1, which is meant for testing when there is no remaining block left.

Upvotes: 0

webwurm
webwurm

Reputation: 89

This works for me:

public static void Main()
{
    int availableBlocks = int.Parse(Console.ReadLine());
    int newBlocks = 0; // blocks for the new level
    int sumBlocks = 0; // sum of used blocks
    int edgeLength = 0; // blocks on one side of the level
    int level = 0; // which level are we

    while (true)
    {
        // e.g. availableBlocks = 15
        //
        // edge | new | sum | ok? | level
        // 0      0     0     yes   0
        // 1      1     1     yes   1
        // 3      9     10    yes   2
        // 4      16    26    no    -

        // edgeLength increases by 2, except for the first top-level
        if (edgeLength==0)
        {
            edgeLength++;
        } else
        {
            edgeLength += 2;
        }

        newBlocks = edgeLength * edgeLength;
        sumBlocks += newBlocks;

        // Check, if we still have enought blocks
        if (sumBlocks <= availableBlocks)
        {
            level++;
        } else
        {
            Console.WriteLine(level);
            break;
        }
    }
}```

Upvotes: 1

Matt Timmermans
Matt Timmermans

Reputation: 59144

It looks like you've been just messing with this trying to get it to work. You've complicated it with code that has no real purpose, and now it's confusing.

Your loop has 2 exit conditions when only one is necessary, you have ebene = 1 in there for no reason, etc.

You are taking the wrong approach. If you just mess with your code until it works for whatever tests you're applying, then you'll never really be confident that it works for stuff you didn't test.

You need to prove to yourself that it is correct. Try something like this:

  • Ensure that, at the top of the loop, the total block count, base area, and edge length are valid for a pyramid size ebene+1. (This is called a loop invariant)
  • Exit the loop at the top if the total number of blocks required by that pyramid is more than you have
  • Otherwise, increment ebene and calculate the variables for the next size, and loop.

If you implement this simple procedure, then you will be confident that the result is correct.

Upvotes: 1

Related Questions