wanbo's blog

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

By wanbo, 10 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

»
10 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
  • »
    »
    10 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
    • »
      »
      »
      10 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
  • »
    »
    10 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
  • »
    »
    10 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
    • »
      »
      »
      10 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
»
10 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
»
10 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
  • »
    »
    10 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