[Community Puzzle] Prime Fractals in Pascal's Triangle

Puzzles
#1

https://www.codingame.com/training/expert/prime-fractals-in-pascals-triangle

Send your feedback or ask for help here!

Created by @comp0zr,validated by @Husoski,@JohnCM and @VonDerManzen.
If you have any issues, feel free to ping them.

1 Like
#2

Hello,

Thank you very much for this interesting puzzle!

I managed so far to pass all tests except 5 cases in the last test (“Mixed”), listed below:

7	7988010013839035920	7988010013839035920
11	7472816619014586368	6351072931327186848
7	6366831854239599616	1850952926
7	7832857774167014400	6353159535988834304
5	7812645415879167072	85239928691027968

Expected results:

735443764
664426332
186541925
735443764
942108952

For these 5 tests, R is above the upper bound of 1e18 specified in the statement. This upper_bound seems to be constructed from max(uint64_t)/max( P).

I obtain 608304338 for instance for the case 7 7988010013839035920 7988010013839035920, which is conveniently a R == C one. I am most likely mistaken, but just in case, can you double check that there were no overflow during the generation of the value 735443764 for this test? :slight_smile:

Note: R is also greater than 1e18 for the 3 other cases below, but they do not seem to have the potential anomaly (maybe because the result after a last involved multiplication is > R even with overflow):

13	2361250235388728896	2416949
7	3563023483574034432	3370633290388482048
11	2353094913903362048	1255179497
3 Likes
#3

You’re absolutely correct! I’ve updated the “Mixed” test case and validator with the correct results, and also increased the upper bound on R to 10^19 to match the inputs.

Thanks a lot for bringing this to my attention. Please let me know whether or not you’re able to get 100% now.

2 Likes
#4

Hi, thank you for the update!
All tests and validators pass correctly now :slight_smile:
(maybe we can remove these posts from the puzzle discussion)

#5

Hi,

Thank you very much for the puzzle,

Being a CS student with 1+ years of coding, I’ve always looked for a challenge that is seemingly impossible, but with the right amount of effort and time to solve it eventually,
so far this was the most challenging problem I’ve come across, and I’d really feel super accomplished if I can solve it.

I was successful with the first test case, though after browsing through the other test-cases, it seems to me now that I’m too early in the game for it.

While of looked through the concepts needed to know for solving it, I came across memoization etc. now my strongest language currently is Java, and I realized that some test-cases will have numbers of rows like: 15744537121098240, I’m very bad at mathematics, and currently with long type in Java was only able to create an algorithm that can print me out a row, up until row 20 using n choose k,

So I figured that I’ll have to instead use a recursive algorithm that will return me an element’s value based on (-1 row same column) + (-1 row -1 column) [I don’t know how the formula is called] and for optimization store that element in a 2d array or ArrayList and return whatever I have stored without having to recalculate a value I’ve already calculated.

The issue with that is that if I have a row like: 15744537121098240 that is bigger than a long, forcing me to use BigInteger instead, and even if arrays would store that many elements I don’t think time or memory would allow for me to pass test-cases.

I’m wondering if it’s too far for me to try solving it at my current skill level, or if there are any resources to help me solve it,

I’d really appreciate a response and Thanks again for an awe inspiring (at least for me) puzzle,

#6

Do you aware that a java long value has 8 bytes, that can stores whole numbers from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807 ?

#7

ur right, my bad, I forgot the L at the end thus getting integer value too large from intelij.
But I anyway have to figure out optimization which I will work on now…

#8

@java_coffee_cup:
also for context row 114 column 50’s value is: 659,098,269,441,164,911,071,480,492,639,771
so even if the indexes aren’t greater than long, the values the indexes contain are massively larger…

#9

If you are using nCr to brute-force a number and then determine its divisibility, and then doing a counting…this is a toy program only good for experiment.

I guess the nCr value of the first few triangles are good enough to be reused billion times for much larger scales.

#10

How to calculate the first 10**19 rows of pascal triangle in python?

I tried:
1- not storing last, never used values in rows (didn’t work cause of the r=c cases).
2- running pascal function only once, and using the value it returns for each input.
3- running my code on my computer, and it ran out of 8 GB RAM.
4- both memoisation and tabulation for the pascal function.

is python that slow, or am I that bad?
EDIT: it is not slow, half the people who shared their code used python