Codeforces 560E – Solution with code



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

  • 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.

    Isha Agarwal May 24, 2020 3:34 pm Reply
  • How, total no. of paths from (0,0) to (i,j) is i+j C i, considering no black cell encounter?

    Nikhil Kumar May 24, 2020 3:34 pm Reply
  • I dont know that language. What is name of that language?

    Kuro Neko May 24, 2020 3:34 pm Reply
  • I almost exploxed, but i get it

    Subaru Kun May 24, 2020 3:34 pm Reply
  • May be its similar to rate in a maze problem.

    vivek kumar May 24, 2020 3:34 pm Reply
  • Exactly rat in a maze problem

    Saurav Anand May 24, 2020 3:34 pm Reply
  • Hey. Please make a video on Suffix Tree automation…

    Abhinav Jain May 24, 2020 3:34 pm Reply
  • 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 ?

    anant grover May 24, 2020 3:34 pm Reply
  • Really enjoy this problem 😀
    but you dont do codeforces solutions anymore?

    Grev May 24, 2020 3:34 pm Reply
  • thanks for sharing this problem 🙂

    Aparichit Singh May 24, 2020 3:34 pm Reply
  • 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.

    Janhavi Savla May 24, 2020 3:34 pm Reply
  • Great video.
    Great channel.
    Keep em coming.

    Thanks

    Abhiram R May 24, 2020 3:34 pm Reply
  • 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.

    Amish Sharma May 24, 2020 3:34 pm Reply
  • 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)

    Sarovar Vihar May 24, 2020 3:34 pm Reply
  • 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 😊😊

    Kartik Bagoli May 24, 2020 3:34 pm Reply
  • 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.

    Ayush Kumar May 24, 2020 3:34 pm Reply
  • nice one👍

    b naveen May 24, 2020 3:34 pm Reply
  • Hey man, Can you explain why some problems say to do ANS%10^9+7 something like that?

    Raj May 24, 2020 3:34 pm Reply
  • 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

    Shubham Saini May 24, 2020 3:34 pm Reply
  • hey man uh r just awsm….

    sujit kumar May 24, 2020 3:34 pm Reply

Leave a Reply

Your email address will not be published. Required fields are marked *