Find the nearest clone Discussions |

6 years ago+ 0 comments

A neat problem, let down somewhat by its testcases and Editorial :(

Firstly, as many people have mentioned, nearly all the testcases have "-1" as the solution: it's not hard to add some simple testcases that give a bit of variety e.g. https://pastebin.com/2MggcfBT

Secondly, the complexity analysis of the Editorial solution is wrong: the following snippet generates a testcase, obeying the given constraints, that will leave the Editorial solution grinding away for minutes on end:

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int main()
{
    // Generate a testcase that triggers O(N^2) performance
    // in Find the Nearest Clones Editorial solution.
    // 1'000'000 nodes and 1'000'000 edges, so within
    // the allowed constraints!
    const int n = 1'000'000;
    vector<pair<int, int>> edges;
    vector<int> colours(n);
    colours[0] = 1;
    for (int i = 0; i < n / 2; i++)
    {
        edges.push_back({1, i + 2});
        colours[i + 1] = 1;
    }
    for (int i = n / 2; i < n; i++)
    {
        edges.push_back({1, i + 1});
        colours[i] = 2;
    }

    cout << n << " " << edges.size() << endl;

    for (const auto& edge : edges)
    {
        cout << edge.first << " " << edge.second << endl;
    }

    for (const auto colour : colours)
    {
        cout << colour << endl;
    }

    cout << 2 << endl;

    return 0;
}

This should probably be added as a testcase - it would be interesting to see how many other solutions also choke on it!

(Note that a solution whose worst-case performance is equal to the claimed performance of the Editorial is possible, with a little bit of extra work :))

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge