 Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki Blog Search Turing Chat Room Members
Ccc 2012       Author Message
danc Posted: Thu Mar 01, 2012 9:12 pm   Post subject: RE:Ccc 2012

Well, me being a noob, I didn't know that in C++ you can store vectors inside pairs... so I didn't get it until after I found that out (after the contest D: ) but (if we're allowed to post solutions?) it's BFS. You can represent the game as a graph, with edge weights of 1 and edges between any given state and all the possible moves from there.

(If you don't think I should have posted that, yell at me and I'll take it down)    crossley7 Posted: Thu Mar 01, 2012 9:50 pm   Post subject: RE:Ccc 2012

bfs is 1 way to solve it although the naive implementation is expensive for memory (though how expensive I don't know).

There is also the recursive solution (basically a dfs i guess) and most any search algorthm would work if you knew the correct way to implement it. I used the naive recursion with an inefficient memoization that times out for 3 of the 5 test cases but does at least get the correct answer eventually  danc Posted: Thu Mar 01, 2012 10:17 pm   Post subject: RE:Ccc 2012

Hmmm, my solution uses 54 Mb of memory and runs in 10s on the largest case... but that's because I use and compare dynamic arrays representing the states...

Of course, it can also be done by representing the state in a string, but that's more difficult but that makes it much faster and better for memory. 102897108 Posted: Thu Mar 01, 2012 10:34 pm   Post subject: RE:Ccc 2012

I used a number(indicating the No. of a state) to represent a state and some minor tricks to avoid unnecessary calculations. Memory used is 14mb crossley7 Posted: Thu Mar 01, 2012 11:01 pm   Post subject: RE:Ccc 2012

also curious how people went about number 3 with the giant input. I had a frequency array of 1 - 1000 that would slowly increment values as it reads in the 2 million inputs then naively finds how many max values, second max values there are and then checked the 3 cases for the output (multiple max, 1 max, multiple second max, 1 max, 1 second max). My solution runs in about half a second in the worst case in c++.

What were other ways of going about that on (ideally more efficient) trintith  Posted: Thu Mar 01, 2012 11:41 pm   Post subject: (No subject)

crossley7 @ Thu Mar 01, 2012 11:01 pm wrote:
also curious how people went about number 3 with the giant input. I had a frequency array of 1 - 1000 that would slowly increment values as it reads in the 2 million inputs then naively finds how many max values, second max values there are and then checked the 3 cases for the output (multiple max, 1 max, multiple second max, 1 max, 1 second max). My solution runs in about half a second in the worst case in c++.

What were other ways of going about that on (ideally more efficient)

My C++ solution runs in 70 ms on a solid state, or 200 ms on a normal hard drive on the worst case. I used sort(...) from <algorithm> on a vector filled with elements of a class which stores value (pH) and count (frequency). You need to define a member function in this class (lets call the class 'C'): 'bool operator<(const C& other) const' based on frequency. Once it's sorted by frequency, I did the trickery you described with the max frequency and second-to-max frequency.

This is dominated by the hard drive, but is there a better way?

Also, when grading solutions, are all test cases for a question worth the same? Are all questions worth the same. My wonderful teacher promised to finish marking by the end of next week and I'm impatient. danc Posted: Thu Mar 01, 2012 11:44 pm   Post subject: RE:Ccc 2012

Test cases are all worth the same (3), except for number 5 I think, which has 7 test cases with between 1-3 points. crossley7 Posted: Thu Mar 01, 2012 11:55 pm   Post subject: RE:Ccc 2012

Nice, I don't like using classes for contest problems (I generally feel they are overkill), but it would have cut down the time for the second aspect of the program (after assigning input). Nice solution there. I haven't checked my exact runtime, but I do know that considering it does over 4 million commends (2 million read, 2 million increments) + finds the max/min in under half a second I feel good about that. Now for my teacher to send my code to Waterloo for official marking and find out when round 2 qualifiers get posted    trintith  Posted: Fri Mar 02, 2012 12:23 am   Post subject: RE:Ccc 2012

I got 63. I did a DFS instead of a BFS for 4. I even knew I needed to do a BFS. A two-line change (which I thought I made), and I would have gotten 72. Je suis idiot. VK_eipi Posted: Fri Mar 02, 2012 4:02 am   Post subject: Re: Ccc 2012

For S3, after building the frequency table, you can iterate through the possible readings 1 to 1000 just once, keeping track of 6 variables: frequency, lower bound, and upper bound of the max-frequency and second-max-frequency readings. Then at the end, you check which case it is and work it out. E.g. If second max frequency is different from max (only one reading with max, so max_low=max_high), then take the bigger of (max_low - max2_low) and (max2_high - max_low), if one is negative the other's absolute value is bigger anyways.

Because you iterate in order, simplifications can be made such as only setting lower bound when a higher frequency is found and setting upper bound every single time the frequency matches. (You can even share one variable for the two upper bounds, since they are never simultaneously relevant, but it makes things confusing).

For S4, my friend came up with the idea to represent the state as an n-length array of n-bit binary numbers (integers), which might be the same as what user 102897108 means by "a number." Essentially, the coins are considered to be worth powers of two and each pile is represented by its total value, with moving a coin just equal to adding and subtracting the relevant entries. The smallest coin in a pile is equal to the smallest significant 1-bit, which can be calculated by the trick x&(-x). 102897108 Posted: Fri Mar 02, 2012 4:11 am   Post subject: Re: Ccc 2012

VK_eipi @ Fri Mar 02, 2012 1:02 am wrote:
For S3, after building the frequency table, you can iterate through the possible readings 1 to 1000 just once, keeping track of 6 variables: frequency, lower bound, and upper bound of the max-frequency and second-max-frequency readings. Then at the end, you check which case it is and work it out. E.g. If second max frequency is different from max (only one reading with max, so max_low=max_high), then take the bigger of (max_low - max2_low) and (max2_high - max_low), if one is negative the other's absolute value is bigger anyways.

Because you iterate in order, simplifications can be made such as only setting lower bound when a higher frequency is found and setting upper bound every single time the frequency matches. (You can even share one variable for the two upper bounds, since they are never simultaneously relevant, but it makes things confusing).

For S4, my friend came up with the idea to represent the state as an n-length array of n-bit binary numbers (integers), which might be the same as what user 102897108 means by "a number." Essentially, the coins are considered to be worth powers of two and each pile is represented by its total value, with moving a coin just equal to adding and subtracting the relevant entries. The smallest coin in a pile is equal to the smallest significant 1-bit, which can be calculated by the trick x&(-x).

Haha that's what i meant. But i guess what you wanted to say was that the coins are worth powers of N instead of powers of 2 ) VK_eipi Posted: Fri Mar 02, 2012 5:02 am   Post subject: Re: Ccc 2012

102897108 @ Fri Mar 02, 2012 1:11 am wrote:
VK_eipi @ Fri Mar 02, 2012 1:02 am wrote:
For S3, after building the frequency table, you can iterate through the possible readings 1 to 1000 just once, keeping track of 6 variables: frequency, lower bound, and upper bound of the max-frequency and second-max-frequency readings. Then at the end, you check which case it is and work it out. E.g. If second max frequency is different from max (only one reading with max, so max_low=max_high), then take the bigger of (max_low - max2_low) and (max2_high - max_low), if one is negative the other's absolute value is bigger anyways.

Because you iterate in order, simplifications can be made such as only setting lower bound when a higher frequency is found and setting upper bound every single time the frequency matches. (You can even share one variable for the two upper bounds, since they are never simultaneously relevant, but it makes things confusing).

For S4, my friend came up with the idea to represent the state as an n-length array of n-bit binary numbers (integers), which might be the same as what user 102897108 means by "a number." Essentially, the coins are considered to be worth powers of two and each pile is represented by its total value, with moving a coin just equal to adding and subtracting the relevant entries. The smallest coin in a pile is equal to the smallest significant 1-bit, which can be calculated by the trick x&(-x).

Haha that's what i meant. But i guess what you wanted to say was that the coins are worth powers of N instead of powers of 2 )

I actually do mean powers of 2, because I have a separate number for each position. The coins can only be "there"/"not there".

I considered using powers of N (base-N number with digits equal to pile #) since it is the most compact way to represent the state, but I didn't know how to determine the smallest coin of each pile efficiently, since the piles are all jumbled together. What is your method for doing this? trishume  Posted: Fri Mar 02, 2012 8:09 am   Post subject: Re: Ccc 2012

I was using ruby to write the contest so I thought that it would be too slow for S3 but it wasn't.
The first thing I did is write a script to generate a huge test case so I could constantly check speed.

It turns out that it was fast enough and that ruby's massive method chains helped me write a really short solution For S4 I only had an hour left and I am a really slow programmer, so I had to make the decision between taking the whole hour to write an A* solution, or to look for a simpler mathematical solution.
Unfortunately I never found a mathematical solution. So my final submission was
 code: puts "IMPOSSIBLE" # for me to find a mathematical solution... NeilV Posted: Fri Mar 02, 2012 5:54 pm   Post subject: RE:Ccc 2012

see this is why I love python. For S4 I just kept the state as a list and stored it in a dictionary, which has constant lookup time. In other words, I let python hash it for me  bl0ckeduser Posted: Fri Mar 02, 2012 6:42 pm   Post subject: Re: Ccc 2012

Can anyone explain how the grade is calculated ?
Someone seems to have mentionned "full 75", but I only see 27 test files on the Robart website.

BTW my unoptimal S1, S2, S5 C solutions are here:         