Cell division Solving algorithm problems

Question

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); } } } 

Answer 1

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).