Search found 17 matches

by dull_jester
Mon Mar 06, 2017 2:57 pm
Forum: Volume 13 (1300-1399)
Topic: 1300 - Parallel Expectations
Replies: 1
Views: 405

Re: 1300 - Parallel Expectations

Consider this input: d := 45 - 86 e := 22 - 9 j := 92 - f c := 49 - 91 e := 12 - 45 j := 24 + f e := f - 90 f := 44 - 91 END g := 68 + 97 c := 40 + 75 b := 64 + a j := 7 - b i := a + 52 j := 41 + 19 b := 28 - b a := a + b END The first program does not access the variables "a" and "b" at all, so the...
by dull_jester
Sat Feb 25, 2017 10:59 pm
Forum: Volume 118 (11800-11899)
Topic: 11864 - Probability Calculation
Replies: 1
Views: 497

Re: 11864 - Probability Calculation

OK, I've figured out how for a given M to split the sum into two parts. The first part can be cached independent of M (for given p), the other part is dependent on M, and has to be recalculated for every M (again, for given fixed p). I get TLE. Is this the approach you took? Do you answer each query...
by dull_jester
Fri Feb 10, 2017 9:55 pm
Forum: Volume 12 (1200-1299)
Topic: 1251 - Repeated Substitution with Sed
Replies: 1
Views: 780

Re: 1251 - Repeated Substitution with Sed

OK, I do a BFS with bitmasks, each word being encoded with an at most 50-bit unsigned long long... Result: TLE. Question: what else needs to be done apart from BFS?
by dull_jester
Sun Jan 29, 2017 8:13 pm
Forum: Volume 4 (400-499)
Topic: 449 - Majoring in Scales
Replies: 17
Views: 1852

Re: 449 - Majoring in Scales

Ok, we've got tone-tone-semitone-ton-tone-tone-semitone thing. Now, what is, say, "FIFTH UP"? Does it mean, starting from the current "starting" note, keep going to the next note in the scale while also adding +2 to the counter if the transition was "tone". and +1 is the transition was semitone, and...
by dull_jester
Thu Jan 26, 2017 9:10 pm
Forum: Volume 15 (1500-1599)
Topic: 1595 - Symmetry
Replies: 1
Views: 643

Re: 1595 - Symmetry

The judge I/O does not adhere to the problem description: there are duplicate points! I checked this with assert. Once I remove duplicates, my algo got Accepted.
by dull_jester
Wed Jan 18, 2017 5:49 pm
Forum: Volume 2 (200-299)
Topic: 240 - Variable Radix Huffman Encoding
Replies: 6
Views: 5235

Re: 240 - Variable Radix Huffman Encoding

Yes, alexiago is right! Just got Accepted. Although this rule is not written very well in the problem description. Such a pity!
by dull_jester
Wed Jan 18, 2017 1:27 pm
Forum: Volume 2 (200-299)
Topic: 212 - Use of Hospital Facilities
Replies: 6
Views: 3105

Re: 212 - Use of Hospital Facilities

Are there multiple runs? So, what is the input format? What is the exact format if numPatients = 100? 100 won't fit into two columns, but two columns for patient ID number is what is shown in sample I/O.
by dull_jester
Wed Jan 18, 2017 3:04 am
Forum: Volume 2 (200-299)
Topic: 212 - Use of Hospital Facilities
Replies: 6
Views: 3105

Re: 212 - Use of Hospital Facilities

If two patients emerge from surgery at the same time, the patient with the lower number will be the first assigned to a recovery room bed. (If in addition the two patients entered surgery at the same time, the one first on the roster is first assigned a bed.) Here, "lower number" means lower number...
by dull_jester
Tue Jan 17, 2017 3:05 pm
Forum: Volume 8 (800-899)
Topic: 822 - Queue and A
Replies: 4
Views: 2871

Re: 822 - Queue and A

I believe judge's input is incomplete. I got Accepted, but my output differs from the above in 23 cases from the 100.
by dull_jester
Tue Jan 17, 2017 1:54 am
Forum: Volume 8 (800-899)
Topic: 822 - Queue and A
Replies: 4
Views: 2871

Re: 822 - Queue and A

Out of 100 Brian's cases, my code produces 77 correctly. My algo is as follows. For the second test case, for instance, my code produces 13902, three minutes short of the correct answer. How the staff members get assigned to jobs? I do it in rounds. First, each staff members selects herself a reques...
by dull_jester
Tue Nov 22, 2016 2:04 am
Forum: Volume 17 (1700-1799)
Topic: 1720 - Weather Report
Replies: 1
Views: 992

Re: 1720 - Weather Report

Huffman encoding for the first sample input is (code and probabilities)

Code: Select all

00 --> 0.05
010 --> 1.0E-6
011 --> 0.049999
1 --> 0.9
However, this does not even match the sample output. What's wrong with using Huffman here?
by dull_jester
Wed Nov 16, 2016 2:56 am
Forum: Volume 107 (10700-10799)
Topic: 10743 - Blocks on Blocks
Replies: 20
Views: 10397

Re: 10743 - Blocks on Blocks

Ok, from Cho's hints I've been able to go as far as this:

a_n = \sum_{k=1}^{n}b_{n,k},
b_{n,k} = \sum_{t=1}^{n-k}(t+k-1)b_{n-k,t}

I can take this one step further, but how to get to the formula a_n = ?a_{n-1} + ?a_{n-2} + ?a_{n-3}?
Cho's derivation is no longer accessible.
by dull_jester
Sun Nov 13, 2016 10:10 pm
Forum: Volume 14 (1400-1499)
Topic: 1459 - Flowers Placement
Replies: 1
Views: 1178

Re: 1459 - Flowers Placement

Short of using permanent of a matrix, how to solve this?...
by dull_jester
Sun Nov 13, 2016 1:41 pm
Forum: Volume 111 (11100-11199)
Topic: 11119 - Chemical Attraction
Replies: 19
Views: 6894

Re: 11119 - Chemical Attraction

I am also checking the stability, as well as that all the pairs are present. However, WA. any ideas why? /* * 11119. chemical Attraction * TOPIC: bipartite matching, stable matching * status: */ #include <cassert> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <...
by dull_jester
Wed Nov 09, 2016 7:40 pm
Forum: Volume 11 (1100-1199)
Topic: 1161 - Objective: Berlin
Replies: 2
Views: 1279

Re: 1161 - Objective: Berlin

Cities are vertices, flights are edges with capacities. Perfect. But how to deal with the time parameter? The easiest way is that we redefine a vertex as a (city,timestamp) pair, but that would lead to the explosion in the number of vertices.

Go to advanced search