Animated DIGJUMP Editorial

editorial
, ,
1

Problem Statement: http://www.codechef.com/JUNE14/problems/DIGJUMP

This is my first Animated Editorial , Sugessions are welcome :slight_smile:

16 Likes
2

Nice!! First time i see an animated tutorial here.

Since you said suggestions are welcome, So here goes.

Don’t put everything in a single GIF. Sometimes i need to understand a particular step so i might wanna look at that step for more than a few seconds, But in your GIF, i can’t stop it on one Step only, it will go through the entire algorithm and then come back to the step. So my suggestion would be to split the GIF between each step and post them one below each other, so i can look at one step as long as i want.

PS: Although your GIF was pretty small so it was easy to follow it. The above advice is when you make some other GIF that might have more number of frames.

You should copy the text inside the GIF and paste it along with your GIF in the Editorial, In case the frame changed too quickly i couldn’t read the whole text inside the GIF, i could just scroll down and look at what it said. Also in case im viewing this on a device that doesn’t support GIF’s (Like a mobile phone) I could still read the text and get an idea of how the problem has to be solved.

Keep up the good work, mate. Happy coding!!

Btw, i think you didn’t had to look at all the other numbers once you’ve reached the last element, since this is bfs, I don’t remember exactly, i could be wrong.

3 Likes
3

@s1h33p, thx for animated editorial. can you post also jpg-s that you used to make this gif, pls. btw, i got the reason of that lightning gif :wink:

1 Like
4

Make a video of this so we can stop and stare at a slide unless we understand it. Good initiative bro.

1 Like
5

Thanks for Suggestions Tacoder :slight_smile:

6

This is awesome! Codechef please introduce this in your editorials. It’s a big help! Thanks s1h33p!

3 Likes
7

Yea, this is BFS Approach :stuck_out_tongue:

8

Great animation :smiley:

However when implementing my solution for this problem, I used a modified BFS, it passes all the test cases that I have found in the comments but still get TLE when submitting, is there any way to optimize it further ?

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <queue>

std::queue<long> jump(long i, char S[],int visited[], long N)
{
    std::queue<long> mylist;
    long j;
    for(j = N-1; j > 0; j--)
        if(S[i] == S[j])
            if(!visited[j])
                mylist.push(j);

return mylist;

}


char S[100000];

int visited[100000];

std::queue<long> myqueue, mylist;


int main()
{
    
    long N, number = 1, step = 0, v, x;

    scanf("%s",&S);
    N = strlen(S);
    for(long i=0; i < N; ++i)
        visited[i] = 0;
    myqueue.push(0);
    while(!myqueue.empty())
    {
        for(long i = 0 ; i < number; ++i)
        {
            v = myqueue.front();
            myqueue.pop();
            visited[v] = 1;
            if(v == (N-1))
            {
                printf("%ld",step);
                return 0;
            }
            else
            {
                mylist = jump(v,S,visited,N);
                while(!mylist.empty())
                {
                    x = mylist.front();
                    mylist.pop();
                    myqueue.push(x);
                    visited[x] = 1;
                }
                if(v > 0)
                    if(!visited[v-1])
                    {
                        myqueue.push(v-1);
                        visited[v-1] = 1;
                    }

                if(v < N-1)
                    if(!visited[v+1])
                    {
                        myqueue.push(v+1);
                        visited[v+1] = 1;
                    }
            }
        }
        number = myqueue.size();
        step++;
    }
    return 0;
}
9

@garakchy, it took 34 pics to make :p. i can mail you in rar format if u want. Uploading all pics here will make it ugly.

10

@s1h33p do one thing create an video of all the pictures that you have used while creating gif. you can create video with the help of any movie maker software.

Or you can upload the pictures on slide share(https://www.slideshare.net/login) as a ppt and share the link here.

Hope to see the more and more editorials of this type…