## 11858 - Frosh Week

Moderator: Board moderators

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### 11858 - Frosh Week

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11858 - Frosh Week

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

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 11858 - Frosh Week

HI "Igor9669" now i got Acc

md_yusuf
New poster
Posts: 9
Joined: Fri Jun 25, 2010 11:09 pm

### Re: 11858 - Frosh Week

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

New poster
Posts: 3
Joined: Wed Aug 04, 2010 1:17 pm

### Re: 11858 - Frosh Week

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11858 - Frosh Week

Think of the case like this

Code: Select all

``````3
1000000
9324234
4835``````

Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 11858 - Frosh Week

use long long to avoid wa

md_yusuf
New poster
Posts: 9
Joined: Fri Jun 25, 2010 11:09 pm

### Re: 11858 - Frosh Week

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
New poster
Posts: 7
Joined: Tue Jul 06, 2010 9:52 pm
Contact:

### 11858 - Frosh Week

Use simple merge sort. As I did, apply merge sort to count the swaps..
i Quit for a fresher start

laituanksa245
New poster
Posts: 20
Joined: Tue Jan 10, 2012 4:23 pm
Location: Vietnam

### WA 11858 - Frosh Week

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

Code: Select all

``````Code removed
``````
Last edited by laituanksa245 on Mon Jan 21, 2013 5:13 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: WA 11858 - Frosh Week

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``````
Check input and AC output for thousands of problems on uDebug!

laituanksa245
New poster
Posts: 20
Joined: Tue Jan 10, 2012 4:23 pm
Location: Vietnam

### Re: WA 11858 - Frosh Week

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: WA 11858 - Frosh Week

I used merge sort
Check input and AC output for thousands of problems on uDebug!

lukai
New poster
Posts: 25
Joined: Wed Dec 05, 2012 8:11 pm

### 11858 - Frosh Week

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
Last edited by lukai on Tue Feb 05, 2013 10:45 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: UVA 11858 , Frosh work

Change line 82 to:
while(scanf("%lld",&n)==1)
Check input and AC output for thousands of problems on uDebug!