Hello all, I'm currently struggling in this question, and cannot seem to find a direction in which I should approach this question. This question was asked in an online assessment on hackerrank yesterday. Any help or direction in which I should tackle this will be really greatful! Thanks.

Edit 1. I've mentioned my thought process as of yet in the comments.

Edit 2. Also, before downvoting, can you please mention the reason, so that I can learn what part of this blog I posted is causing the trouble, thanks.

Hello all, sorry for this lame doubt, but I could not find any answer online.

Why is it that when implementing a 0-1 BFS, a visited array isn't necessary, while in Dijkstra it is necessary. According to cp-algorithm for dijkstra,

"Therefore we need to make a small modification: at the beginning of each iteration, after extracting the next pair, we check if it is an important pair or if it is already an old and handled pair. This check is important, otherwise the complexity can increase up to O(nm)."

Shouldn't the same be applicable to 0-1 BFS also? And if not, why do we require it for Dijkstra?

Me and my friends have been trying to create a Gym contest. But after entering the contest, we get the following page :

We can open the problem list page, but are not able to open any problem. Also, one more thing we noticed was that, those who had rating below 1600 were able to participate, and those with 1600+ were getting this error. I've never created a gym contest before, so if there is something I'm messing, please let me know.

I was wondering what is a good estimate for the upper bound on the number of operations, which can be done under a second. So I decided to test and come up with a result. But the more I test on different systems, the more confusing it becomes for me. Below is the code which I used for testing, and I found widely varying results:

#include <iostream>
#include <ctime>
using namespace std;
#define int long long

const int N = 9e6;
int a[N], b[N];

signed main()
{
    int tt = 1000*clock()/CLOCKS_PER_SEC;

    for(int t=1; t<=100; t++)
    {
        for(int i=0; i<N; i++)
            a[i] = i%897896;
    }

    cout<<1000*clock()/CLOCKS_PER_SEC-tt<<"ms\n";
}

The results are as following. Note, I have a 64 bit Linux OS, with g++ 9.3.0

• On my system with g++ -std=c++17 : 2436 ms
• On my system with g++ -std=c++17 -static -O2 : 1551 ms
• On Codeforces Custom Test with C++17 : 4641 ms
• On Codeforces Custom Test with C++17 (x64) : 892 ms
• On Windows 8.1 (x64 VBox) with C++14 : 2015 ms

I wanted to ask, what is the reason behind such a drastic variation among different systems? Also, what should be a good estimate for the number of operations under a second?

I'm really sorry if this post sounds stupid, but I'm currently struggling in DP and want to tackle every problem in every possible aspect. The question states that we're given a particular capacity weight W, and we have N items, with ith element having v[i] value and w[i] weight, and we want to maximize the total value we can achieve ( Basically a knapsack problem ). Constraints are as follows,

W <= 1e4;
vi <= 1e9;
wi <= 1e4;
N <= 1e4;

This question can be done, in O(N*W) Time and Space complexity using both top-down and bottom-up approach, and I can further reduce the space to O(2*W) and time O(N*W) using bottom-up approach [link to the bottom-up approach : Link], but I'm unable to think of a similar space-reduced top-down approach. Any intuition behind implementing the "state-reduced" top-down approach will be greatly appreciated.