11136 - Hoax or what

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

Moderator: Board moderators

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

11136 - Hoax or what

Post by helloneo » Mon Oct 23, 2006 4:37 am

Hello..~
Can anybody tell me what is the output for this input..?

Code: Select all

2
2 1 1
2 2 5
0
Thanks..~

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Oct 23, 2006 7:24 am

I am not sure what interpretation you have, but isn't it obviously 3 (0+3)?

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

Post by helloneo » Mon Oct 23, 2006 7:30 am

Darko wrote:I am not sure what interpretation you have, but isn't it obviously 3 (0+3)?
Thanks for reply..
I was pretty sure about my program.. but getting WA..
So, I was wondering what I'm supposed to do if the highest bill and lowest bill is same..
Now I got AC with "long long" :D

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Mon Oct 23, 2006 4:46 pm

I'm not sure the problemsetter considered this, but this problem can be solved pretty easily using C++ STL's "multiset". At first I tought the test cases were made so that using STL would give a TLE, but it passed on 8s.
Daniel
UFRN HDD-1
Brasil

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Mon Oct 23, 2006 5:20 pm

danielrocha wrote:I'm not sure the problemsetter considered this, but this problem can be solved pretty easily using C++ STL's "multiset". At first I tought the test cases were made so that using STL would give a TLE, but it passed on 8s.
i used multiset too , but is there a faster way except using 10^6 size array?

tanx
Arsalan
In being unlucky I have the record.

StanleY Yelnats
New poster
Posts: 12
Joined: Tue Sep 12, 2006 6:54 pm

Post by StanleY Yelnats » Mon Oct 23, 2006 6:23 pm

I used two priority queue however it was a WA
but the algorithm seems to be ok, i'm still working on it

( WA in 2.2sec )

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Mon Oct 23, 2006 6:46 pm

I think if you implement your our heap, maybe, could be faster that an array, but this is data-dependent.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Oct 23, 2006 8:07 pm

About STL not timing out - did you use cin to read the input? I used Java's TreeSet with some modifications during the real contest, but it was TLE when I used Scanner but got AC when I used BufferedReader, which was probably generous of them, I don't know. I don't think that solving problems should depend on the way you read input.

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Tue Oct 24, 2006 9:22 am

Darko wrote:About STL not timing out - did you use cin to read the input? I used Java's TreeSet with some modifications during the real contest, but it was TLE when I used Scanner but got AC when I used BufferedReader, which was probably generous of them, I don't know. I don't think that solving problems should depend on the way you read input.
as it is mentioned in the problem statemant that the input size is 16MB , i used scanf to read the input
In being unlucky I have the record.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Oct 24, 2006 3:05 pm

We didn't have that information during the provincial contest. And even if we did, I don't see why using of scanf would be mandatory. The closest thing that comes to that in Java is Scanner, but is way too slow. I got it accepted here under 2 secs but with my own priority queue and some funky I/O. I don't think that one should have to reinvent those wheels (that are part of standard libraries) in order to solve a problem.

(Note: TreeSet, Scanner and BufferedReader are not available on UVa)

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Tue Oct 24, 2006 3:33 pm

At UVa we cannot allow time limit more than 10 second. To let the java pass we can make the input file smaller but that will allow mady bad C codes pass which it already did. So it is hard to make an adjustment. I know some other online judges allow more time for java but currently we don't have that provision.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Oct 24, 2006 3:46 pm

Well, just allowing BufferedReader would help a lot with Java I/O. I am not sure why it's not allowed here. You can use a buffer, its size is limited to 2048 bytes, but it works (that's how I read that 16MB file). But I've seen someone posting C code in which they used an 1MB buffer. So I have no idea why Java's buffer is limited in that way, too.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Oct 24, 2006 3:49 pm

Stanley, try this case:

Code: Select all

2
2 1 1
2 2 2
0

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Tue Oct 24, 2006 4:15 pm

Try bugs and suggestions to ask carlos. I use very very limited amount of java (when I am forced to write a java soln) so I cannot comment on this.

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

Post by Artikali » Tue Oct 24, 2006 9:35 pm

i also used multiset, but i am getting WA

i am newer using STL
Last edited by Artikali on Wed Oct 25, 2006 5:35 am, edited 1 time in total.

Post Reply

Return to “Volume 111 (11100-11199)”