margaery's blog

Difficult icpc problem
By margaery, history, 8 years ago, In English

hey, can someone please help me with this problem? https://icpcarchive.ecs.baylor.edu/external/74/7401.pdf https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=691&page=show_problem&problem=5423

You are given an infinite binary indexed tree, where each node's value is its index. You're also given two integers, N and K. you're supposed to print a walk on this tree, where each node you visit, you either add or subtract it to your sum. The length of the walk must be K and the final sum must be N.

thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 6   Vote: I like it +9 Vote: I do not like it

If N is not even you can always go to the left son. These nodes are exponents of 2. Consider N in base 2 and a bit i, which is not the MSB. If the bit

Unable to parse markup [type=CF_TEX]

is set then consider i as an addition to the sum. Otherwise, we still want to add 2i to the sum, but we also want to cancel all the bits i + 1, i + 2, .. j - 1, considering j as the smallest index that is greater than i and it is of a set bit. To do so, we notice that

Unable to parse markup [type=CF_TEX]

. Obviously, we now can write down the signs for the (i + 1, j — 1) substring. Every position which shares the same parity with

Unable to parse markup [type=CF_TEX]

will be added the sum and the others will be subtracted. Doing this, we have used the nodes

Unable to parse markup [type=CF_TEX]

and we have the sum

Unable to parse markup [type=CF_TEX]

, from which we subtract 2i, obtaining 2i just what we wanted in the first place. We are allowed to follow this path because it is known that

Unable to parse markup [type=CF_TEX]

.

If N is even, find the solution for N - 1. At the end, instead of going from the node

Unable to parse markup [type=CF_TEX]

to the last node on the left, choose the right node instead, which is

Unable to parse markup [type=CF_TEX]

.

For example, 9 in base 2 is

Unable to parse markup [type=CF_TEX]

, so we take  - 1 +

Unable to parse markup [type=CF_TEX]

+ 4 + 8. For 10 we will simply modify the former solution, taking

Unable to parse markup [type=CF_TEX]

instead of

Unable to parse markup [type=CF_TEX]

.
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you so much for your awsome explanation! lots of love to Bucharest :)

    → Reply