The_mysterio's blog

By The_mysterio, history, 3 months ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By The_mysterio, history, 5 months ago, In English

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.

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

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

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By The_mysterio, history, 5 months ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

By The_mysterio, history, 5 months ago, In English

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

Read more »

 
 
 
 
  • Vote: I like it
  • -12
  • Vote: I do not like it

By The_mysterio, history, 8 months ago, In English

Hello Everyone, This is a just a thought that came to my mind. Normally we sort numbers with the time complexity of n log n where n is the number of numbers present in the array.Same for a list of characters. However, for a list of given strings,let us say all the strings are of equal length and that length is m. For comparing two strings we need at most iterations.So in that case , isnt the complexity (n^2)*m ???Because the recurrence relation will be T(n)=2*T(n/2)+ n*m---> where merging takes m units of time for each comparison of two strings... If anyone can clarify this doubt, It will be of great help.. Thanks in advance

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By The_mysterio, history, 8 months ago, In English

Hello Codeforces community, A newbie here.My name is Sayan Chaudhuri and I am from India. Although as you can see my rating is low, I particularly face high difficulty while solving problems based on games. Like problems of DIv 3C or Div2B which often are problems based on games, I find it extremely troubling to solve them. I just get bamboozled when I find the term "optimally" as it does not occur to me, what an optimal move could be...So, how do you guys approach these problems on games.. If anyone can give me some intution or any sort of other help that may help me to overcome this difficulty. round 668 div2 problem B Sequential Nim- this problem is an example. I am not just able to understand how to solve it.... Thanking you in advance...

Read more »

 
 
 
 
  • Vote: I like it
  • +15
  • Vote: I do not like it

By The_mysterio, history, 11 months ago, In English

Kindly help me with the solution of this problem https://codeforces.com/contest/1362/problem/D My solution https://codeforces.com/contest/1362/submission/82683708 Please help me to find out my error.It seems to me ,the statement *s.rbegin()!=s.size() is causing the problem but not finding any test case to understand why it should be wrong.. My algorithm is as follows... 1)check whether any two neighbouring vertices have same topic--->statement arr[i]==arr[u] does that where u is neighbour of i. 2)if not same,then I map the topic values given, to values starting from 1.So if the topic values avaialable are 2,4,5 then I map 2->1,4->2,5->3. The reason is I will be checking the condition as to whether there exists a topic number smaller than the topic number of current vertex being processed such that the current vertex has no edge to any other vertex having that smaller topic number. So,this mapping is stored in the mapping array. then I process each vertex and its adjacent vertices.The topics of the current vertex as well as the adjacent vertices are pushed into set s.Now if the above stated condition in the previous paragraph holds,then the last element of this set will obviously be not equal to size of the set.So we will be printing -1. Is there some misundrstanding here? Thanks in advance to anyone who will help this novice coder...

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it