Mock CCC

[mseo]

hmm... since the friday has passed, is it okay if people discuss their solutions?

I think my answers to questions 1-4 are correct, but I have no idea how to approach question #5

CCC is in 4 days

[TerranceN]

DtY @ Fri Feb 19, 2010 11:07 pm wrote:

The last CCC question from last year (wireless), the last line of sample input is "5115", but the grid is only three tall, so that falls out of bounds.

On the diagram, it's drawn at point (1,5), rather than point (5,1). Am I misreading the input, or is that a misprint?

http://cemc.uwaterloo.ca/contests/computing/2009/stage1/seniorEn.pdf

I believe you are misreading the input, I think you mixed up x and y. Look at the edits I made to the diagram, does that help?

[DtY]

TerranceN @ Sat Feb 20, 2010 2:36 am wrote:

DtY @ Fri Feb 19, 2010 11:07 pm wrote:

The last CCC question from last year (wireless), the last line of sample input is "5115", but the grid is only three tall, so that falls out of bounds.

On the diagram, it's drawn at point (1,5), rather than point (5,1). Am I misreading the input, or is that a misprint?

http://cemc.uwaterloo.ca/contests/computing/2009/stage1/seniorEn.pdf

I believe you are misreading the input, I think you mixed up x and y. Look at the edits I made to the diagram, does that help?

Ohh, I get what I was doing, (1,3), and (3,1) were both there, so when I went to make sure I was reading it right, I looked for (1,3), found (3,1) and saw it was there.

Thanks for the diagram

[edit] Woo, got it, except for being slow with the actual test data.
Is there a time limit on how long your program runs?

[TerranceN]

I don't think so, but I don't see how this would take a long time to run. How did you program this?

I would just go through each grid point and check if each point is in or on the circle, and have a total bitrate for each point and just increase that. I have no idea if that is how it is supposed to/the best way be done though (This year will be my first CCC).

The one that really has me stumped out of thoses is the degrees of seperation one. I have no idea where I would even begin. Any help would be appreciated.

[DtY]

That's how I did it, it worked fine on the sample input (really fast), but when I ran it on the actual test data (which you wouldn't get when you're doing the contest), it was too slow.

I'm sure it would have been fast enough if I was using C.

--
Actually, mine was a little different than that, I started with a grid filled with zeroes, then for each coffee shop with wifi, loop over every point within a square around that point, and if it's within a circle of the wifi, increment that point by the bitrate.

[TerranceN]

Ok, after looking at the test data I understand why it took so long. It's a grid of 1000 x-values by 30000 y-values, and there are about 1000 circles, some of which have radii of over 9000!!! But seriously, no matter what language you use that would take a long time. Here is an example of one of the circles

730 14872 17630 4

So you would have to check (2 * 17630) * (2 * 17630) (it would not let me put the squared symbol) points to see if they are in the circle (actually less cause they would not be on the grid, but still)... Now times that by about 500 (as the other 500 have small radii).

[A.J]

Sorry about the delay guys. I have included solutions (in C++) to the problems with descriptions to #1 -> #4 in the programs. As for #5 (and a copy of #4), I have also included a word document with these.

Sorry about the delay once again.

Feel free to ask me any other questions,
AJ

(P.S: Continue to send me solutions if you want me to mark them)

[A.J]

Ok, here's an updated solution of #5 (and by updated, I mean better).

This solution is due to Brian Bi, Woburn Collegiate Institute (similar to my solution but more precise):
"First we make two critical observations:

1. The order in which tiles are tapped is irrelevant.
2. Tapping a tile twice is the same as not tapping it at all.

Combining these two observations yields the result that all we have to do is pick some subset of the tiles, then tap each tile in that subset exactly once. Each tile on the billboard is either tapped or not tapped, so on a 16 ? 16 billboard, there are 2256 different subsets to try. Attempting to try them all will clearly time out, but can earn 5 of the 15 points.

A smarter strategy is needed to get 15/15. Here's what we do. Notice that since we may tap tiles in any order, it is acceptable to tap them row by row: that is, we start by tapping any tiles we wish to tap on the first row, then we move on to the second one, and so on, never revisiting a row. Now notice that once we have tapped our tiles on the first row, some tiles may still be black on the first row. The only way to make these white now is to tap the tiles directly underneath them in the second row. Furthermore, we cannot tap any additional tiles on the second row, because this would flip some additional tiles on the first row, turning them black. That is, once we have tapped the first row, we immediately know which tiles to tap on the second. But then this immediately tells us which tiles to tap on the third row, for the same reason: we tap exactly those tiles on the third row that are now below black tiles on the second row. And so on, down to the last row. If we are lucky, after tapping tiles on the last row there will not remain any black tiles. We brute-force all possible subsets of tiles on the first row to tap, in each case chasing the tiles down to the last row and counting our taps as we do so. We then report the lowest count associated with a completely white billboard. If none of the combinations we try gives a completely white billboard at the end, we know it is impossible, and report that the billboard is damaged."

[DtY]

TerranceN @ Sat Feb 20, 2010 11:48 am wrote:

Ok, after looking at the test data I understand why it took so long. It's a grid of 1000 x-values by 30000 y-values, and there are about 1000 circles, some of which have radii of over 9000!!! But seriously, no matter what language you use that would take a long time. Here is an example of one of the circles

730 14872 17630 4

So you would have to check (2 * 17630) * (2 * 17630) (it would not let me put the squared symbol) points to see if they are in the circle (actually less cause they would not be on the grid, but still)... Now times that by about 500 (as the other 500 have small radii).

Actually, the way you worded that made me realize that you could instead loop over a quarter of that, the top right corner, and set four points, the remaining three quadrants each time. Since in a high level language like python, most of the overhead is in all the iteration, it would probably drastically increase the speed.

You could also get a good speed increase by using C arrays (via numpy) instead of python lists (since C arrays can be modified in constant time, whereas python lists have slower lookups in deeper elements). You probably wouldn't be able to use numpy though, since it's not part of the std python install, and I'm not sure what reason schools would have to install it.

[A.J]

Guys, this thread is strictly for the Mock CCC. Any discussion of other CCC problems should be taken to a separate thread.

Thanks

[jimjim168]

DtY @ 2010-02-20, 12:07 pm wrote:

The last CCC question from last year (wireless), the last line of sample input is "5115", but the grid is only three tall, so that falls out of bounds.

On the diagram, it's drawn at point (1,5), rather than point (5,1). Am I misreading the input, or is that a misprint?

http://cemc.uwaterloo.ca/contests/computing/2009/stage1/seniorEn.pdf

Hey man, you see, the point in left-bottom is (1,1). And the east-west road passing (1,1) pointing at the east is the X-axis.
The north-south road passing (1,1) pointing at the north is the Y-axis. So needless to say, the sample input is right... Cuz the description says the input is X,Y, which are X-coordinate and Y-coordinate...
BTW, Do you think that University of Waterloo can make such a mistake?

P.S: I ain't a Canadian so there might be some grammar mistakes in my expression...

[A.J]

Guys....seriously, another thread!

[DtY]

Sorry for the off topic discussion, it just threw me off that it gave height then width, but x then y (the two pieces of information they gave you were backwards from each other).

Btw, thanks for these questions, donno if I said that already

[A.J]

Oh, no problem. Thanks should also go to Brian, who helped me arrange the problem set and converted it to Latex