[Community Puzzle] Unit Fractions


#1

https://www.codingame.com/training/easy/unit-fractions

Send your feedback or ask for help here!

Created by @java_coffee_cup,validated by @cg123,@Deltaspace and @JBM.
If you have any issues, feel free to ping them.


#2

You should describe task more explicit. Most of time I was trying to undestand why compiler want exactly 2…k pairs of fractions, where k are unknown)


#3

It is part of the challenge.
This puzzle is to find out how many possible solutions there are, and then list out all these solutions.
The constraint for n is given. Under this constraint the number of possible solutions will not grow to infinity. The test cases are good reference for how complicated the solution can be.


#4

My progress for this problem is 42% and I’m stuck here…
How can I get any help if I can’t see the solutions? I’m a beginner :baby:


#5

Can you pass all testcases?


#6

I passed 3 out of 7 testcases. I can share the code so far.


#7

No need to share your code yet.

Treat this puzzle as a Math problem. Base on the testcases you failed, try manually calculating the results and cross check it with the expected answers.
It is tedious but after doing a few lines you should know the routine.

If there is a difference, find out why.
When math is no longer a problem, do coding again.

P.S.
This puzzle is very easy to produce testcase. Just give it a number >= 1.
Try inputs of 1 to 20 and see what output you get by manual calculation and by your program.


#8

Well … I already figured it out that the rule for x and y should be:
x=(n+a)*int(n/a)
y=n+a, where a is a divisor of n.

But, for example when n=12:
1/12 = 1/156 + 1/13
1/12 = 1/84 + 1/14
1/12 = 1/60 + 1/15
1/12 = 1/48 + 1/16
1/12 = 1/36 + 1/18
// # 1/12 = 1/30 + 1/20
// # 1/12 = 1/28 + 1/21
1/12 = 1/24 + 1/24
my code finds all of these except the ones commented.
And this is the same for the case when n=100:
1/100 = 1/10100 + 1/101
1/100 = 1/5100 + 1/102
1/100 = 1/2600 + 1/104
1/100 = 1/2100 + 1/105
// # 1/100 = 1/1350 + 1/108
1/100 = 1/1100 + 1/110
// # 1/100 = 1/725 + 1/116
1/100 = 1/600 + 1/120
1/100 = 1/500 + 1/125
// # 1/100 = 1/350 + 1/140
1/100 = 1/300 + 1/150
// #1/100 = 1/225 + 1/180
1/100 = 1/200 + 1/200
I can’t figure it out by what rule these fractions appear… (the commented ones)


#9

For you, it is still a Math problem. Your approach is not perfect.

Take 1/12 = 1/28 + 1/21 as an example.
As you know this answer is correct but you do not know how to obtain 28 and 21, you could play a bit of reverse-engineering.

21 = 12 + a
so that a is 9.

Is 9 a “divisor” of 12?

9 can be obtained from 3*3, and 3 is a factor of 12. Find a correct way to expand your possible values of a


#10

Ha ha, now I get it!
You really have good teaching skills.

Thanks a lot for your patience and hints!!


#11

Is there a problem with the validator? I get for “12”:

Échec

Trouvé : 1/…
Attendu : Rien

(Failure. Found: 1…, expected: nothing.)
The first line should be 1/12 = 1/156 + 1/13 (which I see in stdout).
Why does the test fail?


#12

It sounds like you are printing too much - it was expecting no more input but you gave it an extra line.


#13

Oh, sorry. I got the point.
Yes, printing too much :slight_smile:. In a way …
Thank you for your prompt answer!


#14

This would be great puzzle for ClashOfCode. Hard enough to stop “typists clashes”, compressible enough to play </> mode. But now it has been compromised by being puzzle of the week so everyone will type pre-processed solution. What a pitty


#15

n = 9999 is killing me. There’s no chance that I can ques a pattern for an x for the loop.
The first 3 are x/3+((x/3*2)) but after that is just some random numbers or I can’t see that pattern.


#16

Look back in this thread. A peer coder proposed an algorithm which is not perfect but must be better than using brute force. Suggestions to fix the imperfectness are also there. Base on these to invent your own algorithm.


#17

Hello, I’ve been sitting for the fourth day and can’t understand how to solve this problem. I tried to find all the divisors and on them to decide how one of the coders provided the algorithm from above but it didn’t work, because the validator didn’t skip trying to expand all the values ​​by raising them to a power and checking for value * value <n or Math.pow (value, i) <n or by brute-force coefficients, i.e. x / y == 1 / n but it didn’t help in other words, I despaired reading about Egyptian Fractions I didn’t find anything either, I’m very grateful if someone helps, I’m not very good at math and all my formulas were doomed to failure


#19

Hello,
Has everyone found a relation between “y” and “next y” ?
I wrote a brute force algorithm which works quite well, but when the input is to high, it didn’t provide the answer in due time.
Has an exemple, with 100 as input, I get:
1/100 = 1/10100 + 1/101
1/100 = 1/5100 + 1/102
1/100 = 1/2600 + 1/104
1/100 = 1/2100 + 1/105
1/100 = 1/1350 + 1/108
1/100 = 1/1100 + 1/110
1/100 = 1/725 + 1/116
1/100 = 1/600 + 1/120
1/100 = 1/500 + 1/125
1/100 = 1/350 + 1/140
1/100 = 1/300 + 1/150
1/100 = 1/225 + 1/180
1/100 = 1/200 + 1/200
The result is good but every single y value from n+1 to 2*n is tested. I’d like to find a code who will tell if y=180, so nextY = 200. Has someone already find what I’m looking for ?


#20

I do not know an easy “next()” function for this purpose.
I know that testing each integer in your said range is very possible within the puzzle constraint. If you find it timeout, it is likely because your testing algorithm is not efficient.

So now you got a new target of improvement, and near success.


#21

thanks, I’ll try to improve the algorithm