silversRayleigh's blog

By silversRayleigh, history, 4 years ago, In English

I was trying to solve the problem Jail Destruction. I used square root decomposition approach. I divided whole array in sqrt(N) blocks and sorted each block w.r.t height and maintained a counter for each block which contains the value by which whole block has been subtracted. To process query of 2nd type, I iteratively changed the values of start/end blocks and processed them again while increased counter value for intermediate blocks. Similarly for query of first type, I calculated value of start/end blocks and for intermediate blocks used binary search as well as suffix sum.

While submitting the solution I got WA. Can anyone please let me know if there is anything wrong with the idea or help me find bug in my code. I have tried multiple time but to no avail.


Link to Problem : Link to solution :

Full text and comments »

By silversRayleigh, 5 years ago, In English

Hello Everyone. I was trying to solve this problem using Dinic algorithm. Since, I have never used the algorithm before, there are some bugs in my code which I am unable to find. I have spent considerable amount of time trying to debug it. Can anyone please help me in debugging my code?

Link to code :


Full text and comments »

By silversRayleigh, history, 5 years ago, In English

Hello Everyone,

I was trying to solve a problem in which I was given a set of number(in range 1-10^5 and size of set is at max 10^5). Task was to form the two disjoint sets from the given set such that sum of elements of each set is at least X(in range 1-10^5) and sum of size of both sets is minimized.

I tried a lot but could only come up with O(n^2) solution. Can anyone please suggest some idea on how to do it?

Note : Union of disjoint sets need not be the original set.


Full text and comments »

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