Code optimization | C++ | Sololearn: Learn to code for FREE!
Новый курс! Каждый программист должен знать генеративный ИИ!
Попробуйте бесплатный урок
+ 1

Code optimization | C++

Hi I have an input vector of string. Each string has space separated two integers. For example, vector<string> inp = {"1 2","2 5"} This means there are two input as below: 1-> end row and 2-> end col 2->end row and 5->end col for each input, we need to add one value to existing value from row 1 col 1 to end row and end col. After all the operations, we need to find out max value count for entire matrix. We can assume matrix initial state as 0 for all cells. Please find attached code for same. As it is brute force, I am getting Time Limit Exceeded. Can any one suggest the optimal approach? I will try to take it forward and implement then. https://www.sololearn.com/en/compiler-playground/ch9iQ8W0DVGR Thanks in advance...!

20th May 2024, 10:55 AM
Ketan Lalcheta
Ketan Lalcheta - avatar
6 ответов
+ 4
The TLE didn't happen for me when I tried both of your sample inputs within the code. Did you resolve the problem? I see an opportunity to optimize the parsing code. Though it wouldn't make a measurable difference, at least the code would be more elegant: //#include <string> #include <sstream> . . . //size_t idx = one.find(' '); //int row = stoi(one.substr(0, idx)); //int col = stoi(one.substr(idx + 1)); int row, col; std::istringstream issOne(one); issOne >> row >> col; This is a faster way to extract row and col, as it eliminates creating intermediate substrings and function calls to stoi(). StringStream is optimized to parse and perform the int conversion.
20th May 2024, 5:24 PM
Brian
Brian - avatar
+ 3
You can use a technique called difference array (or 2D prefix sum) which allows you to efficiently perform range updates on a 2D grid. This will significantly more efficient than the brute force method, reducing the time complexity to O(N+R×C), where, 𝑁 is the number of input ranges, 𝑅 and 𝐶 are the number of rows and columns in the matrix, respectively. Check this link: https://blog.garybricks.com/2d-prefix-array-and-2d-segment-tree-overview
20th May 2024, 5:08 PM
`нттየ⁴⁰⁶
`нттየ⁴⁰⁶ - avatar
+ 2
" large number for rows and cols like 10 power 4 inputs and each has row and col as 10 power 4." have you considered threading? https://www.geeksforgeeks.org/maximum-in-a-2d-matrix-using-multi-threading-in-cpp/
21st May 2024, 11:00 AM
Bob_Li
Bob_Li - avatar
+ 1
I wanna make sure my algorithm is proper and efficient before I shift to threads
22nd May 2024, 2:32 AM
Ketan Lalcheta
Ketan Lalcheta - avatar
0
Thanks Brain for this tip. TLE will happen if input number is very large and when it has large number for rows and cols like 10 power 4 inputs and each has row and col as 10 power 4.
21st May 2024, 5:32 AM
Ketan Lalcheta
Ketan Lalcheta - avatar
0
Hi `нттየ⁴⁰⁶, Thanks for sharing this. I had this prefix sum approach in mind , but was confused to apply this in the current scenario. As far as I know, for prefix sum method, we precompute everything based on static input of matrix or array. Query range is in variable and it does not modify the content of matrix or array. How to make it work in current scenario? Here, each query input modifies the input values of matrix cells by 1.
21st May 2024, 5:35 AM
Ketan Lalcheta
Ketan Lalcheta - avatar