POPGATES, NOTALLFL, SWAPPALI video Editorials

CodeChef February Lunchtime 2020
At the Gates (POPGATES): https://youtu.be/r-GLxhBcoLQ
Not All Flavours (NOTALLFL): https://youtu.be/VMhsSel-In8
Swapping to Palindrome (SWAPPALI): https://youtu.be/lPP48R_ecyE

Your feedback is highly appreciated.

2 Likes

In Not All Flavours (NOTALLFL) problem:

why here O(n^2) method will work when the constraints are:

1 ≤T≤ 1,000

1 ≤ N ≤ 10^5

2 ≤ K ≤ 10^5

1 ≤ Ai ≤ K for each valid i

the sum of N over all test cases does not exceed 10^6

so if i take,

t = 1, n = 10^5, k = 2

and array as 1, 1, 1, … upto (10^5 - 10/100) or some small value, and rest as 2

then through O(n^2) approach will fail.

Is it that this test case is not valid or I am wrong or this test case has not been consider at all!!

Yes, N^2 approach should fail here, maybe the underlying test cases are weak. If for each index we find the window size using nested loop running from index+1 to N, we should get TLE ideally.
Can you share the link where N^2 is accepted?