Page 1 of 1
364 - Constitutional Computing
Posted: Tue Jun 05, 2012 12:57 pm
by stubbscroll
I'm stumped on the sample input on this problem. The output of the first test case doesn't make sense to me.
For the first case, I get the following numbers of representatives (basically taken from the problem statement):
Code: Select all
State H J A W
----- -- -- -- --
Anxit 2 2 2 2
Bored 8 9 8 8
Confu 11 11 10 11
Dismy 6 5 6 6
Ecsta 3 3 4 3
With these numbers, the output should be like this according to my understanding:
Code: Select all
Data set 1:
For 30 representatives:
Anxit is favored by no method.
Bored is favored by Jefferson.
Confu is favored by Hamilton and Jefferson and Webster.
Dismy is favored by Hamilton and Adams and Webster.
Ecsta is favored by Adams.
The sample output and my output differ in the two last lines.
I have some questions to the four people who got accepted: What is the trick to this problem? What is your answer to this test case? Does this problem even have a correct dataset?
I submitted a program which seems to be correct according to my interpretation (which fails the sample) but it gets Wrong Answer.
Re: 364 - Constitutional Computing
Posted: Wed Jun 06, 2012 1:42 am
by brianfry713
I agree with your logic and also get WA.
Re: 364 - Constitutional Computing
Posted: Thu Jun 07, 2012 1:48 am
by brianfry713
Yes the sample output is wrong. This problem does not have a correct dataset.
Re: 364 - Constitutional Computing
Posted: Fri Dec 21, 2012 2:58 pm
by Ivor
brianfry713 wrote:Yes the sample output is wrong. This problem does not have a correct dataset.
Can you elaborate on how you got it accepted? What should be interpreted differently to what is stated in the problem description?
I.
Re: 364 - Constitutional Computing
Posted: Fri Dec 21, 2012 9:07 pm
by brianfry713
In order to get AC your code needs to match the sample I/O, which is wrong. I don't know the incorrect logic used. Krzysztof Stencel, Ruben Spaans, and I collaborated on a new dataset and fixes to the problem description, then emailed it to the admin six months ago, but it hasn't been updated.
Re: 364 - Constitutional Computing
Posted: Fri Dec 21, 2012 9:43 pm
by Ivor
You mean match for that particular case only? And I agree, I can't figure out the logic behind that output. As far as I can see it, that output seems kind of an impossibility. Anyway, hopefully the test set will get switched and problem rejudged. I don't know how long it even takes Carlos (is he still the one managing it?) to get around to it. Would 6 months be enough to warrant an inquiry?
I.
Re: 364 - Constitutional Computing
Posted: Sat Dec 29, 2012 11:06 pm
by brianfry713
The judge's output is the incorrect sample output. I'll ask again to get it fixed.
Re: 364 - Constitutional Computing
Posted: Fri Feb 22, 2013 9:24 pm
by brianfry713
I created a new dataset for this problem, now try submitting correct code.
Re: 364 - Constitutional Computing
Posted: Mon Feb 25, 2013 10:05 pm
by brianfry713
For this input:
Code: Select all
8
Calif 727
Nevad 291
Orego 758
Washi 633
Arizo 125
Monta 62
Color 507
Idaho 192
49
0
0
The correct output is:
Code: Select all
Data set 1:
For 49 representatives:
Calif is favored by no method.
Nevad is favored by Adams.
Orego is favored by no method.
Washi is favored by Jefferson.
Arizo is favored by Hamilton and Adams and Webster.
Monta is favored by no method.
Color is favored by Hamilton and Jefferson and Webster.
Idaho is favored by no method.
The total is 3,295 so for 49 representatives, we divide by 67.24 for the true apportionment of representatives. In the Hamilton method, the left overs go to Arizo, Idaho, Calif, and Color. I divide by 63.20 for the Jefferson method. I divide by 72.60 for the Adams method. I divide by 67.50 for the Webster method.
Code: Select all
State Population True Hamilton Jefferson Adams Webster
Calif 727 10.81 11 11.50 11 10.01 11 10.77 11
Nevad 291 4.33 4 4.60 4 4.01 5 4.31 4
Orego 758 11.27 11 11.99 11 10.44 11 11.23 11
Washi 633 9.41 9 10.02 10 8.72 9 9.38 9
Arizo 125 1.86 2 1.98 1 1.72 2 1.85 2
Monta 62 0.92 1 0.98 1 0.85 1 0.92 1
Color 507 7.54 8 8.02 8 6.98 7 7.51 8
Idaho 192 2.86 3 3.04 3 2.64 3 2.84 3
Re: 364 - Constitutional Computing
Posted: Mon Aug 26, 2013 2:58 pm
by Ivor
brianfry713 wrote:The total is 3,295 so for 49 representatives, we divide by 67.24 for the true apportionment of representatives. In the Hamilton method, the left overs go to Arizo, Idaho, Calif, and Color. I divide by 63.20 for the Jefferson method. I divide by 72.60 for the Adams method. I divide by 67.50 for the Webster method.
Finally got back to this task. Can you tell me whether it's actually important to use floats as you've outlined in this example? I've done all my calculations with integers and I'm not sure if there could be a difference.
What I'm doing is this (rep - number of representatives, pop - population, rep_size - what I'm dividing by, frac - fractional part for Hamilton method)
Hamilton: rep
= pop * 1000 / rep_size; frac = (pop * 1000) % rep_size; Set pop to 1 and frac to 0 if pop = 0. Then use fractions in descending order, for non-zero fractions to add 1 to rep.
Jefferson: rep = pop * 1000 / rep_size; Set pop[i] to 1 if pop[i] = 0.
Adams: rep[i] = (pop[i] * 1000 - 1) / rep_size + 1
Webster: rep[i] = pop[i] * 1000 / rep_size; add +1 if (((pop[i] * 1000) % rep_size) * 2 >= rep-size). Set pop[i] to 1 if pop[i] = 0.
Anything I might be missing when searching for the suitable rep_size value for each method?
I.
Re: 364 - Constitutional Computing
Posted: Tue Aug 27, 2013 1:43 am
by brianfry713
I've solved this using floating points to calculate divisors for Jefferson, Adams, and Webster and also without using floating point at all and both methods match the judge's I/O (which I created with help from Krzysztof Stencel and Ruben Spaans).
You can send me or post your code if you're having trouble. Maybe there is an issue with the way you compute Hamilton. I use:
rep = pop * 1000 * number of representatives / total population
if(rep == 0) then rep = 1 and frac = -1
if(rep != 0) then frac = (pop * 1000 * number of representatives) % total population
Then use fractions in descending order to add 1 to rep until all extra representatives are distributed.
Re: 364 - Constitutional Computing
Posted: Tue Aug 27, 2013 10:43 am
by Ivor
Tried it your way for Hamilton, even used long longs. Still doesn't work. I'll try to find the mistakes without sending the code for the moment, though. If I'll be ready to give up on it, then.
brianfry713 wrote:Then use fractions in descending order to add 1 to rep until all extra representatives are distributed.
Do you sort the fractions in descending order? What if you have exactly 1 extra representative and two equal fractions? I start looking in the order of states and the first largest fraction is used. If there is another one that is equal to it, it gets used the next time if there are still extra representatives. Could this approach be wrong?
And regarding output. When choosing which methods a state is favored by, should only the method with smallest number of representatives be omitted, or all that are not the largest?
I.
Re: 364 - Constitutional Computing
Posted: Tue Aug 27, 2013 11:15 am
by Ivor
Never mind. Found my mistake in the output section. Both, your and my version, for Hamilton is OK. Equal fractions issue doesn't seem to occur. Just for the info I'll underline the correct answer for my question.
Ivor wrote:And regarding output. When choosing which methods a state is favored by, should only the method with smallest number of representatives be omitted, or all that are not the largest?
I.
Re: 364 - Constitutional Computing
Posted: Tue Aug 27, 2013 10:55 pm
by brianfry713
Yes, we designed the judge's input so that the equal fractions issue won't occur.