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) 





Sponsor Sponsor



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 secondtomax 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 13 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 





Sponsor Sponsor



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 twoline 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 maxfrequency and secondmaxfrequency 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 nlength array of nbit 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 1bit, 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 maxfrequency and secondmaxfrequency 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 nlength array of nbit 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 1bit, 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 maxfrequency and secondmaxfrequency 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 nlength array of nbit 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 1bit, 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 (baseN 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:
http://sites.google.com/site/bl0ckeduserssoftware/ccc2012partialsols.zip
(I messed up S3, didn't know what to do for S4) 






