Posted: 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<iostream> #include<fstream> #include<cmath> usingnamespace 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))return1;
if(y==1&&x==2)return1;
return0;
} if((x<pow5[m]/5)||(x>=4*pow5[m]/5))return0; // 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)return1;
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 return0;
} 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)return1;
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 return0;
} 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)return1;
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 return0;
} }
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.

Sponsor Sponsor

Helldemon80

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

A.J

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

Dratino

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

Helldemon80

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

ultimatebuster

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

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):
ifnot recurse:
returnsorted(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 notin consider:
consider.append(j)

returnsorted(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 notin s:
s.append(i) returntuple(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 inxrange(N+1):
socialNetwork[i] = Person(i)

for i inxrange(1, N):
j = int(raw_input())
socialNetwork[j].add(i)

sets = [tuple()]

for i inxrange(1, N):
removed = removeMultiples(i) if removed notinsets:
sets.append(removed) for j inxrange(2, N):
removed = removeMultiples(i, j) if removed notinsets:
sets.append(removed) for k inxrange(3, N):
removed = removeMultiples(i, j, k) if removed notinsets:
sets.append(removed) for l inxrange(4, N):
removed = removeMultiples(i, j, k, l) if removed notinsets:
sets.append(removed) for q inxrange(5, N):
removed = removeMultiples(i, j, k, l, q) if removed notinsets:
sets.append(removed)

#print sets printlen(sets)

Dratino

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

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.

A.J

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

helLOHELlo

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

Dratino

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

RandomLetters

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

Shanethe13

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

A.J

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

Shanethe13

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

Quantris

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

usingnamespace 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.