fcspartakm's blog

By fcspartakm, 6 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +22
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice!

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

    I also solve it with maxflow like an assignment problem. 38199894

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

    What's the time complexity of your solution?

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

      doesn't matter dude! his sol is over-kill for this problem. just assign days greedily. Whichever exam comes first gets preparation day first.

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Very fast! Thank you

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for quick explanation. Is there any solution which works faster than "brute solution" for problem D?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For G you don't need to iterate all the exams every day.

38195700 complexity is O(n*logm) insted of O(n*m)

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

    Excellent thanks for posting

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

    I might be a little late but can you please explain your logic ?

»
6 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

A simple way of understanding 978E - Bus Video System:

Define pre[i]  = 

Let's take an arbitrary variable initial which could hold all possible initial values.

It is easy to see this inequality holds true:

0  ≤  initial + pre[i]  ≤  w,

Which implies:

 - pre[i]  ≤  initial  ≤  w - pre[i]

We can reduce this to:

max(0,  - pre[i])  ≤  initial  ≤  min(w, w - pre[i])

Solving this inequality and finding the range gives us the final answer.

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

For F instead of using vectors with quarrels another nice way is to process the quarrels by incrementing an array containing the "number of quarrels with less skilled programmers". Then we can just directly subtract the number in that array at the end.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution 38178463 to problem 978E - Bus Video System is O(n).

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

My solution 38166452 to problem 978B - File Name was similar to the one in the tutorial, but easiest, it's how many ocurrences have the string "xxx" in the string s.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

fcspartakm I think there was a typo in the tutorial of problem F: "we can user array of pairs" for "we can use array of pairs".

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Regexp solution is very easy to write for B :P

print sum(map(lambda x : len(x) - 3 + 1, re.findall('x{3,}', raw_input())))