I know it would be an overkill, but I was wondering if this problem could be solved using Segment Tree and Lazy Propagation ? I haven’t coded it yet, I just want to know if its a valid approach or not ?
1 Like
By sqrt decomposition ,how to handle updates for calculating x in similarity = similarity - x + y where x is the similarity of l to r range
@taran_1407 could you plz tell the fault in my logic?
or , can anyone plz tell why i am getting TLE ???
I’m using segment tree with lazy updates and Binary Search to look for similarities !!
Thanks in advance !!
I’m having some trouble in calculating x. I can’t seem to understand how to calculate the value of x in less than O(N).
Link to my code:
[1]
*I have commented the portion (in the main function) where I'm having a problem with **"TODO: "***
Can someone please help me out with this?
Thank you.
[1]: https://ide.codingblocks.com/#/s/29672I too have used segment tree with lazy propagation and binary search(in a sorted array of pairs of (B[i],i)) for similarity.
The complexity is O(N(log N)^2).
Algorithm:
Maintain Segment Tree for similarity.
In each query:
- Propagate changes in the path from
root to L and root to R away from
root.O((log N)^2) - Calculate similarity in the sections between L and R. O((log N)^2)
- Propagate changes that we just made towards root. O((log N))
My code passes all given tests except one. I have used random tests but could not find any test in which it fails.
Could someone find the bug in code or flaw in the algorithm or a test in which it fails.
Link to Code
Thanks
1 Like
why is tester’s solution getting runtime error??
The above solution have same code. but Their submission time is different. Until Yesterday the solution which was giving 100 pts is now Showing Runtime Error for one subtask.
@admin @taran_1407 @teja349. Please look into this matter.
Same Code gives two different out comes how???
Testers Solution it gives Runtime Error
Setters Solution it gives TLE
Can this problem be done in O(N^2) time?
Can you explain your approach a bit more?
Yes, there were many square root dec submissions which passed.
I have used Segment tree and Lazy Propagation approach but I am getting TLE. Can u please tell me what improvement can be done as it is also having same time complexity. I think clearing the map everytime is resulting in TLE, How can I improve that?
say we have similarity for a block calculated (for initial position, we can manually calculate).
After update, two border blocks can be updated naively and middle blocks all will have same value, so, we can calculate for each block range using binary search or Merge sort tree as explained above.
actually i am asking do we have to store array A in (range,value) manner always or we can handle updates in any other way …(thanx …)
We use coordinate compression on array B.
@siddhant22 bro i am also facing same problem with similar kind of logic… in one case getting Runtime error… ur issue resolved?
As i know, admin is looking into this matter as this was already reported.
@huzaifa242 bro same problem i am facing…same solution submitted in giving diff time giving differt output behaviour with runtime errro… different different attemp with exact same line of code giving different output
Not Yet… Got a very different result after resubmission(CodeChef: Practical coding for everyone) with minor changes. The one test that was not passed earlier is passed now but other cases now have Wrong answer. So, it seems like my code has some undefined behaviour(maybe something like segmentation fault that is not detected).
Also, another resubmission(CodeChef: Practical coding for everyone) with additional conditions 'and’ed in assert converts the SIGABRT in my original submission to a WA which is also weird.