L19 Programming Problem Championship: Round 5 (I/O)

[Solomon]

Leaderboard

1. bernds - 18
2. Solomon, ugoertz - 12
3. gamesorry - 11
4. dfan - 9
5. jeromie, quantumf, peti29 - 5
6. Kirby - 3

Contest Link: https://open.kattis.com/contests/u2cf55

Start Time: 2017-06-02 17:00:00 UTC (Fri June 2 2017 10am PST, 19:00 CEST)
Duration: 60 hours
Problems: 6
Theme: I/O

Past Rounds:

• Round 4 (May 19 2017)
• Round 3 (May 12 2017)
• Round 2 (May 6 2017)
• Round 1 (April 28 2017)

[peti29]

Oh, I just saw this. Joined...

[Solomon]

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.

[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.

[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...

Code: Select all

sys.setrecursionlimit(25000)

Code: Select all

sys.setrecursionlimit(50000)

Code: Select all

sys.setrecursionlimit(100000)

Code: Select all

sys.setrecursionlimit(200000)

Sadly, even though it passes on Kattis, it won't work on my very own machine by default (segfault).

[gamesorry]

Congratulations to Bernd!

Couldn't pass the last test case for Multi-Touch Gesture Classification. Wondering what I'm missing here ...

Code: Select all

import math

a = []
b = []

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

         ax.append(sum(qx)/len(qx))
         ay.append(sum(qy)/len(qy))

agx = sum(ax)/len(ax)
agy = sum(ay)/len(ay)

bx = []
by = []

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

         bx.append(sum(qx)/len(qx))
         by.append(sum(qy)/len(qy))

bgx = sum(bx)/len(bx)
bgy = sum(by)/len(by)

#pan_dist = math.sqrt((agx-bgx)*(agx-bgx)+(agy-bgy)*(agy-bgy))
pan_dist = (agx-bgx)*(agx-bgx)+(agy-bgy)*(agy-bgy)

grip_spread_a = 0
grip_spread_b = 0
for i in range(len(ax)):
   grip_spread_a += math.sqrt((ax[i]-agx)*(ax[i]-agx)+(ay[i]-agy)*(ay[i]-agy))
   grip_spread_b += math.sqrt((bx[i]-bgx)*(bx[i]-bgx)+(by[i]-bgy)*(by[i]-bgy))

grip_spread_a /= len(ax)
grip_spread_b /= len(bx)

#zoom_dist = math.fabs(grip_spread_a - grip_spread_b)
zoom_dist = (grip_spread_a-grip_spread_b)*(grip_spread_a-grip_spread_b)

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)

def getRot(x1, y1, x2, y2):
   cross = x1 * y2 - x2 * y1
   dot = x1 * x2 + y1 * y2
   #l1 = math.sqrt(x1 * x1 + y1 * y1)
   #l2 = math.sqrt(x2 * x2 + y2 * y2)
   l = math.sqrt((x1 * x1 + y1 * y1) * (x2 * x2 + y2 * y2))
   #if l1 == 0 or l2 == 0:
   if l == 0:
      return 0
   if (cross > 0):
      #return math.acos(dot/(l1*l2))
      return math.acos(dot/l)
   else:
      #return -math.acos(dot/(l1*l2))
      return -math.acos(dot/l)

touch_rotation = 0
for i in range(len(ax)):
   touch_rotation += getRot(ax[i] - agx, ay[i] - agy, bx[w[i]] - bgx, by[w[i]] - bgy)

touch_rotation /= len(ax)

rotation_dist = (grip_spread_a * touch_rotation)
rotation_dist *= rotation_dist

"""
print(ax)
print(ay)
print(bx)
print(by)
print(w)
print("pan dist =", pan_dist)
print("zoom dist =", zoom_dist)
print("rotation dist =", rotation_dist)
print("grip spread a =", grip_spread_a)
print("grip spread b =", grip_spread_b)
print("Touch rotation =", touch_rotation)
"""
print(len(ax), end='')
print(' ', end='')
if (pan_dist > zoom_dist):
   if (pan_dist > rotation_dist):
      print("pan")
   else:
      print("rotate ", end='')
      if touch_rotation > 0:
         print("counter-clockwise")
      else:
         print("clockwise")
else:
   if (zoom_dist > rotation_dist):
      print("zoom ", end='')
      if grip_spread_b < grip_spread_a:
         print("in")
      else:
         print("out")
   else:
      print("rotate ", end='')
      if touch_rotation > 0:
         print("counter-clockwise")
      else:
         print("clockwise")

@Solomon: Thank you for the interesting contest. As for the recursion, now I always avoid it unless I'm doing exhaustive searching

[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?).

[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

[bernds]

Thanks for organizing the contest.

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:

Code: Select all

#ifndef _GNU_SOURCE
#define _GNU_SOURCE
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <float.h>

struct touchpoint
{
  double x, y;
};

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;

  double grip_xd = grip_xa - grip_xb;
  double grip_yd = grip_ya - grip_yb;
  double grip_dist = sqrt (grip_xd * grip_xd + grip_yd * grip_yd);

#ifdef DEBUG
  printf ("grips: %f:%f %f:%f dist %f\n", grip_xa, grip_ya, grip_xb, grip_yb, grip_dist);
#endif

  double spread_a = 0;
  double spread_b = 0;

  for (int i = 0; i < npt_b; i++)
    {
      double axd = pts_a[i].x - grip_xa;
      double ayd = pts_a[i].y - grip_ya;
      double bxd = pts_b[i].x - grip_xb;
      double byd = pts_b[i].y - grip_yb;
      spread_a += sqrt (axd * axd + ayd * ayd);
      spread_b += sqrt (bxd * bxd + byd * byd);
    }
  spread_a /= npt_a;
  spread_b /= npt_b;

  double avg_angle = 0;
  for (int i = 0; i < npt_a; i++)
    {
      int n = best_matches[i];
      double vecxa = pts_a[i].x - grip_xa;
      double vecya = pts_a[i].y - grip_ya;
      double vecxb = pts_b[n].x - grip_xb;
      double vecyb = pts_b[n].y - grip_yb;
      double lena = sqrt (vecxa * vecxa + vecya * vecya);
      double lenb = sqrt (vecxb * vecxb + vecyb * vecyb);
      double angle = atan2 (vecyb, vecxb) - atan2 (vecya, vecxa);
      if (angle > M_PI)
        angle -= 2 * M_PI;
      else if (angle < -M_PI)
        angle += 2 * M_PI;
      avg_angle += angle;
#ifdef DEBUG
      printf ("%d [%f %f -> %f]\n", n, lena, lenb, angle);
#endif
    }
  avg_angle /= npt_a;
  double rot_dist = avg_angle * spread_a;
#ifdef DEBUG
  printf ("angle %f, spread %f, rot_dist %f\n", avg_angle, spread_a, rot_dist);
#endif

  printf ("%d ", npt_a);
  if (fabs (rot_dist) > fabs (spread_a - spread_b) && fabs (rot_dist) > grip_dist)
    {
      printf ("rotate ");
      if (rot_dist < 0)
        printf ("counter-");
      puts ("clockwise");
    }
  else if (fabs (spread_a - spread_b) > grip_dist)
    {
      if (spread_a > spread_b)
        puts ("zoom in");
      else
        puts ("zoom out");
    }
  else
    printf ("pan\n");

  exit (0);
}

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.

[Solomon]

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

Code: Select all

from sys import setrecursionlimit
from collections import deque

setrecursionlimit(200000) # UNSAFE! (but AC...)

GRID_SIZE = 10

def dfs(res, grid, x, y, n):
    if not grid[x][y]:
        return False
    if y == n - 1:
        return True

    grid[x][y] = False
    if dfs(res, grid, min(GRID_SIZE - 1, x + 1), y + 1, n):
        return True
    if dfs(res, grid, max(0, x - 1), y + 1, n):
        res.appendleft(y)
        return True
    return False

def main():
    n = int(input())
    grid = []
    res = deque()

    for _ in range(GRID_SIZE):
        # False -> Obstacle
        grid.append([coord != 'X' for coord in list(input())])

    dfs(res, grid, GRID_SIZE - 1, 0, n)

    print(len(res))
    for x in res:
        print(x, 1)

if __name__ == '__main__':
    main()

[gamesorry]

Thank you bernds, after going through your code I found the part I was missing:

Description in the problem:

The correspondence is chosen such that the sum of squared distances between corresponding touch points is minimized.

However, I took it for granted and used the sum of distances instead:

Code: Select all

delta = math.sqrt((ax[k]-bx[i])*(ax[k]-bx[i])+(ay[k]-by[i])*(ay[k]-by[i]))

Changing it to

Code: Select all

delta = (ax[k]-bx[i])*(ax[k]-bx[i])+(ay[k]-by[i])*(ay[k]-by[i])

solves the problem.

[peti29]

Thanks for organizing the round!
Unfortunately this time I had next to no time / energy to program.

[ugoertz]

(Would you mind posting your solution, Solomon?

Code: Select all

from sys import ...

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.

Best, Ulrich