simp1eton's blog

By simp1eton, 14 years ago, In English
Hi all,

I refer you to the following problem.

http://www.codeforces.com/contest/10/problem/E

I tried reading the codes of people who solved the problem, but the codes are pretty cryptic to me. Can someone please enlighten me? Thanks :)
  • Vote: I like it
  • 0
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It's based on a theorem from this paper
14 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
Wow thanks! I will read this paper carefully.

But is there another way to solve this problem without prior knowledge? It gets a bit daunting if the only way to solve problems is to know some obscure formula beforehand :S

Or maybe, is there an intuitive way from which one can derive the algorithm?

Thanks in advance!
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I don't know… During the contest I came to some conclusions similar to the proof in the paper, so in principle it's possible to obtain it independently. It's only 1 page long, after all.
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Would it be possible for you to share how you came up with the algorithm? Your thought processes etc? Thanks! =D
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I haven't found the algorithm, just some observations and I don't even remember them :)