NWERC 2022 Solutions

readme.md

I tried my best to recreate our solutions we had in NWERC. However, there are some missing, and some are changed.

A: unsolved B: solved (py) C: solved (py) D: solved, not included E: solved (py) F: unsolved G: solved (cpp) H: solved, not included I: solved (py) J: solved (cpp) K: solved (py) L: unsolved

In particular, read my E and K code :) they're good. Also, G code might be insightful on how to implement code nice and quickly (took me 5 minutes to write it).

I have also included some of my validator files below, since I don't understand how the output validators work.

I will implement the rest of the problems when I am free. I can't seem to figure out how to do O(n) convex hull intersection (which seems to be possible), but O(nlogn) suffices, which is done by line sweeping. A is adhoc and L is flow...

B.py

from decimal import *

getcontext().prec = 100

# abstract into two blocks, air and water
# let height of water be x
# then water    CoM has position x / 2       and mass x * d_w
# and  air      CoM has position (h + x) / 2 and mass (h - x) * d_a
# and  combined CoM has position c           and mass x * d_w + (h - x) * d_a

h, r, d_a, d_w = map(Decimal, input().split())


def calc(x):
    new_weight = (x * x * d_w + (h + x) * (h - x) * d_a) / 2
    new_mass = x * d_w + (h - x) * d_a
    return new_weight / new_mass


# ternary search
l = 0
r = h
for _ in range(200):
    m1, m2 = (2 * l + r) / 3, (l + 2 * r) / 3
    if calc(m1) > calc(m2):
        l = m1
    elif calc(m1) < calc(m2):
        r = m2
    else:
        l, r = m1, m2

print(l)

B_check.sh

# a few check.sh are similar to this:
# B, C, (I), J, K

for i in $(seq -w 1 26); do
	python3 B.py < $(ls ./data/secret/$i-*.in) > b.out
	python3 -c "import glob; \
		f1 = open(glob.glob('./data/secret/$i-*.ans')[0]).read(); \
		f2 = open('b.out').read(); \
		assert(abs(float(f1) - float(f2)) < 1e-6); \
		print('Passed test case $i')
	"
done

C.py

from math import floor, sqrt


def calc(r2):
    # r2 is square of radius, which is an integer
    # sum top right quadrant then multiply by 4
    s = 0
    x = 1
    while x**2 <= r2:
        s += floor(sqrt(r2 - x**2))
        x += 1
    return s * 4


s = int(input())
l = 0
r = 10**9
res = -1

while r >= l:
    mid = (l + r) // 2
    if calc(mid) > s:
        res = mid
        r = mid - 1
    else:
        l = mid + 1

print(sqrt(res))

E.py

import sys
from fractions import Fraction
from collections import Counter
from math import gcd, sqrt, floor

print = lambda *args: sys.stdout.write(' '.join(map(str, args)) + '\n')

a, b = map(int, input().split('/'))
g = gcd(a, b)
a //= g
b //= g

if a < b - 1:
    print("impossible")

elif a == b - 1:
    # star graph
    print(b, b - 1)
    for i in range(2, b + 1):
        print(1, i)

else:
    d = 10**6 // b
    a *= d
    b *= d

    # now a / b has b closest to 10^6
    # we want b nodes with sum of dist = a

    # first build chain of k nodes where k(k - 1) / 2 <= a
    # then remaining (b - k) nodes have sum of dist a - k(k - 1) / 2
    # this has to be between (b - k) and k(b - k)
    lim = floor((1 + sqrt(1 + 8 * a)) / 2)

    for k in range(1, lim + 1):
        rem = a - k * (k - 1) // 2

        if b - k <= rem <= k * (b - k):
            # build dist
            arr = [1] * (b - k)
            rem -= b - k

            for i in range(b - k):
                if rem == 0:
                    break
                max_pos = min(rem, k - 1)
                arr[i] += max_pos
                rem -= max_pos

            # print length
            print(b, b - 1)
            # print(Counter(arr))

            # print chain
            for i in range(2, k + 1):
                print(i - 1, i)

            # print remaining
            for i in range(b - k):
                print(i + k + 1, arr[i])

            break

    else:
        raise RuntimeError(f"Cannot find solution for {a // d} / {b // d}")

G.cpp

#include <bits/stdc++.h>
using namespace std;

// helper functions
int right() {
  cout << "? right" << endl << flush;
  int r;
  cin >> r;
  return r;
}

int left() {
  cout << "? left" << endl << flush;
  int r;
  cin >> r;
  return r;
}

int flip() {
  cout << "? flip" << endl << flush;
  int r;
  cin >> r;
  return r;
}

void submit(int r) { cout << "! " << r << endl << flush; }

int cur, steps, pattern[50];
deque<int> prev50;

int main() {
  // random pattern
  for (int i = 0; i < 50; i++) {
    pattern[i] = rand() & 1;
  }

  cin >> cur;

  // first, solve for n <= 50
  // clear right 50, go back, flip, go at most 50, see if sees the light
  for (int i = 0; i < 55; i++) {
    if (cur) {
      cur = flip();
    }
    cur = right();
  }

  for (int i = 0; i < 55; i++) {
    cur = left();
  }

  cur = flip();

  for (int i = 1; i <= 50; i++) {
    cur = right();
    if (cur) {
      submit(i);
      return 0;
    }
  }

  // now, we set the next 50 to pattern
  for (int i = 0; i < 50; i++) {
    if (cur != pattern[i]) {
      cur = flip();
    }
    cur = right();
  }

  // and keep walking until we find pattern
  // we add the current bit, then pop front until it matches
  while (prev50.size() < 50) {
    steps++;
    prev50.push_back(cur);
    while (!prev50.empty()) {
      // check if prev50 matches pattern already
      bool match = true;
      for (int i = 0; i < prev50.size(); i++) {
        if (pattern[i] != prev50[i]) {
          match = false;
          break;
        }
      }
      if (match) {
        break;
      }

      // if not, we pop front
      prev50.pop_front();
    }
    cur = right();
  }

  submit(steps);
}

G_check.sh

g++-11 -o G G.cpp
for i in $(seq -w 1 203); do
	python3 G_validator.py -t $i "./G"
done

G_validator.py

# Note by grhkm:
# I cannot figure out how output_validators given in the directory works
# So I modified the testing_tool to work with testing solutions instead

import glob
import argparse
import subprocess
import sys
import traceback

DEBUG = False


def write(p, line):
    assert p.poll() is None, 'Program terminated early'
    if DEBUG:
        print('Write: {}'.format(line), flush=True)
    p.stdin.write('{}\n'.format(line))
    p.stdin.flush()


def read(p):
    assert p.poll() is None, 'Program terminated early'
    line = p.stdout.readline().strip()
    assert line != '', 'Read empty line or closed output pipe. Make sure that your program started successfully.'
    if DEBUG:
        print('Read: %s' % line, flush=True)
    return line


def wrong_answer(p, reason):
    sys.stdout.write('%s\n' % reason)
    p.kill()


parser = argparse.ArgumentParser(description='Grader for the Going in Circles problem')
parser.add_argument('-t', dest='test_case', metavar='test_case', default="1")
parser.add_argument('program', nargs='+', help='Invocation of your solution')

args = parser.parse_args()
test_case = int(args.test_case)
assert 1 <= test_case <= 203, f'Test Case {test_case} must be between 1 and 203.'

with open(glob.glob(f'data/secret/{test_case:03}-*.in')[0], 'r') as fin:
    sequence = fin.read().split()[1]

sequence = list(sequence)
for c in sequence:
    assert c in '01', f'Character {c} may not appear in the input sequence.'

n = len(sequence)
position = 0

queries = 0
queries_limit = 3 * n + 500

with subprocess.Popen(" ".join(args.program),
                      shell=True,
                      stdout=subprocess.PIPE,
                      stdin=subprocess.PIPE,
                      universal_newlines=True) as p:
    try:
        write(p, sequence[position])

        while True:
            response = read(p)

            if response.startswith('? '):
                if queries == 50000:
                    wrong_answer(p, 'Program used too many queries, aborting')
                    break

                queries += 1
                action = response[2:]

                if action == 'right':
                    position = (position + 1) % n

                elif action == 'left':
                    position = (position - 1) % n

                elif action == 'flip':
                    sequence[position] = str(1 - int(sequence[position]))

                else:
                    wrong_answer(p, 'Program gave unrecognized action')

            elif response.startswith('! '):
                answer = response[2:]
                assert answer.isnumeric(), 'Expected final guess to be a positive integer'
                answer = int(answer)

                if answer == n:
                    assert queries <= queries_limit, 'Program printed correct solution, but used too many queries'
                    assert p.stdout.readline() == '', 'Printed extra data after finding solution'
                    assert p.wait() == 0, 'Did not exit cleanly after finishing'
                    break

                else:
                    wrong_answer(p, 'Program printed incorrect solution')
                    break

            else:
                wrong_answer(p, 'Program gave invalid response')
                break

            write(p, sequence[position])

    except:
        traceback.print_exc()

    finally:
        sys.stdout.flush()
        sys.stderr.flush()
        if DEBUG:
            sys.stdout.write(f'Used {queries} queries, limit is {queries_limit}.\n')
            sys.stdout.write('Program exit code: {p.wait()}\n')
        sys.stdout.write(f'Passed test case {test_case}\n')
        sys.stdout.flush()

I.py

from math import gcd
from functools import reduce

a, b = map(int, input().split())
arr = input().split()
fs, bs = [], []

for i in range(b - a + 1):
    if 'Fizz' in arr[i]:
        fs.append(i + a)
    if 'Buzz' in arr[i]:
        bs.append(i + a)

ft = b + 1 if (len(fs) == 0) else (
    reduce(gcd, [fs[i + 1] - fs[i] for i in range(len(fs) - 1)])
    if len(fs) > 1 else fs[0])

bt = b + 1 if (len(bs) == 0) else (
    reduce(gcd, [bs[i + 1] - bs[i] for i in range(len(bs) - 1)])
    if len(bs) > 1 else bs[0])

print(ft, bt)

I_check.sh

for i in $(seq -w 1 71); do
	python3 I.py < $(ls ./data/secret/$i-*.in) > i.out
	python3 -c "import glob; \
		f1 = open(glob.glob('./data/secret/$i-*.in')[0]).read().strip().split('\n'); \
		f2 = open('i.out').read(); \
		a, b = map(int, f1[0].split()); \
		x, y = map(int, f2.split()); \
		seq = [str(t) if (t % x != 0 and t % y != 0) else (('Fizz' if t % x == 0 else '') + ('Buzz' if t % y == 0 else '')) for t in range(a, b + 1)]; \
		s1 = ' '.join(seq); \
		s2 = f1[1].strip(); \
		assert s1 == s2, f'{s1} != {s2}'; \
		print('Passed test case $i')
	"
done

J.cpp

#include <bits/stdc++.h>
// #include <bitset>
using namespace std;

struct Interval {
  int l, r, idx;
};

bool cmp(Interval a, Interval b) {
  if (a.l != b.l) {
    return a.l < b.l;
  }
  return a.r > b.r;
}

const int N = 2e5;
const int INF = 1e9;

int n, right_index[N + 1], ans[N + 1];
vector<Interval> intervals;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);

  cin >> n;
  intervals.resize(n);

  for (int i = 0; i < n; i++) {
    cin >> intervals[i].l >> intervals[i].r;
    intervals[i].idx = i;
    intervals[i].r += intervals[i].l;
  }

  sort(intervals.begin(), intervals.end(), cmp);

  for (int i = 0; i < n; i++) {
    int r = intervals[i].r;
    if (right_index[0] < r) {
      ans[intervals[i].idx] = 0;
      right_index[0] = r;
    } else {
      int largest = -1, L = 0, R = n;
      while (R >= L) {
        int M = (L + R) / 2;
        if (right_index[M] >= r) {
          largest = M;
          L = M + 1;
        } else {
          R = M - 1;
        }
      }
      ans[intervals[i].idx] = largest + 1;
      right_index[largest + 1] = max(right_index[largest + 1], intervals[i].r);
    }
  }

  for (int i = 0; i < n; i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
}

K.py

import sys

sys.setrecursionlimit(10**6)


def main():
    n, k = map(int, input().split())

    # build graph, check if
    # (1) only single loop or (multiple) paths after removing leaves
    # (2) degree <= 2
    # note that we check every component

    graph = {i: set() for i in range(k)}
    for _ in range(n):
        a, b = map(int, input().split())

        graph[a - 1].add(b - 1)
        graph[b - 1].add(a - 1)

    graph = {v: list(graph[v]) for v in graph}

    # degree
    for v in range(k):
        # leaves `u` are fine, since (on the pizza) we can just place it
        # next to `v` and ignore them
        if len([u for u in graph[v] if u != v and graph[u] != [v]]) > 2:
            # print(graph)
            return False

    # search on each nodes for components
    vis = [False] * k
    cycle = False
    cnt = 0

    # update: dfs will segfault and run out of stack
    '''
    def dfs(v, pt=-1):
        # pt is parent i.e. previous node
        # l is length, ignores "fake cycles"
        # returns cycle or not

        # handle cycles
        if vis[v]:
            return True

        # search
        vis[v] = True
        _cycle = False
        for u in graph[v]:
            if u != pt and u != v:
                _cycle = _cycle | dfs(u, v)

        return _cycle
    '''

    for v in range(k):
        if vis[v] or graph[v] == []:
            continue

        cnt += 1
        # print(f'dfs({v})')

        # simulates dfs
        stack = [(v, -1)]
        while len(stack) > 0:
            v, pt = stack.pop()
            if vis[v]:
                cycle = True
                continue

            vis[v] = True
            for u in graph[v]:
                if u != pt and u != v:
                    stack.append((u, v))

    if cycle:
        return cnt == 1

    return True


if __name__ == '__main__':
    if main():
        print("possible")
    else:
        print("impossible")