POJ 1182: "Food Chain"

-

POJ 1182: Food Chain

Problem Statement

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。 
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。 
有人用两种说法对这N个动物所构成的食物链关系进行描述： 
第一种说法是"1 X Y"，表示X和Y是同类。 
第二种说法是"2 X Y"，表示X吃Y。 
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。 
1） 当前的话与前面的某些真的话冲突，就是假话； 
2） 当前的话中X或Y比N大，就是假话； 
3） 当前的话表示X吃X，就是假话。 
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。 

Interpretation

There are 3 types of animals - A, B, and C. A eats B, B eats C, and C eats A. A person tells you K statements about N animals. There are 2 types of facts, in this format:
  • 1 X Y - Animal X and Animal Y are the same type
  • 2 X Y - Animal X EATS Animal Y
You are to count how many lies there are. A statement is a lie when it meets at least one of these criteria:
  • X or Y is bigger than N (there is no such animal)
  • X is said to eat itself
  • It contradicts with a previous statement that's not a lie

Specifications

Data Structures and How

This problem utilizes a union-find data structure. However, this union-find data structure has to be altered to consider in another array, keeping track of the relationship between the node and its root. There are only three possible relationships between two nodes, X and Y: same, X eats Y, or Y eats X. For this reason the relationships are identified with the numbers 0, 1, and 2. 
This "relationship factor" has a few special properties. When the relationship between X and Y is R1 and the relationship between Y and Z is R2, then the relationship between X and Z is the sum of R1 and R2 mod 3.
If X and Y is in the same tree and we don't know the relationship of X and Y but we do know their relationship with their root, then the relationship of X and Y is the difference of the relationship of X and the relationship of Y (in respect of the root) mod 3.
These are very useful towards our program.

Why?

The disjoint set is used to store relationships between nodes that are verified to be true.

Things to Watch Out

  • In the Union-Find Set (and any other tree), each node has only one parent, not a set of parents, unlike a directed graph.
  • POJ ignores "ios_base::sync_with_stdio(false)".

Code
#include <cstdio>
#define MAXN 50005
using namespace std;

int N, rela[MAXN];

class DSSet
{
private:
    int rt[MAXN];
public:
    DSSet()
    {
        for(int i=0; i<N; i++) { rt[i] = i; rela[i] = 0; }
    }
    int root(int n)
    {
        if(rt[n] == n) return n;
        int p = rt[n];
        rt[n] = root(p);
        rela[n] = (rela[n] + rela[p]) % 3;
        return rt[n];
    }
    void merge(int m, int n, int com)
    {
        int rm = root(m), rn = root(n);
        rt[rn] = rm;
        rela[rn] = (rela[m] - rela[n] + com + 2) % 3;
    }
};

int main()
{
    int K, ans = 0; scanf("%d %d", &N, &K);
    DSSet S;
    for(int i=0; i<K; i++)
    {
        int com, x, y; scanf("%d %d %d", &com, &x, &y);
        if(x > N || y > N || (x == y && com == 2)) ans++; // definite LIE - prelimanaries
        else if(S.root(x) == S.root(y))
        {
            if(com == 1 && rela[x] != rela[y]) { ans++; continue; } // definite LIE
            if(com == 2 && (rela[x] + 1)%3 != rela[y]) { ans++; continue; } // definite LIE
        }
        else S.merge(x, y, com);
    }
    printf("%d\n", ans);
}

Comments

Post a Comment

Popular posts from this blog

USACO Training "subset": Subset Sums

-
USACO Training "subset": Subset Sums Problem Statement Subset Sums JRM For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical. For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical: {3} and {1,2} This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions). If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum: {1,6,7} and {2,3,4,5} {2,5,7} and {1,3,4,6} {3,4,7} and {1,2,5,6} {1,2,4,7} and {3,5,6} Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways. Your program must calculate the answer, not look it up from a table. PROGRAM NAME: s
Read more

USACO 2018 Open: Talent Show

-
Image
USACO 2018 Open Talent Show In Short Given N objects with value Vi and weight Wi, a collection of elements is said to have total value-to-weight ratio as (the sum of their value) divided by (the sum of their weight). Find the best possible value-to-weight ratio of these X objects, given the restraint that the collection must have total weight at least W. Return that ratio multiplied by 1000 and floored. Analysis It would be very difficult to calculate this optimal ratio - we'd have to either try all possible collections - O(2^n), where n is at most 250, about 10 to the power of 75 calculations, OR use a greedy heuristic - get the objects with the best ratio until it satisfies the weight limit. Neither of those are too to our liking, so how about searching for it? The search space is linear and not infinite - it asks for the ratio to the closest thousandths. The search space is sorted as well - if ratio X is achievable, then ratio Y < X is also achievable, if
Read more

OpenJudge 1768: Kadane's Algorithm on 2D Arrays

-
OpenJudge 1768: Kadane's Algorithm on 2-D Arrays Simple Version Given a 2-D matrix of integers, find the sub-matrix of this whose sum is maximized, and find that sum. The size of the matrix is no larger than 100 by 100. Analysis O(N^4) - Works, but naive     That's true, an naive O(N^4) version would work. We simply need to calculate (two dimensional!) prefix sums first. A quick review to what 2-D prefix sums are:     The 2-D prefix sum of two coordinates, X and Y, is the sum of all elements that have X-coordinate less than or equal to X, and Y coordinate less than or equal to Y.     It can be calculated through tabulation by removing overlapping areas.     Let P be the prefix sum array and V be the array of values, so the formula is as follows:     P[x, y] = V[x, y] - P[x-1, y] - P[x, y-1] + P[x-1, y-1].     We need to add the P[x-1, y-1] at the end since subtracting P[x-1, y] and P[x, y-1] we had overlapped the P[x-1, y-1]. Then, all we need to
Read more