CodeChef February Lunchtime 2020
At the Gates (POPGATES): CodeChef February Lunchtime 2020 | At the Gates | POPGATES - YouTube
Not All Flavours (NOTALLFL): CodeChef February Lunchtime 2020 | Not All Flavours | NOTALLFL - YouTube
Swapping to Palindrome (SWAPPALI): CodeChef February Lunchtime 2020 | Swapping to Palindrome | SWAPPALI - YouTube
Your feedback is highly appreciated.
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?