c# code understanding(or c++ translation)

[iamnone12]

    public class Pair
    {
        public int Count;
        public int Length;
    }

    public class PairsList
    {
        public LinkedList<Pair> Pairs;
        public int TotalCount;
    }

    class Program
    {

        static void Main(string[] args)
        {
            int[] rows = new int[] { 0, 0, 1, 1, 2, 2 };
            int[] cols = new int[] { 2, 2, 0 };
            bool success = Solve(cols, rows);
        }

        static bool Solve(int[] cols, int[] rows)
        {
            PairsList pairs = new PairsList() { Pairs = new LinkedList<Pair>(), TotalCount = 0 };

            FillAllPairs(pairs, cols);

            for (int r = 0; r < rows.Length; r++)
            {
                if (rows[r] > 0)
                {
                    if (pairs.TotalCount < rows[r])
                        return false;

                    if (pairs.Pairs.First != null && pairs.Pairs.First.Value.Length > rows.Length - r)
                        return false;

                    DecrementPairs(pairs, rows[r]);
                }
            }

            return pairs.Pairs.Count == 0 || pairs.Pairs.Count == 1 && pairs.Pairs.First.Value.Length == 0;
        }

        static void DecrementPairs(PairsList pairs, int count)
        {
            LinkedListNode<Pair> pair = pairs.Pairs.First;

            while (count > 0 && pair != null)
            {
                LinkedListNode<Pair> next = pair.Next;

                if (pair.Value.Count == count)
                {
                    pair.Value.Length--;
                    if (pair.Value.Length == 0)
                    {
                        pairs.Pairs.Remove(pair);
                        pairs.TotalCount -= count;
                    }
                    else if (pair.Next != null && pair.Next.Value.Length == pair.Value.Length)
                    {
                        pair.Value.Count += pair.Next.Value.Count;
                        pairs.Pairs.Remove(pair.Next);
                        next = pair;
                    }
                    count = 0;
                }
                else if (pair.Value.Count < count)
                {
                    count -= pair.Value.Count;
                    pair.Value.Length--;
                    if (pair.Value.Length == 0)
                    {
                        pairs.Pairs.Remove(pair);
                        pairs.TotalCount -= pair.Value.Count;
                    }
                    else if(pair.Next != null && pair.Next.Value.Length == pair.Value.Length)
                    {
                        pair.Value.Count += pair.Next.Value.Count;
                        pairs.Pairs.Remove(pair.Next);
                        next = pair;
                    }
                }
                else // pair.Value.Count > count
                {
                    Pair p = new Pair() { Count = count, Length = pair.Value.Length - 1 };
                    pair.Value.Count -= count;
                    if (p.Length > 0)
                    {
                        if (pair.Next != null && pair.Next.Value.Length == p.Length)
                            pair.Next.Value.Count += p.Count;
                        else
                            pairs.Pairs.AddAfter(pair, p);
                    }
                    else
                        pairs.TotalCount -= count;
                    count = 0;
                }

                pair = next;
            }
        }

        static int FillAllPairs(PairsList pairs, int[] cols)
        {
            List<Pair> newPairs = new List<Pair>();

            int c = 0;
            while (c < cols.Length && cols[c] > 0)
            {
                int k = c++;
                if (cols[k] > 0)
                    pairs.TotalCount++;
                while (c < cols.Length && cols[c] == cols[k])
                {
                    if (cols[k] > 0) pairs.TotalCount++;
                    c++;
                }
                newPairs.Add(new Pair() { Count = c - k, Length = cols[k] });
            }

            LinkedListNode<Pair> pair = pairs.Pairs.First;

            foreach (Pair p in newPairs)
            {
                while (pair != null && p.Length < pair.Value.Length)
                    pair = pair.Next;

                if (pair == null)
                {
                    pairs.Pairs.AddLast(p);
                }
                else if (p.Length == pair.Value.Length)
                {
                    pair.Value.Count += p.Count;
                    pair = pair.Next;
                }
                else // p.Length > pair.Value.Length
                {
                    pairs.Pairs.AddBefore(pair, p);
                }
            }
            return c;
        }
    }

can someone explain this c# code i tried to understand it but couldn't please help me understand this code or wtire a similar code in c++

[iamnone12]

1

I will illustrate the algorithm with an example.

Assume we have m rows and n columns. Let rows[i] be the number of 1s in row i, for 0 <= i < m, and cols[j] be the number of 1s in column j, for 0 <= j < n.

For example, for m = 3, and n = 4, we could have: rows = {4 2 3}, cols = {1 3 2 3}, and the solution array would be:

1 3 2 3
+--------
4 | 1 1 1 1
2 | 0 1 0 1
3 | 0 1 1 1
Because we only want to know whether a solution exists, the values in rows and cols may be permuted in any order. The solution of each permutation is just a permutation of the rows and columns of the above solution.

So, given rows and cols, sort cols in decreasing order, and rows in increasing order. For our example, we have cols = {3 3 2 1} and rows = {2 3 4}, and the equivalent problem.

3 3 2 1
+--------
2 | 1 1 0 0
3 | 1 1 1 0
4 | 1 1 1 1
We transform cols into a form that is better suited for the algorithm. What cols tells us is that we have two series of 1s of length 3, one series of 1s of length 2, and one series of 1s of length 1, that are to be distributed among the rows of the array. We rewrite cols to capture just that, that is COLS = {2/3 1/2 1/1}, 2 series of length 3, 1 series of length 2, and 1 series of length 1.

Because we have 2 series of length 3, a solution exists only if we can put two 1s in the first row. This is possible because rows[0] = 2. We do not actually put any 1 in the first row, but record the fact that 1s have been placed there by decrementing the length of the series of length 3. So COLS becomes:

COLS = {2/2 1/2 1/1}
and we combine our two counts for series of length 2, yielding:

COLS = {3/2 1/1}
We now have the reduced problem:

3 | 1 1 1 0
4 | 1 1 1 1
Again we need to place 1s from our series of length 2 to have a solution. Fortunately, rows[1] = 3 and we can do this. We decrement the length of 3/2 and get:

COLS = {3/1 1/1} = {4/1}
We have the reduced problem:

4 | 1 1 1 1
Which is solved by 4 series of length 1, just what we have left. If at any step, the series in COLS cannot be used to satisfy a row count, then no solution is possible.

The general processing for each row may be stated as follows. For each row r, starting from the first element in COLS, decrement the lengths of as many elements count[k]/length[k] of COLS as needed, so that the sum of the count[k]'s equals rows[r]. Eliminate series of length 0 in COLS and combine series of same length.

Note that because elements of COLS are in decreasing order of lengths, the length of the last element decremented is always less than or equal to the next element in COLS (if there is a next element).

EXAMPLE 2 : Solution exists.

rows = {1 3 3}, cols = {2 2 2 1} => COLS = {3/2 1/1}
1 series of length 2 is decremented to satisfy rows[0] = 1, and the 2 other series of length 2 remains at length 2.

rows[0] = 1
COLS = {2/2 1/1 1/1} = {2/2 2/1}
The 2 series of length 2 are decremented, and 1 of the series of length 1. The series whose length has become 0 is deleted, and the series of length 1 are combined.

rows[1] = 3
COLS = {2/1 1/0 1/1} = {2/1 1/1} = {3/1}
A solution exists for rows[2] can be satisfied.

rows[2] = 3
COLS = {3/0} = {}
EXAMPLE 3: Solution does not exists.

rows = {0 2 3}, cols = {3 2 0 0} => COLS = {1/3 1/2}

rows[0] = 0
COLS = {1/3 1/2}

rows[1] = 2
COLS = {1/2 1/1}

rows[2] = 3 => impossible to satisfy; no solution.