Codeforces 560E – Solution with code

20
40



This is a video editorial on the hardest problem on codeforces round 560. The problem deals with finding number of paths in a matrix using dynamic programming, combinatorial math and inclusion-exclusion.

Feel free to post your comments below. Cheers!

Problem Statement:

Solution Code:

Inverse Modulo:

Combinatorics:

Dynamic Programming:

Nguồn: https://dothihoa.com

Xem thêm bài viết khác: https://dothihoa.com/cong-nghe

20 COMMENTS

  1. Thanks for this, wonderful explanation. I submitted the code with this approach but still, I get Time Limit Exceed on test case 7. Any lead on how to resolve it will be helpful. I do regular programming on CodeChef but I am pretty new to Codeforces.

  2. I did it w/o using combinations , what I did was
    iterate through each element in the 2D integer array(which can be done while filling true or false in a boolean array ..black for false and white for true).. so I will be having 2 different arrays one boolean and other integer , now if ( boolean_array[i][j]==false) which means it is a black cell then integer_array[i][j]=true
    else do the following
    if i==0 and j==0
    then integer_array[i][j]=0
    integer_array[i][j]=integer_array[i-1][j]+integer_array[i][j-1] also check for 0th row or 0th column index respectively …at last the last element of the 2-D array will have the answer .. basically I have used a DP approach … Is it correct ?

  3. Hey Gaurav ! I really need your help!
    I started practicing on codechef and everytime I submit a problem ,I get a time-exceeded error.The output is correct but this error just doesn't seem to go whichever method I use(recursion ,DP,etc).I read online and used scanf,printf instead of cin,cout ,but I still am getting a Time limit error.I am wasting hours on a simple problem because of this.
    please go through my code:
    Question: https://www.codechef.com/problems/PALIN

    #include <iostream>
    #include <algorithm>
    #include<vector>
    #include <string>
    using namespace std;
    bool is_palin(long long int num);
    long long int next_palin(long long int n);
    int main()
    {
    int t;
    cin>>t;
    vector<long long int> a;
    long long int n;
    for(int i=0;i<t;i++)
    {
    cin>>n;
    a.push_back(next_palin(n));
    }
    for(int i=0;i<a.size();i++)
    {
    cout<<a[i]<<endl;
    }
    }

    bool is_palin(long long int n)
    {

    string s = to_string(n);
    int len=s.length();
    for(int i=0;i<len/2;i++)
    {
    if(s[i]!=s[len-i-1])
    return false;
    }
    return true;

    }
    long long int next_palin(long long int n)
    {

    while(1)
    {
    bool var=is_palin(n);
    if(var==true)
    break;

    else n++;
    }
    return n;
    }
    There is more more problem which I solved using both DP and recursion but getting the same error.

  4. Hello sir,
    I want a suggestion. Actually, I am practicing beginner level questions on codeshef. I am in Btech 3rd sem, and still I am struggling with beginner level questions. Please suggest me or help to do it in a better way because it is sometimes frustrating when I am not able to solve those problems.

  5. Hey Gaurav, what was your interview process with Directi like? Directi in my college only offers upto application engineer profile, how did you get a call for platform engineer? Frcrce rocks(except the rules)

  6. Greetings Sir,
    I am confused as to which language I should choose for competitive coding
    (1)Python
    Or (2)C++
    Please give your valuable comments and suggest best language for competitive coding purpose
    Thanks in advance 😊😊

  7. Hey Gaurav, I stumbled upon your channel while searching for CP. I'm in class 11 with Java, how do you suggest I get started with CP? I love simple programming, but a senior suggested that I try CP. We have just started 2D Array in school. Thanks.

  8. Thank You bhaiya…your videos help me alot….Can u make series or episodes On how to solve graph/trees problem in JAVA with code

LEAVE A REPLY

Please enter your comment!
Please enter your name here