11136 - Hoax or what

[helloneo]

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]

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

[helloneo]

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"

[danielrocha]

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.

[arsalan_mousavian]

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

[StanleY Yelnats]

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]

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

[Darko]

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.

[arsalan_mousavian]

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

[Darko]

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]

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]

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]

Stanley, try this case:

Code: Select all

2
2 1 1
2 2 2
0

[shahriar_manzoor]

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]

i also used multiset, but i am getting WA

i am newer using STL

Code: Select all