Couple of observations and the algorithm is very simple:
multiply p*3 (that is if all 3 scores are the max)
subtract 2 (that is the least possible total for a non surprising
result)
if the sum of all 3 scores is equal or above (3p-2) then add it tot
the total (r+=1)
if not, just check if the remaining surprising can be used to make it
possible. remember that a surprising result can only add 2 as maximum.
So, if you still have S, and the difference is >=2 (only if p>1) then
add it (r+=1) and use a suprising (S-=1)
Here's mine.... In Basic!
For i As Integer = 1 To T
'N,S,p are taken from the file
p = p * 3 - 2
r = 0
For j = 3 To N + 2
If CInt(x(j)) >= p Then
r += 1
ElseIf (CInt(x(j)) >= (p - 2)) AndAlso (S > 0) AndAlso
(p > 1) Then
r += 1
S -= 1
End If
Next
sw.WriteLine(String.Format("Case #{0}: {1}", i, r))
Next i
On Apr 15, 11:10 am, Jesper Jurcenoks <[email protected]> wrote:
> hi Mostafama
>
> For Problem B, there are a number of inefficient and memory consuming
> algorithms, and a few elegant ones.
>
> If you use an elegant solution you will not have any memory problems.
>
> here is my solution in python which does not consume any memory.
>
> def count_func(inputdata):
> (testcase, N, S, p, ti) = inputdata
> count = 0
> cutoff = 3*p-2
> cutoff_surprising = 3*p-4
> for total in ti:
> if total >= cutoff:
> count +=1
> elif p>1 and total >= cutoff_surprising and S>0:
> count += 1
> S -= 1
>
> return (testcase, count)
>
> On Sun, Apr 15, 2012 at 3:09 AM, mostafamabrouk
>
>
>
> <[email protected]> wrote:
> > Hi
> > While i was solving problem B in the qualification round for large input. i
> > got out of memory exception - java heap space not sufficient.
> > May anyone tell me what is the solution for such problem ?
> > Thank you
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Google Code Jam" group.
> > To view this discussion on the web visit
> >https://groups.google.com/d/msg/google-code/-/n_NV7iDRit4J.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > For more options, visit this group at
> >http://groups.google.com/group/google-code?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
