Computer Science Canada Solutions, DWITE 2011-2012 #2-4

 Author: Yves [ Wed Jan 18, 2012 8:19 pm ] Post subject: Re: Solutions, DWITE 2011-2012 #2-4 Cyril @ Wed Jan 18, 2012 7:58 pm wrote:simply note that there are only 2^n = 15 states I think you mean 2^n = 32768 states. I came across this solution but somehow forgot to memoise!

 Author: Cyril [ Wed Jan 18, 2012 8:26 pm ] Post subject: RE:Solutions, DWITE 2011-2012 #2-4 Hahahaha, oops. Somehow, in my head, the operator precedence went like 2^(n = 15).

 Author: crossley7 [ Wed Jan 18, 2012 9:55 pm ] Post subject: RE:Solutions, DWITE 2011-2012 #2-4 Thanks for the solutions Cyril. Could you possibly give pseudo code for number 3 from today? I don't really understand that solution (I have to look 4 and 5 up, but that is just from my lack of algorithm knowledge) Also thanks for dialling it up today. I enjoyed the challenge

Author:  Cyril [ Wed Jan 18, 2012 11:36 pm ]
Post subject:  Re: Solutions, DWITE 2011-2012 #2-4

 code: int componentSize bool visited[] graph G(V, E) //number of vertices, edges procedure dfs(vertex v): //counts vertices adjacent to vertex 0    if not visited[v]:        do nothing    else:       visited[v] = true       componentSize += 1       for all u adjacent to v:          dfs(u) boolean isConnected(): //checks if graph is connected    for all vertices v:       visited[v] = false    componentSize = 0    dfs(0)    return componentSize == |V| //whether all vertices were reached from vertex 0 int countBridges():    int bridges = 0    for each edge e:       if e is part of a multiple bond, do nothing       else:          remove e          if not isConnected():             bridges += 1    return bridges

 Author: Cyril [ Wed Jan 18, 2012 11:38 pm ] Post subject: Re: Solutions, DWITE 2011-2012 #2-4 If you're more interested in implementation details, I could send you the code I used to verify test cases, but I'm afraid I won't have the time to touch it up.

 Author: d310 [ Thu Jan 19, 2012 8:16 pm ] Post subject: Re: Solutions, DWITE 2011-2012 #2-4 Just a comment for 4.5, the runtime complexity can be O(n*2^(d-1)). You can eliminate half of the possible combinations by making the following observation: The smallest value for -x-y-z is the highest value for x+y+z. Likewise, the highest value for -x-y-z is the lowest value for x+y+z.

 Author: crossley7 [ Thu Jan 19, 2012 8:43 pm ] Post subject: RE:Solutions, DWITE 2011-2012 #2-4 Thanks Cyril, I think I understand the implementation from that. I'm starting CS finally next semester in about 2 weeks and at that time I'm going to be looking at coding the solutions for all of these dwite problems and just wanted to understand how to go about it.

 Author: ihsh [ Thu Jan 19, 2012 10:45 pm ] Post subject: Re: Solutions, DWITE 2011-2012 #2-4 Quote:4.4 Lego Ladder Some of you got the recursive solution; the correct one was very close! Let's represent a state of the game as the subset of blocks left. We define a function f(S), which answers the question "in the state S, does the player to move have the winning strategy?" For some S, we already have a ladder, so f(S) = false. Otherwise, we consider all states reachable from S. If there is some state T reachable from S such that f(T) = false, then f(S) = true; our winning strategy is just to take the move that brings S to T. If there exists no such move, then f(S) = false. To get this brute-force solution to run in time, simply note that there are only 2^n = 15 states. So, once we've computed f(S), we can put it in a lookup table, and we'll be able to access it in constant time. Then, the running time will be something like O(n * 2^n), which will run in time. Could anyone help me with a problem that I have? So I made a program that uses the above algorithm, and it works for all the test cases. However, I have one major problem with representing the states of a game. Right now, for a game that initially has n blocks, I have 2^n states, such that each state has a different combination of legoes in the row. Each state is represented by a decimal integer from 0 to (2^n)-1, so that the binary expansion of the decimal integer represents the combination of the lego blocks in the game (with 0= not present and 1=present) . For example, say there are 4 blocks in a row, state 6 will be: -> 0110 in binary -> the state where only the second and third blocks are left. So I have a function, f(n) that sees whether a player has a winning strategy at state n: 1. Converts n to binary, and checks if it forms a ladder 2. If not, generates a list of binary numbers that have exactly one less '1' than the binary of n 3. Call f(n) for the decimal representation of each of the binary numbers And as you can tell, it's kind of redundant, as I have to constantly convert the numbers from binary to decimal or from decimal to binary. So is there anyway to do this more efficiently? Thanks.

 Author: tedying [ Fri Jan 20, 2012 10:04 pm ] Post subject: Re: Solutions, DWITE 2011-2012 #2-4 Also for #5, depending on the language, you might or might not need to use the quadratic formula and a bunch of if statements. This submission (in Python) works fine in C: http://dwite.org/uploads/7ypdjhf1de1lrnj/2583/187/0/d5.py C version: http://pastebin.com/TL285AK2 I get about a 200x speedup in C (.3 seconds instead of 1 minute). In fact, just starting Python and reading in the test data takes about as much time as calculating the answer in C. \$ time ./d5 #c solution real 0m0.287s user 0m0.282s sys 0m0.003s \$ time python -c '[map(int,x.split())for x in open("DATA5.txt")]' #python input only real 0m0.282s user 0m0.231s sys 0m0.029s Edit: Python: http://pastebin.com/tGLhTBYX C: http://pastebin.com/NXCDN5vA These shrink the time to about 600 ms and 10 ms The solution is similar to Cyril's solution algebraically.

 Author: Cyril [ Fri Jan 20, 2012 11:21 pm ] Post subject: Re: Solutions, DWITE 2011-2012 #2-4 d310 @ Thu Jan 19, 2012 8:16 pm wrote:Just a comment for 4.5, the runtime complexity can be O(n*2^(d-1)). You can eliminate half of the possible combinations by making the following observation: The smallest value for -x-y-z is the highest value for x+y+z. Likewise, the highest value for -x-y-z is the lowest value for x+y+z. I covered this in the last line of my solution. And pshhh, O(n * 2^(d-1)) and O(n * 2^d) are exactly the same thing, hahaha.

 Author: Cyril [ Fri Jan 20, 2012 11:43 pm ] Post subject: Re: Solutions, DWITE 2011-2012 #2-4 ihsh: Nice reasoning. Your strategy of mapping subsets of a set of size N to integers from 0 to 2^N - 1 is a standard technique, and for testing purposes, we used it in exactly the way you described. There is a nice way to do this! Use bitwise operators. x << n: shifts x to the left by n bits (you can think of this as multiplication by 2^n) x >> n: shifts x to the right by n bits (you can think of this as integer division by 2^n) a | b, a & b, a ^ b: takes the or/and/xor of corresponding bits ~x: inverts every bit in x So, if you have such a representation stored in an integer N: N | (1 << r) is 0 if the rth bit of N is 0, and non-zero otherwise. N -= 1 << r removes item r. Or, if you like, N &= ~(1 << r). You can think of ~(1 << r) as a "mask" that takes out the rth bit. (1 << N) - 1 should be your initial state. They are actually more primitive (and faster) than your conventional arithmetic operations. If you use Java, and want to investigate further (in particular, find out how negative numbers are treated), be sure take a look at <<< and >>> as well.

 Author: ihsh [ Sat Jan 21, 2012 11:52 am ] Post subject: Re: Solutions, DWITE 2011-2012 #2-4 Wow thanks! This is going to be very useful for a lot of problems. Also, just wondering, when would one ever need to use negative numbers when using bitwise operators?

 :