week of 11/28

calico!

---

📝 notes

have a great weekend!

---

CALICO

info:

you can find all of the problems here: (https://calicojudge.com/domjudge/team/problems) after you make a DOMJudge account.

if you can't access it for whatever reason, please let me know, as i can download the PDFs for the problems and email them to you !

performance review:

overall, a pretty lack-luster performance. i did the contest solo, since i forgot to find a team, which was a huge oversight.

the contest was overall pretty easy, but i spent too long on problem 7 debugging a python solution. if i had more time, i could have definitely solved a few more problems.

in the end, i only got ~

$50$th place. ;w;

problems:

all subtasks for each problem (including) bonuses are solved in these writeups, unles otherwise specified.

bookshelf

We're given a bookshelf, with

$n$ shelves, each shelf occupying

$h_i$ space, and we have to find the volume of the bookcase.

Here are the values given:

solution

This is a straightforward geometry problem!

We'll use complementary counting, by taking the volume of the bookshelf, and subtracting all the empty space.

The volume of the bookcase intially is:

$((b\times (n+1))+\sum _{i=0}^{i<n}{h}_i)\times (2b+w)\times d$.

The volume of each shelf-space is

$h_i\times d\times w$ for all

$i$, so we'll just subtract this from the initial volume.

That's it!

time complexity:

$\mathcal{O}(1)$

rso (registered student orgs)

berkeley has a system of naming student-run organizaitons.

• they must not be longer than 50 characters
• they must not begin with any of these words in any case
  • "California"
  • "Cal"
  • "Berkeley"
• rsos registered prior to
  $2010$ are exempt.

check whether a given RSO is valid.

solution:

we just check for the conditions given…

time complexity:

$\mathcal{O}(1)$

paint

you have

$x$ buckets of orange paint,

$y$ buckets of brown paint, and

$z$ buckets of white paint.

to change a bucket from orange to brown, it costs:

$C_{BO}$ (both ways)

to change a bucket from brown to white, it costs:

$C_{BW}$ (both ways)

to change a bucket from orange to white, it costs:

$C_{OW}$ (both ways)

you want to change all your buckets of paint to one color.

find the minimum cost to do so.

solution:

note that to change a bucket to another color, we have two choices.

• change it directly
• change it to an intermediate color, and then change it to that color.

since we only have three colors, we'll try switching all the buckets to each color, and take the minimum path (directly or the sum of the other two).

time complexity:

$\mathcal{O}(1)$

bottles

each student refills their water bottle at a comunal station in their building. this dispenser only dispenses water at

$1$ liter a minute, and a long line has formed.

each student has a water bottle of a different size, and you have to figure the minimum cumulative waiting time of all students, given that each student has to wait for the student ahead to finish refilling before they can start.

output the minimum time, and the optimal order of the line.

bonus: if there are multiple orderings with the minimum time, output the ordering which minimizes the number of displaced students.

solution

we know that if we ever want to minimize the sum of a prefix, we should sort the given input.

that suffices for the main tests, but for the bonus, we need a little bit more work.

to minimize the number of students moved, we want to assign students to the right place within their given "component", since there may be mutliple students with the same bottle capacaity.

we know this component spans a given subsegment of the final array, so we'll just assign as many students to their original positions.

time complexity:

$\mathcal{O}(n)$

bread

here we have a slightly more challenging problem.

(copy-pasted from the problem statement)

for all of the subtasks,

$N,K,D\le {10}^5$, and

$NK\le {10}^5$

solution:

unfortunately, i don't think i can completely explain my intuition to solve this problem during the contest, the reason being: right when i saw

$NK\le {10}^5$, i sprung at the idea.

but, ill try to explain all the factors which might lead you to this classical solution.

• $NK\le {10}^5$ (already mentioned)
• no meal card activations for the next
  $d$ days
• d is constant
• the location of the next zero is constant, and you take the sum of a subsegment, which can be calculated on the fly in
  $\mathcal{O}(1)$, with
  $\mathcal{O}(N)$ precomputation.

this all helps bring out the idea of Knapsack DP.

the only caveats being that we have to calculate the sum of elements until the next

$0$ in the array, or until after

$d$ days have passed, whichever comes first.

so, we have to precompute these two arrays:

• prefix sum for subsegment sum
• suffix array to keep track of the next
  $0$ in the array

from this, we can process our transitions in

$\mathcal{O}(1)$ time, dropping our time complexity to

$\mathcal{O}(NK)$!

this is enough to solve the main tests and all bonuses.

chainsawsage man

Denji is cutting sausage chains to make himself a nice dinner, but his chainsaws only cut in a certain way!

Denji has his

$N$ sausage chains hanging on a grid, the top of the

$i$th chain at point

$h_i$, and the bottom at

$l_i$. Each sausage spans

$1$ unit.

To savor his dish, he plans to cut only a specific amount of sausage.

he can cut the line at two horizontal points, and collects all of the sausage within the two.

solution:

the last bonus set is a bit more complicated, and i haven't gotten around to solving that yet, but for every other bonus, we can simply build a prefix sum, and query all possible subsegments.

time complexity:

$\mathcal{O}(n^2)$

toki

toki pona is a language focused on minimalism and simplicity.

each syllable in a toki pona word is composed of syllables, which form the following form.

(C)v(n)

we start with an optional consonant, then a mandatory vowel, and an optional "n" at the end.

toki pona only has 14 letters:

the consonants m, n, p, t, k, s, w, j, l
the vowels a, e, i, o, u

and words cannot contain any of these illegal subsequences (including between syllables):

wu, wo, ji, ti, nn, or nm

adjacent vowels are also not allowed.

find whether a given word is valid in toki pona.

solution

While the bonus test set only spans up to

${10}^3$, i was able to pass all test cases for up to

${10}^6$ with DP.

it's completely possible that the test cases were just weak, but because i haven't found a counter-case where this would not work, i'll describe it below.

a word, as described in the problem statement is composed of syllables, each syllable spanning up to

$3$ letters.

thus, if we have some prefix of a word, such that the last (

$\le 3$) form a valid syllable, if the prefix

$i-\{1,2,3\}$ works, then this prefix also forms a valid word.

since

$3$ is a tiny constant, we can try all previous syllables, giving us a

$\mathcal{O}(3n)=\mathcal{O}(n)$ solution.

---

here we start problems that i weren't able to solve in contest.

tower

Herry Bother is trapped inside of Molderwort's signature creations, a circle of towers. Herry needs to destroy all of the towers to escape.

Herry can start at any point

$i$ out of Molderwort

$n$ towers, and continues to walk clockwise in a circle. It turns out, Hogwarts never taught Herry how to turn around.

Each tower has a power value

$p_i$, and in order to destroy it, he has to have a current power level

$\ge p_i$.

Each hour his power level increases by one, and the distance between towers

$i,(i+1)\mathrm{mod}n$ is given as

$d_i$.

Find the minimum time for Herry to destroy all

$n$ towers.

solution

here's the solution to the main test set with

$n\le 100$.

my current solution has a time complexity of

$n\cdot (n\log n)$ which unfortunately doesn't solve for the bonus, but also overqualifies for the main tests.

while i try to optimize it, ill explain the gist of it.

note that if Herry should ever wait at a tower, he can wait all of it at his starting tower, and it wouldn't make a difference.

then, at any starting point, we can find the minimum waiting time by binary searching on it.

this is enough to solve the main tests.

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

int main() {
  int tc;
  cin >> tc;
  for (int _ = 0; _ < tc; _++) {

	int n;
	cin >> n;
	vector<int> p(n), w(n);
	for (int i = 0; i < n; i++) {
	  cin >> p[i];
	}

	for (int i = 0; i < n; i++) {
	  // i -> (i + 1) % n
	  cin >> w[i];
	}

	int bst = 1e9;
	for (int i = 0; i < n; i++) {
	  rotate(p.begin(), p.begin() + 1, p.end());
	  rotate(w.begin(), w.begin() + 1, w.end());

	  int lo = 0, hi = 1e6;
	  int sfs = 0;

	  while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		int svr = 0;
		int pw = mid;
		bool kk = 1;
		for (int i = 0; i < n; i++) {
		  if (p[i] > pw) {
			kk = 0;
		  }

		  pw += w[i];
		  if (i != n - 1)
			svr += w[i];
		}

		if (kk) {
		  hi = mid;
		} else {
		  lo = mid + 1;
		  sfs = svr;
		}
	  }

	  bst = min(bst, lo + sfs);
	}
	cout << bst << endl;
  }
}