StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>As far as I can tell, the code at the link that you provided is not the best solution, nor even a working solution. The code which you copied from that link seems to make sense, but previous to the copied code, when the values are read into <code>A</code>, they are XORed by the value read in before them:</p> <pre><code>for (int i = 1; i <= N; i++) { scanf("%d", &A[i]); A[i] ^= A[i - 1]; } </code></pre> <p>...meaning the following input:</p> <pre><code>1 4 1 2 3 4 </code></pre> <p>...gets stored into <code>A</code> like so:</p> <pre><code>A[0]: 00000000000000000000000000000000 = 0 A[1]: 00000000000000000000000000000001 = 1 A[2]: 00000000000000000000000000000011 = 3 A[3]: 00000000000000000000000000000000 = 0 A[4]: 00000000000000000000000000000100 = 4 </code></pre> <p>For the previous input, the correct answer should be:</p> <pre><code>F(1, 1) + F(1, 2) + F(2, 2) + F(1, 3) + F(2, 3) + F(3, 3) + F(1, 4) + F(2, 4) + F(3, 4) + F(4, 4) = 1 + 3 + 2 + 2 + 1 + 3 + 5 + 6 + 7 + 4 = 34 </code></pre> <p>...but here's what we get using the algorithm you posted as the "best one" (sum of <code>c</code> * (<code>N</code> - <code>c</code> + 1) * 2 ^ <code>i</code> from <code>i</code> = 0 to <code>i</code> = 29)</p> <pre><code>2 * (4 - 2 + 1) * 1 + 1 * (4 - 1 + 1) * 2 + 1 * (4 - 1 + 1) * 4 = 6 + 8 + 16 = 30 </code></pre> <p>So it's off by four, and therefore isn't a working solution to the problem, let alone the best working solution.</p> <p>Note that if the values <strong>hadn't</strong> been XORed when they were read in, here's what would be in <code>A</code>:</p> <pre><code>A[0]: 00000000000000000000000000000000 = 0 A[1]: 00000000000000000000000000000001 = 1 A[2]: 00000000000000000000000000000010 = 2 A[3]: 00000000000000000000000000000011 = 3 A[4]: 00000000000000000000000000000100 = 4 </code></pre> <p>So then the formula sum of <code>c</code> * (<code>N</code> - <code>c</code> + 1) * 2 ^ <code>i</code> from <code>i</code> = 0 to <code>i</code> = 29 would give:</p> <pre><code>2 * (4 - 2 + 1) * 1 + 2 * (4 - 2 + 1) * 2 + 1 * (4 - 1 + 1) * 4 = 6 + 12 + 16 = 34 </code></pre> <p>...which is the correct answer, according to the problem statement on the website you linked. I think this is why we've seen answers so far that agree with the code you posted - the code you posted makes sense, even if the preceding code (found at the page to which you linked) makes the entire program erroneous.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload