Computer Science Canada

CCC 2006
Author:  bugzpodder [ Tue Feb 28, 2006 10:19 am ]
Post subject:  CCC 2006
Feel free to post anything related to CCC 2006 in this thread. However, refrain from posting questions/solutions until 5pm today.
Author:  MysticVegeta [ Tue Feb 28, 2006 10:46 am ]
Post subject: 
Too bad I cant write it
Author:  Cervantes [ Tue Feb 28, 2006 5:22 pm ]
Post subject: 
S4 was quite the problem. It took me quite a while to understand the problem. It sure would've been good to have known something about matrices and groups. After I (sort of) figured out what it was asking, it wasn't very hard. If not for time constraints at the end, I think it would have been not very difficult.
Author:  MysticVegeta [ Tue Feb 28, 2006 6:33 pm ]
Post subject: 
Can someone post the questions?
Author:  JackTruong [ Tue Feb 28, 2006 7:06 pm ]
Post subject: 
Aren't there people in Hong Kong that also write the CCC? It's roughly 10AM or so there, and they're writing it "today" (March 1st) at 4:30PM to 7:30PM. So it's won't be a good idea to post questions/answers yet, assuming they get the same batch.
Author:  MysticVegeta [ Tue Feb 28, 2006 7:23 pm ]
Post subject: 
I need those questions =\
Author:  Tony [ Wed Mar 01, 2006 10:10 am ]
Post subject: 
Hong Kong's competition is now over. Could someone please post the questions?
Author:  DIIST [ Wed Mar 01, 2006 10:35 am ]
Post subject: 
Shocked I took the contest yesterday. Only managed to get up to S3 Razz
Author:  Kaze828 [ Wed Mar 01, 2006 4:54 pm ]
Post subject: 
I still don't understand S4. All I was able to do was to check whether a number has been repeated in any column or row (like Sudoku). Still got 5 points for it though Smile.
Author:  bugzpodder [ Wed Mar 01, 2006 4:56 pm ]
Post subject: 
What don't you understand? All you need to do is apply the definition of the group.
Author:  JackTruong [ Wed Mar 01, 2006 5:05 pm ]
Post subject: 
Anyone managed to attempt S5? I had a blank face after reading it for the 5th time.
Author:  Kaze828 [ Wed Mar 01, 2006 5:07 pm ]
Post subject: 
I didn't really understand what the definition of the group was. I didn't even try S5.
Author:  Tony [ Wed Mar 01, 2006 5:45 pm ]
Post subject: 
Could any of you guys post the questions?
Author:  MysticVegeta [ Wed Mar 01, 2006 6:15 pm ]
Post subject: 
I second that Tony!! I NEED THOSE QUESTIONS!!!! Mad Mad
Author:  JackTruong [ Wed Mar 01, 2006 6:26 pm ]
Post subject: 
I'll probably do a scan for the senior problems and if I have time, the junior ones too.
Author:  MysticVegeta [ Wed Mar 01, 2006 6:28 pm ]
Post subject: 
Thanks a lot Jack!!! Razz
Author:  cool dude [ Wed Mar 01, 2006 6:31 pm ]
Post subject: 
i did only 3 out of the 5 questions because of time issues and we had to write on a laptop which kept minimizing my programs for some odd reason. i think the touch pad was way to sensitive. anyways
which one do u want me to give u guys b/c i'm not goin to type all the questions out and i don't have a scanner.

here's the one i found difficult understanding. problem 4

here is a list for you left just this morning by your parents
1. do your math homework
2.call your grandma
3.call me at work
4. call your friends
5.feed the dog
7. let the dog out. watch television

your parent given u constraints on these tasks:

1.do your math work before u watch tv
2.do math homework before u call your friend
3.call grandma before u do math homework
4.call me at work before u call friend
5.feed the dog after u call me at work

your to do list can be abbreviated to:
1,7
1,4
2,1
3,4
3,5

x,y represent the task numbered x should be done before task numbered y

additional insturctions are emailed to u by your parent. write programto use original to do list and the additional instructions to output a list of your jobs in order u must do them, or alternately, if u cannot comlete them, u should output that there is no way to complete these tasks, and u r just going to bed

input specifications
u will be given pairs of numbers, one number per line, to represent the additional instructions to be included with your original to do list. the data terminates with the input pair 0 and 0. u can assume that there will be at most 10 additional constarints

output specifications
u should output a list of tasks in orfetr that they should be performed or an error message saying that the tasks cannot be completed. if there r multiple orders in which the tasks may be completed, the following tie breaking rule must be used:

if there is set of taks which may be performed at the same time during the process, the smallest numbered taks should be performed first.

sample input
6
2
5
4
0
0

[/b]output
3 5 6 2 1 4 7

explanation for output
the input data tells us that task 6 must be performed before task 2, and task 5 before taks 4. the only tasks with no prerequisites are 3 and 6, so we choose 3 because it has the lower number. then 5 and 6 are possible; 5 is chosen, then 6. next must come 2, followed by 1. then both 4 and 7 are possible; the lower one is chosen first.

-------------------------------------------------------------------------------------

P.S. whoever solves it pleases post answer i wanna see how u did it. thanks.
Author:  MysticVegeta [ Wed Mar 01, 2006 6:50 pm ]
Post subject: 
=\ its really hard to understand it like this, I wil wait for Jack to scan them.
Author:  cool dude [ Wed Mar 01, 2006 7:16 pm ]
Post subject: 
its actually almost exactly word by word how it said on the contest. thats why i said its really difficult to understand it and i had to read it quite a lot of times to get it. read it over a couple times u might get it. that was prolly one of the hardest ones. the first 2 were the easiest ever. especially the second one because it was like 12 lines.
Author:  JackTruong [ Wed Mar 01, 2006 7:33 pm ]
Post subject: 
That question was part of the junior set, which I'll try my best to scan in later.

Senior problems are up:

Question 1: [Page 1] [Page 2]
Question 2: [Page 1] [Page 2]
Question 3: [Page 1] [Page 2]
Question 4: [Page 1] [Page 2]
Question 5: [Page 1] [Page 2]
Package: CCC Senior 2006
Author:  MysticVegeta [ Wed Mar 01, 2006 7:44 pm ]
Post subject: 
cool thanks
Author:  MysticVegeta [ Wed Mar 01, 2006 8:05 pm ]
Post subject: 
Heh lol, if I was still doing turing, I see #3 getting easily coded with whatdotcolor
Author:  Paul [ Wed Mar 01, 2006 9:03 pm ]
Post subject: 
Number 2, no one in my school had all the cases, because of one case:

They expect you to know that if 25 letters has been found, the last one will automatically be known. Say you have a message and a cypher, with 25 letters of the alphabet, then given a message with 26 letters, they expect you to know the last letter, because all others are known. I know some people at other schools got this, just not mine. Tricky CCC people -_-

Its really easy in turing, discounting the one case, even so, its easily solved with an array of the letters found and the alphabet I suppose, its easy to do but no one here thought of it, including me:
here's my number 2 anyway, just posting it because I'm sure there are people who can do the other solutions much better than I did
code:

var filename : string := "s2.in"
var fileno : int

open : fileno, filename, get

var TexT : string
var Cypher : string
var Code : string

get : fileno, TexT : *
get : fileno, Cypher : *
get : fileno, Code : *
for a : 1 .. length (Code)
    if index (Cypher, Code (a)) not= 0 then
        put TexT (index (Cypher, Code (a))) ..
    else
        put "." ..
    end if
end for
close (fileno)
Author:  Paul [ Wed Mar 01, 2006 9:04 pm ]
Post subject: 
MysticVegeta wrote:
Heh lol, if I was still doing turing, I see #3 getting easily coded with whatdotcolor

No, it cannot, since the lines probably do not cross on an integer point, there is no rule saying they must. And whatdotcolor can only check each pixel, limiting the accuracy. I thought about it too. It could probably be done given an infinite resolution.

All I did was write a function checking if 2 lines intersect, passing in the coordinates of the start and end of each line. So you check each edge of each building with the line itself. Its probably not the best way.

Also you need to include cases like divide by zero, if you're using y=mx+b, and lines with the same slope.

Unfortunately I was rushed, and I was off by 1 in every test case, my teacher says.
Author:  Cervantes [ Wed Mar 01, 2006 9:07 pm ]
Post subject: 
That would involve drawing to the screen. You're only supposed to display the final answer to the screen. Would that be illegal?
Author:  Paul [ Wed Mar 01, 2006 9:08 pm ]
Post subject: 
I dunno, not if it draws in the background I suppose, as long as you have the answers on screen. BUT as I said, it probably wouldn't work unless for the simplest cases.
Author:  MysticVegeta [ Wed Mar 01, 2006 11:00 pm ]
Post subject: 
Cervantes wrote:
That would involve drawing to the screen. You're only supposed to display the final answer to the screen. Would that be illegal?


Why yes it does, but there is no rule saying, you are not allowed to open a window and then close it Laughing
Author:  MysticVegeta [ Wed Mar 01, 2006 11:01 pm ]
Post subject: 
Paul wrote:
MysticVegeta wrote:
Heh lol, if I was still doing turing, I see #3 getting easily coded with whatdotcolor

No, it cannot, since the lines probably do not cross on an integer point, there is no rule saying they must. And whatdotcolor can only check each pixel, limiting the accuracy. I thought about it too. It could probably be done given an infinite resolution.

All I did was write a function checking if 2 lines intersect, passing in the coordinates of the start and end of each line. So you check each edge of each building with the line itself. Its probably not the best way.

Also you need to include cases like divide by zero, if you're using y=mx+b, and lines with the same slope.

Unfortunately I was rushed, and I was off by 1 in every test case, my teacher says.


Do the test cases require it to be "that" accurate that a pixel cant cover it?
Author:  Paul [ Wed Mar 01, 2006 11:33 pm ]
Post subject: 
Hm, actually, now that I think about it, give it a try. It can be done. But in my opinion, in order for you to get it accurate enough, its not any easier than the math method of doing things.

1. The way you'll follow the lines to check for intersections
2. Accuracy, if you're on a 800x600 resolution, you'll only have such amount of grid points. But considering the restrictions they give you, it should be able to work somewhat.
3. what if they gave you the max number of buildings with like 30 sides each? it'll get pretty complex with whatdotcolor. Hint: there are only like 5 test cases though, and the number of sides never went past 8 or 10 I believe.

I still suggest doing it with math though.
Author:  MysticVegeta [ Thu Mar 02, 2006 1:32 am ]
Post subject: 
Well ofcourse I will do it the math way, cause I am doing it in java, I was just suggesting an idea and bringing up andy in the discussion and I am sure he would love my suggestion LOL.
Author:  Andy [ Thu Mar 02, 2006 9:06 am ]
Post subject: 
i cracked up when i read your suggestion.. I'm going home this weekend, i guess i'll try it the whatdotcolor way on the bus..
Author:  bugzpodder [ Thu Mar 02, 2006 9:09 am ]
Post subject: 
hehe that case in #2 is indeed tricky, very good for a topcoder question lol. #3, well, it would be trivial if you had some pre-written library. Which is more or less recommended if you are ever aiming for stage 2.
Author:  MysticVegeta [ Thu Mar 02, 2006 2:32 pm ]
Post subject: 
The 2005 pinball S5 was more nastier than this P5 one.
Author:  Paul [ Thu Mar 02, 2006 5:07 pm ]
Post subject: 
bugzpodder wrote:
hehe that case in #2 is indeed tricky, very good for a topcoder question lol. #3, well, it would be trivial if you had some pre-written library. Which is more or less recommended if you are ever aiming for stage 2.


I dunno why I haven't done it yet >_< I've encountered the same type of problem so many times Sad This time I was off by 1 in every case.
Author:  person [ Thu Mar 02, 2006 7:34 pm ]
Post subject: 
one thing that interests me is that if u advance to stage 2 while taking the Senior CCC, ur no longer allowed to use Java

anyone know y?
Author:  MysticVegeta [ Thu Mar 02, 2006 8:06 pm ]
Post subject: 
Xiao, post the Junior problems.
Author:  Kaze828 [ Thu Mar 02, 2006 9:12 pm ]
Post subject: 
I was going to write a function for determining if two lines intersect too but then I remember I can just use Line2D in java, that saved me alot of time.
Author:  Cervantes [ Thu Mar 02, 2006 9:44 pm ]
Post subject: 
Kaze828 wrote:
I was going to write a function for determining if two lines intersect too but then I remember I can just use Line2D in java, that saved me alot of time.

In a 2D plane, determining if two lines intersect is as easy as
code:

def intersect?(line1, line2)
    line1.slope != line2.slope
end

Determining where the two lines intersect is what requires a (relatively) a lot more work. Or, determining whether a line segment intersects with another line segment.

I assume you meant this. Smile
Author:  zylum [ Thu Mar 02, 2006 11:46 pm ]
Post subject: 
anyone have any ideas for #5?
Author:  MysticVegeta [ Fri Mar 03, 2006 10:50 am ]
Post subject: 
Well the thing that makes this even more difficult is that the cells change in the next generation. I am guessing with no advanced algorithms knowledge, the best one can do is brute force..? But as you can see, we could find a lot of previous generations using that method, but then we need to go previous of those previous o_O, which, by using brute force, is really really and I mean really slow. Michael, I am gonna go in TC and find some pros that know me and link them the problem. maybe they can give some ideas..? Cause I clearly see this can nohow be done using brute force.
Author:  gvc [ Fri Mar 03, 2006 12:37 pm ]
Post subject: 
MysticVegeta wrote:
Well the thing that makes this even more difficult is that the cells change in the next generation. I am guessing with no advanced algorithms knowledge, the best one can do is brute force..? But as you can see, we could find a lot of previous generations using that method, but then we need to go previous of those previous o_O, which, by using brute force, is really really and I mean really slow. Michael, I am gonna go in TC and find some pros that know me and link them the problem. maybe they can give some ideas..? Cause I clearly see this can nohow be done using brute force.


The key observation is that the grid has a maximum of 20 locations, so there are only 2^20 = 1 million possible configurations. For every possible configuration you can compute and record the successor. I'll leave it for you to figure out how to convert that information into what's required for S5.
Author:  MysticVegeta [ Fri Mar 03, 2006 1:46 pm ]
Post subject: 
@gvc: Do you mean 2^10 starting positions or any type of position possible?

@all: wow the J5 was a joke. When I saw that othello board, I expected some recursive solution but the simplicity of it amazed me, simply checking 8 directions and the solution presents itself. I think J4 is more challenging than J5 just like last year. They make J5 sound so confusing, but really its easy as hell.
Author:  gvc [ Fri Mar 03, 2006 1:58 pm ]
Post subject: 
MysticVegeta wrote:
@gvc: Do you mean 2^10 starting positions or any type of position possible?



Just to be clear, I'm speaking of S5. You are to find predecessors in the Game of Life.

The maximum grid size is 4x5. That's 20 grid positions. Each position is either live or dead. That's 2^20 combinations. Map each configuration to an integer and compute successor[c] for all configurations c. All configurations, not just possible starting configurations.
Author:  gvc [ Fri Mar 03, 2006 2:06 pm ]
Post subject: 
person wrote:
one thing that interests me is that if u advance to stage 2 while taking the Senior CCC, ur no longer allowed to use Java

anyone know y?


CCC follows IOI practice. IOI currently supports C++ and Pascal.
Author:  MysticVegeta [ Fri Mar 03, 2006 3:27 pm ]
Post subject: 
What happens to people who use java to advance to Stage 2? They are pretty much forced to use C++
Author:  gvc [ Fri Mar 03, 2006 3:43 pm ]
Post subject: 
MysticVegeta wrote:
What happens to people who use java to advance to Stage 2? They are pretty much forced to use C++


That's right. C++ or Pascal. Same for people who write the first stage in Turing, Perl, Python, Basic, PGP, and so on.
Author:  thegoose [ Fri Mar 03, 2006 4:07 pm ]
Post subject: 
gvc wrote:

The key observation is that the grid has a maximum of 20 locations, so there are only 2^20 = 1 million possible configurations. For every possible configuration you can compute and record the successor. I'll leave it for you to figure out how to convert that information into what's required for S5.


What would be the time limit for S5 be? It is possible for a program to enumerate all gardens of Edens, then see what their successors are (iterating until a state is repeated). Would this solution receive full marks as well?

The test data for no.2 brought back the nightmares of tring to get a ACM problem accepted.....
Author:  gvc [ Fri Mar 03, 2006 4:23 pm ]
Post subject: 
thegoose wrote:
gvc wrote:

The key observation is that the grid has a maximum of 20 locations, so there are only 2^20 = 1 million possible configurations. For every possible configuration you can compute and record the successor. I'll leave it for you to figure out how to convert that information into what's required for S5.


What would be the time limit for S5 be? It is possible for a program to enumerate all gardens of Edens, then see what their successors are (iterating until a state is repeated). Would this solution receive full marks as well?

The test data for no.2 brought back the nightmares of tring to get a ACM problem accepted.....


There are only a million configurations. It is easy to find all the gardens of edens by marking all successors (anything unmarked at the end is a garden of eden). But you'd be silly to do separate forward searches from each garden of eden. You can do an all-points search considering all gardens at the same time - that takes linear time with a BFS. (Linear in the number of configurations, that is.)

Whether or not the separate searches would run in our lifetimes, I'm not sure. Depends on the number of edens and the length of the paths. Perhaps people with the naive method got lucky. CCC tries to ensure that the actual time limit is not a big factor, but sometimes they don't do so well. In spite of the guidelines, some teachers let the solutions run for hours. I know only one or two of last year's full-mark S5s actually used the correct algorithm.

What did you do?
Author:  thegoose [ Fri Mar 03, 2006 4:39 pm ]
Post subject: 
gvc wrote:
What did you do?


I did BFS and its runtime was 1.38 seconds a Pentium 4. I know at least one other person who also did BFS.
Author:  cool dude [ Fri Mar 03, 2006 8:10 pm ]
Post subject: 
does somebody have the answers for the juniour competition? its a lot easier than the senior.
Author:  MysticVegeta [ Fri Mar 03, 2006 8:41 pm ]
Post subject: 
Here is a detailed analysis by me on the junior set:
http://www.compsci.ca/v2/viewtopic.php?t=11477
Author:  Chinchilla [ Thu Mar 30, 2006 3:48 pm ]
Post subject: 
Paul: funny because that's the only question where I managed to get all the test cases

I made alot of stupid mistakes in the problems but my approach to each problem at the time of the contest was as follows

1st: I just built a string that contained all the letters that are possible for the 2 flies, and for each baby I just did a lookup whether that letter was there, not sure where I screwed up but I didn't get all the test cases

2nd: Simple, I used STL and a map as a "letter lookup"

3rd: I made a table of edges and made a "function" (mathematical) to get a certain y value depending on the x. Than I checked whether or not the line touched or passed through an edge in my table.

4th: I treated the inverse property as a special case of identity (from what I could tell that's the truth). Than I recursed through the whole table.

5th: Time was running short. This question was similar to one I did awhile ago, I forget the exact name monkey paradise or something, monkeys can plant trees at different corners, and if a tree is to stay alive it needs a monkey tending to it, I dunno, maybe you guys know. I was working on a n OOP solution for it, making a global "garden" and than each cell in the garden can point to a blank or an object which would be the "live cell." and they would have member functions that controls it's life. I ended up running out of time, so I commented out all the code and made it output '2' (I ended up getting one of the test cases right Smile )


in short, I fucked up alot. I only got about 47 points D:.. what pisses me off was that the problems were so easy, I just make alot of mistakes. I'll win next year Smile
Author:  bugzpodder [ Sat Apr 01, 2006 10:34 am ]
Post subject: 
u should never do OOP on an algorithm contest, unless its like tree nodes or something.
Author:  Chinchilla [ Sat Apr 01, 2006 3:51 pm ]
Post subject: 
Why not, it's alot easier to visualize and code when you have a simple structure to it. Solving problems doesn't necesarilly demand a procedural view on the code.
Author:  Cervantes [ Sat Apr 01, 2006 4:03 pm ]
Post subject: 
Agreed. OOP is wonderful, even for contests. I wrote the CCC in Ruby and wrote my own classes to solve every problem. (Well, every problem that I solved, that is. Wink)

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy