I was solving a question which uses a trie and I've taken care of the number of nodes and I repeatedly got MLE upon implementing it using 2D arrays and pointers as well.

I've looked at submissions that used a similar logic and they are getting AC.

Any help as to why this is happening is highly appreciated.

Question : 514C

Submission with Pointers : Pointers

Similar submission : Also Pointers

Submission with 2D array : Array

Similar submission : Also Array

Sorry if I missed something obvious. I am legit stuck here and I can't figure out why this is happening. Can anyone please tell why?

[UPD]

The MLE was occurring because string str was being stored in the function stack multiple times and when the level of recursion becomes huge, it resulted in an MLE. Declaring the variable global solved it.

Accepted submissions :

Array

Pointers

[EDIT]

I think at this point we all can safely agree that there is no such thing as "talent" and even if there is such a thing,hard work beats talent any day.So I request you all to please stop arguing about this.I genuinely made this post to get all of your suggestions and get some tips/tricks which might help me along the way but this post had turned into more of an argument about why all the LGMs were born with this so called talent and are invincible and can't be reached. I believe that with enough hard work, anyone can reach LGM and if that is not happening, it is because we are not putting enough effort.I agree I'm not the right person to say this when I myself am terrible at CP but I am willing to invest a lot of my time to get better at it.

[POST]

Dear all,

I am not good at competitive programming but I am willing to put in the effort to get better at it. I had a small question which I though might help me and a lot of people like me who want to get better at CP.

It is not a question asking how to solve problem X or which method to use.

1:

I just wanted to know if, let's say you start solving a question. Can you look at the question and realize.. Oh!! this question can be solved using DP or graphs or some paradigm Y.

Or rather, how long does it usually take for the idea to click in your head?

2:

Also, do you have a specific method to determine what to use(I know it is not possible in most cases) like looking at the constraints or the time limit or anything like that?

3:

Is there any particular pattern you follow while solving problems? Like.. do you select a problem to solve in you free time randomly or based on a particular tag?

4:

I found a couple of good blog entries by Morass and DarthPrince from which I practice topic specific problems and I am practicing algorithms from CLRS. Are there any resources that I am missing? If so can you please specify the names or post the links?

5:

Also, on an average basis, how much time do you spend on CP per day?

Thank you.

I was solving some problems and I found an interesting thing regarding the execution times on the server. If anyone could provide me with an explanation it would be amazing. Thanks :)

Here are the links to the submissions :

1 : 62ms

2 : 30ms

For those who didn't check the submissions here's what happened :

62ms code :

int n;
cin>>n;

cout<<3*n/2<<endl;
return 0;

30ms code :

string str0,str1;
cin>>str0>>str1;

int cnt=0;
str0+="$";
int len=str1.length();
REP(i,len)
    if(str1[i]==str0[cnt])
        ++cnt;

cout<<cnt+1<<endl;

return 0;

}

No matter how I look at it the second code should have more exec time right?

Any help regarding this is highly appreciated.

I came across this problem and I submitted a DFS solution and it got AC.

But it took way lesser time than I expected it to take.

Like...

Forgetting all the vertices which can't be reached, at every level we have 10 new vertices and the depth is 1000 in the worst case.

Wouldn't a DFS have a huge number of steps and this code took around 30ms.

Any reasoning as to why my reasoning is wrong would be highly appreciated :)

I didn't understand why the method mentioned in the editorial works. Can someone provide me with a proof for why it works?

Question : 357B

Editorial Solution :

Let's process the dances in the given order and determine the colors of dancers' clothes. If there are no dancer from some previous dance, we can give the dances different colors arbitrarily. And if there is such dancer, we already know the color of his clothes. So, we arbitrarily distribute the other two colors between the remaining two dancers.

package main

import "fmt"

import "math"

func main(){

var n,k int;

fmt.Scanf("%d %d",&n,&k);

var arr[100] int;

for i := 0 ; i < n ; i++ {
    fmt.Scanf("%d",&arr[i]);
}

for i := 0 ; i < n ; i++ {
    max_idx,cur_max := i,arr[i] ;
    for j := i+1 ; j < n ; j++ {
        cur_max := int(math.Max(float64(cur_max),float64(arr[j])));
        if ( cur_max == arr[j] ){
            max_idx = j;
        }
    }
    arr[i],arr[max_idx] = arr[max_idx],arr[i];
}

cnt := 0;

for i := 0 ; i < n ; i++ {
    if (arr[i] >= arr[k-1] && arr[i] > 0){
        cnt++;
    } else{
        break;
    }
}

fmt.Println(cnt);

}

This was my code for 158A.

The output for the first test case on my PC was 6 but it shows 0 on cf server.

Can someone point out where I've gone wrong?

Thanks in advance :)