RedBtats's blog

By RedBtats, history, 9 months ago, In English,


i was trying to solve this problem on a2oj and it keeps giving me wrong answer and i don't know where is the mistake in my equations so any help is appreciated

my sol :

  • Vote: I like it
  • +4
  • Vote: I do not like it

9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Can you please briefly explain what everything in your code does? People aren't interested in debugging unreadable and unannotated code.

Also make a class for modular arithmetic for god's sake, with this thing: %mod))%mod )%mod; you're bound to make an error sooner or later.

Anyway this is how you can get out of those situations: make a program to generate thousands of small test cases. Make another "naive" solution (or in this case you can copy someone's accepted solution) and compare the outputs on the small test cases. This way you're bound to find a small test case where your program gives the wrong output. Then you can find out where your logic is wrong.

  • »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks for your hints , the code is really a mess , the problem is that i can't get an accepted solution for the problem as the website doesn't allow it and i searched google and it have no solution online

    i have cleaned my code a bit here

    first in my code i get the xck of k from 1 to x and store them in an array to use it later same for yck

    and i get the factorial of all numbers and the modulus inverse of all of them

    then i get

    only inclusive functions : we get them when the A subset is smaller than the B subset like : when X = 2 and Y = 3 so only inclusive functions we can get when A = 1 , B= 2,3 and when A = 2 , B=3 , so i loop on the lengths where len(A) < len(B) and i get the npk(len(B),len(A)) and multiply it by all combinations of B from Y with this length of B and after i get all the number of functions with all lengths of B to this certain length of A , i multiply it with the combinations of A from X with this length of A

    only surjective functions : we get them when the B subset is smaller than the A subset like in the previous example the only surjective functions are A=2,3 B= 1 and A=3 B=2 so i don the opposite of the only injective functions but here the number of functions i get differently i get the factorial of the length of B to distribute all elements of B on A and then the rest of places of A i put on them the rest of elements of B with all the combinations to do so

    bijective functions : we get them when length of A is equal to B so i loop on all equal lengths and compute the number of functions by getting all the permutations of distribute B elements on A without repetitions

    the total number of functions : we loop all over the lengths of A and B and get all the diffrent permutations of this two lengths

    if even u could solve it and give me the accepted solution i would be grateful

    • »
      9 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      You can always write a completely naive, brute-force solution that iterates over all possible functions or something like that. It doesn't need to be fast enough or anything. But make something that is "obviously correct" and compare its outputs to the outputs of your program, with thousands of small inputs.

      I can look at your code later but try this. That's the single most effective way to find bugs or mistakes in thinking.