[gcj] Re: Distributed CodeJam: Scala please?
I think it's a bit more complicated than that (sandboxing changes, UI changes, writing sample solutions, testing - just to name a few). This isn't to say we don't want Scala. I do. I want Scala, and Haskell, and Go, and C#, and a lot of other things, too. But for now, let's think of this as a Beta. I want to expose this to you all, see what you think about the format, what can be improved, and do better next year. And if there's enough of you crying for Scala, we'll work on it :) -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/252e468e-391e-4c9a-82ba-54fd524b6447%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[gcj] Bug in Java PutChar/GetChar in DCJ test runner
I've been trying out the Distributed Code Jam testing tool, and I noticed an apparent bug when running Java code due to the use of the char type in the API. This program sends the char with value 255 from node 0 to node 1, but node 1 receives the char value 65535: class Main { public static void main(String[] args) { if (message.MyNodeId() == 0) { char outC = 255; System.out.printf(Sending %d%n, (int)outC); message.PutChar(1, outC); message.Send(1); } else if (message.MyNodeId() == 1) { message.Receive(0); char inC = message.GetChar(0); System.out.printf(Received %d%n, (int)inC); } } } Here's what it prints: $ dcj test --source Main.java --library dummy_library.java --nodes 2 ... STDOUT 0: Sending 255 STDOUT 1: Received 65535 Duration: 87ms (longest running instance: 1) The trouble happens because char in Java is a 16-bit unsigned type, but it's being sent as a signed 8-bit signed value (-1 in this case). When it gets turned back into a char, sign extension fills in the higher-order bits as 1s, so the value received is different from the value sent (even though the value sent was in the range 0 to 255). To avoid this, you could mask off the lower-order bits (e.g. value 0xff) so that received characters are always in the 0-255 range. Alternatively, since the intention of PutChar/GetChar is to send a single byte, it seems like the Java message class should really be using the byte type instead of the char type for GetChar and PutChar. -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/cdf3ec8e-0fe4-438e-8b5f-bc39be761dc7%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[gcj] Re: Distributed CodeJam: Scala please?
That sounds fair! And if there's enough of you crying for Scala, we'll work on it :) How do you measure the crying level? If it's the volume of tears (you tyrant!) I kid I kid =). -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/c3a3a127-5c84-4c53-a091-c7f4c488465e%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[gcj] DCJ: total sent size limit
Hi! I am tried to run simple program exchanges 10K messages between nodes and run ended with `Error of instance 0: total sent message size limit (8388608 bytes) exceeded` Does it mean that we will have this 8Mb limit per node along with to 1000 messages and 10Kb per message (10Kb * 1000 ~= 10Mb)? Thank you! Mikhail -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/89b82b55-2dcb-4ae5-9040-d06659e61db6%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[gcj] Messages in Polish in parunner.exe
Hi, Is it intended behavior that parunner.exe at some point prints messages in Polish? I am trying to use -trace_comm=true to see things like: czekam na wiadomość od instancji. It is similar enough to Russian for me to have any problems, but might be different for other contestants. -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/40ae2e46-4378-4773-98ea-b1acac504c9f%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[gcj] An approach to round 2 problem D - without using dynamic programming at all
Hi all, I suggest another approach for solving problem D of round 2. My approach does not need any dynamic programming, but I do use combinatorial methods instead. And also I do still need to enumerate in order to find solutions to some linear equation. Unfortunately for me, I thought about it only after the round ended, so I did not pass, but I did check this solution afterwards. I have the same analysis as the GCJ analysis, up to the point of Now we can use dynamic programming to assign…. Specifically we note that there are 5 types of rows: Type O: 3... 3... Type I. 2... Type II. 122... 122... Type III. 222112... 11... Type IV. 2212... 1212... 1222... As noted in the analysis, type O alternates with types I, II, III, IV. Types II, III, IV are valid only if C is divisible by 3, 6, 4 respectively. After type I come two rows of 3, so this occupies 3 rows. In the same way Type II occupies 4 rows, etc. We should only note that at the bottom/top there might be 2 consecutive rows of 3, or not. Therefore, we can find quickly the possibilities of HOW MANY appearances we have of each of the types I, II, III, IV. It is easy to verify if a count is valid by a simple linear equation (to which I found all solutions by simple enumeration). After we have a possibility of the count of each types, we then have to ORDER the types – which is above which. This can be quickly computed by the multinomial: Multinomial(x+y+z+w, (x, y, z, w)) = (x+y+z+w)! / (x!)*(y!)*(z!)*(w!) Finally, for each such solution we have to multiply it by the number of possible PHASES between the rows. Suppose we have only rows of type I (and obviously type O) - then all phases look the same. Suppose we have only rows of type II (and obviously type O, and maybe even I) - then the number of different phases for type II rows are 3**(n-1) (** is exponent, n is the number of rows of type II). Suppose we have only rows of type III (and obviously type O, and maybe even I) - then the number of different phases for type III rows are 6**(m-1) (** is exponent, m is the number of rows of type III). Suppose we have rows of types II and III (but not IV) – then the number of different phases will be 3**(n-1) for type II, and 6**(m-1) for type III but we also have to multiply it by 3 for the phase between the two types. So we get as the number of possible phases 3 * 3**(n-1) * 6**(m-1) Etc etc…. The code actually does not seem to be complicated, and it can be described more shortly then the explanation above. I attach my python code which seems to work. The only difference is that I numbered types II, III, IV differently than the GCJ analysis, so the numbering of the variables t2, t3, t4 is not consistent with the order of the types as described above. All counts are computed modulo 17 as requested in the problem. @memoize_it def factorial (n): s = 1 for i in range(1,n+1): s *= i return s @memoize_it def multinomial (*args): s = 1 for i in args: s *= factorial(i) return factorial (sum(args)) // s MODULO = 17 def compute_result (R, C): cnt = 0 range_t1 = list(range(35)) if C % 6 == 0: range_t2 = list(range(35)) else: range_t2 = [0] if C % 4 == 0: range_t3 = list(range(35)) else: range_t3 = [0] if C % 3 == 0: range_t4 = list(range(35)) else: range_t4 = [0] for t1 in range_t1: for t2 in range_t2: for t3 in range_t3: for t4 in range_t4: # The case of rows of 3 at the top, no 3's at the bottom if 4 * t4 + 5 * t3 + 4 * t2 + 3 * t1 == R: cnt += calc2 (t1, t2, t3, t4) # The case of rows of 3 at the bottom, no 3's at the top if 4 * t4 + 5 * t3 + 4 * t2 + 3 * t1 == R: # I know it's twice of the same above cnt += calc2 (t1, t2, t3, t4) # The case of rows of 3 at the top and at the bottom if 4 * t4 + 5 * t3 + 4 * t2 + 3 * t1 == R-2: cnt += calc2 (t1, t2, t3, t4) # The case of no 3's at the bottom row, neither at the top row if 4 * t4 + 5 * t3 + 4 * t2 + 3 * t1 == R+2: cnt += calc2 (t1, t2, t3, t4) return cnt % MODULO def calc2 (t1, t2, t3, t4): res = multinomial (t1, t2, t3, t4) res %= MODULO if t2: res *= pow(6, t2-1, MODULO) res %= MODULO if t3: res *= pow(4, t3-1, MODULO) res %= MODULO if t4: res *= pow(3, t4-1, MODULO) res %= MODULO if t2 and t4: res *= 3 if t2 and t3: res *= 2 return res % MODULO -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send
[gcj] Testing round for Distributed GCJ
I believe at some point somewhere in Google Code Jam distributed guide there was a notification about Testing contest to be run for 48 hours somewhere around now. Was this idea dropped? I don't see anything mentioning it now. -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/c52881ba-9036-4e76-8e2b-13a26f5071f4%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[gcj] a Linear Programming approach to problem B of round 2
During round 2 I recognized that problem B can be described as a Linear Programming problem. There are two restrictions: R_1 * t_1 + ... + R_n * t_n = V C_1 * R_1 * t_1 + ... + C_n * R_n * t_n = V * X t_1, ..., t_n are all non-negative Finally the objective is: Minimize (max{t_1, ..., t_n} ) That's quite a regular LP problem. I know that obviously coding a solution to LP is much harder than the simple analysis of this specific problem. Nevertheless, I was wondering – did anyone tried to solve it this way? I know that LP might need more time to solve. Is it doable in the GCJ time constraints (i.e., does it take less than 8 minutes to get the full output?) Does anyone know? -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/e782962e-7d0e-4fb0-b46d-d39f850e346b%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[gcj] Re: Testing round for Distributed GCJ
вторник, 9 июня 2015 г., 15:19:49 UTC-5 пользователь Stanislav Zholnin написал: I believe at some point somewhere in Google Code Jam distributed guide there was a notification about Testing contest to be run for 48 hours somewhere around now. Was this idea dropped? I don't see anything mentioning it now. I see it now on the timer - Distributed Practice Round. Is it 48 hours as was described? -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/57351df1-7bf4-4825-8e7f-5be1fa110a16%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] a Linear Programming approach to problem B of round 2
Yes - see for example linguo's solution. He solved bilingual as an integer linear programming problem too. Edward On 9 Jun 2015, at 21:09, bigOnion haibren...@gmail.com wrote: During round 2 I recognized that problem B can be described as a Linear Programming problem. There are two restrictions: R_1 * t_1 + ... + R_n * t_n = V C_1 * R_1 * t_1 + ... + C_n * R_n * t_n = V * X t_1, ..., t_n are all non-negative Finally the objective is: Minimize (max{t_1, ..., t_n} ) That's quite a regular LP problem. I know that obviously coding a solution to LP is much harder than the simple analysis of this specific problem. Nevertheless, I was wondering – did anyone tried to solve it this way? I know that LP might need more time to solve. Is it doable in the GCJ time constraints (i.e., does it take less than 8 minutes to get the full output?) Does anyone know? -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/e782962e-7d0e-4fb0-b46d-d39f850e346b%40googlegroups.com. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups Google Code Jam group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CD8F176F-A884-4F52-8CD6-30C1E8BE60D1%40gmail.com. For more options, visit https://groups.google.com/d/optout.