facug91's blog

By facug91, history, 9 years ago, In English

Hi everbody! Well, I've been trying to understand the solution for this problem for a while, but I think I need a little help.

Link: https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&Itemid=99999999&category=571&page=show_problem&problem=4164

Solutions (all SWERC 2012): http://users.dsic.upv.es/swerc_12/ProblemSet2012/SWERC-2012-solution-outlines.pdf

Yes, it has a pdf with the solution explained. The thing is that there is a mistake (or I can not understand what they mean). They talk about a function SOD(x), which is Sum Of Divisors of x. But the SOD of 12, for example, clearly isn't 3, as they say in the pdf.

I hope someone can give me a hand with it, and if you have some extra topics I can read about, that might help me with this problem, would be great as well!

Thanks in advance.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By facug91, 10 years ago, In English

Hi everyone, I'm trying to solve this well-known problem, but with ternary search. I think it's possible, and in fact all the test cases I've proved pass, but I keep getting WA, so it might be some problems. If some one could help me, or tell me why this approch doesn't work. Here's my code:

#include <bits/stdc++.h>
#define EPS 1e-9
using namespace std;

double l, w;

double f (double x) {
	return x*(l-x-x)*(w-x-x);
}
double ternary_search () {
	double lo = EPS, hi = (((l<w)?l:w)/2.0)-EPS, mid1, mid2;
	for (int i=0; i<100; i++) {
		mid1 = lo + (hi-lo)/3.0;
		mid2 = hi &mdash; (hi-lo)/3.0;
		if (f(mid1) > f(mid2)) {
			hi = mid2;
		} else if (f(mid1) < f(mid2)) {
			lo = mid1;
		} else {
			hi = mid2;
			lo = mid1;
		}
	}
	return hi;
}

int main () {
	
	while (scanf("%lf %lf", &l, &w) != EOF) {
		printf("%.03lf 0.000 %.03lf\n", ternary_search()+EPS, (((l<w)?l:w)/2.0)+EPS);
	}
	
	return 0;
}

Thanks!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By facug91, 10 years ago, In English

Hi everyone, I'm looking for problems involving RSQ static. I know it's a very simple technic, but I need it for a class, to give them some problems to practice. I've solved a lot of problems with it, but I've never classified them, and weirdly I can't find any of them googling. Until now I have this two: http://codeforces.net/problemset/problem/313/B http://coj.uci.cu/24h/problem.xhtml?abb=2111 If someone has some others, from any judge, I'll appreciate it. Thanks!

Full text and comments »

Tags dp, rsq
  • Vote: I like it
  • +8
  • Vote: I do not like it