Posted: Wed Mar 30, 2011 10:51 pm Post subject: Re: CCC 2011 Solutions/Analyses

VK_eipi @ Wed Mar 30, 2011 12:28 am wrote:

Dratino, which 8 cases did you use to get your "best of 8" solution for S4? The most obvious answer, that you kept the order of {A+,B+,AB-} patients constant while cycling through possible orders for {A-,B-,O+} donors or vice versa, will probably fail one of the following 6 test cases (all should return 4):

Actually, it was 2*2*2: For each of A-, B-, and O+, I cycled through whether to donate to type 1 or type 2 that can be donated to by that type. So, A- would choose whether to donate to A+ or AB- first.

Besides that, order is unimportant due to symmetry.

Unfortunately, due to recently installing Linux on my system and only backing up certain files, I don't have my program files anymore... I'd have to get them from my teacher.

Quote:

From what I've tested, I think that Case 1 will always work if, right before this section, O+ blood >= A+ patients and Case 2 will always work if this section begins with A+ patients >= O+ blood. So at least one of these two should always work.

Did you run it through the 3 test cases that I posted above?

You have to remember that the rhesus factor (the positive-negative thing) is just another antigen - it's misleading the way it's written, as if there's something special about it, when really there isn't. Try expressing it in terms of positive being a hypothetical C antigen (technically, the letter is actually D, but we won't care about that for now). That's how I discovered that everything is symmetrical.

Then, you're doing types AC and C.

Sponsor Sponsor

VK_eipi

Posted: Thu Mar 31, 2011 4:07 am Post subject: Re: CCC 2011 Solutions/Analyses

Dratino @ Wed Mar 30, 2011 8:51 pm wrote:

Actually, it was 2*2*2: For each of A-, B-, and O+, I cycled through whether to donate to type 1 or type 2 that can be donated to by that type. So, A- would choose whether to donate to A+ or AB- first.

Besides that, order is unimportant due to symmetry.

The outer order is in fact important, as shown by my test cases.

If your donor order is A-, B-, O+, consider the following:
Blood: 2 A-, 1 B-, 1 O+; Patients: 2 A+, 2 AB-
(Correct answer: 4, with A- giving 1 each to A+ and AB-, B- giving 1 to AB-, O+ giving 1 to A+)
First, A- will choose whether to donate to A+ or AB-.
If A- donates (greedily) to A+, then we are left with 1B- and 1O+ for 2AB-. Since O+ cannot give to AB-, we will not get all 4.
If A- donates to AB-, then we are left with 1B- and 1O+ for 2A+, and again, it will return 3 not 4.
So whatever A- chooses, it will not get the correct answer.
In general, if you start with X, I can find a way to make both starting with X->XY and starting with X->XZ a mistake.

Dratino wrote:

Did you run it through the 3 test cases that I posted above?

You have to remember that the rhesus factor (the positive-negative thing) is just another antigen - it's misleading the way it's written, as if there's something special about it, when really there isn't. Try expressing it in terms of positive being a hypothetical C antigen (technically, the letter is actually D, but we won't care about that for now). That's how I discovered that everything is symmetrical.

Then, you're doing types AC and C.

I put it through your 3 test cases. My algorithm works (i.e. at least one of my 2 cases returns 9 for each test)

I do understand that the + can be treated as another antigen; it's thanks to one of your early posts that I realized that , and I built my test cases and solutions upon that notion. (I prefer using the "+" instead of C or D, and I also like to visualize the "single" to "double" cases with a circle of 6 in the order A, A+, +, B+, B, AB, A, ...)

I do realize that because of the symmetry, the AC and C (A+ and +) thing is pretty arbitrary. There were 6 functionally equivalent pairs of orders I could have chosen from (actually more, since I made some purely aesthetic adjustments) and this was just the first one I had.

My best of 2 solution is based on the idea that X to XY can only be a mistake if it precedes both Y to XY and X to XZ.
Therefore, the first "single" to "double" move (eg A to AB) in a fixed order is always a potentially exploitable mistake.
My zigzag pattern ensures that this is the only possible mistake. For example:
A to AB
A to A+
+ to A+
+ to B+
B to B+
B to AB

Fixed orders have (a) fixed mistake(s), which is exploitable by test cases such as yours. Your method only switches between two "adjacent" (sharing a node) mistakes, which my test cases exploit. My best of 2 solution has mistakes "two apart", for which I am not yet able to find an exploit. The +/A+ inequality thing was my attempt at a proof, but how I got there is full of diagrams and intuitive leaps, so I'm not quite sure about it.

--------------------------------

crossley7 wrote:

I saw S4 and immediately thought greedy actually as the ones with fewer possible ones that you can take from are the ones you want to take first. ie o- would be very first check and ab+ is last. During the contest I completely blanked and forgot to code that - blood can go to + patients and so I only got 3/15 on that question. I haven't gone back to add that coding in, but i think my algorithm still works if you just add that in to the end.

Unfortunately, the -/+ thing makes a significant enough difference that any fixed greedy algorithm is unable to handle all possible cases. It helps to visualize the threefold symmetry in the manner Dratino has described: by treating the "+" like a "C" (equal status to A and B).

One example that will not work with your posted algorithm is the following:
Blood = 1 A-, 1 O+; Patients = 1 A+, 1 B+ (Answer is 2)

Dratino

Posted: Sat Apr 02, 2011 10:40 am Post subject: Re: CCC 2011 Solutions/Analyses

VK_eipi @ Thu Mar 31, 2011 4:07 am wrote:

I do realize that because of the symmetry, the AC and C (A+ and +) thing is pretty arbitrary. There were 6 functionally equivalent pairs of orders I could have chosen from (actually more, since I made some purely aesthetic adjustments) and this was just the first one I had.

My best of 2 solution is based on the idea that X to XY can only be a mistake if it precedes both Y to XY and X to XZ.
Therefore, the first "single" to "double" move (eg A to AB) in a fixed order is always a potentially exploitable mistake.
My zigzag pattern ensures that this is the only possible mistake. For example:
A to AB
A to A+
+ to A+
+ to B+
B to B+
B to AB

Fixed orders have (a) fixed mistake(s), which is exploitable by test cases such as yours. Your method only switches between two "adjacent" (sharing a node) mistakes, which my test cases exploit. My best of 2 solution has mistakes "two apart", for which I am not yet able to find an exploit. The +/A+ inequality thing was my attempt at a proof, but how I got there is full of diagrams and intuitive leaps, so I'm not quite sure about it.

Whoops. Yeah, I get what you're talking about now. It doesn't actually have to do with AC and C, but rather which order you choose to do them in. That makes it best of 48

Well, I'm not complaining, because I got full marks for the problem anyway (Which reminds me, I still haven't gotten my code back yet. I still need to try it.)

*edit*

Come to think about it, your solution is ingenious - it's actually the exact same reasoning I used for the greediness outside of that ring. The reason that a greedy algorithm works for everything outside this ring (the A-AC-C-BC-B-AB ring) is because there is an absolute order in place - once ABC has donated, the only other type that, say, AB (or any other 2-antigen type) could donate to that isn't a type that has already donated (namely, ABC) is itself, and at this time, either all the units of ABC blood have been donated, or all the patients that have ABC blood have been satiated (meaning that AB could then only donate to itself).

Once all the 2-antigen types have donated, this is also true for the 1-antigen types (A, B, and C), except this time, they have many possible orders in which to prioritize the donations (a total of 720 - 6! for 6 different possible donation chains). Donating to ABC always comes last, as ABC has the most relaxed requirement and therefore the lowest priority.

The caveat with this is that once one chain out of the six is saturated, you're left with an absolute order anyway. Let's say that the A-AC-C-BC-B-AB chain is 2-3-7-5-12-8. Then, resolving A-AC first leaves us with 0-1-7-5-12-8. And what do you know - only C can donate to AC now, which is an absolute order. Then, only BC can receive from C, only B can donate to BC, and all the way around. The final result of this chain is simply 0-0-1-0-4-0, which means that all the patients were satiated, and we still have blood to spare.

In other words, here is how the greedy algorithm would work with this algorithm (correct me if I'm wrong):

Make ABC donate to ABC first.

Make AB, BC, and AC first donate to themselves, then to ABC if possible.

Make A, B, and C donates to themselves.

Follow the A-AB-B-BC-C-CA-A chain whichever way it goes.