BEAUSUB - Editorial

I am kind of a newbie to this field. Can you please tell or share the chart, if there is any, how it is decided that how many test cases should take how much time?
When it would give TLE and when it wouldn’t.
Thankyou.

10^7 operations can be executed in 1 sec. More than this will give TLE.
but here 10^8 is accepted because of weak test cases.

Why codechef editorials are harder than its problem statements itself?

7 Likes

can anyone share from brute - > memoization - > iterative in this way @cubefreak777

4 Likes

When will the video editorial of this problem be available?

Can anyone explain me slow solution here, I am unable to understand it

I made arrays global and it got accepted ,i don’t understand why it happens only on codechef ,that you think you did something wrong and waste time on it but at the end you realize it was not wrong.

1 Like

my O(NK) solution giving TLE
https://www.codechef.com/viewsolution/49213233

Has anyone solved it using memoization ? if yes, then can you please share your approach/solution ?

1 Like

I too was thinking of some O(N) approach initially.

Solution: 49179372 | CodeChef (basic idea)

Solution: 49191250 | CodeChef(with some changes)

Can anyone tell what is wrong in the approach ? I am following notion of standard LIS not exactly but kind of… I am maintaining length[] array for length of subsequence and distinct[] array for number of different adjacent elements…

Why do we need pref_max(i,k)? Why don’t we just keep the longest k-beautiful subsequence until i position in f( i, k). We can get it by f(i , k)=max( f(i-1, k-1) , f(last( i ), k ) ) +1.

How are Leetcode editorials better? Keep in mind that Codechef has much harder problems.

21 Likes

Please don’t talk nonsense about the weak tests and bad constraints. Solutions that compute up to 4 \cdot 10^8 operations can easily pass in one second, so 10^8 is nowhere near tight with a problem of these constraints. O(N \log N) passes for N \leq 10^7 easily in c++, giving issues in java/python, so it’s not weird at all why a TNK passes.

1 Like

excuse me bro if you understand the editorial can you please explain it with a simple example
especially reducing the transitions part containing the two bullet points
thank you :slightly_smiling_face:

why not video tutorial is not out yet?? Eagerly waiting. I have tried with recursion and memo but tle
occurred.

1 Like

why did my O(n*k) is giving tle ?
Anyone Help
https://www.codechef.com/viewsolution/49197825

when we will have a video editorial for this problem?

1 Like

Is this not giving TLE as the complexity is more than O(NK)??

It does give TLE, but that reply was for @chandan_125 who wanted to know the code for brute force approach