I was trying a problem on LCS topic and was stuck. It will be really helpful if anyone can provide me a hint to the problem.
Problem :-ADASEED
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | adamant | 155 |
4 | cry | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
I was trying a problem on LCS topic and was stuck. It will be really helpful if anyone can provide me a hint to the problem.
Problem :-ADASEED
Name |
---|
Auto comment: topic has been updated by humblefoolboi (previous revision, new revision, compare).
Hello Chauhan saab
$$$ \frac{N}{L} \le 100$$$ suggests that we can try out the pairing of same colors as they are fewer.
One solution would be to first make all pairs of same color (with pair I mean we want them at same position in our last sequence). If we want $$$x$$$ and $$$y$$$ to be at same position, then $$$\forall\ i$$$ where $$$ min (x, y) \le i\ \le max (x, y)$$$, $$$A_{i}$$$ and $$$B_{i}$$$ must be choped (supposing A and B the given two array). This would mean after forming all pair we should select some such that they don't overlap (while of course maximizing length) but probably it will TLE if we select literally all pairs.
For any index $$$i$$$ if we try finding other index $$$j$$$ from other array such that $$$i \le j$$$, I don't think it makes sense to try more than one as the smallest such $$$j$$$ should be better than rest surely so therefore we don't take all the pairs one for each (as a starting) from both arrays this might make it in time but not sure enough.
Just realized second part is pure crap. I does make sense to try more than one.