Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
CCC 2011 Solutions/Analyses
Author Message
A.J

Posted: 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.

Quantris

Posted: 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.
A.J

Posted: 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.
ultimatebuster

Posted: 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.
A.J

Posted: 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.
Quantris

Posted: 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
A.J

Posted: 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.
AlexWang

Posted: 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..

Quantris

Posted: 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.
Dratino

Posted: 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.
Quantris

Posted: 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';   }
Dratino

Posted: 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
Quantris

Posted: 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.
VK_eipi

Posted: 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.
crossley7

Posted: 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.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 2 of 3  [ 33 Posts ]
Goto page Previous  1, 2, 3  Next
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: