MSTEP - Editorial

PROBLEM LINK:

Practice
Contest

Author: Lalit Kundu
Tester: Kevin Atienza
Editorialists: Pushkar Mishra and Suhash Venkatesh

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given is a grid of size N imes N. It contains numbers from 1 to N^2. You start at the cell numbered 1, move to 2, then to 3, and so on up till N^2. Report the total manhattan distance traversed in doing so.

EXPLANATION:

Subtask 1 and 2
We keep an array M of size N^2 and a variable Dist = 0. M* stores the coordinates of number i in the grid. Let M*.x denote the x-coordinate and M*.y denote the y-coordinate. Dist stores the total distance moved. Once array M has been filled, we can iterate from i\,=\,1 to N^2 and keep increasing the variable Dist by the distance moved while going from i-1 to i:

Dist = Dist + abs(\,M*.x-M[i-1].x)\,\, + abs(\,M*.y-M[i-1].y)\,\,

Note that Manhattan distance between i and i-1 is being added to Dist. This is because the question says that you can only move from one cell to another if the latter shares an edge with the former.

COMPLEXITY:

\mathcal{O}(N^2)

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

1 Like

what is the problem in this code
######################################
import java.io.;
import java.util.
;
import java.lang.*;

class Matrix{
		public static void main(String args[]) throws java.lang.Exception{
			
			PrintWriter pw=new PrintWriter(System.out);
			
			Scanner sc = new Scanner(System.in); 
			int t=sc.nextInt();
			while(t>0){
			
				long n=sc.nextInt();
				long p=n;
				long a[][]=new long[(int)n][(int)n];
				long b[]=new long[(int)(n*n)];
				long c[]=new long[(int)(n*n)];
				
	
				for(long i=0;i<n;i++){
					for(long j=0;j<n;j++){
						a[(int)i][(int)j] = sc.nextInt();
						p=a[(int)i][(int)j];
						b[(int)(p-1)]=i;
						c[(int)(p-1)]=j;
						
					}
				}
	
				long s=0;
				for(int i=0;i<((n*n)-1);i++){
					s=s+Math.abs(b[(int)i+1]-b[(int)i])+Math.abs(c[(int)i+1]-c[(int)i]);
				}
					pw.println(s);
			t--;
			}
		pw.flush();
		}
} 

######################################

Check this video and subscribe to the channel for more video editorials…


Sometime you may learn some new method,hope this helps…

Why wouldn’t this code run on the CodeChef IDE? It ran without problems on two other online IDE’s, but it gave a runtime error on the CodeChef IDE.

#include <iostream>

using namespace std;

int main()
{
unsigned int T;
cin >> T;

unsigned int** mat;
unsigned int N, num, lastNum, moves;
unsigned int ypos, nextYpos, xpos, nextXpos;
bool breakCheck;

for (unsigned int tnum=0; tnum<T; tnum++)
{
    cin >> N;
    moves = 0;
    mat = new unsigned int*[N];
    for (unsigned int i=0; i<N; i++)
    {
        mat* = new unsigned int[N];
    }
    
    for (unsigned int y=0; y<N; y++)
    {
        for (unsigned int x=0; x<N; x++)
        {
            cin >> num;
            mat[y][x] = num;
        }
    }
    
    lastNum =  N * N;
    
    num = 0; moves = 0;
    
    breakCheck = false;
    
    for (unsigned int y=0; y<N; y++)
    {
        for (unsigned int x=0; x<N; x++)
        {
            if (mat[y][x]==1)
            {
                ypos = y; xpos = x;
                breakCheck = true;
                num = 1;
                break;
            }
        }
        
        if (breakCheck)
        {
            break;
        }
    }
    
    do 
    {
        breakCheck = false;
        num = num+1;
        for (unsigned int y=0; y<N; y++)
        {
            for (unsigned int x=0; x<N; x++)
            {
                if (mat[y][x]==num)
                {
                    nextYpos = y; nextXpos = x;
                    breakCheck = true;
                    break;
                }
            }
            
            if (breakCheck)
            {
                break;
            }
        }
        
        if (nextYpos<ypos)
        {
            moves += (ypos - nextYpos);
        }
        
        else
        {
            moves += (nextYpos - ypos);
        }
        
        if (nextXpos<xpos)
        {
            moves += (xpos - nextXpos);
        }
        
        else
        {
            moves += (nextXpos - xpos);
        }
        
       ypos = nextYpos; xpos = nextXpos;
            
    } while (num!=lastNum);
    
    for (unsigned int i=0; i<N; i++)
    {
        delete[] mat*;
    }
    
    delete[] mat;
    
    cout << moves;
    if ((tnum+1)!=T)
    {
        cout << '

';
}
}

return 0;

}

my ans is showing partially correct … can any tell my mistake for the 2 subcase:
https://www.codechef.com/viewsolution/8279310

@deeksha_garg

HI



MISTAKE


Only Mistake ,I found was dimension of Array

Because you have initialize i and j with 1

That mean i, j can have value upto 500


FACT


As you know Actual Program use 0-based index

To Accessing i=500 you should have size 501 array


ADVICE


To get rid of such error always use arr[requiredsize+5]

i.e. N=100, int arr[100+5]

Hope It helps you…


FEEDBACK



HERE IS YOUR CORRECTED CODE


#include<stdio.h>
#include<math.h>

int main(){

        int t,m[501][501],n;
        long i,j,r[250001],c[250001],step;

        scanf("%d",&t);

    while(t--){

        step=0;
        scanf("%d",&n);

        for(i=1;i<=n;i++){

            for(j=1;j<=n;j++){

                scanf("%d",&m*[j]);
                r[m*[j]]=i;
                c[m*[j]]=j;
            }
        }

        for(i=2;i<=n*n;i++)
            step=step+(abs(r*-r[i-1]))+(abs(c*-c[i-1]));
        printf("%ld

",step);

    }
    return 0;
}


HAPPY CODING



why is my code showing wrong answer…?
https://www.codechef.com/viewsolution/8294143

can we take required move is equal to ((n-1)*2)*n for finding steps ? where n is sqrt of dimension of array.

Hello all,

I only get 30% for my code.
All of subtask 2 is failing … Why is that ?

#!/usr/bin/perl 
my @arguments=get_arguments();
# T stands for test_case
my $test_cases=shift(@arguments);

if( $test_cases <= 5 ){
	for(my $test=0;$test<$test_cases;$test++){
##here starts the actual action: 
# N
#
		my $matrix_size=shift(@arguments);
		if( 1 <= $matrix_size and $matrix_size <= 500 ){

			my @matrix;
			for(my $i=0;$i<$matrix_size;$i++){
				$e=0;
				for my $cell (split(" ",shift(@arguments))){
					$matrix[$i][$e]=$cell;
					$e++;
				}
			}

			my $total_steps=0;
			my $base=1; 
			my $loops=$matrix_size * $matrix_size;

			my $next=0;
			while ($next < $loops ){
				my @base_coord=();
				$next=$base+1;
				my @next_coord=();

				for(my $i=0;$i<$matrix_size;$i++){
					for(my $e=0;$e<$matrix_size;$e++){
						if($matrix[$i][$e] == $base ){
							push(@base_coord,$i);
							push(@base_coord,$e);
						}
						if($matrix[$i][$e] == $next){
							push(@next_coord,$i);
							push(@next_coord,$e);
						}
					}
				}


				my $steps_to_x = $base_coord[0] - $next_coord[0];
				my $steps_to_y = $base_coord[1] - $next_coord[1];
				$base++;
				$total_steps+=($steps_to_x > 0 ) ? $steps_to_x :  $steps_to_x * -1; 
				$total_steps+=($steps_to_y > 0 ) ? $steps_to_y :  $steps_to_y * -1 ;

			}
			print $total_steps . "
"; 
		}else{
			for(my $i=0;$i<$matrix_size;$i++){
				shift(@arguments);
			}
		}

	}
}

sub get_arguments{
	my @arr=();
	while( my $line = <> ){
		push(@arr,$line);
	}

	return @arr; 
}

Hi,

Anyone, kindly, explain me why my code is partially working:
https://www.codechef.com/viewsolution/8937656

Thanks

I am getting RE.What is the problem?

https://www.codechef.com/viewsolution/9283165

@lone_ranger97 because you are declaring 2 arrays of order 10^5 so its crossing memory limits

I am getting a WA for my code. https://www.codechef.com/viewsolution/9695755

I could solve the problem with cin instead of using scanf in C++;
I did this by adding

std::ios::sync_with_stdio(false);

to the program. The speed difference in cin and scanf is largely due to the iostream I/O functions maintaining synchronization with the C I/O functions. It turns out that this internal syncing/flushing is what normally slows down iostream I/O. If we’re not mixing cstdio and iostream, we can turn it off, and then iostream is fastest.

int main()
{
int n,t,a[700][700],x=2,x1,y1,X,Y,i,j,x2,y2,count=0;
scanf("%d",&t);
while(t–)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&a*[j]);
if(a*[j]==1)
x1=i,y1=j,x=2;
}
}
for(i=0;i<n&&x<=(nn);i++)
{
for(j=0;j<n;j++)
{
if(a
[j]==x)
{
x2=i,y2=j;
if(x2-x1<0)
X=x1-x2;
else
X=x2-x1;
if(y2-y1<0)
Y=y1-y2;
else
Y=y2-y1;
count=count+X+Y;
x1=x2,y1=y2;
x++;
i=j=0;
}
}
}
printf("%d
",count);
count=0;
}
return 0;
}
What is problem in it??

can any explain me what is wrong with this code?
im getting wrong answer
https://www.codechef.com/viewsolution/10979970

#include<bits/stdc++.h>
using namespace std;
int r[250005],c[250005];
int main()
{
int t;
scanf("%d",&t);
while(t–)
{
int n;
long long ans=0;
scanf("%d",&n);
int ar[505][505],i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&ar*[j]);
r[ar*[j]]=i;
c[ar*[j]]=j;
}
}
for(i=2;i<=nn;i++)
ans+=(abs(r
-r[i-1])+abs(c*-c[i-1]));
cout<<ans<<endl;
}
return 0;
}

Your code is correct. It got AC

https://www.codechef.com/viewsolution/8167442

What problem did you face?