failed test

[rain bolt]

trying to solve this question
https://codeforces.com/group/MWSDmqGsZm/contest/223339/problem/T
but i keep failing on test 32
used the website at the bottom of the page to get the recursive formula
c(n, r) = c(n-1, r-1) + c(n-1, r)
not sure if the problem comes from the formula or im doing smt else wrong

#include <iostream>
using ll = long long;

ll c(ll n, int r){
    if(n == r || r == 0) return 1;
    return c(n-1, r-1) + c(n-1, r);
}

int main(){
    ll n; int r;
    std::cin>>n>>r;
    std::cout<<c(n,r);
}

[tame echo]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[still pond]

the formula looks correct, but the numbers can get really large

and if the answer is k, your solution will actually call c k times

which means you should get timeouts for larger values of n and r

[rain bolt]

i realised that so i tried storing already computed values

#include <iostream>

using ll = long long;

ll table[65535][31];

void ini(){
    for(size_t i=0;i<65535;++i)
        for(size_t j=0;j<31;++j)table[i][j]=-1;
}

ll c(ll n, int r){
    if(r == n || r == 0)return 1;
    if(table[n][r] != -1)return table[n][r];
    table[n][r] = c(n-1, r-1) + c(n-1, r);
    return table[n][r];
}

int main(){
    ll n; int r;
    std::cin>>n>>r;
    ini();
    std::cout<<c(n,r);
}

now i get up to test 56

ill try a an approach using loops

[rain bolt]

!solved

[tame echo]

Thank you and let us know if you have any more questions!

This thread is now set to auto-hide after an hour of inactivity

[rain bolt]

forgot to say
changed the formula to be
(n*c(n-1, r-1))/r

#include <iostream>
using ll = long long;

ll c(ll n, int r){
    if(n == r || r == 0) return 1;
    return (n*c(n-1, r-1))/r;
}

int main(){
    ll n; int r;
    std::cin>>n>>r;
    std::cout<<c(n,r);
}

[still pond]

hmm, but the other formula was correct too, right?

so it's just about speed?

[rain bolt]

ye, it was also correct
just needed a more optimised solution

[teal thistle]

when will n will equal to r if it just go -1

for example n = 1 and r = 2

then it go n = 0 and r =1

so it stop because of r

[teal thistle]

then u need specify it

[rain bolt]

i pasted the link to the website with the question at the top

[rain bolt]

shouldve read it first

[teal thistle]

oh so u need implement specificly with recursion

it not allowed without right?

[rain bolt]

yes

luckily the last solution passed all tests

[teal thistle]

so u need make just this

right?

[rain bolt]

yup

[rain bolt]

tried using chat gpt at one point and i all i can say is llm's are bad at c++

[tame echo]

Did you mean: LLVM

[teal thistle]

do it not n/(r*c(n-1,r-1))?

[teal thistle]

huh

[teal thistle]

im looking her

[rain bolt]

what exactly do you mean by this

[teal thistle]

oh wait

so

wait

[rain bolt]

you tryna get a recursive formula with less calls?

[teal thistle]

right

i will done that without a recursion at all but btw

btw what is mean (-5)!

a wait