MSTEP - Editorial

pushkarmishra · August 31, 2015, 6:02pm

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 \times 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[i] stores the coordinates of number i in the grid. Let M[i].x denote the x-coordinate and M[i].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[i].x-M[i-1].x)\,\, + abs(\,M[i].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

buckyinjaipur · September 14, 2015, 4:15pm

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();
		}
}

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

dragonemperor · September 14, 2015, 4:49pm

Your code is correct. It got AC

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

What problem did you face?

ankit15 · September 14, 2015, 11:35pm

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

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

amatsco · September 21, 2015, 9:52pm

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[i] = 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[i];
    }
    
    delete[] mat;
    
    cout << moves;
    if ((tnum+1)!=T)
    {
        cout << '\n';
    }
}

return 0;

}

deeksha_garg · September 29, 2015, 7:18pm

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

rcsldav2017 · September 30, 2015, 1:48am

@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[i][j]);
                r[m[i][j]]=i;
                c[m[i][j]]=j;
            }
        }

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

    }
    return 0;
}

HAPPY CODING

anshul_m · October 2, 2015, 1:22am

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

bhargav431997 · October 16, 2015, 8:52am

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

ekai · November 10, 2015, 1:18am

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 . "\n"; 
		}else{
			for(my $i=0;$i<$matrix_size;$i++){
				shift(@arguments);
			}
		}

	}
}

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

	return @arr; 
}

banabanaban · December 12, 2015, 8:40pm

Hi,

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

Thanks

lone_ranger97 · February 3, 2016, 12:22pm

I am getting RE.What is the problem?

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

killjee · February 3, 2016, 5:30pm

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

ACR · March 18, 2016, 4:54pm

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

dxdy · June 15, 2016, 5:59pm

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.

ragapt123 · June 15, 2016, 6:38pm

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[i][j]);
if(a[i][j]==1)
x1=i,y1=j,x=2;
}
}
for(i=0;i<n&&x<=(n*n);i++)
{
for(j=0;j<n;j++)
{
if(a[i][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\n",count);
count=0;
}
return 0;
}
What is problem in it??

ajayravi14 · July 31, 2016, 4:34pm

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

salman_1 · December 23, 2016, 12:45pm

#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[i][j]);
r[ar[i][j]]=i;
c[ar[i][j]]=j;
}
}
for(i=2;i<=n*n;i++)
ans+=(abs(r[i]-r[i-1])+abs(c[i]-c[i-1]));
cout<<ans<<endl;
}
return 0;
}