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
2 Likes
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();
}
}
######################################
ankit15
September 14, 2015, 11:35pm
3
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
4
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;
}
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[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
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
9
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;
}
Hi,
Anyone, kindly, explain me why my code is partially working:
https://www.codechef.com/viewsolution/8937656
Thanks
killjee
February 3, 2016, 5:30pm
12
@lone_ranger97 because you are declaring 2 arrays of order 10^5 so its crossing memory limits
ACR
March 18, 2016, 4:54pm
13
dxdy
June 15, 2016, 5:59pm
14
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[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??
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[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;
}
Your code is correct. It got AC
https://www.codechef.com/viewsolution/8167442
What problem did you face?