Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 CCC 2011 Solutions/Analyses
Index -> Contests
Goto page Previous  1, 2, 3  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
A.J




PostPosted: 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.
Sponsor
Sponsor
Sponsor
sponsor
Quantris




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




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




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




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




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




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




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




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




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




PostPosted: 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 Smile

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 <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 = 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




PostPosted: 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 Smile


If you do share them, tell me how they did Very Happy
Quantris




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




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




PostPosted: 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:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 2 of 3  [ 33 Posts ]
Goto page Previous  1, 2, 3  Next
Jump to:   


Style:  
Search: