11858 - Frosh Week

All about problems in Volume 118. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11858 - Frosh Week

Post by MRH » 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.

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

Re: 11858 - Frosh Week

Post by Igor9669 » 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!

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

Re: 11858 - Frosh Week

Post by MRH » Thu Oct 07, 2010 10:51 am

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

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

Re: 11858 - Frosh Week

Post by md_yusuf » 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....

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

Re: 11858 - Frosh Week

Post by ask_1171 » 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;

}

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 11858 - Frosh Week

Post by helloneo » Sat Nov 13, 2010 4:13 pm

Think of the case like this

Code: Select all

3
1000000
9324234
4835
Your code invoke the uninitialized memory read error

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

Re: 11858 - Frosh Week

Post by Jehad Uddin » Sun Nov 14, 2010 5:31 am

use long long to avoid wa

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

Re: 11858 - Frosh Week

Post by md_yusuf » 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 ?

User avatar
Psh
New poster
Posts: 7
Joined: Tue Jul 06, 2010 9:52 pm
Location: Bangladesh
Contact:

11858 - Frosh Week

Post by Psh » Fri Feb 11, 2011 5:51 pm

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

Post by laituanksa245 » Fri Jan 18, 2013 6:42 pm

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

Post by brianfry713 » Fri Jan 18, 2013 10:01 pm

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

Post by laituanksa245 » 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 ?

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

Re: WA 11858 - Frosh Week

Post by brianfry713 » Mon Jan 21, 2013 10:09 pm

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

Post by lukai » 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

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

Post by brianfry713 » Mon Feb 04, 2013 11:37 pm

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

Post Reply

Return to “Volume 118 (11800-11899)”