nikalosaberidze's blog

Code Jam 1 Round
By nikalosaberidze, 11 years ago, In English

Tomorrow is Code Jam's first round. Code Jam. I hope that will be good problems and two hours and thirty minutes will be enough to solve problems :))) Goodluck everybody :)))

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Is number of the participants too much?

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

What is the solution for C-large?

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

    I wonder what is the probability that the solution is unique?

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

    Apply Bayes' theorem to find vector which maximize posterior probability

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to approach B large.I wasn't getting any intuition from the problem description.Trying out few test cases did gave some pointers but that was not enough to solve it in time.

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

    Suppose we had v1, ..., vn and we were standing at the beginning, that is v1.

    If v2 > v1, then spending more than R in v1 would be wrong right? And at least we should spend R (remember R ≤ E), because we will recover it anyway before getting to v2. This happens because we would rather (greedily) spend energy in v2 than in v1, and spend the "excess" (due to the fact that energy never exceeds E) in v1.

    Now, suppose v2 < v1, but v3 > v1, then again, spending more than 2R = (3 - 1)R would be wrong, so we spend 2R (actually min{2R, remainingenergy}, because we can recover the full E by the time we get to v3) in v1, and move on to v2.

    Try to complete the idea ;P

    → Reply
»
11 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Кто-нибудь знает какие есть хитрые баги в B-large? У меня она упала на контесте, но сейчас тот же самый код зашел в дорешивании. Решение — стандартное жадное.

→ Reply