VAIMIN - Editorial

general
, , , , ,
5

Can anyone suggest a good fast way to be good at combinatories and counting?

I mean should we study it from some math book,or solve more problems?

4 Likes
6

If I am not wrong, the problem doesn’t mention about paths and grid cells anywhere but in the above editorial i am seeing all about grids.

7

This was one hell of a good question. I really suck at these kind of 2D optimization problems. Kudos to the setter :smiley:

8

One of The best Editorials I have ever read !!!

Thank You very much @vaibhav18197

9

This problem is a direct application to Bertrand’s Ballot Theorem here. Read the proof by reflection method for understanding.

1 Like
10

Is there a mistake in this equation in the explanation?

Ways=(x1+x2+y1+y2)C(x1+x2)−(x1+x2+y1+y2)C(x1+x2+(c−1)).

For me it should have been:

Ways=(x2-x1+y2-y1)C(x2-x1)−(x2-x1+y2-y1)C(y2-x1+(c−1)).

Maybe, I misunderstood the first part of the explanation…

1 Like
11

Nice Editorial.
Learnt New Concept.

12

You did a good job nonetheless. Practice more and get it next time :slight_smile:

1 Like
13

I am as clueless as you because i just read the problem and did minor corrects for formatting xD. @vaibhav18197 can help you here :slight_smile:

14

@vaibhav18197, can u please check my code!!

15

Yes. I need tips as well :frowning:

16

Another related problem: Chef and Big Matrix :slight_smile:

17

xD . Reduce the problem to path and grids then from the superficial storyline.

2 Likes
18

D. Knuth will help you! 4 parts of “The Art of programming” is a bible for an algorithmic programmer. You can start with “Concrete Math”(Knuth and Patashnik). https://www.csie.ntu.edu.tw/~r97002/temp/Concrete%20Mathematics%202e.pdf

7 Likes
19

And here comes the one and only…@mgch xD xD xD xD xD

3 Likes
20

Thank u sooo much @mgch,u really are an inspiration for us :slight_smile:

21

Earlier query answer -

In modular maths -

This relation is working because.

(inv[k]*fac[k])\%MOD=1;

\implies (inv[k+1]*fac[k+1])\%MOD=1;

multiply both sides by inv[k]\%MOD;

\implies (inv[k+1]*fac[k+1]*inv[k])\%MOD=inv[k]\%MOD;

\implies (inv[k+1]*(k+1)*fac[k]*inv[k])\%MOD=inv[k]\%MOD;

from (1)

\implies (inv[k+1]*(k+1)*1)\%MOD=inv[k]\%MOD

3 Likes
22

Thank You very much Sir! I got it.

1 Like
23

Abra-Kadabra- and we’re done. Have a check for your comment @aryanc403 and tell if any correction is needed.

1 Like
24

Your code has complexity of pqM. (p*q for the dp and M for find operation in each recursive call)
Constrains for third task were: p,q < 2000 and M < 3000
So it would even exceed 10^9, hence the TLE.

Also, your code was missing the following condition check:
if(good > p or bad > q) return 0;
Hence, your previous submission were getting RE(SIGSEGV). Since it may happen good ~ p + q = 4000 → that would exceed your array limits.

I incorporated the above mentioned changes in your code & got this code pass 1st subtask.

Hope that helps. :slight_smile:

2 Likes