I tried to solve the problem but have not been able to identity how will BIT work here. The problem requires subsequences but as far as i understand BIT handles cases from 0 to some specific n. I tried to convert the problem into this type but have not been able to.
Please do not provide the code, just give me the logic with detailed explanation of how this problem can be solved.
LIS Modified Logic Help
you are write , now think about compressing the values such that order doesnt change
exx , 1 5 10 15
compresses to 1 2 3 4
now use bit or segment
Didn’t quite get what you are saying.
Are you saying that if i have a test case like
arr = 5 3 2 1 4
w = 10 7 8 5 6
Then i should convert the arr to this: 1 2 3 4 5?
Can you please elaborate more with the help of this test case. Also explain how to use BIT Here and how to get sub sequences.
search aabout coordinate compression , after that think about the question
I read about coordinate compression and wrote the code which works for the test cases that i have tried but whn i submit it, it gives wrong answer. Please tell me if i used the correct logic or not.
- First i compressed the arr[i] values.
- Then for every element in arr starting from index i , i update first bit to store maximum value.
- Then i query for the same element, i.e get me the LIS with ending index at i and maximum sum ending index at i.
- i do this for each index and take maximum.
This logic works for given test cases and a few others that i have tried.
The link to code : https://ide.codingblocks.com/s/112261
Please provide a few corner cases where this code fails or provide explanation where i am going wrong. Plz provide test cases.
Thank you.
i am also doing with the same logic,
check the contrainsts and look at the code-
you also have to clear the tee again and again because of the test cases