puf's blog

By puf, history, 5 years ago, In English

We are given a weighted graph with $$$N$$$ vetices and $$$M$$$ edges.

Is there any polynomial way to build spanning tree from original graph so that Mex of values on edges of ST is maximal?

Full text and comments »

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

By puf, history, 7 years ago, translation, In English

We have array of zeros of length N. There are 3 types of queries in the problem:

  1. Add 1 to all nums with indexes in range [l, r].
  2. Subtract 1 from all nums with indexes in range [l, r].
  3. Print count of zeros in [l, r].

In each step there are no negative numbers.

I am solving it so: Make sqrt-decomposition, for each block store deque, where d[i] is count of i in the block. When we need to add 1 to all nums in the block, just push_front(0), it'll shift all the values by 1. Similarly pop_front(), when we subtracting 1 from all nums in the block. If block isn't fully in the range manually change counts. For 3rd query type summarise d[0] for blocks inside the range, for first&last blocks run cycle and count zeros. Complexity O(N√N)

Is this solution correct? Are there solutions faster?

Full text and comments »

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