CCC 2006

[Andy]

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

[bugzpodder]

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.

[MysticVegeta]

The 2005 pinball S5 was more nastier than this P5 one.

[Paul]

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 This time I was off by 1 in every case.

[person]

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?

[MysticVegeta]

Xiao, post the Junior problems.

[Kaze828]

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.

[Cervantes]

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.

[zylum]

anyone have any ideas for #5?

[MysticVegeta]

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.

[gvc]

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.

[MysticVegeta]

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

[gvc]

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.

[gvc]

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.

[MysticVegeta]

What happens to people who use java to advance to Stage 2? They are pretty much forced to use C++