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.

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

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?

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

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

Hi, thank you for the update!

All tests and validators pass correctly now

*(maybe we can remove these posts from the puzzle discussion)*

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,

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 ?

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â€¦

@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â€¦

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.

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