Contest 2 - Hints to Problems [OFFICIAL]

why 4 is not the correct answer. You can see here that ><<>>
<<>> is a valid expression and it's length is 4.
if you are saying that valid expression must start from index zero than I am wrong.
But No where I understood in the question is that expression must start with valid expression then only we will count.
Please Explain a bit.

Read the problem statement carefully it has asked for the length of the longest valid ‘prefix’, so the expression must start with ‘<’.

Thanks, I have corrected and submitted successfully.

1 Like

will someone please explain matched brackets problem? I am unable to understand the second part of the question. (specially the first positions)

I’m not sure why my logic is wrong. I am keeping track of encountered flavours in unordered_map(since insert is O(1)) and if the length of map is equal to “k” then I’m checking if max<count.
Current complexity is O(n+n) which can be reduced to O(n)

#include <iostream>
#include<unordered_map>
#include<vector>
using namespace std;

int main() {
	// your code goes here
	long long int t, n ,k, p, max=0, count=0; vector<long long int> ar; unordered_map<long long int, int> l;
	std::cin >> t;
	while(t--)
	{
	    std::cin >> n>>k; max=0; count=0; ar.clear(); l.clear();
	    
	    while(n--)
	    {
	        std::cin >> p;
	        ar.push_back(p);
	    }
	    if(k==1)
	    {
	        std::cout << 0 << std::endl;
	        continue;
	    }
	    for(p=0;p<ar.size();p++)
	    {
	        l[ar[p]]=1;
	        
	        if(l.size()==k)
	        {
	            if(max<count)
	            max=count;
	            l.clear();
	            count=0;
	        }
	        count++;
	        //std::cout << max<<"---"<<count << std::endl;
	    }
	    if(max<count)
	           max=count;
	    std::cout << max << std::endl;
	}
	return 0;

}

in stupid machine question, i’ve implemented it through brute force. Following is my solution link: https://www.codechef.com/viewsolution/44713205
. It is giving correct answer. but my analysis shows that it’s worst case time complexity is O(n^2) when s[1…n] is reverse sorted. So, why does it not give TLE? Can anyone help me to figure out whether my analysis was wrong or something else. Thnx in advance.