Блог пользователя silversRayleigh

Автор silversRayleigh, история, 5 лет назад, По-английски

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.

TIA.

Link to Problem : https://mirror.codeforces.com/gym/102307/problem/J Link to solution : https://mirror.codeforces.com/gym/102307/submission/60750946

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор silversRayleigh, 6 лет назад, По-английски

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 : https://repl.it/@NikhilAgrawal/RoastedAdoredOpposites

TIA!

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор silversRayleigh, история, 6 лет назад, По-английски

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.

TIA

Полный текст и комментарии »

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится