wanbo's blog

HackRank 101Hack is Coming! Start your new journey from here after ACM WF

By wanbo, 9 years ago, In English

Hello Coders,

The 25th edition of 101 Hack is here. This time we have 5 interesting challenges lined up for you.
The contest commences on 20th May 2015 at 16:30 UTC, and will run for 2 hours. You can sign up for the contest here.

You will get a Hackerrank T-shirt if you ranked in top 10.

The problem statements will be available in English and Chinese.

Problem Setters

PraveenDhinwa

Problem Testers

wanbo

GL&HF

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

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What's wrong with my solution for Devu and a Journey on Metro?

double solve(int n, int k, List<Edge>[] g) {
	long[] d = new long[n]; // d[v] = distance from 0 to v
	dfs(0, -1, g, d, 0);    // calculate distance using dfs

	double[][] mc = new double[n][n];

	for (int from = 0; from < n; from++) {
		double pr = 1.0 / g[from].size();
		for (Edge e : g[from]) {
			mc[from][e.to] = pr;
		}
	}

	double[] p = pow(mc, k)[0]; // some illegal Markov chain magic
	double ans = 0;
	for (int i = 0; i < n; i++) {
		ans += d[i] * p[i]; // expected value
	}

	return ans;
}

Or this is the right way but i have some mistakes in another part of code? May be problem with precision.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    I've just calculated P[k][v] — probability to be in vertex v in k steps. You can do it naively since k <= 50 and n <= 50. Instead of "some illegal Markov chain magic" :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Shocked by the performance of the top teams from the ICPC world final, we intended to make the problem relatively easy to make many people feel like [tourist].

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    i failed because of this :

    actual : 2.568375701948238E9

    expected : 2568375701.948237895965576172

    I did all calculations in doubles (there's no long double in java)

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe it is because of the precision checker's problem, I do not think 1e-6 will make precision problems for this kind of challenge.

    Anyone knows how codeforces implemented the precision checker?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You should find default CF checkers in Polygon.

      Is it a bug in some standard checker or was it written specifically for this problem?

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I've got some questions about editorial. Please, can someone prove me: Why minimal number of swaps <= 1 and why it's optimal to do swaps which decrease the string size as less as possible?

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

There seem to be problems with grading of Devu and a Journey on Metro, several people have complained that outputs that are (within precision margin) the same as expected ones are judged as incorrect.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Sorry about this, the implementation of the precision check has problem, it just check the absolute difference, and haven't check the relative difference, it is a disaster! As a tester, it is mostly my fault, because I just checked if cout << fixed << setprecision(5) and setprecision(6) and setprecision(7) will get the correct answer or not. I do not know the built-in precision checker only check the absolute difference. :(

    → Reply