Help with weirdo (cant figure out mistake in code)

help
1

CodeChef: Practical coding for everyone :: here is the link, I am getting WA in subtask 2 and cant figure out the mistake whatsoever.

Appoach: Used dp to figure out whoi s alice and who is bob and then simple map,array calculations to find out x,fx,n,m for bob,alice respectively.

3

What u could have done is simply check every substring of 3 if every such string contains 2 vowels it would be of alice else bob
Use log for calculations

4 Likes
4

I dont think there is a problem with checking…will try again using log :slight_smile:

5

Lets say alice prepared 100 dishes and all dishes are ‘aa’; Hence the denominator is pow(200, 100) (since 200 a’s and 100 dishes) which leads to overflow.

That’s why you should calculate it using logarithm.

log(sa/sb) = log(sa) - log(sb)

log(a*b) = log(a) + log(b)

log(a^x) = x*log(a)

log(sa) = (log(xa) - nlog(fxa)) + (log(xb) - nlog(fxb)) + … + (log(xz) - n*log(fxz))

Similarly obtain log(sb).

log(sa/sb) = log(sa) - log(sb)

sa/sb = e^(log(sa) - log(sb))

If log(sa) - log(sb) > 20 then Infinity. Else calculate and print the answer.

8 Likes
6

Calculate log10 bases if ans>7 print inf else pow(10,ans)

7

hi netish bro i am from psgitech coimbatore! glad to see u

9

yes netish bro but m inactive ! lol

11

ok apologise!just out of curiousity…

12

Its ok. Congrats for 5 stars.

13

thanks friend!hoping to meet you soon…and good luck everyone for the upcoming cook off

15

There are three different parts because of which this problem can give you unsuccessful submission for your solutions.

  1. Finding strings wrongly - Though this is easiest part to handle, but identifying strings correctly belonging to Alice and Bob can be tricky. For example for recipes like aaabbaaa (Bob), baabab (Bob),
    abaabaabaa (Alice) etc.

  2. Handling 10^5 test caes with 10 recipes of max length |S| <= 10 each. This can give you TLE for slow computtation when handling with the rest of the test cases. Notice that this particular case doesn’t exceed the double value type’s range, so you can simply handle the Sa and Sb in simple vars to improve the time complexity. Also, note that iterating through all 26 alphabets (even when absent in the inputs) here can also contribute to additional latency.

  3. This is the second subtask of the problem. Handling cases where |S| <= 100000 and 10< L<= 100000. Here computing (fXa)^N and (fXb)^M can exceed the double value’s range. Here idea is that since you have to print only with accuracy of 10^-6, keep all Xa, Xb, fXa, fXb values in form of x.xxxxx,
    like 1.35523535 and keep powers separately. like powerXa, powerXb, powerFxa, powerFxb.
    compute result = (xA * fXb) / (xB * fXa) and power = powerXa + powerFxb - powerXb - powerFxa
    if power >= 7, then print Infinity else print the actual result by adding back the resultant power to the result.
    Compute all high powers in O(logN) and O(logM) time to avoid TLE.

1 Like
16

why are we calculating pow(10,ans) ??

17

Yeah thanks for your input…it was due to your point number 3. I upsolved it using log.

18

Bro ans calculated in log must be powered to get actual answer. Pow(10,log10(a))=a

1 Like
19

The thing is pow(sa,a) can be extremely huge, like EXTREMELY HUGE because a can in the worst case be 10^5. so if we try to store pow(sa,a) and pow(sb,b) even in double, it is stored as inf.
So without using log theres the no way to solve this.

20

Thanks bro… I tried many different logic but could get only 25 marks …but after reading ur post my solution got accepted with 100 marks .
Thankyou very much.