Can anyone kindly elaborate the solution of topcoder srm 800 div 2 400 pointer problem?? Topcoder has not yet released any editorials and so I am having a hard time trying to figure out the solution Thanks in advance...

# | User | Rating |
---|---|---|

1 | Benq | 3650 |

2 | Radewoosh | 3648 |

3 | tourist | 3579 |

4 | ecnerwala | 3551 |

5 | Um_nik | 3494 |

6 | Petr | 3452 |

7 | ksun48 | 3432 |

8 | jiangly | 3349 |

9 | maroonrk | 3338 |

10 | Miracle03 | 3314 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 211 |

2 | awoo | 187 |

3 | Errichto | 186 |

3 | rng_58 | 186 |

5 | SecondThread | 182 |

6 | Um_nik | 176 |

6 | Ashishgup | 176 |

8 | maroonrk | 173 |

9 | antontrygubO_o | 171 |

10 | -is-this-fft- | 168 |

The topic of this blog comes from this problem in the link https://codeforces.com/contest/20/problem/C

I decided to apply BFS to find the shortest path from 1 to n. In the internet, I found almost every article saying BFS cannot be applied to find shortest path in a unevenly weighted graph. Well, I am unable to understand why so. I applied the BFS with a little amount of tweak.

Initially when a node is visited, the shortest distance of that node from origin is set as : distance of node from origin=distance of its parent from origin + weight of the edge through which the node is getting discovered.

If we visit a node that has already been visited, then we check whether this new path to the already visited node is shorter than the previous path through which it was visited. If so, then update the shortest distance of the already discovered node from the origin and change the parent accordingly.

This is my code with the above approach :- https://codeforces.com/contest/20/submission/102479947

I am getting wrong answer as you can see. I do not ask you to debug my code. But I want to know isn't my approach valid? I infact feel that this approach can be used to find shortest path to all the nodes from a single vertex instead of using Djikstra.

Any comments???.....

Thanks in advance. Please kindly copy-past the links in your browser if you want to view the above links. I do not know how to paste links in the blog

Hello community, We all know that the 2 properties for a DP problem are 1) Overlapping Subproblems 2) Optimal Substructure . So, when we start doing DP problems, many like me first try to find out whether the problem can be solved recursively and if so does it have overlapping subproblems. But doing this during a contest takes a lot of time. People who are able to comfortably solve DP problems during a contest, do you guys really check these two patterns , whether they exist in the problem or do you look for any other insights??

Thank you if you choose to reply in the comments

Hello all, I am trying to find the complexity of the below code

"#include <bits/stdc++.h>

using namespace std;

int main() {

```
long long int n;
cin>>n;
vector<int>factors[1000001];
for(int i=2;i<=n;i++)
{
for(int j=1;j*i<=n;j++)
{
factors[j*i].push_back(i);
}
}
return 0;
```

}"

What I am mainly doing in the code is trying to store factors of all the numbers from 1 to n (n<=1000000). As you can see , factors is a vector of vectors. factors[i] will store all the factors for number i. The code works as follows 1. Fix a number i in the outer loop 2. For all the multiples of i that lies within n, push i as it's factor-->this is being done in the inner loop. According to my calculation, the complexity should be nlog(n) which should easily pass in a time limit of 1s but when I am running the above code on Codechef compiler with n=1000000, the execution time is coming >2s.

If anyone can kindly help, I will be highly obliged. Thank you..

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/14/2021 16:45:53 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|