C# – Code Forces – Not Afraid

Posted on March 30, 2017 by

CodeForces.Com is probably the only place in the world, where an amateur would be able to compare himself with the best in class professionals. Imagine, if everyone was able to play daily vs Cristiano Ronaldo 🙂

Thus, every now and then I am taking a look at the site and checking the problems they publish. In the 406B competition, the second problem has attracted my attention.

The problem itself is somehow not difficult, but the description is:

Since the giant heads have appeared in the sky all humanity is in danger, so all Ricks and Mortys from all parallel universes are gathering in groups to find a solution to get rid of them.

There are n parallel universes participating in this event (n Ricks and n Mortys). I. e. each of n universes has one Rick and one Morty. They’re gathering in m groups. Each person can be in many groups and a group can contain an arbitrary number of members.

Ricks and Mortys have registered online in these groups. So, a person can have joined a group more than once (developer of this website hadn’t considered this possibility).

Summer from universe #1 knows that in each parallel universe (including hers) exactly one of Rick and Morty from that universe is a traitor and is loyal, but no one knows which one. She knows that we are doomed if there’s a group such that every member in that group is a traitor (they will plan and destroy the world).

Summer knows that if there’s a possibility that world ends (there’s a group where all members are traitors) she should immediately cancel this event. So she wants to know if she should cancel the event. You have to tell her yes if and only if there’s at least one scenario (among all 2ⁿ possible scenarios, 2 possible scenarios for who a traitor in each universe) such that in that scenario the world will end.

Input

The first line of input contains two integers n and m (1 ≤ n, m ≤ 10⁴) — number of universes and number of groups respectively.

The next m lines contain the information about the groups. i-th of them first contains an integer k (number of times someone joined i-th group, k > 0) followed by k integers v_i, 1, v_i, 2, …, v_i, k. If v_i, j is negative, it means that Rick from universe number - v_i, j has joined this group and otherwise it means that Morty from universe number v_i, j has joined it.
Sum of k for all groups does not exceed 10⁴.

Output

In a single line print the answer to Summer’s question. Print “YES” if she should cancel the event and “NO” otherwise.

Pretty much what they want you to do, is to see whether in one line you have a positive and a negative number. E.g., if you have -5 and 5, it means that you have both Rick and Morty there, thus the answer cannot be YES. That simple! If in any of the lines, you do not have a -n and n, you should return a YES, because there is a chance that noone in the group is a traitor. If we have -n and n, for sure we have at least 1 traitor – Rick or Morty.

Here is what I did:

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

class Startup
{
    static void Main()
    {
        List input = Console.ReadLine().Split().Select(int.Parse).ToList();
        int universes = input[0];
        int groups = input[1];
        string result = "";
        string resultEnd = "";

        for (int i = 0; i < groups; i++)
        {
            List inputs = Console.ReadLine().Split().Select(int.Parse).ToList();
            inputs.RemoveAt(0);
            List positive = new List();
            List negative = new List();
            result = "YES";

            foreach (int person in inputs)
            {
                if (person > 0)
                {
                    positive.Add(person);
                    if (negative.Contains(person))
                    {
                        result = "NO";
                    }
                }
                else
                {
                    int negativeValue = person * -1;
                    negative.Add(negativeValue);
                    if (positive.Contains(negativeValue))
                    {
                        result = "NO";
                    }
                }                
            }
            if (result == "YES")
            {
                resultEnd = "YES";
            }
        }

        if (resultEnd != "YES")
        {
            resultEnd = "NO";
        }


        Console.WriteLine(resultEnd);
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

class Startup

{

static void Main()

{

List input = Console.ReadLine().Split().Select(int.Parse).ToList();

int universes = input[0];

int groups = input[1];

string result = "";

string resultEnd = "";

for (int i = 0; i < groups; i++)

{

List inputs = Console.ReadLine().Split().Select(int.Parse).ToList();

inputs.RemoveAt(0);

List positive = new List();

List negative = new List();

result = "YES";

foreach (int person in inputs)

{

if (person > 0)

{

positive.Add(person);

if (negative.Contains(person))

{

result = "NO";

}

else

{

int negativeValue = person * -1;

negative.Add(negativeValue);

if (positive.Contains(negativeValue))

{

result = "NO";

}

if (result == "YES")

{

resultEnd = "YES";

}

if (resultEnd != "YES")

{

resultEnd = "NO";

}

Console.WriteLine(resultEnd);

}

The idea is that we read the groups and then we ignore the first number, telling us how many people are in the group. Then we make two lists – positives and negatives and we add a number in each list. After adding the number, we check whether we have this number in the other list. For the negative numbers, we take their absolute value.

Pretty much that is it – one should probably read the condition 3 times before realizing what is needed. But once you get it, it’s really doable.

Cheers! 🙂