However it maybe, we’ll do it this time 
1 Like
Karan be like : swagat kro hamara 
2 Likes
Nothing like that. I am just so excited!
HOPE FOR NO MUCH MATHS THIS TIME
4 Likes
I think there’s a problem with the constraints of TANDON, normally a problem accepts a solution which runs in time which is a small multiple of the minimum (expected) time. My solution seems efficient and takes about 2-3 secs in worst case (even with all optimization hacks). Please verify if the time limit is 1 sec or 3 secs.
1 Like
In problem Bacterial Reproduction, I got a different verdict for the exact same solution when resubmitted it. Can anyone explain to me how it happened and can admin look into it as the only test case failed due to TLE in one solution got accepted for the same solution when I resubmitted the same code.
Links to submissions: Submission 1
Submission 2
1 Like
JIIT’s time limit is real strict, but most likely because I decided to pursue Cayley instead of going to a combinatorics solution instead.
1 Like
@just1star
Can you please tell your solution idea ? As soon as I saw JIIT, mind went blank…no approach comes to mind even for 10 pts… 
bhai any try for last one??
1 Like
I also had a hard time optimizing the last 10. Firstly I reduced every polynomial into half which helped me get to 90, however after that I have to use polynomial division and a few minor optimizations to the N ^ 2 operations for the full 100.
Also that 0.06s use combinatorics and I did say I probably would have had an easier time if I went in that direction instead 
1 Like
How did you guys approached JIIT, I wasn’t able to think of any optimal solution for it. I haven’t studied many topics so bummer there but it’d be very helpful if someone can share his approach
Initially I was also trying using GFs and NTT. With those I was only getting 90 points Then I thought of some other solutions and managed to think of a inclusion-exclusion one.
1 Like
can u tell me how u created GFs… im thinking in the same way but unable to make GFs thats satisfied the solution… maybe i need more practice to make GFs…
I did not actually use generating function. Only inclusion exclusion and NTT. later I eliminated NTT to get full score but for generating function you can think in this direction:
After reducing problem to this problem => Count number of ordered sequences of length “q” where each number choosen is from the set {1, 2, 3, 4. … n} and from this set first x numbers are appearing odd number of times and rest are appearing even number of times.
The answer to above problem is actually the coefficient of x^q in (1+x^2/2!+ x^4/4! …)^(n-a)* (x/1! + x^3/3! + x^5/5! …). which is further equal to coefficient of x^q in (e^x+e^-x)^(n-a) * (e^x-e^-x)^(a) (using taylor expansion). Now we have to expand this sequence using binomial expansion of only two terms.
This is my idea behind GF but I did not think further than this as some other solution came to my mind.
2 Likes
Always Add (+ or -) 0.10 seconds because everytime CPU time differs.
For example, you have solved a soln for 1.60 seconds, next time it can give 1.54 or 1.66 seconds for example, but the difference won’t be that high.
2 Likes
this part is simple for arranging the odd number of times by only row or by only column…
if i take both at same time like odd number of times row and column at same time then i got stuck with some extra cases… that part i’m not able to solve by GF… i just waste my 8 days on this problem…
by the way what is NTT ?? never heard about it…
and thanx…
NTT is “Number theoritic transform” used for fast multiplication of two polynomials where coefficients of final polynomial is required modulo some number.
1 Like
There can be minor difference in time taken depending on load. You code is almost taking 2 secs.
1 Like