C# – CodeForces – Game of Rows

Posted on August 22, 2017 by

Vitosh Posted in C Sharp Tricks, CodeForces

CodeForces.com has become something like a hobby – instead of thinking about a topic for an article, I simply solve a problem there and blog about it. Thus, lately I have taken a look at Round 428, Division 2, problem 2, a problem concerning splitting units of people in an airplane. Pretty much, this is how the task looks like:

Daenerys Targaryen has an army consisting of k groups of soldiers, the i-th group contains ai soldiers. She wants to bring her army to the other side of the sea to get the Iron Throne. She has recently bought an airplane to carry her army through the sea. The airplane has nrows, each of them has 8 seats. We call two seats neighbor, if they are in the same row and in seats {1,2}, {3,4}, {4,5}, {5,6} or {7,8}.
Daenerys Targaryen wants to place her army in the plane so that there are no two soldiers from different groups sitting on neighboring seats.
Your task is to determine if there is a possible arranging of her army in the airplane such that the condition above is satisfied.

Input
The first line contains two integers n and k — the number of rows and the number of groups of soldiers, respectively. The second line contains k integers a1,a2,a3,…,ak), where ai denotes the number of soldiers in the i-th group.

Output
If we can place the soldiers in the airplane print “YES” (without quotes). Otherwise print “NO” (without quotes).

At first I was thinking that I have to use some kind of module arithmetics and with a few loops I would be able to fix it. Until I started to think, that actually it would be quite tough, as far as the logic is a bit different – e.g. if you have 1 row and units like 1, 2, 3 there is no place for even a single unit more. E.g., 1,2,3,1 would be too much, as far as they would be sitting to each other. But 4, 4 is quite possible. Thus, the module arithmetics should be forgotten.

Then I have decided to use a matrix and to start filling it with units. I have just passed the first 4 tests and I have noticed that it is not gonna happen…

I have simply noticed that the maximum limit of soldiers is 1 million (100 groups with 100.000 soldiers per group) and I realized that my looping around a matrix and putting the soldiers in a corresponding row would be too slow for the 1 second test limit. But the solution was worth seeing, I had a specific function for each type of soldier splitting – a function for 4 soldiers, function for 3 soldiers, function for 2 soldiers and function for 1 soldier. Of course, with a loop in the functions, so it works until no more soldiers are left. I built that solution with the idea to fix it later, but it seemed unworkable, thus I have decided to forget about the matrices that should be filled out and concentrate on something better.

Thus, without a matrix, I have built up the following solution:

We have two types of seats – 4 together and 2 doubles in a row
The 4 seats together are once per row and the 2 doubles are twice per row
It does not matter whether we have 4 or 3 soldiers in a group. It does not matter at all. They would still be taking the same amount of chairs. This is a bit difficult to realize, but it is like this – build a solution with groups like these – [3,3] [4,3] [4,4] and one row. Can you add even a single soldier from another group to this row? You cannot. Thus 3 and 4 are the same.
If you have two soldiers from a group there are only 2 ways to fit them – in the double left or right or taking 3 seats from the middle 4. And thus, leaving one seat left from the middle 4. With the one seat from the middle 4 you are producing a single seat, where a soldier can sit.
If there is no way to find a sit for a group of 2 soldiers, then split them into two groups of 1 soldier and search again for 2 single seats. You may be lucky.
If you fail to find enough seats for the group of more than 3, then its a failure. If you fail to find enough seats for a single left soldier, its a failure. If it is a failure, print “NO”.

This is the code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Startup
{
    public static void Main()
    {
        List<int> liInput = ReadLineAndParseToList();
        int numberOfRows = liInput[0];
        int numberOfGroups = liInput[1];

        int oneSeat = 0;
        int twoSeats = numberOfRows * 2;
        int fourSeats = numberOfRows;

        List<int> liSoldiers = ReadLineAndParseToList();
        List<int> liLeft = new List<int> { 0, 0, 0 };

        bool blnOk = true;

        liSoldiers.Sort();
        liSoldiers.Reverse();

        for (int i = 0; i < liSoldiers.Count; i++)
        {
            while (liSoldiers[i]>=3 && blnOk)
            {
                if (fourSeats>0)
                {
                    liSoldiers[i] -= 4;
                    fourSeats--;
                }
                else if (twoSeats > 0)
                {
                    liSoldiers[i] -= 2;
                    twoSeats--;
                }
                else
                {
                    blnOk = false;
                }
            }

            if (blnOk && liSoldiers[i] > 0)
            {
                liLeft[liSoldiers[i]]++;
            }
        }

        while(liLeft[2]>0 && blnOk)
        {
            if (twoSeats>0)
            {
                twoSeats--;
            }
            else if(fourSeats>0)
            {
                fourSeats--;
                oneSeat++;
            }
            else
            {
                liLeft[1] += 2;
            }
            liLeft[2]--;
        }

        if (liLeft[1] > (oneSeat + twoSeats + fourSeats * 2))
        {
            blnOk = false;
        }

        Console.WriteLine("{0}",blnOk ? "YES":"NO");
    }

    public static List<int> ReadLineAndParseToList()
    {
        return Console.ReadLine().Split().Select(int.Parse).ToList();
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

class Startup

{

public static void Main()

{

List<int> liInput = ReadLineAndParseToList();

int numberOfRows = liInput[0];

int numberOfGroups = liInput[1];

int oneSeat = 0;

int twoSeats = numberOfRows * 2;

int fourSeats = numberOfRows;

List<int> liSoldiers = ReadLineAndParseToList();

List<int> liLeft = new List<int> { 0, 0, 0 };

bool blnOk = true;

liSoldiers.Sort();

liSoldiers.Reverse();

for (int i = 0; i < liSoldiers.Count; i++)

{

while (liSoldiers[i]>=3 && blnOk)

{

if (fourSeats>0)

{

liSoldiers[i] -= 4;

fourSeats--;

}

else if (twoSeats > 0)

{

liSoldiers[i] -= 2;

twoSeats--;

}

else

{

blnOk = false;

}

if (blnOk && liSoldiers[i] > 0)

{

liLeft[liSoldiers[i]]++;

}

while(liLeft[2]>0 && blnOk)

{

if (twoSeats>0)

{

twoSeats--;

}

else if(fourSeats>0)

{

fourSeats--;

oneSeat++;

}

else

{

liLeft[1] += 2;

}

liLeft[2]--;

}

if (liLeft[1] > (oneSeat + twoSeats + fourSeats * 2))

{

blnOk = false;

}

Console.WriteLine("{0}",blnOk ? "YES":"NO");

}

public static List<int> ReadLineAndParseToList()

{

return Console.ReadLine().Split().Select(int.Parse).ToList();

}

Yup! That was it! Enjoy it! 🙂

Tagged with: C#, codeforces, Game of rows, greed

C# – CodeForces – Game of Rows

Related posts: