Forcharc's blog

By Forcharc, history, 21 month(s) ago, translation, In English,
 
 
 
 
  • Vote: I like it  
  • +15
  • Vote: I do not like it  

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

the content isn't working now: while opening file this message is found "the archive is either in unknown format or damaged"

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Very strange. Anybody has a similar problem?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I had that problem too. But when I opened that file with 7zip, it has been opened normally.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

reoutloaded

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know how to solve 3rd problem (C problem) in better complexity than O(N*sqrt(N))?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Consider a set of points (l, r) on plane such that 0 ≤ l ≤ r ≤ n - 1 where the point (l, r) corresponds to a segment [l, r].

    Consider some number x and all its occurrences. Suppose that the number x is one of the numbers that make some particular segment [l, r] be bad. Then one of the following situations should happen: either there are from 1 to x - 1 or more than x + 1 occurrences of x in [l, r]. That means that for the fixed l there are two segments of banned values for r. Actually, for any possible l lying between two consectuvie x's, those two banned segments for r will be the same. It can be reformulated that there are O(cx) banned rectangles on a plane that point (l, r) isn't allowed to be in, where cx is the number of occurrences of x.

    Construct all such rectangles for all numbers x, there will be O(n) of them in total, and then calculate the number of points that do not lie in any banned rectangle in via sweeping line.

    Although this solution has better time complexity, there are solutions that work even faster because they do not utilize much memory and use only simple operations.

    Code for reference:

    solution by me: http://pastebin.com/k0GHWxuQ

    solution by Errichto: http://pastebin.com/UXziv4iD

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the solution of problem A Day1?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The download link doesn't work for me, can you share the problem statements somewhere else?

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's in Russian anyway

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh ok. I thought it was in english since the discussion was in english.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Problem A

      GL & HF :)