364 - Constitutional Computing

[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.

[brianfry713]

I agree with your logic and also get WA.

[brianfry713]

Yes the sample output is wrong. This problem does not have a correct dataset.

[Ivor]

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.

[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.

[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.

[brianfry713]

The judge's output is the incorrect sample output. I'll ask again to get it fixed.

[brianfry713]

I created a new dataset for this problem, now try submitting correct code.

[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

[Ivor]

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.

[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.

[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.

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.

[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.

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.

[brianfry713]

Yes, we designed the judge's input so that the equal fractions issue won't occur.