1061 - Consanguine Calculations

[TurtleShip]

Hi, I keep getting a WA for this problem.

My approach is essentially a brute force.
Given either ( a parent and a child ) or ( two parents ), I try all possible combinations and check if it is valid.
Below is my code. I named my variables/method names and added comments so that it is easy to see what I am trying to do.

Code: Select all

Removed after AC

Even though the problem mentions that the order of blood type within a curly brace does not matter, I have a feeling that the judge might actually be checking some kind of ordering of blood type.

Here is input I built, and my output.

Input and output updated after getting AC

Code: Select all

A+ A+ ?
A+ B+ ?
A+ AB+ ?
A+ O+ ?

B+ A+ ?
B+ B+ ?
B+ AB+ ?
B+ O+ ?

AB+ A+ ?
AB+ B+ ?
AB+ AB+ ?
AB+ O+ ?

O+ A+ ?
O+ B+ ?
O+ AB+ ?
O+ O+ ?

A- A+ ?
A- B+ ?
A- AB+ ?
A- O+ ?

B- A+ ?
B- B+ ?
B- AB+ ?
B- O+ ?

AB- A+ ?
AB- B+ ?
AB- AB+ ?
AB- O+ ?

O- A+ ?
O- B+ ?
O- AB+ ?
O- O+ ?

A- A- ?
A- B- ?
A- AB- ?
A- O- ?

B- A- ?
B- B- ?
B- AB- ?
B- O- ?

AB- A- ?
AB- B- ?
AB- AB- ?
AB- O- ?

O- A- ?
O- B- ?
O- AB- ?
O- O- ?

A+ ? A+ 
B+ ? A+ 
AB+ ? A+
O+ ? A+

A+ ? B+
B+ ? B+
AB+ ? B+
O+ ? B+

A+ ? AB+
B+ ? AB+
AB+ ? AB+
O+ ? AB+

A+ ? O+
B+ ? O+
AB+ ? O+
O+ ? O+

A- ? A+ 
B- ? A+ 
AB- ? A+
O- ? A+

A- ? B+
B- ? B+
AB- ? B+
O- ? B+

A- ? AB+
B- ? AB+
AB- ? AB+
O- ? AB+

A- ? O+
B- ? O+
AB- ? O+
O- ? O+

A+ ? A- 
B+ ? A- 
AB+ ? A-
O+ ? A-

A+ ? B-
B+ ? B-
AB+ ? B-
O+ ? B-

A+ ? AB-
B+ ? AB-
AB+ ? AB-
O+ ? AB-

A+ ? O-
B+ ? O-
AB+ ? O-
O+ ? O-

A- ? A-
B- ? A-
AB- ? A-
O- ? A-

A- ? B-
B- ? B-
AB- ? B-
O- ? B-

A- ? AB-
B- ? AB-
AB- ? AB-
O- ? AB-

A- ? O-
B- ? O-
AB- ? O-
O- ? O-

E N D

Code: Select all

Case 1: A+ A+ {A+, A-, O+, O-}
Case 2: A+ B+ {A+, A-, AB+, AB-, B+, B-, O+, O-}
Case 3: A+ AB+ {A+, A-, AB+, AB-, B+, B-}
Case 4: A+ O+ {A+, A-, O+, O-}
Case 5: B+ A+ {A+, A-, AB+, AB-, B+, B-, O+, O-}
Case 6: B+ B+ {B+, B-, O+, O-}
Case 7: B+ AB+ {A+, A-, AB+, AB-, B+, B-}
Case 8: B+ O+ {B+, B-, O+, O-}
Case 9: AB+ A+ {A+, A-, AB+, AB-, B+, B-}
Case 10: AB+ B+ {A+, A-, AB+, AB-, B+, B-}
Case 11: AB+ AB+ {A+, A-, AB+, AB-, B+, B-}
Case 12: AB+ O+ {A+, A-, B+, B-}
Case 13: O+ A+ {A+, A-, O+, O-}
Case 14: O+ B+ {B+, B-, O+, O-}
Case 15: O+ AB+ {A+, A-, B+, B-}
Case 16: O+ O+ {O+, O-}
Case 17: A- A+ {A+, A-, O+, O-}
Case 18: A- B+ {A+, A-, AB+, AB-, B+, B-, O+, O-}
Case 19: A- AB+ {A+, A-, AB+, AB-, B+, B-}
Case 20: A- O+ {A+, A-, O+, O-}
Case 21: B- A+ {A+, A-, AB+, AB-, B+, B-, O+, O-}
Case 22: B- B+ {B+, B-, O+, O-}
Case 23: B- AB+ {A+, A-, AB+, AB-, B+, B-}
Case 24: B- O+ {B+, B-, O+, O-}
Case 25: AB- A+ {A+, A-, AB+, AB-, B+, B-}
Case 26: AB- B+ {A+, A-, AB+, AB-, B+, B-}
Case 27: AB- AB+ {A+, A-, AB+, AB-, B+, B-}
Case 28: AB- O+ {A+, A-, B+, B-}
Case 29: O- A+ {A+, A-, O+, O-}
Case 30: O- B+ {B+, B-, O+, O-}
Case 31: O- AB+ {A+, A-, B+, B-}
Case 32: O- O+ {O+, O-}
Case 33: A- A- {A-, O-}
Case 34: A- B- {A-, AB-, B-, O-}
Case 35: A- AB- {A-, AB-, B-}
Case 36: A- O- {A-, O-}
Case 37: B- A- {A-, AB-, B-, O-}
Case 38: B- B- {B-, O-}
Case 39: B- AB- {A-, AB-, B-}
Case 40: B- O- {B-, O-}
Case 41: AB- A- {A-, AB-, B-}
Case 42: AB- B- {A-, AB-, B-}
Case 43: AB- AB- {A-, AB-, B-}
Case 44: AB- O- {A-, B-}
Case 45: O- A- {A-, O-}
Case 46: O- B- {B-, O-}
Case 47: O- AB- {A-, B-}
Case 48: O- O- O-
Case 49: A+ {A+, A-, AB+, AB-, B+, B-, O+, O-} A+
Case 50: B+ {A+, A-, AB+, AB-} A+
Case 51: AB+ {A+, A-, AB+, AB-, B+, B-, O+, O-} A+
Case 52: O+ {A+, A-, AB+, AB-} A+
Case 53: A+ {AB+, AB-, B+, B-} B+
Case 54: B+ {A+, A-, AB+, AB-, B+, B-, O+, O-} B+
Case 55: AB+ {A+, A-, AB+, AB-, B+, B-, O+, O-} B+
Case 56: O+ {AB+, AB-, B+, B-} B+
Case 57: A+ {AB+, AB-, B+, B-} AB+
Case 58: B+ {A+, A-, AB+, AB-} AB+
Case 59: AB+ {A+, A-, AB+, AB-, B+, B-} AB+
Case 60: O+ IMPOSSIBLE AB+
Case 61: A+ {A+, A-, B+, B-, O+, O-} O+
Case 62: B+ {A+, A-, B+, B-, O+, O-} O+
Case 63: AB+ IMPOSSIBLE O+
Case 64: O+ {A+, A-, B+, B-, O+, O-} O+
Case 65: A- {A+, AB+, B+, O+} A+
Case 66: B- {A+, AB+} A+
Case 67: AB- {A+, AB+, B+, O+} A+
Case 68: O- {A+, AB+} A+
Case 69: A- {AB+, B+} B+
Case 70: B- {A+, AB+, B+, O+} B+
Case 71: AB- {A+, AB+, B+, O+} B+
Case 72: O- {AB+, B+} B+
Case 73: A- {AB+, B+} AB+
Case 74: B- {A+, AB+} AB+
Case 75: AB- {A+, AB+, B+} AB+
Case 76: O- IMPOSSIBLE AB+
Case 77: A- {A+, B+, O+} O+
Case 78: B- {A+, B+, O+} O+
Case 79: AB- IMPOSSIBLE O+
Case 80: O- {A+, B+, O+} O+
Case 81: A+ {A+, A-, AB+, AB-, B+, B-, O+, O-} A-
Case 82: B+ {A+, A-, AB+, AB-} A-
Case 83: AB+ {A+, A-, AB+, AB-, B+, B-, O+, O-} A-
Case 84: O+ {A+, A-, AB+, AB-} A-
Case 85: A+ {AB+, AB-, B+, B-} B-
Case 86: B+ {A+, A-, AB+, AB-, B+, B-, O+, O-} B-
Case 87: AB+ {A+, A-, AB+, AB-, B+, B-, O+, O-} B-
Case 88: O+ {AB+, AB-, B+, B-} B-
Case 89: A+ {AB+, AB-, B+, B-} AB-
Case 90: B+ {A+, A-, AB+, AB-} AB-
Case 91: AB+ {A+, A-, AB+, AB-, B+, B-} AB-
Case 92: O+ IMPOSSIBLE AB-
Case 93: A+ {A+, A-, B+, B-, O+, O-} O-
Case 94: B+ {A+, A-, B+, B-, O+, O-} O-
Case 95: AB+ IMPOSSIBLE O-
Case 96: O+ {A+, A-, B+, B-, O+, O-} O-
Case 97: A- {A+, A-, AB+, AB-, B+, B-, O+, O-} A-
Case 98: B- {A+, A-, AB+, AB-} A-
Case 99: AB- {A+, A-, AB+, AB-, B+, B-, O+, O-} A-
Case 100: O- {A+, A-, AB+, AB-} A-
Case 101: A- {AB+, AB-, B+, B-} B-
Case 102: B- {A+, A-, AB+, AB-, B+, B-, O+, O-} B-
Case 103: AB- {A+, A-, AB+, AB-, B+, B-, O+, O-} B-
Case 104: O- {AB+, AB-, B+, B-} B-
Case 105: A- {AB+, AB-, B+, B-} AB-
Case 106: B- {A+, A-, AB+, AB-} AB-
Case 107: AB- {A+, A-, AB+, AB-, B+, B-} AB-
Case 108: O- IMPOSSIBLE AB-
Case 109: A- {A+, A-, B+, B-, O+, O-} O-
Case 110: B- {A+, A-, B+, B-, O+, O-} O-
Case 111: AB- IMPOSSIBLE O-
Case 112: O- {A+, A-, B+, B-, O+, O-} O-

I saw that 142 people out of 170 people who tried solved this question. Can anybody who solved it please upload your output to my input? It would be great if anyone can point out a flaw in my code. Thanks so much in advance!

[lbv]

Hi, I keep getting a WA for this problem.
(..)
Even though the problem mentions that the order of blood type within a curly brace does not matter, I have a feeling that the judge might actually be checking some kind of ordering of blood type.

I understand the frustration, but it's extremely rare that something that is explicitly stated in a problem statement is wrong. This seems to be a "special judge" problem, and the ordering apparently doesn't matter, as expected.

I just wanted to mention it because, as I've witnessed first hand in teammates during competitions, it may help reduce your stress levels if you stopped assuming that the problem statements tell lies .

Here is input I built, and my output. (..)

Here's the output from my program for a few test cases where I noticed relevant differences:

Input

Code: Select all

A+ ? B+
A+ ? B-
O+ ? B+
AB- ? AB+
AB- ? AB-
E N D

Output

Code: Select all

Case 1: A+ {B-, AB-, B+, AB+} B+
Case 2: A+ {B-, AB-, B+, AB+} B-
Case 3: O+ {B-, AB-, B+, AB+} B+
Case 4: AB- {A+, B+, AB+} AB+
Case 5: AB- {A-, B-, AB-, A+, B+, AB+} AB-

Hope it helps.

[TurtleShip]

Thank you so much lbv!

I made a careless mistake where blood "B" can come from either "AB" or "O". The correct logic should be "B" can come from either "AB" or "B"

Your input/output helped a lot!

Thanks!!

[dibery]

If you get stuck in this problem. Remember {} is not needed when there's only one possibility.
I just stuck at this point for a long time.

Input

O- O- ?
E N D

Output

Case 1: O- O- O-

[Zyaad Jaunnoo]

If you get stuck in this problem. Remember {} is not needed when there's only one possibility.
I just stuck at this point for a long time.

Input

O- O- ?
E N D

Output

Case 1: O- O- O-

Thanks!

[seeva92]

Hi, Can you please explain the 1061 problem with two simple inputs? I am unable to relate the description with the input. Please help me on this case.. Shiva

[ebb]

Hi,

I'm getting WA and I am running out of ideas. I have tested my code with the inputs provided in this thread and in uDebug and the result is the same. The only difference is the order of the blood types inside the curly braces, but the problem statement says the order doesn't matter.

I have generated all possible inputs and checked manually the output and I would say it works fine.

And lastly I have compared my code with other solutions online and they seem to follow a similar line of thought.

Could someone take a look at my code and see if there's anything wrong? Thank you very much in advance!

Code: Select all

Removed after getting Accepted. Read my posts below to see the explanation

[feodorv]

Code: Select all

!line.equals("E N D")

Maybe the data file ends with

Code: Select all

E   N     D   

or something like that. You could check only first letter 'E'.

PS I have added new input on uDebug which covers all possible cases.

[ebb]

Thank you very much for your help feodorv.

I have changed the end condition to

Code: Select all

line.indexOf('E') == -1

but I still get WA.

I have checked my code with your input in uDebug and it works correctly. The only difference is the order, but the problem statement says it's irrelevant. Should we trust it though? I mean, so far the problem statements I have solved seem to be accurate, but I haven't solved that many problems so I cannot really say they all are accurate... Now I will try to code something that replicates the order in other solutions, just in case.

By the way, here's a quick program I wrote to check if 2 solutions are indeed the same ignoring the order:

Code: Select all

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;


public class Test {
    public static void main(String[] args) throws IOException {
        BufferedReader in1 = new BufferedReader(new FileReader("good.txt"));
        BufferedReader in2 = new BufferedReader(new FileReader("bad.txt"));
        String line1 = in1.readLine();
        String line2 = in2.readLine();
        int i = 1;
        while (line1 != null) {
            if (line1.contains("IMPOSSIBLE") && line2.contains("IMPOSSIBLE")) {
                System.out.println("Case " + i + " OK");
            } else if (line1.contains("IMPOSSIBLE") || line2.contains("IMPOSSIBLE")){
                System.out.println("Case " + i + " BAD");
            } else {
                int open1 = line1.indexOf('{');
                int open2 = line2.indexOf('{');
                int close1 = line1.indexOf('}');
                int close2 = line1.indexOf('}');
                if (open1 == -1 && open2 == -1) {
                    System.out.println("Case " + i + " OK");
                } else if (open1 == open2 && close1 == close2) {
                    String[] split1 = line1.substring(open1 + 1, close1).split(", ");
                    String[] split2 = line2.substring(open2 + 1, close2).split(", ");
                    List<String> list1 = Arrays.asList(split1);
                    List<String> list2 = Arrays.asList(split2);
                    Collections.sort(list1);
                    Collections.sort(list2);
                    if (list1.equals(list2)) {
                        System.out.println("Case " + i + " OK");
                    } else {
                        System.out.println("Case " + i + " BAD");
                    }
                } else {
                    System.out.println("Case " + i + " BAD");
                }
            }
            line1 = in1.readLine();
            line2 = in2.readLine();
            i++;
        }
        in1.close();
        in2.close();
    }
}

[ebb]

I've now tried setting the order in the same way as the solutions in uDebug: O-, O+, AB-, AB+, B-, B+, A-, A+.

But it still gets WA

[ebb]

I found the problem in my code. feodorv's comment about whitespace was very close to the issue. The key was in the problem statement:

To improve readability, whitespace may be included anywhere on the line except inside a single blood type specification

It says "anywhere", which means there can be whitespace at the beginning and end of the line. Once I took care of that, my solution was accepted. I've added new input to uDebug that showcases this scenario.

As a generalization, my advice regarding input reading is:
- always trim whitespace at the beginning and end of the input (this problem is a good example of the headaches it can cause)
- always take into account the possibility of unneeded empty lines between valid lines in the input (there are problems where the use of blank lines is inconsistent between the statement, the judge's input and/or uDebug input, e.g. 10306 - e-Coins)
I guess most people don't encounter this kind of issues as often while using C++ or Java's Scanner, but for the rest, make a habit of considering them.

Finally, I encourage anyone who is truly stuck in a problem to let it breath for a time, weeks, months even, and then come back. You'll have accumulated more experience and may notice your error quickly.

Thanks everyone!