1061 - Consanguine Calculations

All about problems in Volume 10. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
TurtleShip
New poster
Posts: 3
Joined: Sun Apr 06, 2014 7:20 pm

1061 - Consanguine Calculations

Post by TurtleShip » Sun Apr 06, 2014 7:27 pm

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 :D

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!
Last edited by TurtleShip on Mon Apr 07, 2014 9:43 am, edited 1 time in total.

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 1061 - Consanguine Calculations

Post by lbv » Mon Apr 07, 2014 7:11 am

TurtleShip wrote: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 :).
TurtleShip wrote: 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
New poster
Posts: 3
Joined: Sun Apr 06, 2014 7:20 pm

Re: 1061 - Consanguine Calculations

Post by TurtleShip » Mon Apr 07, 2014 9:45 am

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
Learning poster
Posts: 75
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

Re: 1061 - Consanguine Calculations

Post by dibery » Wed Aug 06, 2014 10:24 am

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-
Life shouldn't be null.

User avatar
Zyaad Jaunnoo
Experienced poster
Posts: 120
Joined: Tue Apr 16, 2002 10:07 am

Re: 1061 - Consanguine Calculations

Post by Zyaad Jaunnoo » Thu Mar 19, 2015 7:13 pm

dibery wrote: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! :wink:

seeva92
New poster
Posts: 3
Joined: Fri Oct 09, 2015 7:57 am

Re: 1061 - Consanguine Calculations

Post by seeva92 » Tue Oct 20, 2015 8:49 am

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
New poster
Posts: 7
Joined: Sat Nov 19, 2016 8:44 pm

Re: 1061 - Consanguine Calculations

Post by ebb » Sat Nov 19, 2016 9:07 pm

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
Last edited by ebb on Sun Apr 16, 2017 2:02 pm, edited 2 times in total.

feodorv
New poster
Posts: 5
Joined: Mon Jun 06, 2016 12:42 pm

Re: 1061 - Consanguine Calculations

Post by feodorv » Sun Nov 20, 2016 8:32 am

ebb wrote:

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
New poster
Posts: 7
Joined: Sat Nov 19, 2016 8:44 pm

Re: 1061 - Consanguine Calculations

Post by ebb » Sun Nov 20, 2016 9:20 pm

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
New poster
Posts: 7
Joined: Sat Nov 19, 2016 8:44 pm

Re: 1061 - Consanguine Calculations

Post by ebb » Sun Nov 20, 2016 9:31 pm

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
New poster
Posts: 7
Joined: Sat Nov 19, 2016 8:44 pm

Re: 1061 - Consanguine Calculations

Post by ebb » Sun Apr 16, 2017 2:21 pm

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!

Post Reply

Return to “Volume 10 (1000-1099)”

Who is online

Users browsing this forum: No registered users and 1 guest