HackerRank Hack the Interview VI (Asia Pacific) "0-1 Graph" author's solution is wrong

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

HackerRank Hack the Interview VI (Asia Pacific) is a contest with Amazon gift cards worth up to $500 as prizes for top 3. I found one of its problems' official solution wrong. I sent message to its author a day ago but I haven't got a reply yet. Therefore, I make this post to get some attention from the community.

Problem , Editorial

Problem Setter's code :

#include<bits/stdc++.h>
using namespace std;
vector<int> g[200001];
long maxSum(int n, vector<vector<int>> edges){
    for(auto j:edges){
        g[j[0]].push_back(j[1]);
        g[j[1]].push_back(j[0]);
    }
    queue<int> q;
    vector<bool> vis(n+1);
    vector<int> d(n+1);
    q.push(1);
    vis[1] = true;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : g[v]) {
            if (!vis[u]) {
                vis[u] = true;
                q.push(u);
                d[u] = d[v] + 1;
            }
        }
    }
    int curmin = 1e9;
    long sum = 0;
    for(int i=n; i>=1; i--){
        if(d[i]>curmin) d[i] = curmin;
        curmin = min(curmin, d[i]);
        sum += d[i];
    }
    return sum;
}

int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> edges;
    for(int i=0; i<m; i++){
        int u,v;
        cin >> u >> v;
        edges.push_back({u,v});
    }
    long ans = maxSum(n,edges);
    cout << ans << endl;
}

The setter's solution is wrong. Consider the following test case:

The setter's solution outputs 4 with the following d[].

d: 0 1 1 2

But it's not possible to have such d[]. If d[4] = 2, then d[2] >= 2. Since d[3] <= 1, it's impossible. The answer should be 3 with the following d[].

d: 0 1 1 1

My submission during contest can pass the above test case. I am not sure whether it's correct or not, please help me verify.

My code

#include <bits/stdc++.h>
using namespace std;
/* nichijou */
template<class T,class U>
bool cmax(T & a, const U & b) {return a < b ? a = b, 1 : 0;}
template<class T,class U>
bool cmin(T & a, const U & b) {return b < a ? a = b, 1 : 0;}
/* data type */
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define F first
#define S second
/* STL container */
typedef vector<int> vi;
typedef vector<ll> vll;
#define SZ(a) ((int)(a).size())
#define ALL(a) begin(a), end(a)
#define CLR(a) (a).clear()
#define BK(a) ((a).back())
#define FT(a) ((a).front())
#define DB(a) (a).pop_back()
#define DF(a) (a).pop_front()
#define PB push_back
#define EB emplace_back
/* I gave you my heart and then you turned around. */
void _BG(const char * s) {cerr<<s<<endl;}
template<class T, class ... TT>
void _BG(const char * s,T a, TT...b)
{
    for (size_t c = 0; *s && (c || *s != ','); cerr << *s++)
        c += count(ALL("([{"),*s) - count(ALL(")]}"),*s);
    cerr << " = " << a;
    if (*s) {
        cerr << ", ";
        ++s;
    }
    _BG(s,b...);
}
#ifdef PR3PONY
#define BG(...) do { \
    cerr << __PRETTY_FUNCTION__ << ':' << __LINE__ << ": "; \
    _BG(#__VA_ARGS__,__VA_ARGS__); \
} while(0)
#else
#define BG(...)
#endif
/* Good Luck && Have Fun ! */
const int N = 2e5 +87;
vector<int> g[N];
int d[N], p[N], cc;
int find(int x) {return p[x] == x ? x : p[x] = find(p[x]);}
void meld(int a, int b)
{
    a = find(a), b = find(b);
    if (a == b)
        return;
    --cc;
    p[b] = a;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for  (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    fill_n(d, n + 1, N);
    d[1] = 0;
    vector<int> q = {1}, nq;
    int mx = 1;
    cc = 1;
    p[1] = 1;
    int ptr = 2;
    for (int k = 0; q.size(); ++k) {
        while (p[ptr])
            ++ptr;
        while (!(ptr == mx + 1 && cc == 1)) {
            d[ptr] = k;
            mx = max(mx, ptr);
            q.push_back(ptr);
            p[ptr] = ptr;
            ++cc;
            for (int v : g[ptr])
                if (p[v]) 
                    meld(v, ptr);
            while (p[ptr])
                ++ptr;
        }

        nq.clear();
        for (int u : q) {
            for (int v : g[u]) {
                if (d[v] != N)
                    continue;
                d[v] = k + 1;
                mx = max(mx, v);
                ++cc, p[v] = v;
                meld(v, u);
                nq.push_back(v);
            }
        }
        swap(q, nq);
    }
    //for (int i = 1; i <= n; ++i) cerr << d[i] << " "; cerr << endl;
    ll ans = 0;
    for  (int i = 1; i <= n; ++i) {
        ans += d[i];
    }
    cout << ans << endl;
}

Comments (16)

Show archived | Write comment?

robinz62

4 years ago, # |

I did the problems in this contest as well and came up with the same test case. There were so many things wrong with the contest:

The default input-reading code is very often wrong (I program in Java)
The test case input format for Q1 did not match the description
There was a problem with the test case checker in Q3 (not sure what happened: could not AC in Java but rewrote in C++ and AC'd)
The discussions tab was not working, which really exacerbated the problem with Q2.

The contest quality was embarrassing to say the least. Not sure what happened with hackerrank...

→ Reply

4 years ago, # ^ |

← Rev. 2 →

I thought a lot about the problem and a working solution seems quite involved. Regarding your code, I haven't looked into what it does/dissected it at all, but I just tried running it on the test case

6 6
1 3
3 4
4 5
5 2
4 6
6 2

and your code outputs 6, although I believe the answer should be 5 (only edge (1, 3) can have weight 1).

pr3pony

6 is correct. let (1,3), (2, 6), (4,6) have weight 1 and others have weight 0, the resulting d[] is d: 0 1 1 1 1 2

my code that outputs edge weights

Ah I see. My bad.

alon276

← Rev. 3 →

-10

I mean... I just read the statement and I noticed that the sample is wrong. You see the graph with the weights on it, and the array d is just different than reality.

Edit: I tried to say that you didn't even need to run any codr to see there was something wrong.

bicsi

+135

Guys, there’s an easier way to handle issues about Hacker.* contests than to complain about them:

Spoiler

-is-this-fft-

+76

I think such blogs are necessary, otherwise people don't know to avoid them.

BlaringBlaze

-11

Why should they stop using it. Many people start to learn cp from these Platform. People cannot directly jump to CodeForces. HackerEarth HackerRank and CodeChef all these has main purpose to teach you cp. You can learn there if you are a beginner where as you can not learn anything in CodeForces. Why are you misguiding people. I request every one to go to any platform you like and learn cp. These people are red that does not mean their opinion is correct.

+20

Opinions by definition can't be correct or incorrect.

Anyway the arguments in your comment have almost nothing to do with why we avoid these sites.

-19

So what do you recommend sir. Where should new people go to learn cp tell me some better place to learn. Opinion can be proved wrong. you can say earth is flat but it can be proved wrong easily. also do recommend me something i asked you for. don't just ask people to stop using a platform. It surely might not be good for experienced programmers but it is good for people who want to start. so in that case your opinion is wrong sir.

+12

I learned the first principles from train.usaco.org. And AtCoder beginner contests have a lot of educational problems. And CSES has versions of many "classical" problems.

And the issue here was not beginner-friendliness but poorly prepared problems.

And stop with all this experienced vs beginner stuff. Every red has been a beginner once, the converse doesn't hold. I have had to learn all this stuff too. It's not as if I don't know what it's like to be a beginner.

darshanps

+16

Hello,

I am Darshan, I manage the Content Team at HackerRank. We would like to apologize for the issues in this challenge in our recent contest.

For the complete correctness of the challenge, our author's greedy solution does not suffice, as indicated correctly by you.

We benchmark our challenges through multiple coders, and with this specific challenge, a corner case was not discovered by us which resulted in providing an incorrect challenge. We are carefully evaluating our internal practices in order to avoid such issues in the future.

The Greedy Solution provided as part of the Problem Setters solution missed on this key test case, we will be updating the solution here soon.

We are really sorry for the inconvenience caused and as a result, we have decided to not consider this challenge in the contest to calibrate the results and will update the leaderboard accordingly. We are working on making our problems more robust every day. Your feedback is much appreciated and will help us improve our challenge quality.

Hope to see you again in future contests! Thank you.

+26

Of course people make mistakes, it's more about standards and procedures we have to prevent such mistakes.

Do you stress test your official solution against a simple brute force? I did that to your solution and there are tons of counterexamples. I wouldn't call it a "corner case". (Full disclosure: I only got such results after I added permuting of vertices to the generator. So it's possible you did this but rushed it. Still bad, but a lot better.)

My code, saved as a.cpp

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 25;

int n, m;
vector<pair<int, int>> edges;

int try_ass (int mask) {
  vector<vector<int>> dist (n, vector<int> (n, 1e7));
  for (int i = 0; i < n; i++) {
    dist[i][i] = 0;
  }
  
  for (int i = 0; i < m; i++) {
    int u = edges[i].first;
    int v = edges[i].second;
    if (mask & 1 << i) {
      dist[u][v] = 1;
      dist[v][u] = 1;
    } else {
      dist[u][v] = 0;
      dist[v][u] = 0;
    }
  }

  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }

  int ans = 0;
  for (int i = 1; i < n; i++) {
    if (dist[0][i - 1] > dist[0][i]) return 0;
    ans += dist[0][i];
  }
  return ans;
}

int main () {
  ios::sync_with_stdio(false);

  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;

    edges.push_back(make_pair(u, v));
  }

  int ans = 0;
  for (int i = 0; i < 1 << m; i++) {
    ans = max(ans, try_ass(i));
  }
  cout << ans << endl;
}

Generator, saved as ag.cpp

#include <iostream>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

set<pair<int, int>> edges;

pair<int, int> edge (int u, int v) {
  return make_pair(min(u, v), max(u, v));
}

int main (int argc, char **argv) {
  srand(atoi(argv[1]));
  int n = atoi(argv[2]);
  int m = atoi(argv[3]);

  cout << n << " " << m << endl;
  for (int i = 2; i <= n; i++) {
    int u = 1 + rand() % (i - 1);
    int v = i;
    edges.insert(edge(u, v));
  }

  for (int i = 0; i < m - (n - 1); i++) {
    int u, v;
    do {
      u = 1 + rand() % n;
      v = 1 + rand() % n;
    } while (u == v || edges.count(edge(u, v)));
    edges.insert(edge(u, v));
  }

  vector<int> perm (n + 1);
  for (int i = 0; i <= n; i++) {
    perm[i] = i;
  }
  random_shuffle(1 + perm.begin(), perm.end());
  
  for (auto it = edges.begin(); it != edges.end(); it++) {
    cout << perm[it->first] << " " << perm[it->second] << endl;
  }
}

Shell script

for i in `seq 1 100`; do
    echo $i
    ./ag $i 10 12 > a.in
    ./a < a.in > a.ans
    ./ae < a.in > a.out
    diff a.ans a.out
done

Output

1
2
3
1c1
< 12
---
> 15
4
5
1c1
< 15
---
> 17
6
7
1c1
< 11
---
> 13
8
1c1
< 10
---
> 13
9
1c1
< 10
---
> 11
10
11
1c1
< 11
---
> 13
12
13
14
15
1c1
< 14
---
> 17
16
17
18
1c1
< 9
---
> 10
19
20
1c1
< 10
---
> 11
21
22
23
24
1c1
< 11
---
> 16
25
1c1
< 10
---
> 13
26
27
1c1
< 10
---
> 12
28
29
30
31
1c1
< 13
---
> 15
32
1c1
< 12
---
> 14
33
1c1
< 9
---
> 15
34
35
36
1c1
< 9
---
> 10
37
1c1
< 11
---
> 18
38
39
1c1
< 9
---
> 15
40
41
42
1c1
< 12
---
> 15
43
1c1
< 10
---
> 11
44
1c1
< 10
---
> 14
45
46
47
48
49
1c1
< 10
---
> 12
50
1c1
< 10
---
> 17
51
52
1c1
< 10
---
> 11
53
1c1
< 14
---
> 16
54
1c1
< 14
---
> 16
55
1c1
< 13
---
> 15
56
1c1
< 9
---
> 13
57
58
1c1
< 10
---
> 12
59
1c1
< 9
---
> 13
60
61
62
63
1c1
< 9
---
> 12
64
1c1
< 10
---
> 11
65
66
67
1c1
< 10
---
> 12
68
69
70
71
1c1
< 10
---
> 11
72
73
74
75
76
1c1
< 10
---
> 17
77
78
1c1
< 13
---
> 16
79
1c1
< 10
---
> 11
80
81
1c1
< 14
---
> 15
82
83
1c1
< 12
---
> 14
84
85
86
1c1
< 11
---
> 16
87
1c1
< 13
---
> 15
88
89
90
1c1
< 10
---
> 11
91
92
1c1
< 10
---
> 12
93
94
1c1
< 9
---
> 11
95
1c1
< 11
---
> 13
96
97
1c1
< 11
---
> 12
98
1c1
< 9
---
> 10
99
100

Even more importantly, do you ask authors to prove their solutions? The editorial doesn't say anything about why this greedy solution should even work. Do you have a proof and it is just flawed?

navneet.h

Is this question even solvable, in the given constraints.

kwangg

Will you also update Problem 1 so that the test cases are formatted correctly (as indicated in the problem statement and the sample test cases) and update the leaderboard accordingly?

Hi Darshan, you responded to my other comment about the errors in problem 1 with the private message "We have checked all other questions, and they are correct. The issue was with only the graph problem as I mentioned in my post."

That's incorrect. If you look at problem 1, the problem statement clearly states "The first line contains two space separated integers M and N." Indeed, the Sample Input 0 has M and N on the first line, and the test case (case 0) only passes when M and N are treated as being on the same line. However, the real cases all have M and N on separate lines, and there was no way to know that this was the case.

As a result, every user's CORRECT submission was rejected. In my case, I believe if the question was NOT broken, my placement would have been 2nd place for $250 rather than 3rd place for $100, so I would ask that you correct this issue as well.

Thanks for taking our feedback here!

pr3pony's blog