Lessons learned from solving weirdo (as well as solution)

First off, between every two occurrences of consonants there must be at least two vowels for it to be Alice’s Recipe. Having said that…

This was a really annoying problem, I managed to solve it after quite a few tries. Following lessons were learnt (by me, and they were valuable):

  1. Boost library is really nice.
  2. Don’t forget middle school lessons on how to simplify vulgar fraction. Remove their GCD.
  3. Don’t forget link between GCD and Prime Factors.
  4. Remember that log function, although inaccurate, is really efficient.

The problem involved doing a lot of multiplications and divisions while maintaining accuracy.

Here is what I did:

  1. Prime factorized all numbers concerned. Stored Prime factors as a map. For example 648 can be written as 2^4*3^3. Map format {2:4, 3:3}
  2. Implemented multiplications, divisions and raising to power by manipulating these maps. Raising to power 10 means multiplying all keys by 10. Dividing is subtracting keys. Adding means adding key.
  3. The final solution will be a map with a series of +ve and -ve keys. This will constitute numerator and denominator of final answer.
  4. Generate a vector of long long numbers to store all elements of numerator and same for denominator.
  5. Use log to check whether the fraction generated is greater than 10^8 or less than 10^-8. If so, just output Infinity or zero.
  6. Else use boost library to print the actual answer.

Solution here:: https://www.codechef.com/viewsolution/27850010

5 Likes

U can see my solution then
https://www.codechef.com/viewsolution/27811491

Read from line 334

2 Likes

That’s really nice, but there was a much simpler way😉

Just use naive approach, and get product of all xc,fxa,xb,fxb at one place…then use logarithm on whole expression directly

10 Likes

Okay, will check!

Can you share your solution here?

I just took root L of the score . and recursively multiplied to get answer ( with appropriate break statement ) .

Could u tell why m getting tle in substask 1
And ac in rest
I used same approach as mentioned in thread
https://www.codechef.com/viewsolution/27867163

The same happened with me .
would be great if someone helps !
To get full score i just pust if statement and copied my solution for subtask 1 :sweat_smile:

1 Like

Same here :slight_smile:

WEIRDO - “From Zero to Infinity” - documented code; Editorial-style overview

I was also toying with the whole prime factorisation approach, but thankfully - and slightly surprisingly - using logs turned out to be accurate enough :slight_smile:from-zero-to-infinity-git-log

5 Likes

Fantastic. I will study your code in detail actually. Since I was struggling in the input processing phase too. :slight_smile:
Thanks for sharing!!!

here’s mine

btw also check out @ssjgz code also, it’s pretty neat

3 Likes

Here is explaianation…

3 Likes

Heavy input processing in task 1.

I was facing same issue when I was using maps to shore character frequencies (check here): https://www.codechef.com/viewsolution/27848925

Then I changed my code to use vector and got AC.

Many people did wrong to check whether a string is of Alice or Bob , they just count vowels and conso and check if vowels are greater than equal to conso then it will be of Alice else Bob which is Wrong

Instead of this we have to count vowels and conso in each three consecutive character of string .

1 Like

I used a completely different approach.

take a look here

I was getting AC for subtask 1(1.41s) and WA for subtask 2. I changed from maps and strings to arrays and got AC for subtask 1(0.2s) and WA for subtask 2. Finally on using cpp_dec_float_50 to find the final answer I got AC for subtask 2. Have a look here

https://www.codechef.com/viewsolution/27868379
Did all the things mentioned here still don’t know what is wrong. Please anybody look at this.
Tried everything i knew boost etc.

Though i thought of the same approach but won’t there be cases where the resultant will be small but the power function overflows

Do not calculate power buddy see my solution above mentioned I did not calculate power bcz it will overflow

3 Likes