11858 - Frosh Week

[MRH]

I slove this problem using merge sort but still now Wrong answer please give me any idea about this problem

Thanks in advance.

[Igor9669]

My problem was that I used an array of size 1000000 when I increase it I got Ac! Try this!

[MRH]

HI "Igor9669" now i got Acc
thanks for your help

[md_yusuf]

hi im getting wrong answer.... i cant understand where is the problem...plz check my code

C++

#define max 10000001

long int a[max];
int main ()
{
long int i,n,cnt,t;
// freopen("in.txt","r",stdin);
while(scanf("%ld",&n)==1)
{
cnt=0;
for(i=1;i<=n;i++)
cin>>a;
for(i=1;i<=n;i++)
{
if(a<i)
{
cnt++;
t=a[a];
a[a]=a;
a=t;
i--;
}
}
printf("%ld\n",cnt);
}
return 0;
}

i cant get any idea how i solve this problem using marge sorts plz give me some hints ...
or give me some critical input for which my code does not work...
plz help me....

[ask_1171]

im getting runtime error can any one help me out ??/

#include<iostream>
#include<stdio.h>
using namespace std;
#define mx 1000001


long int r1[mx];
long int r2[mx];



int main()
{
long int p;
long int i;
long int cnt;
long int x;

while(scanf("%ld",&p)==1)
{
cnt=0;
for(i=1;i<=p;i++)
{
cin>>x;
r1=x;
r2[x]=i;
}

for(i=1;i<=p;i++)
{
if(r2!=i)
{

x=r1;
r2[x]=r2;
r1[r2]=x;
cnt++;
}

}

printf("%ld\n",cnt);

}


return 0;

}

[helloneo]

Think of the case like this

Code: Select all

3
1000000
9324234
4835

Your code invoke the uninitialized memory read error

[Jehad Uddin]

use long long to avoid wa

[md_yusuf]

thax for ur help. At first i misunderstand the problem..
then i solve using marge sort..
bt i cant think any better way...
how they solve it under one second runtime...
can anyone help me ?

[Psh]

Use simple merge sort. As I did, apply merge sort to count the swaps..

[laituanksa245]

Can anyone give me some criticial test cases ? I keep getting WA

Code: Select all

Code removed

[brianfry713]

Input:

Code: Select all

3
10
20
30
3
10
30
20
3
20
10
30
3
20
30
10
3
30
10
20
3
30
20
10

AC output:

Code: Select all

0
1
1
2
2
3

[laituanksa245]

Thanks brianfry713.
I finally solved this problem by using merge sort.
I think this problem can also be solved by using segment trees. But I don't know how to do that.

First count the number of inversion in the left child.
Then count the number of inversion in the right child.
But then how do you count the number of inversion that consists of 1 element from the left child and 1 element from the right child ?
Any hint ?

[brianfry713]

I used merge sort

[lukai]

I am using mergesort for finding inversion index. but don't understand why I am getting TLE. please help

Code: Select all

Removed after AC

is there any other technique without using mergesort

[brianfry713]

Change line 82 to:
while(scanf("%lld",&n)==1)