### 11858 - Frosh Week

Posted:

**Thu Oct 07, 2010 4:50 am**I slove this problem using merge sort but still now Wrong answer please give me any idea about this problem

Thanks in advance.

Thanks in advance.

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=53&t=71605

Page **1** of **2**

Posted: **Thu Oct 07, 2010 4:50 am**

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

Thanks in advance.

Thanks in advance.

Posted: **Thu Oct 07, 2010 8:39 am**

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

Posted: **Thu Oct 07, 2010 10:51 am**

HI "Igor9669" now i got Acc

thanks for your help

thanks for your help

Posted: **Fri Nov 12, 2010 5:25 pm**

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....

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

{

cnt++;

t=a[a

a[a

a

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....

Posted: **Fri Nov 12, 2010 8:00 pm**

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;

}

#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

r2[x]=i;

}

for(i=1;i<=p;i++)

{

if(r2

{

x=r1

r2[x]=r2

r1[r2

cnt++;

}

}

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

}

return 0;

}

Posted: **Sat Nov 13, 2010 4:13 pm**

Think of the case like this

Your code invoke the uninitialized memory read error

Code: Select all

```
3
1000000
9324234
4835
```

Posted: **Sun Nov 14, 2010 5:31 am**

use long long to avoid wa

Posted: **Mon Nov 15, 2010 8:12 pm**

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 ?

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 ?

Posted: **Fri Feb 11, 2011 5:51 pm**

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

Posted: **Fri Jan 18, 2013 6:42 pm**

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

Code: Select all

```
Code removed
```

Posted: **Fri Jan 18, 2013 10:01 pm**

Input:AC output:

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
```

Code: Select all

```
0
1
1
2
2
3
```

Posted: **Mon Jan 21, 2013 5:16 am**

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 ?

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 ?

Posted: **Mon Jan 21, 2013 10:09 pm**

I used merge sort

Posted: **Sun Feb 03, 2013 10:59 am**

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

is there any other technique without using mergesort

Code: Select all

```
Removed after AC
```

Posted: **Mon Feb 04, 2013 11:37 pm**

Change line 82 to:

while(scanf("%lld",&n)==1)

while(scanf("%lld",&n)==1)