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 maxflow and passed. When you see a matching problem, you tend to think of maxflow (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.






Sponsor Sponsor



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 >_> (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 sl 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 bottomup fashion (starting on the right and working backwards).
*/
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
typedef vector<int> 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<PII> 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 = N1; 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 counterexamples 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.







