To clarify on what "I/O" theme means, the ways of solving the problems can vary like last week, but solving also involves processing the input and output beyond just outputting a line or an integer (and usually you can tell what the problem is just by looking at the input and output, which in most cases you normally cannot do). For an example of what this means, take a look at this problem.
Re: L19 Programming Problem Championship: Round 5
Posted: Sat Jun 03, 2017 8:44 am
by bernds
Some people appear to be missing from the standings page, so I'm giving the thread a little bump in case they haven't seen it.
Re: L19 Programming Problem Championship: Round 5
Posted: Sun Jun 04, 2017 7:50 pm
by Solomon
Been trying to do everything in Python this time, since it seems much easier for dealing with string manipulations instead of C++. Unfortunately I haven't had much time to warm up to it, and feeling sluggish on the problems as a result having only gotten 3 and hopefully a 4th in by the deadline.
Also, as an aside, I burned 4 attempts on Jetpack for something quite silly...
for i in range(15): row = input().split() r = [] for j in range(30): if (row[0][j] == '.'): r.append(0) else: r.append(1) a.append(r) r = [] for j in range(30): if (row[1][j] == '.'): r.append(0) else: r.append(1) b.append(r)
ax = [] ay = []
for i in range(15): for j in range(30): if a[i][j] == 1: qx = [] qy = [] a[i][j] = 2 qx.append(i) qy.append(j) k = 0 while k < len(qx): x = qx[k] y = qy[k] if x > 0 and a[x-1][y] == 1: qx.append(x-1) qy.append(y) a[x-1][y] = 2 if y > 0 and a[x][y-1] == 1: qx.append(x) qy.append(y-1) a[x][y-1] = 2 if x < 14 and a[x+1][y] == 1: qx.append(x+1) qy.append(y) a[x+1][y] = 2 if y < 29 and a[x][y+1] == 1: qx.append(x) qy.append(y+1) a[x][y+1] = 2 k += 1
for i in range(15): for j in range(30): if b[i][j] == 1: qx = [] qy = [] b[i][j] = 2 qx.append(i) qy.append(j) k = 0 while k < len(qx): x = qx[k] y = qy[k] if x > 0 and b[x-1][y] == 1: qx.append(x-1) qy.append(y) b[x-1][y] = 2 if y > 0 and b[x][y-1] == 1: qx.append(x) qy.append(y-1) b[x][y-1] = 2 if x < 14 and b[x+1][y] == 1: qx.append(x+1) qy.append(y) b[x+1][y] = 2 if y < 29 and b[x][y+1] == 1: qx.append(x) qy.append(y+1) b[x][y+1] = 2 k += 1
def search(k, s, bests, ax, ay, bx, by, u, v, w): if k == len(ax): if s < bests[0]: bests[0] = s for i in range(len(u)): w[i] = u[i] #print("bests =", bests[0]) #print(w) for i in range(len(bx)): if v[i] == -1: u[k] = i v[i] = k delta = math.sqrt((ax[k]-bx[i])*(ax[k]-bx[i])+(ay[k]-by[i])*(ay[k]-by[i])) search(k+1, s + delta, bests, ax, ay, bx, by, u, v, w) v[i] = -1
bests = [1000000000] u = [-1 for i in range(len(ax))] v = [-1 for i in range(len(bx))] w = [-1 for i in range(len(ax))] search(0, 0, bests, ax, ay, bx, by, u, v, w)
@Solomon: Thank you for the interesting contest. As for the recursion, now I always avoid it unless I'm doing exhaustive searching
Re: L19 Programming Problem Championship: Round 5
Posted: Sun Jun 04, 2017 10:12 pm
by Solomon
Ah...pretty disappointed with my performance in this round. Despite not having a good chunk of time during the weekend to work on these, as well as wasting time deciding between using C++ and Python and eventually forcing myself to use Python, I should have still done better than just 3. Really it was just a combination of getting distracted and not thinking long enough . I'll post up the leaderboard tomorrow, and will try to upsolve at least B and F (have pretty good ideas on how to solve them already) by then hopefully. Congratulations to bernds for solving all 6 so quickly, I guess these were not so challenging. If you have time, I'd love to hear your thoughts on how you did E and F.
I think for next round we'll go back to focusing on problem solving techniques (maybe a return on DP problems?).
Re: L19 Programming Problem Championship: Round 5
Posted: Mon Jun 05, 2017 1:29 am
by ugoertz
Thanks, Solomon, for setting up the contest!
This time, I found A, B, C pretty much straightforward. With D I had some problems to meet the time restrictions. (Would you mind posting your solution, Solomon? Since it is more than twice as fast as mine it would be interesting to compare. Form hindsight I am guessing that with my current solution I am storing too much of the paths which turn out to be failures, making the data management slower than necessary.)
For F I have a partial solution in the sense that it passes the first two tests, but fails the third one with "Memory limit exceeded" - the reason being that I use Python's own parser which can be accessed via the ast module, to parse the arithmetic expression. Unfortunately, this parser is quite inefficient ...
Best, Ulrich
Re: L19 Programming Problem Championship: Round 5
Posted: Mon Jun 05, 2017 4:24 am
by bernds
Thanks for organizing the contest.
Solomon wrote:If you have time, I'd love to hear your thoughts on how you did E and F.
On the whole I thought this was the easiest round so far, with nothing requiring too much thought. Problem F was a lot of fun though and possibly even gave me quite a useful tool.
As for D, I'm puzzled that people are using recursion. If you think of the grid as a graph, with each node having two successors (except for the final column), you can make a backwards path computing nodes which can reach the end (marking as 'X' anything whose successors are both 'X' already). Then you just make one forwards pass where we can tell at each point whether one or both of the successors can reach the end. In the case where both do, the example seems to favour releasing the button, so that's what I did.
E is really just a "simple matter of programming". It pretty much tells you all the steps and you just have to write them down (with a little flood-fill-ish first step to identify the touch points). To gamesorry: Not sure what the problem is, but the only difficulty I encountered was computing the correct angles. I ended up using atan2 (y2, x2) - atan2 (y1, x1) and normalizing that into the correct range. It helps to build modified testcases, swapping the two pictures, to verify it's doing the right thing. Maybe compare the numbers you compute to those from my solution:
static int find_touchpoints (struct touchpoint *pts, char pic[15][30]) { int xbuf[15 * 30]; int ybuf[15 * 30]; int n = 0; for (int x = 0; x < 30; x++) for (int y = 0; y < 15; y++) { if (pic[y][x] != 'X') continue; int xtotal = 0; int ytotal = 0; xbuf[0] = x; ybuf[0] = y; pic[y][x] = '0' + n; int nwork = 1; for (int i = 0; i < nwork; i++) { int xt = xbuf[i]; int yt = ybuf[i]; xtotal += xt; ytotal += yt; if (xt > 0 && pic[yt][xt - 1] == 'X') { xbuf[nwork] = xt - 1; ybuf[nwork] = yt; nwork++; pic[yt][xt - 1] = '0' + n; } if (xt + 1 < 30 && pic[yt][xt + 1] == 'X') { xbuf[nwork] = xt + 1; ybuf[nwork] = yt; nwork++; pic[yt][xt + 1] = '0' + n; } if (yt > 0 && pic[yt - 1][xt] == 'X') { xbuf[nwork] = xt; ybuf[nwork] = yt - 1; nwork++; pic[yt - 1][xt] = '0' + n; } if (yt + 1 < 15 && pic[yt + 1][xt] == 'X') { xbuf[nwork] = xt; ybuf[nwork] = yt + 1; nwork++; pic[yt + 1][xt] = '0' + n; } } pts[n].x = (double)xtotal / nwork; pts[n].y = (double)ytotal / nwork; n++; } return n; }
static void print_pic (char pic[15][30]) { for (int y = 0; y < 15; y++) { for (int x = 0; x < 30; x++) putchar (pic[y][x]); putchar ('\n'); } }
static double match (struct touchpoint *pts_a, struct touchpoint *pts_b, int *matches, int *best_matches, int *used, double best, double sum, int n, int len) { if (n == len) { if (sum < best) memcpy (best_matches, matches, 5 * sizeof (int));
return sum; }
for (int i = 0; i < len; i++) if (!used[i]) { used[i] = 1; matches[n] = i; double xd = (pts_a[n].x - pts_b[i].x); double yd = (pts_a[n].y - pts_b[i].y); double t_sum = sum + xd * xd + yd * yd; double t = match (pts_a, pts_b, matches, best_matches, used, best, t_sum, n + 1, len); if (t < best) best = t; used[i] = 0; } return best; }
int main (int argc, char **argv) { char *line = NULL; size_t llen = 0; char pic_a[15][30]; char pic_b[15][30]; struct touchpoint pts_a[5], pts_b[5]; for (int i = 0; i < 15; i++) { if (getline (&line, &llen, stdin) < 0) abort (); memcpy (pic_a[i], line, 30); memcpy (pic_b[i], line + 31, 30); } int npt_a = find_touchpoints (pts_a, pic_a); int npt_b = find_touchpoints (pts_b, pic_b); if (npt_a != npt_b) abort ();
#ifdef DEBUG print_pic (pic_a); putchar ('\n'); print_pic (pic_b); #endif int best_matches[5]; int matches[5]; int used[5]; memset (used, 0, sizeof (used)); double best = match (pts_a, pts_b, matches, best_matches, used, DBL_MAX, 0, 0, npt_a);
#ifdef DEBUG printf ("%f\n", best);
for (int i = 0; i < npt_a; i++) { int n = best_matches[i]; printf ("[%d] %f:%f [%d] %f:%f\n", i, pts_a[i].x, pts_a[i].y, n, pts_b[n].x, pts_b[n].y); } #endif double grip_xa = 0; double grip_xb = 0; double grip_ya = 0; double grip_yb = 0; for (int i = 0; i < npt_b; i++) { grip_xa += pts_a[i].x; grip_xb += pts_b[i].x; grip_ya += pts_a[i].y; grip_yb += pts_b[i].y; } grip_xa /= npt_a; grip_xb /= npt_b; grip_ya /= npt_a; grip_yb /= npt_b;
Problem F: OK, I didn't think of trying to use a Python parser. I did for a brief moment consider bison or yacc but that's really quite silly for a problem that can be solved by a recursive descent parser that fits on one page or so. While you're building up expression nodes, you also compute height/width/lvc based on the subexpressions (if any). Then the top-level expression gives you width and height of the picture you need to draw, so you allocate that, fill it with spaces, and call a recursive render function to put the expressions into the buffer. Trim spaces, and print.
Re: L19 Programming Problem Championship: Round 5
Posted: Mon Jun 05, 2017 10:50 am
by Solomon
ugoertz wrote:(Would you mind posting your solution, Solomon? Since it is more than twice as fast as mine it would be interesting to compare. Form hindsight I am guessing that with my current solution I am storing too much of the paths which turn out to be failures, making the data management slower than necessary.)
Thanks! That's interesting, and I can see some points where this is faster than my solution ... but I guess I would have to create a large test case in order to see which of the differences really matters. (E.g., it is not clear to me whether printing out each raise move individually with duration 1 is faster than adding things up first.) If I get around to it, I will try to do some profiling.
. I'll post up the leaderboard tomorrow, and will try to upsolve at least B and F (have pretty good ideas on how to solve them already) by then hopefully. Congratulations to bernds for solving all 6 so quickly, I guess these were not so challenging. If you have time, I'd love to hear your thoughts on how you did E and F.