I've been looking at past problems to regain some ability on solving DP problems, the result this time is a couple bonus solutions to the problems from this time. On the other hand, I solved more warmup problems for speed and an interesting greedy one.

Morgan and a String

source

This one was very interesting. I spend some time thinking that it wasn't going to be easy solving it because it seemed like a job for a specialized data structure (the author of the problem uses suffix trees in the editorial solution) or some kind of DP, however, a couple of key observations lets a greedy solution to work.

To ensure we're building the lexicographically lowest string, we must always take the lowest character if our next options are different (e.g., the next available characters are different). In the case when both characters are the same we have to start by the (available) string that is lower, and there lies the problem: we must sequentially compare the pairs of characters to be able to determine which string is lower and that leads to a very slow solution if we make this comparison every time we stumble upon two equal characters.

The key observations that allows us to speed things up are the following:

1) If we find a character greater than the one that triggered the search, we can simply output one string after the other up to that char

Take the following case and let $S_i=f$ and $T_j=f$ :

$S=...fabcdgaba..., T=...fabcdgaaa...$

To define what our next step should be, we'll start comparing $S_i$ and $T_j$ until we get to a point where the characters differ. However, in the meantime we'll get to a point where $S_i=g$ and $T_i=g$ ; we still don't know which string to start taking characters from, but we do know that no matter which string we choose, the next characters in the lowest string are ' $fabcdfabcd$ ' so that string can be added to the answer while we keep comparing characters.

2) If we have only one character left in one string and it is equal to the next char in the other one, continue with the longer string

This one is rather simple, take the following case where $S_i=d$ and $T_j=d$ :

$S=dbaab, T=...d$

If we take the $d$ from $T$ we'll be then be forced to take the $d$ from $S$ , producing a suboptimal answer.

With these two observations, solving the problem is now a matter of implementing the mergesort's-merge-like algorithm.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class MorganAndString {

   public static void main(String[] args) throws Exception {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    int K = Integer.parseInt(reader.readLine());
    while (K --> 0) {
      char[] s = reader.readLine().toCharArray();
      char[] t = reader.readLine().toCharArray();
      char[] out = new char[s.length + t.length];
      int si = 0, ti = 0, oi = 0;
      while (si < s.length && ti < t.length) {
        if (s[si] < t[ti]) out[oi++] = s[si++];
        else if (s[si] > t[ti]) out[oi++] = t[ti++];
        else {
          int p = si, q = ti;
          char c = s[si];
          for(; p < s.length && q < t.length; p++, q++) {
            if (s[p] != t[q]) break;
            else if (s[p] > c){
              while(si < p) out[oi++] = s[si++];
              while(ti < q) out[oi++] = t[ti++];
              c = s[p];
            }
          }
          if(p == s.length) out[oi++] = t[ti++];
          else if(q == t.length) out[oi++] = s[si++];
          else {
            if (s[p] < t[q]) out[oi++] = s[si++];
            else out[oi++] = t[ti++];
          }
        }
      }
      while (si < s.length) out[oi++] = s[si++];
      while (ti < t.length) out[oi++] = t[ti++];
      System.out.println(new String(out));
    }
  }
}

Bon Appetit

source

Very simple. Just do what the statement says.

n, k = list(map(int, input().split()))
c = list(map(int, input().split()))
d = int(input())
c.pop(k)
amount = sum(c) // 2
print('Bon Appetit' if d == amount else d - amount)

Counting Valleys

source


Keep track of the moments when we enter and exit a valley and count. There's not much to it.

#include <bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  int n, acc = 0, ans = 0;
  bool valley = false;
  char c;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> c;
    if(c == 'D') acc--;
    if(c == 'U') acc++;
    if(acc < 0) valley = true;
    if(acc == 0 && valley){
      ans++;
      valley = false;
    }
  }
  cout << ans << endl;
  return 0;
}

Drawing Book

source

Not much to it, just take care of the cases with an even number of pages because the answer might change when swiping from the right.

n = int(input())
p = int(input())
left = p // 2
right = ((n + (n % 2 == 0)) - p) // 2
print(min(left, right))

Electronics Shop

source

The constraints of the problem allow for searching among all valid pairs, so just do that.

from itertools import product
s, n, m = list(map(int, input().split()))
k = list(map(int, input().split()))
u = list(map(int, input().split()))
comb = list(filter(lambda x: x <= s, list(x + y for x, y in product(k, u))))
print(max(comb) if len(comb) else -1)

Sock Merchant

source

Not much to say about this one.

from collections import Counter
input()
c = Counter(list(map(int, input().split())))
print(sum([x // 2 for x in c.values()]))

Last words

Don't let yourself be fooled by the labeling of a problem, Morgan and a String was labeled as an expert-level problem.