Crap, I should've read the problem explanation more carefully. Wasted a lot of time cause of that dumb mistake -_-
Lesson learned: Read the problem statements more carefully before coding.
Computer Science Canada CCC 2011 Solutions/Analyses |
| Author: | A.J [ Thu Mar 03, 2011 6:33 pm ] | ||
| Post subject: | CCC 2011 Solutions/Analyses | ||
Here are the solutions/analyses to the CCC problems. I'll only be posting the solutions for the Senior pack, though if there are enough people interested, I could also take up the Junior pack. S1- This problem was fairly straightforward. Given text, you have to count the number of 's' and 'S' and compare this to the number of 't' and 'T' in the text. If there are more 's' or 'S' than (or equal) 't' or 'T', then output 'French'. Otherwise, output 'English'. S2- Another straightforward problem. You are given a student's responses to a multiple choice exam, and you are then given the answer key. You should then output the number of correct answers the student got. A simple counter and an array keeping track of the number of right submissions suffices. S3- This question picks up the difficulty a bit. Partly because there's quite a bit of reading to get through. The basic idea is that you are given a pattern that is observable under 13 different levels of magnifications. Then, given the x and y coordinates of a point, your job is to determine whether the given point contains a 'crystal' or not under a certain magnification m. This question was a pretty good exercise in recursion and a bit of math. The general idea is to create a function 'look(m, x, y)' that determines whether or not the point described by (x, y) under the magnification m contains a crystal or not. First of all, like all recursive functions, you require a base case; here, m = 1 will do just fine (and seeing as only 4 points contain crystal, this takes a short amount of code as well). Next, the recursive step. But before that, there are a few 'ballparking' measures that can be taken; by this I mean that if x is in the leftmost fifth or the rightmost fifth of the board, then clearly the poiint (x, y) won't contain a crystal (Note: the dimensions of the board under magnification level m is 5^m * 5^m, and thus the first and last fifths will be in the intervals [0, 5^(m-1)-1], and [4*5^(m-1)-1, 5^(m)-1]. Be vary of the fact that the board is 0 indexed, i.e. the bottom leftmost has coordinates (0, 0), not (1, 1)). You can continue looking at a few more cases that you already know the result of. For example, if point is in any of the 4 'main' squares (i.e. if either (x is in 2nd fifth, and y is in the 1st fifth or x is in the 3rd fifth and y is either in the 1st or 2nd fifth, or finally if x is in the 4th fifth and y is in the 1st fifth), then you know that the point (x, y) does contain a crystal (as the 4 main squares are always there regardless of the magnification). And the final bit that you can 'ballpark' (i.e. not worry about) are all the points where the y coordinate is in the 3rd fifth of the board or higher (as there's never going to be a crystal there regardless of magnification). So, we finally arrive at the recursive step. This is where most people lost marks (at least based on what I saw). If the x and y coordinates are in the fifth just above one of the 3 main squares (think of the 4 main squares like a podium, where the person who finished first stands in the middle, and the people who finished second and third stand a bit lower on either side of first place), then essentially you have a copy of the (m-1)th magnification of the looking glass on top of each of these three 'podium' squares. Now, you can call the function 'look' again, but this time you call it for magnification (m-1), and for a new pair of coordinates (x, y) (you have to readjust your cordinates so that are within the (m-1) magnification's board). This might be a little hard to follow, so I have included the code below (in C++) to help out:
S4- This problem was another long one. Given the number of units of blood there are available for each of the 8 blood types, and given the number of units of blood type required for patients for each blood type, and given that every patient requires only one unit of blood, determine the maximum number of patients that will receive blood. On top of this, you are also given certain properties: - Patients with blood type O can only receive a unit of blood type O - Patients with blood type A can receive a unit of blood type A or O - Patients with blood type B can receive a unit of blood type B or O - Patients with blood type AB can receive any type of blood Furthermore, patients with Rh-negative blood type can only receive Rh-negative blood, and patients with Rh-positive blood can receive either Rh-negative or Rh-positive blood. I know of quite a few people who attempted to search for a dynamic programming algorithm as soon as the word 'maximize' (I too initially fell prey to this temptation...), though this problem turns out to be a lot easier than that. Since people with certain blood types are more 'restricted' that people with a different blood type (for example patients with blood type O- can only receive O- blood, where as patients of blood type AB+ can receive any type of blood), one strategy is too give blood to the most restricted patients first and then work your way upwards (giving out any extras of any certain blood type that has already been used by the more restricted patients). This type of strategy is usually classified as a 'greedy' algorithm, as you are greedily distributing the units of blood based on certain properties. S5- This problem was quite an interesting one. Unlike in #4, if you saw the word 'minimize' here and thought of dynamic programming, you be would right (well, then again, dynamic programming isn't the 'wrong' way to approach #4. These analyses are merely one take on these problems, so take it with a grain of salt). The problem states that there is a line of up to 1000 switches, each of which are either initially switched on or off. At each turn, you can switch on a light that is switched off, and that's all that you can do. If there is a run (i.e. a contiguous block) of on switches of length 4 or more, the switches all turn off instantaneously. Knowing this, determine the minimum number of switches you need to turn on to eventually have all the lights switched off. There are a couple of ways of solving this. Here's one way to go about solving this problem. This problem actually is kind of similar to #4 from the last round of DWITE (in a way). You create an array, let's call it 'best', of dimensions 1000*1000*4, where best[i][j][k] stores the minimum number of switches you need to switch on between switch i and switch j such that there are exactly k on switches between switch i and switch j (inclusive). Your base cases would be all best[a][b][n], where a <= b, and n is the initial number of switches that are on between switch a and b (this takes O(n^3) to compute naively). Then you work through the intervals [switch i -> switch j] by iterating through all the switches in that interval and try splitting it up into two sections. So, for every switch k betweek i and j, you check whether dp[i][k][i]+dp[k][j][n-i] is less than what is currently stored in dp[i][j][n]. Your final answer would then be stored at dp[1][n][0] (well, depending on whether you 0-based, or 1-based your array indices ). This should run in time. However, like we all know, the O(2^K) brute force would have sufficed as well. I guess that's the way it went. So, I hope this clears things up a bit. Feel free to ask me any question you might have. |
|||
| Author: | Helldemon80 [ Thu Mar 03, 2011 7:17 pm ] |
| Post subject: | Re: CCC 2011 Solutions/Analyses |
Thanks a lot A.J! Anyways for S4, I just want to make sure cause i know i messed this up on the contest. I did the greedy algorithm where the patients with the least compatibility took blood first. But what i messed up with now looking back is that I let patients take other blood before taking their own native blood, is this what you were supposed to do. For example, when i ran through the my algorithm and the O- and O+ have been served, i reach the A-, and in my algorithm they take the O- and then take the A- blood. Was i supposed to take the A- blood first? This is the part that confused me. Thanks |
|
| Author: | A.J [ Thu Mar 03, 2011 7:22 pm ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
Yes, I believe that you are supposed to give the patient that require a type T that type before distributing any extras (so give all the AB's to the AB's, O's to the O's, etc... before giving O's to A's, B's and AB's etc...). |
|
| Author: | Dratino [ Thu Mar 03, 2011 8:36 pm ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
Also, you have to give blood to the types with the most donor restrictions first. So A- would give first to A-, then to A+ and AB-, and finally AB+ if there's still any left. The order in which A+ and AB- are done, however, is pretty arbitrary, and I had to try a total of 8 cases for that one. |
|
| Author: | Helldemon80 [ Thu Mar 03, 2011 8:47 pm ] |
| Post subject: | Re: CCC 2011 Solutions/Analyses |
Crap, I should've read the problem explanation more carefully. Wasted a lot of time cause of that dumb mistake -_- Lesson learned: Read the problem statements more carefully before coding. |
|
| Author: | ultimatebuster [ Thu Mar 03, 2011 8:51 pm ] | ||
| Post subject: | RE:CCC 2011 Solutions/Analyses | ||
I have a pretty crappy version of J5. I'm wondering if anyone else has written it and came up with a better solution? ===Problem Description=== Mark invited some people to join his social network. Some of them invited new people, who invited new people, and so on. Now there are N people in the network, numbered from 1 to N. Mark has decided to remove some people he invited, and the people they invited, and so on. Mark will never remove himself, and we do not allow people to be invited by more than 1 person. Mark can also decide to not remove anyone. ===Input Specification=== The first line contains a single integer N(N <= 6), the number of people in the network. Next are N-1 lines telling us who invited each person. To be precise, line i in this set (1<=i<=N-1) contains a single integer j (with j > i), which indicated that person j is the person who invited person i. Person N is Mark. ===Output specification=== Output a single integer, the number of possible sets of people that can be removed. ===TEST CASE 1=== Input: 3 3 3 Output: 4 Explanation: The first number pof the input indicates there are three people in the network. The next line tells us that Person 1 was invited by Mark, while the last line tells us that Person 2 was also invited by Mark. The set of people that can be removed are {}, {1}, {2}, {1,2} ===TEST CASE 2=== Input: 4 3 4 4 Output: 6 Explanation There are 4 people in the network. Here's a table of who invited who: People inviting | Invited 1 | none 2 | none 3 | 1 4 | 2,3 The possible sets are {}, {1}, {2}, {1,2}, {1,3}, {1,2,3}. Notice set {3} and {2,3} are not possible, since when you remove 3, you must remove 1. ===MY TEST CASE=== Input: 6 2 4 4 5 6 Output: 8 Possible set: {} {1} {1,2} {1,3} {1,2,3,4} {1,2,3,4,5} {3} {1,2,3} (This is worked out by hand) MY SOLUTION IN PYTHON:
|
|||
| Author: | Dratino [ Thu Mar 03, 2011 9:00 pm ] | ||
| Post subject: | Re: CCC 2011 Solutions/Analyses | ||
My personal algorithms for S3 and S4: S3. This one was actually pretty easy for me, and I only used recursion in name, not in code - it was actually a loop. What I did was store a 5x5 array with which squares were definitely empty, and which squares were definitely crystal. The squares that still had to be checked followed the exact same pattern when magnified. The pattern is recorded as follows:
Where -1 means "empty", 1 means "crystal", and 0 means "check deeper if you can; otherwise empty". It's rotated 90 degrees because the coordinate system was transformed. S4. Really, I went on my gut feeling that a greedy algorithm would work on this one. I basically treated the rhesus factor (the + or - thing) as a C antigen (cue biology people raging at me). So now, it's between the blood types O, A, B, C, AB, AC, BC, and ABC (e.g. A- is just A, B+ is BC, etc.). What do you know? All the possible combinations of those three antigens! What makes the greedy algorithm work is the unilateralism of the donations. No antigen type can donate to an antigen type with more letters (O has 0 letters). So, we can take care of ABC first. ABC can only donate to ABC. Then, we have three types that can only donate to themselves, or ABC: AB, AC, and BC. The greedy algorithm will prioritize donating to its own type, then donating to a type with one extra antigen, then two extra, etc. In this case, the AB donors will donate all they can to AB, then whatever's left will go to whatever of ABC is left. After these three types are done, we have three more types that can only donate to either themselves or three of the 4 types that have already been donated to. So, again, type A will donate to itself first, then to AB and AC, then to ABC. Note that A cannot donate to BC, even though it has more letters, because the antigen type does not match at all. This is where the main tricky part of the problem came in. How do you know which one the greedy algorithm should deal with first, AB or AC? Because just arbitrarily assigning an order will not always return the best solution, as I found to my chagrin after 45 minutes of trying to code this problem. As it turns out, you don't. (Or at least, I didn't.) You have to iterate through all of the possible orders in which the donation should be prioritized, as I found out when I was testing my program. That gave me a "best of 8" situation, which is still good. O is the easiest to deal with - it just goes to any types that are left. Now, imagine using this algorithm for four antigens - A, B, C, and D. For A, you'd have to check with AB, AC, and AD, and then ABC, ABD, and BCD - 36 permutations to the power of 4 for 4 different cases. And for AB, you'd have to check with ABC and ABD - 2 permutations to the power of 6 for 6 2-antigen types. That's a total of 107,495,424 cases to check. There's probably a better algorithm for this, obviously. |
|||
| Author: | A.J [ Thu Mar 03, 2011 9:28 pm ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
@Dratino- I think you are overthinking it. Having said that, there were people who implemented max flow min cut for this problem. Though that is an interesting take on the problem. I am interested to hear from anyone who solved #5. Cyril mentioned running a DP algorithms on the runs of on switches (another way you could solve the problem by). |
|
| Author: | helLOHELlo [ Thu Mar 03, 2011 9:28 pm ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
I did some really crapy work at s4 at first which made me didn't have enough time to even look back at s3 But I think if you sort through the order of patients to receive the blood it will work. basics: 1.o- is difinitely the first one and ab+ is difinitely the last one 2.the order between (a- b-) and the order between (a+ b+) does not matter 3.o+ is in front of (a+ b+) so basicly we have o- (a- or b-) o+ (a+ or b+) ab+ as for ab- I simply put it as th second last [ I forgot why i did this, but this might be what I was thinking at the time] o+ could only use o- and o+, but ab- has the choice of o-,a-,b-,and ab- so o+ need to be in front of ab- and same for a+, b+ so the order is o-,(a- or b-),o+,(a+ or b+), ab-,ab+ and the rest is simple... [I'm not sure this is the only order or not, but it works..] |
|
| Author: | Dratino [ Thu Mar 03, 2011 9:40 pm ] |
| Post subject: | Re: RE:CCC 2011 Solutions/Analyses |
A.J @ Thu Mar 03, 2011 9:28 pm wrote: @Dratino- I think you are overthinking it.
Well, that was my thought process during the contest. It's easy to overthink when you're just looking for something that works. XD Also, if you're talking about the ABC thing, that was actually to simplify it. Thinking of the +/- antigen as a different factor made me do things the wrong way, which is when I came up with the C thing to make things symmetrical. Quote: Having said that, there were people who implemented max flow min cut for this problem. Though that is an interesting take on the problem.
I thought of the max flow min cut thing, but had no idea how to implement it. |
|
| Author: | RandomLetters [ Thu Mar 03, 2011 10:19 pm ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
For s4 I drew a chart that showed the blood types in order from O- A- B- AB- O+ A+ B+ AB+ and manually coded to donate(patient, donor) for each valid combination combination in greedy order. So then I had like foreach type donate(type, type) next donate(A-, O-) donate(B-, O-) etc. Actually only 8 permutations if you loop through the same types and every type for B+ |
|
| Author: | Shanethe13 [ Fri Mar 04, 2011 7:01 pm ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
I haven't actually gotten my marks yet, but I'm pretty sure my solution to S5 works. I'd test it myself, but I don't have my source code on me. I created an initial string to store the array of lights ("1010111011" for example), then passed it as an argument to a recursive method. From there, I basically constructed a graph, with each mutation of the string being a node. It would check for sequences of four or more active lights, disable them, then start flipping lights on, creating the corresponding node in the process. If it comes across a node which already exists, it checks that node's distance against the distance of the current iteration, and either continues calculations, or returns depending on which is greater. It also treats the reverse of each string as being equivalent (11001 is the same as 10011), for optimization purposes. I'm not sure if my explanation made any sense, but at its core, it's a glorified pathfinding algorithm, with some memoization thrown in. |
|
| Author: | A.J [ Fri Mar 04, 2011 7:13 pm ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
So essentially you bruteforced it (or implemented a DFS). This should get 15/15, as the largest testcase had <= 25 lights. However, if the testcases did have anywhere near 1000 lights, this method times out. |
|
| Author: | Shanethe13 [ Fri Mar 04, 2011 7:22 pm ] |
| Post subject: | Re: CCC 2011 Solutions/Analyses |
Yep, I used depth-first search. It got the job gone, but it's the efficiency I was worried about. If the test cases are all <=25, it should work though, since I had tested it with 20 lights and it ran in 1-3 seconds depending on the test case. The solution you posted is a lot nicer though. |
|
| Author: | Quantris [ Mon Mar 07, 2011 8:12 pm ] | ||
| Post subject: | Re: CCC 2011 Solutions/Analyses | ||
Hey all, this is my first post. Full disclosure: I'm a university student, the only reason I looked at the CCC is because I've been helping some high-schoolers prepare for it. Not sure if there are many "old guys" here or not. Anyway, just wanted to comment on J5, S4, and S5: J5: The low bound suggests they were expecting a brute-force (try all sets to delete, checking each one to see if it is valid). But there is a simple DP/recursive solution because of the tree structure, and it's ultra short because they give you the nodes in topological order already  This problem is efficiently solvable for much larger values of N. My code follows.
S4: I totally had my blinders on; I jumped straight to min-cut instead of seeing the greedy. But it is actually pretty easy to code if instead of actually writing max-flow (with alternating paths), you simply try all viable s-t cuts and keep the minimum one. I did this by picking some subset of the blood types to keep on the s-side of the cut (2^8 ways to do it) then figuring out which patient types are also on the s-side to avoid an infinite cut capacity (basically, any patient which could accept an s-side blood type). Adding any other patient type to the s-side would only increase the cut capacity so you don't need to try that. Overall it was O(n*2^n) where n is the # of blood types. But I suppose that you could simply try all 2^16 cuts (making sure to properly track the infinite ones) without having to think very hard -- it would probably be a bit easier to code. If, like me, you are skeptical/can't quite convince yourself of the greedy algorithm's correctness, you can actually just prove that you'll end up with no alternating paths if you follow it. S5: You can do this in linear time  Use the fact that the biggest group you can eliminate at once is 7 lights. I'll leave it at that (for now) because it is fun to figure it out. |
|||
| Author: | A.J [ Mon Mar 07, 2011 8:53 pm ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
Hello Quantris Good job on the find for J5. I believe that is the intended solution for the question (compact, and elegant). For S4, there were people who coded up the max-flow and passed. When you see a matching problem, you tend to think of max-flow (but it was also nice that greedy ended up working). As for S5, I won't spoil the fun, though I am kind of skeptical. |
|
| Author: | Quantris [ Thu Mar 10, 2011 10:46 pm ] |
| Post subject: | Re: CCC 2011 Solutions/Analyses |
A.J wrote: As for S5, I won't spoil the fun, though I am kind of skeptical. Skeptical of what, exactly? At least the observation that the most lights you can turn off at once is 7 gets you to a quadratic DP (which, if they had test data with N=1000, is what you'd need instead of O(n^3)). From there, there's a bit of a tricky observation to cut it down to linear, and making it depends greatly (at least for me) on how you approach the quadratic DP. Proving it is correct is also a bit messy (in certain cases) but I'm confident that it works. |
|
| Author: | A.J [ Thu Mar 10, 2011 11:15 pm ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
Well, turns out that the unofficial solutions to #5 also describes an algorithm that runs in linear time (http://access.mmhs.ca/ccc/2011/s5switch.txt). Perhaps you were talking about that? I was skeptical because I wasn't sure how one would go about proving it. If it works, great. |
|
| Author: | ultimatebuster [ Thu Mar 10, 2011 11:36 pm ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
This year's senior is way too easy, isn't it. |
|
| Author: | A.J [ Fri Mar 11, 2011 12:40 am ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
Yeah, it was. Though that probably means that next year's will be hard. |
|
| Author: | Quantris [ Fri Mar 11, 2011 5:43 am ] |
| Post subject: | Re: RE:CCC 2011 Solutions/Analyses |
A.J @ Thu Mar 10, 2011 9:15 pm wrote: Well, turns out that the unofficial solutions to #5 also describes an algorithm that runs in linear time (http://access.mmhs.ca/ccc/2011/s5switch.txt). Perhaps you were talking about that?
I was skeptical because I wasn't sure how one would go about proving it. If it works, great. Actually that solution is wrong, I sent him an email about it. For example it fails the case: 110010010000111 |
|
| Author: | A.J [ Fri Mar 11, 2011 8:42 am ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
Yes, you are right. His solution was merely a heuristic, which usually doesn't work for all possible test cases, but seeing as the test cases for #5 this year were a bit soft, I guess a heuristic would have sufficed. His solution to #4 seem to have failed as well, though it looks like he implemented the greedy algorithm as well. You should send him your linear time solution. |
|
| Author: | AlexWang [ Sat Mar 12, 2011 2:48 pm ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
I used SAP(network flows) to solve s4 cuz that made things easier.. |
|
| Author: | Quantris [ Mon Mar 14, 2011 12:06 am ] |
| Post subject: | Re: CCC 2011 Solutions/Analyses |
A.J wrote: Yes, you are right. His solution was merely a heuristic, which usually doesn't work for all possible test cases, but seeing as the test cases for #5 this year were a bit soft, I guess a heuristic would have sufficed. His solution to #4 seem to have failed as well, though it looks like he implemented the greedy algorithm as well. You should send him your linear time solution. Just did that; had to wait until I had time to comment my solution to attempt to explain what I was doing. Regarding S4, I'm no longer convinced that any greedy algorithm would work (in general, clearly some did work for the CCC test data), and I think that you do have to do some searching of the nature Dratino was talking about to handle all possibilities. What I mentioned before about "no augmenting paths" turned out to be a flawed argument as I was assuming a kind of total order on the blood types which doesn't hold. |
|
| Author: | Dratino [ Thu Mar 17, 2011 2:38 pm ] | ||
| Post subject: | Re: CCC 2011 Solutions/Analyses | ||
Somebody had a linear solution for S5? I feel dumb for using an exponential time solution now >_> (I don't know that much DP, that's why.) Quantris @ Mon Mar 14, 2011 12:06 am wrote: Regarding S4, I'm no longer convinced that any greedy algorithm would work (in general, clearly some did work for the CCC test data), and I think that you do have to do some searching of the nature Dratino was talking about to handle all possibilities. What I mentioned before about "no augmenting paths" turned out to be a flawed argument as I was assuming a kind of total order on the blood types which doesn't hold.
The only reason any old greedy algorithm won't work is because each antigen type can't donate to all antigen types with more letters (A can't donate to BC, B can't donate to AC, etc.). If that were true, then the "total order" you were talking about would exist. It's only best of 8 for three antigen types, but that's because 3 is a very special case (A can't donate to BC is the only type of exception to the total order). If there were four antigen types (say, ABC positive, BC negative, etc.) then max flow min cut would probably be the best solution, because using my method you'd have to perform more than 100,000,000 searches. If anyone's interested in how I found this out, try running these three test cases:
If they don't all return 9, then your program has some errors. Mine returned 7 in the middle of the contest, which is how I figured it out. |
|||
| Author: | Quantris [ Sat Mar 19, 2011 4:17 am ] | ||
| Post subject: | Re: CCC 2011 Solutions/Analyses | ||
Dratino wrote: Somebody had a linear solution for S5? I feel dumb for using an exponential time solution now >_> (I don't know that much DP, that's why.) I don't know if anyone used a linear time solution for the actual contest; an O(n^3) or O(n^4) solution would have easily passed (as would an exponential solution with some simple heuristics). I figured it out afterwards while preparing some comments on the problems; I think I mentioned that I'm a university student "coaching" some high schoolers. Nice test cases for the blood types, I'll probably share them with my students
Since Mr. Robart hasn't yet had time to post my solution on his site, here's what I sent him (complete with the hastily added wall of text at the top trying to explain what is happening):
|
|||
| Author: | Dratino [ Tue Mar 22, 2011 5:37 pm ] | ||
| Post subject: | RE:CCC 2011 Solutions/Analyses | ||
How would your program handle this case:
: ? The answer looks like 2 at first glance, but then you realize that you actually need 3 steps. I figured this out during the contest, but was confused as to what the question was really asking. Quantris wrote: Nice test cases for the blood types, I'll probably share them with my students
If you do share them, tell me how they did  |
|||
| Author: | Quantris [ Tue Mar 22, 2011 10:25 pm ] | ||||
| Post subject: | Re: CCC 2011 Solutions/Analyses | ||||
Dratino wrote: How would your program handle this case:
: ? The answer looks like 2 at first glance, but then you realize that you actually need 3 steps. I figured this out during the contest, but was confused as to what the question was really asking. I'll label the three groups A, B, and C:
We look at the groups from left to right. Group A will either be eliminated by itself, or together with group B (we can't do all three in one go because that would span more than 7 spaces). In case 1, we have to do 2 switches (span of 4 minus 2 lights already on) and we're left with B and C; in case 2 we have to do one switch (span of 5 minus 4 lights already on) and we're left with just C. Case 1 is kind of like saying we'll eliminate B/C before coming back to A, because there's no other way to switch off just A by itself. Now look at case 1. Either we eliminate B by itself, or together with C. The first option (1a) takes 2 more switches, and we're left with C (which is just case 2), while the second (1b) takes one more switch. So 1b is a solution with three switches. Considering case 2, there's only one thing we can do (eliminate C) and that takes 2 switches. So 1a takes 2 + 2 + 2 = 6 switches, and case 2 takes 1+2 = 3 switches. The best we saw was 3 so that's the answer. Note the interesting thing about 1a; you actually can't do 6 switches (extra stuff turns off no matter what order you try). But try to convince yourself that you'll only overestimate the number of switches needed, and also that the optimal solution will be covered by some grouping of the lights into which ones turn off together. |
|||||
| Author: | VK_eipi [ Wed Mar 30, 2011 12:28 am ] | ||
| Post subject: | Re: CCC 2011 Solutions/Analyses | ||
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):
However, I think I might have found a "best of 2" solution. I'm not quite sure though, so counter-examples are welcome. Only the part dealing with distributing {O+, A-, B-} blood to {A+, B+, AB-} patients really matters, since everything else can have a fixed order. So here's how I handle that part: Case 1 1. A- to AB- 2. A- to A+ 3. O+ to A+ 4. O+ to B+ 5. B- to B+ 6. B- to AB- Case 2 1. B- to B+ 2. O+ to B+ 3. O+ to A+ 4. A- to A+ 5. A- to AB- 6. B- to AB- 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. |
|||
| Author: | crossley7 [ Wed Mar 30, 2011 12:50 pm ] |
| Post subject: | RE:CCC 2011 Solutions/Analyses |
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. O- to O- O+ to O+ B- to B- B+ to B+ A- to A- A+ to A+ O- to A- O- to B- O+ to A+ O+ to B+ AB+ to AB+ O+ to AB+ A+ to AB+ B+ to AB+ AB- to AB- O- to AB- A- to AB- B- to AB- O- to O+ B- to B+ A- to A+ O- to A+ O- to B+ AB- to AB+ O- to AB+ A- to AB+ B- to AB+ I think that for this order of solving a greedy solution will work. But then again, since I had the concept to the solution within 5 seconds of understanding the question I probably overlooked something as I solved it in my logic. |
|
| Author: | Dratino [ 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. |
|
| Author: | VK_eipi [ 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) |
|
| Author: | Dratino [ 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):
|
|