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:
 c++: #include #include #include using namespace std; int t, im, ix, iy, pow5[14]; bool look(int m, int x, int y) {     if (m==1) // Base case: magnification level 1     {         if (y==0&&(x==1||x==2||x==3)) return 1;         if (y==1&&x==2) return 1;         return 0;     }     if ((x=4*pow5[m]/5)) return 0; // if the x coordinate is in the first or last fifth, return 0     if (x >= pow5[m]/5 && x < 2*pow5[m]/5) // if the x coordinate is in the second fifth, return 1 if the y coordinate is also in the first fifth (left podium)     {         if (y < pow5[m]/5) return 1;         if (y >= pow5[m]/5 && y < 2*pow5[m]/5) return look(m-1, x-pow5[m]/5, y-pow5[m]/5); // if the point is in the section just above, then recurse through the function for magnification m-1         return 0;     }     if (x >= 2*pow5[m]/5 && x < 3*pow5[m]/5) // if the x coordinate is in the third fifth, return 1 if the y coordinate is also in the first or second fifth (middle podium)     {         if (y < 2*pow5[m]/5) return 1;         if (y >= 2*pow5[m]/5 && y < 3*pow5[m]/5) return look(m-1, x-2*pow5[m]/5, y-2*pow5[m]/5); // if the point is in the section just above, then recurse through the function for magnification m-1         return 0;     }     if (x >= 3*pow5[m]/5 && x < 4*pow5[m]/5) // if the x coordinate is in the fourth fifth, return 1 if the y coordinate is also in the first fifth     {         if (y < pow5[m]/5) return 1;         if (y >= pow5[m]/5 && y < 2*pow5[m]/5) return look(m-1, x-3*pow5[m]/5, y-pow5[m]/5); // if the point is in the section just above, then recurse through the function for magnification m-1         return 0;     } } main() {     freopen("s3.5.in", "r", stdin);     pow5[0] = 1;     for (int i = 1; i < 14; i++) pow5[i] = 5*pow5[i-1]; // generate powers of 5     cin >> t;     while(t--)     {         cin >> im >> ix >> iy;         cout << (look(im, ix, iy)?"crystal":"empty") << endl;     } }

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:
 Python: class Person:     def __init__(self, n):         self.n = n         self.inv = []     def add(self, n):         self.inv.append(n)     def remove(self, recurse=True):         if not recurse:             return sorted(self.inv + [self.n])         else:             consider = self.inv[:] + [self.n]             for i in consider:                 temp = socialNetwork[i].remove(False)                 for j in temp: # Lol could have totally stripped this out because of the set() in the bottom                     if j not in consider:                         consider.append(j)             return sorted(set(consider)) def removeMultiples(*p):     s = []     for n in p:         removed = socialNetwork[n].remove()         for i in removed: # don't need this either lol.             if i not in s:                 s.append(i)     return tuple(sorted(list(set(s)))) # hmm apparently i don't need the list() here according to the top? Didn't know this. socialNetwork = {} N = int(raw_input()) for i in xrange(N+1):     socialNetwork[i] = Person(i) for i in xrange(1, N):     j = int(raw_input())     socialNetwork[j].add(i) sets = [tuple()] for i in xrange(1, N):     removed = removeMultiples(i)     if removed not in sets:         sets.append(removed)     for j in xrange(2, N):         removed = removeMultiples(i, j)         if removed not in sets:             sets.append(removed)         for k in xrange(3, N):             removed = removeMultiples(i, j, k)             if removed not in sets:                 sets.append(removed)             for l in xrange(4, N):                 removed = removeMultiples(i, j, k, l)                 if removed not in sets:                     sets.append(removed)                 for q in xrange(5, N):                     removed = removeMultiples(i, j, k, l, q)                     if removed not in sets:                         sets.append(removed) #print sets print len(sets)

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:
 code: -1 -1 -1 -1 -1  1  0 -1 -1 -1  1  1  0 -1 -1  1  0 -1 -1 -1 -1 -1 -1 -1 -1

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.

 c++: #include using namespace std; int main() {   int N; cin >> N;   int vals[7];   for (int i = 1; i <= N; ++i)     vals[i] = 1;   for (int i = 1; i < N; ++i) {     int p; cin >> p;     vals[p] *= 1 + vals[i];     }   cout << vals[N] << '\n';   }

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:

 code: 0 2 4 0 3 0 0 0 0 0 0 3 0 4 2 0 0 4 3 0 2 0 0 0 0 0 0 2 0 3 4 0 0 3 2 0 4 0 0 0 0 0 0 4 0 2 3 0

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 &gt;_&gt; (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):

 c++: /*    CCC 2011 S5: Switch    solution by Sumudu Fernando    We use a dynamic programming approach; this solution is O(N).    First, we note that any solution can be organized into blocks,    where a block is some set of lights which all turn off at once.    While the order that we turn off the blocks may be important, we can    at least assume that we handle the blocks one at a time.  It should    also be obvious that in an optimal solution, any block must contain at    least one light which was originally on.  Note also that a block cannot    be longer than 7 lights.    We shall regard the originally on lights in terms of connected groups,    since these will always turn off together.  Considering two such groups,    if their span (distance from the left of the leftmost group to the right    of the rightmost one) is 4 or 5, we can always turn off all groups in that    span by filling in the blanks.  Similarly, for spans of 6 and 7, it is    possible to clear the span as a block as long the middle lights (3rd & 4th for    span 6, or 4th for span 7) are off.  So, if we have such a "clearable" span of    length s with l lights already on, it will take s-l switches to clear it as    a block.  If the span is less than 4, we may simply take s as 4 (which means    we'll turn on lights outside the span).  Importantly, we ignore the effect    of such lights on groups outside the block.    Now, we can imagine an O(N^3) algorithm, where for any two groups L and R,    we try all "clearable" blocks inside to clear first (there are O(N) of them),    then recurse on the left and right.    However, it turns out that we can simply consider the groups from left to right    (yielding a linear time algorithm).    The reason this works is that we are not assuming anything about lights outside    the current block, which means that we are effectively indifferent to the order    in which blocks are cleared.  This does mean that we will consider some impossible    cases, such as:     10001, where we presume the two groups are cleared as separate blocks    However, such cases will always take more switches than a larger block (in the above,    clearing both groups in a block of span 5) so they don't affect the correctness of    the algorithm (which is only concerned with the minimum number of switches).    In summary, we consider groups from left to right, and try all possibilities for the    rightmost group in the leftmost block (which must end within 7 spaces), dynamically    solving the subproblem for the groups after that.  In the program below I've written    the dynamic program in a bottom-up fashion (starting on the right and working backwards). */ #include #include #include #include using namespace std; typedef pair PII; typedef vector VI; const int INF = 1000000; int main() {   int K; cin >> K;   bool lights[1000];   for (int i = 0; i < K; ++i) {     char c; cin >> c;     lights[i] = (c == '1');     }   // Find connected groups of on lights   vector lGroups;   lGroups.push_back(PII(0,0));   for (int i = 0; i < K; ++i) {     if (lights[i]) {       if (lGroups.back().second == 0)         lGroups.back().first = lGroups.back().second = i;       ++lGroups.back().second;       }     else if (lGroups.back().second != 0)       lGroups.push_back(PII(0,0));     }   // We'll have an extra entry if there were off lights at the end   if (lGroups.back().second == 0)     lGroups.pop_back();   int N = lGroups.size(), minSwitch[1001] = {0};   for (int i = N-1; i >= 0; --i) {     minSwitch[i] = INF;         int numL = 0;     // we try every group as the rightmost in the block until we get too far away     for (int j = i; (j < N) && (lGroups[j].second - lGroups[i].first <= 7); ++j) {       numL += lGroups[j].second - lGroups[j].first;       int len = max(4, lGroups[j].second - lGroups[i].first);       int t = len - numL;       // for spans of 6 and 7 there are certain configurations that cannot be cleared as a block       if ((len == 6) && lights[lGroups[i].first + 2] && lights[lGroups[i].first + 3])         t = INF;       else if ((len == 7) && lights[lGroups[i].first + 3])         t = INF;       minSwitch[i] = min(minSwitch[i], t + minSwitch[j+1]);       }     }   cout << minSwitch[0] << '\n';   }

Author:  Dratino [ Tue Mar 22, 2011 5:37 pm ]
Post subject:  RE:CCC 2011 Solutions/Analyses

How would your program handle this case:

 code: 10 0 1 1 0 1 1 0 1 1 0

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

 code: 10 0 1 1 0 1 1 0 1 1 0

: ? 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:
 code: 0 1 1 0 1 1 0 1 1 0    A     B     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):

 code: 0 0 2 0 2 0 0 0 0 0 0 1 0 1 2 0 if you put AB- patients first 0 2 2 0 0 0 0 0 0 0 0 2 0 1 1 0 A+ patients first 0 2 0 0 2 0 0 0 0 0 0 1 0 2 1 0 B+ patients 0 2 1 0 1 0 0 0 0 0 0 2 0 2 0 0 O+ donors 0 1 2 0 1 0 0 0 0 0 0 2 0 0 2 0 A- donors 0 1 1 0 2 0 0 0 0 0 0 0 0 2 2 0 B- donors

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.