0
\$\begingroup\$

When G cell divides, it is divided into two G + 1 cells.

In order for the G cell to divide, energy as much as G is required.

What is the minimum energy required to make the total number of cells x?

Input Example (G for each of 2 cells, total number of cells)

1 3 4

Output Example (minimum energy)

3

Input Description Assuming that there is one cell of the first generation and one cell of the first generation in the beginning, the energy required to make a total of four cells is as follows. 1G 3G -> Generation 1 (Energy 1 required) 2G 2G 3G -> Generation 2 (energy 2 required) 2G 3G 3G 3G (total 4 completed final energy 3)

I've answered the question in C #.

Is there a better way or a way to speed it up?

ex) If Sum is 10 million

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{   
  class Program
  {
     static void Main(string[] args)
     {
        StringBuilder m_strbuilder = new StringBuilder();

         List<int> Cells = new List<int>();
         int MinIndex = 0;
         int Sum = 0;
         int FirstCell = 0;
         int SecondCell = 0;

         bool etc = true;
         ulong Result = 0;

         string Inputdata = null;
         string[] Textdata = null;

         while (etc)
        {
           try
           {
             Cells.Clear();

             Inputdata = Console.ReadLine();

             Textdata = Inputdata.Split(' ');

             if (Textdata[0] != null && Textdata[1] != null && Textdata[2] != null)
             { 
                int.TryParse(Textdata[0], out FirstCell);
                int.TryParse(Textdata[1], out SecondCell);
                int.TryParse(Textdata[2], out Sum);
              }

            else
                continue;

            if ( 0 < FirstCell && FirstCell <= 10000000)
            {
                if (0 < SecondCell && SecondCell <= 10000000)
                {
                    if (2 <= Sum && Sum <= 100000000)
                        etc = false;
                    else
                        continue;
                }
                else
                    continue;
             }                     
            else
                continue;
           }

        catch (ArgumentException e)
        {
            Console.WriteLine("Unable to add {0}", e.ToString());
        }
        catch (NullReferenceException e)
        {
            Console.WriteLine("Unable to add {0}", e.ToString());
        }
        catch (IndexOutOfRangeException e)
        {
            Console.WriteLine("Unable to add {0}", e.ToString());
        }
       }

        Cells.Add(FirstCell);
        Cells.Add(SecondCell);        

        if (Cells[0] > Cells[1])
        {
            int TempNum = Cells[1];
            Cells[1] = Cells[0];
            Cells[0] = TempNum;
        }            

         for (int i = 2; i < Sum; i++)
        {                    
            Result += (ulong)Cells[MinIndex]; 

            Cells[MinIndex] += 1; 

            Cells.Insert(MinIndex + 1, Cells[MinIndex]);

            if (MinIndex + 1 != Cells.Count - 1)
            {
                if (Cells[MinIndex + 2] < Cells[MinIndex])
                    MinIndex = MinIndex + 2;
                else
                    MinIndex = 0;
            }
            else
                MinIndex = 0;
        }

        m_strbuilder.Append(Result);
        Console.WriteLine(m_strbuilder);

      }
    }
 }
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Is this from some (public) programming challenge? In that case it would be helpful to add a link. \$\endgroup\$
    – Martin R
    Aug 23, 2018 at 9:29
  • 1
    \$\begingroup\$ no. It was a private coding test. @MartinR \$\endgroup\$
    – geunjae oh
    Aug 23, 2018 at 9:48
  • \$\begingroup\$ Welcome to Code Review! Your last edit was rolled back because after getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information \$\endgroup\$ Aug 24, 2018 at 19:20

1 Answer 1

4
\$\begingroup\$
namespace ConsoleApplication1
{   
  class Program

These names tell no-one anything useful about what the program does, and there's no comment either. If you find this file on your hard drive in a year's time, will you remember what it's for?


        StringBuilder m_strbuilder = new StringBuilder();

        ...

        m_strbuilder.Append(Result);
        Console.WriteLine(m_strbuilder);

m_strbuilder is a misleading name (m_ is one convention for naming fields, but I've never seen it used for local variables); and the StringBuilder is completely unnecessary. Console.WriteLine(object) can be used as well on one object as another, so this could be simplified to

        ...

        Console.WriteLine(Result);

The indentation is crazy. I suspect that it's due to mixed tabs and spaces being converted to all spaces by the StackExchange software. But consistent code formatting is a good thing in general: reformat your code before you commit / submit for review.


         while (etc)
        {
           try
           {
             Cells.Clear();

             Inputdata = Console.ReadLine();

             Textdata = Inputdata.Split(' ');

             if (Textdata[0] != null && Textdata[1] != null && Textdata[2] != null)
             { 
                int.TryParse(Textdata[0], out FirstCell);
                int.TryParse(Textdata[1], out SecondCell);
                int.TryParse(Textdata[2], out Sum);
              }

            else
                continue;

            if ( 0 < FirstCell && FirstCell <= 10000000)
            {
                if (0 < SecondCell && SecondCell <= 10000000)
                {
                    if (2 <= Sum && Sum <= 100000000)
                        etc = false;
                    else
                        continue;
                }
                else
                    continue;
             }                     
            else
                continue;
           }

        catch (ArgumentException e)
        {
            Console.WriteLine("Unable to add {0}", e.ToString());
        }
        catch (NullReferenceException e)
        {
            Console.WriteLine("Unable to add {0}", e.ToString());
        }
        catch (IndexOutOfRangeException e)
        {
            Console.WriteLine("Unable to add {0}", e.ToString());
        }
       }

Firstly, this is a complicated bunch of code with a narrowly defined purpose. On that basis it should be pulled out into a method. This would also allow a more elegant escape from the infinite loop, using return.

Secondly, even if it isn't in a method, some of those variables have narrow scopes and should be defined in their real scope rather than outside it. E.g. Textdata is not used outside the loop, so should be defined inside it.

Thirdly, the convention in C# is that local variables start with a lowercase letter, not an uppercase one.

Fourthly, the error handling is wrong. I tested this without supplying input (because a previous version of the question hardcoded the input and didn't require it to be supplied), and got an infinite loop outputting Unable to add System.NullReferenceException.

Fifthly, the input specification is essentially missing from the spec posted in the question, but I find the assumption that there will be exactly two starting cells to be unnecessarily restrictive. IMO the code could be simpler without that assumption.


         for (int i = 2; i < Sum; i++)
        {                    
            Result += (ulong)Cells[MinIndex]; 

            Cells[MinIndex] += 1; 

            Cells.Insert(MinIndex + 1, Cells[MinIndex]);

            if (MinIndex + 1 != Cells.Count - 1)
            {
                if (Cells[MinIndex + 2] < Cells[MinIndex])
                    MinIndex = MinIndex + 2;
                else
                    MinIndex = 0;
            }
            else
                MinIndex = 0;
        }

Inserting into the middle of a List usually means that you're using the wrong data structure for the task. The right data structure for this approach would surely be a priority queue of some kind.

However, the approach can be optimised a lot. Consider input 1 1 67108864. Initially you have two 1s. After two generations you will have four 2s. After six generations you will have eight 3s. In general, if you have n of the smallest value G, and you still need n or more generations, you can replace all of them with 2n copies of G+1 at cost 2nG. So if you track generation and multiplicity you can go from executing the outer loop Sum - 2 times to roughly log(Sum) times, again using a priority queue. Work through the maths a bit more and you can make it a constant time calculation with no loops (assuming that you only have two cells in the starting state - if you adapt for an arbitrary number of cells as I suggested above, you need one loop).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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