### pr3pony's blog

By pr3pony, history, 2 months ago,

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 Setter's code : The setter's solution is wrong. Consider the following test case: 4 3 1 3 3 4 4 2  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 • +69  » 2 months ago, # | +6 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... •  » » 2 months ago, # ^ | ← Rev. 2 → +6 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 case6 61 33 44 55 24 66 2 and your code outputs 6, although I believe the answer should be 5 (only edge (1, 3) can have weight 1). •  » » » 2 months ago, # ^ | +5 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 2my code that outputs edge weights •  » » » » 2 months ago, # ^ | 0 Ah I see. My bad.  » 2 months ago, # | ← 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.  » 2 months ago, # | +135 Guys, there’s an easier way to handle issues about Hacker.* contests than to complain about them: SpoilerStop using these platforms. •  » » 2 months ago, # ^ | +76 I think such blogs are necessary, otherwise people don't know to avoid them. •  » » » 7 weeks ago, # ^ | -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. •  » » » » 7 weeks ago, # ^ | ← Rev. 3 → +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. •  » » » » » 7 weeks ago, # ^ | -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. •  » » » » » » 7 weeks ago, # ^ | +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. •  » » » » » » » 7 weeks ago, # ^ | ← Rev. 2 → 0 When I had no idea about cp I searched which is the best platform and intelligent people like you recommended codeforces is the best platform. then i came here i coulden't solve a single question. then I went to hacckerrank then moved to hackerearth then i came here. I think these sites have converted more people into coders. than train.usaco.org could ever do. criticism is good but i just don't think it's good idea to tell people to avoid these sites.  » 7 weeks ago, # | +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. •  » » 7 weeks ago, # ^ | +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 #include using namespace std; const int MAX_N = 25; int n, m; vector> edges; int try_ass (int mask) { vector> dist (n, vector (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 #include #include #include #include using namespace std; set> edges; pair 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 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 scriptfor 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  Output1 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? •  » » » 7 weeks ago, # ^ | +2 Is this question even solvable, in the given constraints. •  » » 7 weeks ago, # ^ | +9 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? •  » » 7 weeks ago, # ^ | ← Rev. 3 → +8 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!
•  » » » 7 weeks ago, # ^ |   0 Yes, this will also be fixed. We have updated the tests so that n and m now have space separated input as given in the input format. Leaderboard will be updated accordingly.