hot3eed's blog

Where does this formula in problem 486A come from?
By hot3eed, history, 7 years ago, In English

The formula I'm asking about in problem 486A is the one in most C++ answers which is: n/2-n*(n%2), now where does this formula come from? Also, I found this solution in which the author says that he looked for a pattern (tldr; if the number is even then n/2 or else if it's odd then -1 * ((n+1)/2)) until he found one which actually works, is there any explanation for this pattern? Also, is this kind of patterns a matter of trial and error or is there a way to identify them?

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

»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

You can pair every two consecutive numbers because their sum is always 1. The number of this pairs is exactly n / 2 (integer division). If n is odd, the last number doesn't have pair. Because the sequence starts with negative value, this number will be negative as well. So last number of sequence is n and in case n is odd (n doesn't have pair), you must subtract it from n / 2.

I hope you understand now.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Oh it makes sense now, thanks a lot! Now, sorry if this sounds like a stupid question --just getting started in competitive programming here-- but what should I start reading to get acquainted with these kinds of stuff? I mean, where did all those people come up with that clever formula n/2-n*(n%2), or is it just a know practice?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      You don't have to write solution like this. Same can be achieved with longer code. For example I solved it using 2 ifs. The hardest part is to come up with efficient algorithm. Then you must implement it with help of data structures and algorithms in books. I recommend you to google about best books. My favorite is Competitive programming 3 (Steven Halim). You can also watch tutorials on Youtube. But most important is PRACTICE (solve a lot of problems).

      → Reply