Блог пользователя wanbo

Автор wanbo, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • +39
  • Проголосовать: не нравится

»
11 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
11 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    11 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

    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. :(