CLBRKT EDITORIAL

editorial
, , , ,
23

Congrats for 4* again!

1 Like
24

It’s because the “defines” which are written “after” can’t be performed on the code above it. (Be it, functions or anything else, too).

1 Like
25

:disappointed_relieved::disappointed_relieved::disappointed_relieved: Could not solve just bcoz of endl

1 Like
26

Oh thanks , I don’t know about them , Thanks

1 Like
27

@sarthakmanna Hey, great contest but I wanted to ask you something. Why were the time limits so tight? A mere change from map to unordered_map converted TLE to AC. This feels unfair as the core logic was right.

TLE: CodeChef: Practical coding for everyone
AC: CodeChef: Practical coding for everyone

only diff is unordered_map

1 Like
29

It’s just because, when you have to access a value in a map in the order of >=10^6 times, use unordered_map because it’s faster than map, but another constraint is that the max. value of the “key” should not be high. If the max. value of key isn’t that high (<=10^7) and also you have to do high number of accesses, then use “unordered_map” instead of “map” to avoid TLE. Else, use “map”.

30

Yes I’ve realised that now but I still feel this should’ve been accepted. Had I coded the same thing in python using dictionary it would’ve given AC. I lost my 4 stars to a damned unordered_map :frowning:

31

https://www.codechef.com/viewsolution/35681581
Explain me how could this solution possibly get TLE .

32
AC Code 
#include  <bits/stdc++.h>
#define ll   int
#define  endl "\n"
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace  std;


int main()
{
    fastIO
    ll t;
    cin>>t;
    while(t--)
    {
        string str;
        cin>>str;
        int n=str.size();
        str = " "+str;
        vector <ll> data(str.size()+1,0);
        ll last = INT_MAX;
        stack<ll> clbr;
        for(ll i = str.size()-1;i>=1;i--) {
         if(str[i]==')') {
             if(last != INT_MAX)
                 data[i] = last;
             clbr.push(i);
         }
         else
         {
             if(clbr.size()>0)
             {
                data[i] = clbr.top();
                last = clbr.top();
                clbr.pop();
             }
             else{
                last=0;
             }
         }
        }
       ll q;
       cin>>q;
       for(ll i=0;i<q;i++)
       {
           ll n;
           cin>>n;
           if(data[n])
               cout<<data[n]<<endl;
           else
               cout<<-1<<endl;
       }
    }
    return 0;
}

/*
 1
 (())(())))(((()))))))((()()()))((()())))((())()))((()()))(())
  10
  12 43 55 2 56 46 1 23 17 60
 */

If you prefer link
The only mistake was not updating the last in case of consecutive (..(..( iterating from right to left.
A test case where your original code fails:

(())()()((((()
1 Like
33

here is my solution hope it may help you:CodeChef: Practical coding for everyone

34

Thank you, @akshitm16

1 Like
35

here is your AC solution :slight_smile: CodeChef: Practical coding for everyone

1 Like
36

I too, got AC just after using unordered_map instead of map, after seeing your post :slight_smile:

37

omg, it’s like i dont even know this language. Could you please tell me what exactly i did wrong, also look at this submission. CodeChef: Practical coding for everyone
It’s literally the same thing except that u defined it before hand. Why is it like this ?

38

yes I have modified your submission for AC in the previous link , I think the since the constraints are very tight you need to declare the vector of size(n+1) inside function or you should declare the vector of size(10^7) globally , since you are declaring the vector of 10^7 in main function it is giving TLE , i exactly don’t know why but will try to get to you asap

39

My submission using two stacks.

First character stack stores opening brackets and pops it as soon as a close bracket is encountered.

Second stack stores indexes where the opening brackets appear and for the corresponding closed bracket sequence. The index of the closing bracket is stored at the index of the opening bracket.

Lastly if we still have opening brackets left in our stack that implies those brackets never got a balanced bracket sequence, so for their indexes the answer is -1.

Finally the indexes which haven’t been assigned any values (i.e neither -1 nor any index position)
they have to store the value for the next minimum index which has a stored value.

My submission - CodeChef: Practical coding for everyone

40

can anyone tell me what is wrong with this approach or give me the edge case

                    int ans[]=new int[n+1];
		ans[n]=-1;
		for(int i=n-1;i>0;i--)
		{
			if(a[i]==')')
			{
				st.push(i);
				ans[i]=ans[i+1];
			}
			else
			{
				if(st.isEmpty())
				{
					ans[i]=-1;
				}
				else
				{
					ans[i]=st.pop();
				}
			}
		}


		for(int x:ans)
			pw.print(x+" ");

		int q=sc.nextInt();

		System.out.println(q);
		for(int i=0;i<q;i++)
			pw.println(ans[sc.nextInt()]);
41

VIDEO EXPLANATION

42

this is the solution CodeChef: Practical coding for everyone i suubmitted during contest and got TLE and the same code i pasted during practice i got AC CodeChef: Practical coding for everyone can someone please explain . if there is something i m missing please guide me .

43

https://www.codechef.com/viewsolution/35695318
It gives WA. Please provide me a test case where my program fails.