----------------------------------- A.J Thu Mar 03, 2011 6:33 pm 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 #include #include #include using namespace std; int t, im, ix, iy, pow5 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 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. ----------------------------------- Helldemon80 Thu Mar 03, 2011 7:17 pm 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 ----------------------------------- A.J Thu Mar 03, 2011 7:22 pm 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...). ----------------------------------- Dratino Thu Mar 03, 2011 8:36 pm 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. ----------------------------------- Helldemon80 Thu Mar 03, 2011 8:47 pm 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. :| ----------------------------------- ultimatebuster Thu Mar 03, 2011 8:51 pm 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 _> (I don't know that much DP, that's why.) 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[/code] 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. ----------------------------------- Quantris Sat Mar 19, 2011 4:17 am 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.) 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): /* 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 ----------------------------------- Dratino Tue Mar 22, 2011 5:37 pm RE:CCC 2011 Solutions/Analyses ----------------------------------- How would your program handle this case: 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 :D ----------------------------------- Quantris Tue Mar 22, 2011 10:25 pm Re: CCC 2011 Solutions/Analyses ----------------------------------- How would your program handle this case: I'll label the three groups A, B, and C: [code] 0 1 1 0 1 1 0 1 1 0 A B C [/code] 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. ----------------------------------- VK_eipi Wed Mar 30, 2011 12:28 am 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): 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. ----------------------------------- crossley7 Wed Mar 30, 2011 12:50 pm 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. ----------------------------------- Dratino Wed Mar 30, 2011 10:51 pm 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): 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. 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. ----------------------------------- VK_eipi Thu Mar 31, 2011 4:07 am Re: CCC 2011 Solutions/Analyses ----------------------------------- 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. 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 :D, 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. -------------------------------- 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 Sat Apr 02, 2011 10:40 am Re: CCC 2011 Solutions/Analyses ----------------------------------- 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 :D (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. Make A, B, and C donate to ABC, if possible. Make O donate to any leftover types.