Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Ccc 2012
Index -> Contests
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Yves




PostPosted: Fri Mar 02, 2012 6:52 pm   Post subject: Re: Ccc 2012

bl0ckeduser @ Fri Mar 02, 2012 6:42 pm wrote:
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/ccc-2012-partial-sols.zip
(I messed up S3, didn't know what to do for S4)


For S1 to S4, there are 5 cases each with 3 points awarded per case. Partial marks are not awarded for partially correct cases.
For S5, there are 7 cases. The first four are worth 2 each, the second-to-last worth 1, and the remaining two 3 each.
Sponsor
Sponsor
Sponsor
sponsor
ihsh




PostPosted: Fri Mar 02, 2012 10:27 pm   Post subject: Re: Ccc 2012

I finally coded a working solution for S4, which involves a DFS, and states represented like this:
code:

1344 //coin '1' is in location 1, coin '2' is in location 3, coin '3' is in location 4, and coin '4' is in location 4


And since it's a brute-force DFS, I had to limit the the number of steps to 50 for it to run in time...
danc




PostPosted: Fri Mar 02, 2012 10:34 pm   Post subject: RE:Ccc 2012

But why not just use BFS with the same state? BFS, I believe, would run much faster and be not much more difficult to code?

But I probably don't know best.
ihsh




PostPosted: Fri Mar 02, 2012 10:51 pm   Post subject: Re: RE:Ccc 2012

danc @ Fri Mar 02, 2012 10:34 pm wrote:
But why not just use BFS with the same state? BFS, I believe, would run much faster and be not much more difficult to code?

But I probably don't know best.

Because I don't know how to implement a BFS. Embarassed

Oh, and I just noticed that my java IDE doesn't support the Queue class. Hmm, it seems like I should really switch to another IDE; no Scanner, no ArrayList, no HashMap, and now no Queue. Also, please allow me to ask a very ignorant question: without queues, is it possible to (easily) code a BFS?
crossley7




PostPosted: Fri Mar 02, 2012 11:19 pm   Post subject: RE:Ccc 2012

create a manual queue with an array and index of where you started. Ideally a flexible array/vector would be best to use for this purpose or at least something that you can quickly remove elements/indexes from. In C++ I normally use vectors for my queue in a bfs, but you can use makeshift ways of creating a queue.
VK_eipi




PostPosted: Sat Mar 03, 2012 1:26 am   Post subject: Re: RE:Ccc 2012

NeilV @ Fri Mar 02, 2012 2:54 pm wrote:
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 Smile


To clarify, were you referring to a tuple instead of an actual Python list? Lists in Python are not hashable and cannot be used as dictionary keys.
danc




PostPosted: Sat Mar 03, 2012 7:52 am   Post subject: Re: RE:Ccc 2012

crossley7 @ Fri Mar 02, 2012 11:19 pm wrote:
create a manual queue with an array and index of where you started. Ideally a flexible array/vector would be best to use for this purpose or at least something that you can quickly remove elements/indexes from. In C++ I normally use vectors for my queue in a bfs, but you can use makeshift ways of creating a queue.

So do you usually just leave all the elements in the vector and simply shift your index of access variable? Why not just use a queue?

And BFS is not too hard. Sounds like maybe you do know how to implement it if you're asking about a queue. You push your starting state onto the queue, and loop until some condition is true (in this case, whether you win, or queue is empty). Inside the loop, you access the next state, and then find all the possible moves from there and push them onto the back of the queue. It is also necessary to keep track of which states you have already examined, in order to prevent pushing and repushing useless states back onto the queue. Maybe you didn't need that explanation, but I hope that helps.
crossley7




PostPosted: Sat Mar 03, 2012 8:47 am   Post subject: RE:Ccc 2012

I normally index the value at the end of a depth then remove the first element as I check it. Once it reaches that value that I know is the last one of a depth, I increase my depth counter and reset the index to the end of the vector.
Sponsor
Sponsor
Sponsor
sponsor
danc




PostPosted: Sat Mar 03, 2012 9:19 am   Post subject: RE:Ccc 2012

How much faster is that than actually using a queue?
crossley7




PostPosted: Sat Mar 03, 2012 11:17 am   Post subject: RE:Ccc 2012

Not sure since I never have used Java and I'm not sure of exact efficiency. It is more that I know how a vector works and haven't used a queue type if that even exists in C++. My knowledge of the language is relatively primitive and so I make do with what I do know
danc




PostPosted: Sat Mar 03, 2012 11:23 am   Post subject: RE:Ccc 2012

Oh. I was referring to the queue in C++. Makes life pretty easy. You can store pairs in it etc.
NeilV




PostPosted: Sat Mar 03, 2012 11:33 am   Post subject: Re: RE:Ccc 2012

VK_eipi @ Sat Mar 03, 2012 1:26 am wrote:
NeilV @ Fri Mar 02, 2012 2:54 pm wrote:
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 Smile


To clarify, were you referring to a tuple instead of an actual Python list? Lists in Python are not hashable and cannot be used as dictionary keys.


Yeah actually I did convert it to a tuple for the dictionary. But then I worked with it as a list since tuples are immutable.
crossley7




PostPosted: Sat Mar 03, 2012 12:49 pm   Post subject: RE:Ccc 2012

ok, danc. Well, now after the last dwite and this, I have learned 2 new types in c++ Very Happy

Didn't know about pairs or queue. Both of those would make some problems much easier
ultimatebuster




PostPosted: Sat Mar 03, 2012 1:06 pm   Post subject: RE:Ccc 2012

Ah this is embarassing.. I have a 54 according to my teachers. I failed at question 3 and 4, where question 3 it's a matter of just being stupid: all of my own test cases are really the same case.. and here's the incorrect line:

CODE:

return max(secondreadings) - topreadings[0]


Where as the correct is

CODE:

      if min(secondreadings) < topreadings[0]:
        return min(secondreadings) - topreadings[0]
      else:
        return max(secondreadings) - topreadings[0]


... Can't believe I made a stupid error especially since i instantly saw my problem when i ran through the first test case.. damnit.

Something went wrong in my BFS algorithm or my hashing algorithm for S4. It looks like all of the test cases gave incorrect answers for my solution in S4, even though all my own tests passed.

It's probably going to turn out to be something really really dumb as well.. so I don't even want to spend hours debugging my BFS algorithm..
danc




PostPosted: Sat Mar 03, 2012 1:12 pm   Post subject: Re: RE:Ccc 2012

crossley7 @ Sat Mar 03, 2012 12:49 pm wrote:
ok, danc. Well, now after the last dwite and this, I have learned 2 new types in c++ Very Happy

Didn't know about pairs or queue. Both of those would make some problems much easier

haha, and i guess while you're at it, i'll mention priority queues too! useful for dijkstra's, but top element is always the largest value, so you have to negate them. both are in <queue>. useful stuff, yo!
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 6 of 9  [ 122 Posts ]
Goto page Previous  1, 2, 3, 4, 5, 6, 7, 8, 9  Next
Jump to:   


Style:  
Search: