s = input()
print("Thank you", s)

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

int main(){
  cin.tie(0) -> sync_with_stdio(0);
  string s; cin >> s;
  cout << "Thank you " << s;
}

x, y = map(int, input().split())
print(6*x + 4*y)

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

int main(){
  cin.tie(0) -> sync_with_stdio(0);
  long long x,y; cin >> x >> y;
  cout << 6*x + 4*y;
}

g, h = input().split()
if g == "thor" or h != "mjolnir":
  print("Yes")
else:
  print("No")

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

int main(){
  cin.tie(0) -> sync_with_stdio(0);
  string g, h; cin >> g >> h;
  if(g == "thor" || h != "mjolnir") cout << "Yes";
  else cout << "No";
}

We could use a long chain of if statements to construct Roman Numerals in general, but that's annoying. Converting between integers and roman numerals, while possible, is nontrivial. Instead, notice that the constraints on the inputs are very small.

Hardcode the conversions between integers and roman numerals. To convert from roman numerals to integers, we need a data structure where we can index with strings. For example: RomanToInt["II"] = 2.

We can use maps or hashmaps to hardcode from roman numerals to integers. Most languages will have library versions of these data structures.

RomanToInt = {"I": 1, "II": 2, "III": 3, "IV": 4, "V": 5, "VI": 6, "VII": 7, "VIII": 8, "IX": 9, "X": 10}
IntToRoman = {1: "I", 2: "II", 3: "III", 4: "IV", 5: "V", 6: "VI", 7: "VII", 8: "VIII", 9: "IX", 10: "X"}

x_rom, y_rom = input().split()

x_int = RomanToInt[x_rom]
y_int = RomanToInt[y_rom]
sum_int = x_int + y_int

sum_rom = IntToRoman[sum_int]
print(sum_rom)

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

int main() {
  map<string,int> RomanToInt = {
    {"I", 1}, {"II", 2}, {"III", 3}, {"IV", 4}, {"V", 5},
    {"VI", 6}, {"VII", 7}, {"VIII", 8}, {"IX", 9}, {"X", 10}
  };
  map<int,string> IntToRoman = {
    {1, "I"}, {2, "II"}, {3, "III"}, {4, "IV"}, {5, "V"},
    {6, "VI"}, {7, "VII"}, {8, "VIII"}, {9, "IX"}, {10, "X"},
    {11, "XI"}, {12, "XII"}, {13, "XIII"}, {14, "XIV"}, {15, "XV"},
    {16, "XVI"}, {17, "XVII"}, {18, "XVIII"}, {19, "XIX"}, {20, "XX"}
  };

  string x_rom, y_rom; cin >> x_rom >> y_rom;

  int x_int = RomanToInt[x_rom];
  int y_int = RomanToInt[y_rom];
  int sum_int = x_int + y_int;

  string sum_rom = IntToRoman[sum_int];
  cout << sum_rom;
  return 0;
}

n = int(input())
debt = 0

for i in range(n):
  type, amt = input().split()

  if type == "withdraw":
    debt += int(amt)
  if type == "repay":
    debt -= int(amt)
    
  debt *= 2

print(debt)

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

int main() {
  int n; cin >> n;
  int debt = 0;

  for(int i=0; i<n; i++){
    string type; int amt; cin >> type >> amt;

    if(type == "withdraw") debt += amt;
    else debt -= amt;
    
    debt *= 2;
  }

  cout << debt;
  return 0;
}

Sort the list of animals in alphabetical order. Now, all instances of the same animal would be next to each other. We just need to verify that there is no index in our list that is different than its neighbors. We can check $$$a_i$$$ against $$$a_{i-1}$$$ and $$$a_{i+1}$$$ for all $$$i$$$. We should be careful about evaluating neighbors at the two ends of the list.

Time Complexity: $$$O(S \log n)$$$, where $$$S$$$ is the sum of the lengths of all strings.

We can create a map/dictionary from animal names to frequency counts. For each animal, we increase the value of the map/dict at the key of the animal name. Then, we can iterate through our diction to check whether all values are at least two.

Time Complexity: $$$O(S \log n)$$$, where $$$S$$$ is the sum of the lengths of all strings.

n = int(input())

a = []
for i in range(n):
  animal = input()
  a.append(animal)
a = sorted(a)

ans = "Yes"
for i in range(n):
  if (i == 0 or a[i] != a[i-1]) and (i == n-1 or a[i] != a[i+1]):
    ans = "No"

print(ans)

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

int main() {
  int n; cin >> n;

  vector<string> a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  sort(a.begin(), a.end());

  string ans = "Yes";

  for(int i=0; i<n; i++){
    if((i==0 || a[i] != a[i-1]) && (i==n-1 || a[i] != a[i+1])) ans = "No";
  }

  cout << ans;
  return 0;
}

Build the bracelet bead by bead. It doesn't matter where we start since it's circular.

The next bead in our sequence must be a neighbor of the previous bead. There are only two options. How can we deduce which one comes next?

n = int(input())

a = []
for i in range(n):
  x, y = map(int, input().split())
  a.append((x-1,y-1))

curr = 0
prev = -1

for i in range(n):
  print(curr+1, end = " ")

  if prev != a[curr][0]:
    prev = curr
    curr = a[curr][0]
  else:
    prev = curr
    curr = a[curr][1]

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

int main() {
  int n; cin >> n;

  vector<pair<int,int>> p(n);
  for(int i=0; i<n; i++){
    cin >> p[i].first >> p[i].second;
    p[i].first--; 
    p[i].second--;
  }

  int curr = 0, prev = -1;
  for(int i=0; i<n; i++){
    cout << curr+1 << " ";
    if(p[curr].first != prev){
      prev = curr;
      curr = p[curr].first;
    }
    else{
      prev = curr;
      curr = p[curr].second;
    }
  }

  return 0;
}

If the length and width are at least two, then $$$2w + 2l - 4 = x$$$ and $$$(w-2) \cdot (l-2) = y$$$ and

Iterate over $$$w$$$ and see if the $$$l$$$ that matches the first equation also matches the second equation.

Watch out for the edge case when the width or the height is one.

If we know the width and length, we could calculate the amount of red and blue tiles with the formulas $$$x = (2l + 2w - 4)$$$ and $$$y = (l - 2) \cdot (w - 2)$$$. Let's check all $$$l$$$ from $$$1$$$ to $$$x+y$$$ and see if there is a $$$w$$$ that satisfies both constraints. For the first constraint, we have $$$w = (x + 4 - 2l)/2$$$. Check if this $$$w$$$ also satisfies the second equation.

We additionally have to check the edge cases for $$$l$$$ equals 1, which can be accounted for manually ($$$y$$$ must be equal to zero in this case).

Time Complexity: $$$O(x + y)$$$

Read the previous solution. To check if $$$w$$$ and $$$l$$$ were valid, note that we used equations $$$x + y = wl$$$ and $$$y = (w - 2) \cdot (l - 2)$$$. We can solve these equations for $$$w$$$ and $$$l$$$ using algebra, and then the quadratic formula. Be careful about double precision.

Time Complexity: $$$O(1)$$$

x, y = map(int, input().split())

if y == 0:
  print(x+y, 1)
else:
  if x%2 == 1 or x < 4:
    print(-1)
  else:
    for l in range(2, x//2+1):
      w = (x + 4 - 2*l)//2
      if((l-2) * (w-2) == y):
        print(l, w)
        break
      if(l == x/2):
        print(-1)

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

int main() {
  int x,y; cin >> x >> y;
  if(y==0) cout << x+y << " " << 1;
  else{
    if(x%2 == 1 || x < 4) cout << "-1";
    else{
      for(int l = 2; l <= x/2; l++){
        int w = (x + 4 - 2*l)/2;
        if((l-2) * (w-2) == y){
          cout << l << " " << w;
          break;
        }
        if(l == x/2) cout << "-1";
      }
    }
  }
  return 0;
}

If $$$nm$$$ is divisible by $$$k$$$, there's always a solution. If $$$nm$$$ isn't divisible by $$$k$$$, there's no solution.

Find a way to walk between adjacent cells on the grid where you go through each cell exactly once. Why is this helpful?

n, m, k = map(int, input().split())

if (n*m)%k != 0:
  print(-1)
else:
  cpc = (n*m)//k
  for i in range(n):
    for j in range(m):
      if i%2 == 0:
        print((i*m + j)//cpc + 1, end = " ")
      else:
        print((i*m + (m-1-j))//cpc + 1, end = " ")
    print()

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

int main() {
  int x,y; cin >> x >> y;
  if(y==0) cout << x+y << " " << 1;
  else{
    if(x%2 == 1 || x < 4) cout << "-1";
    else{
      for(int l = 2; l <= x/2; l++){
        int w = (x + 4 - 2*l)/2;
        if((l-2) * (w-2) == y){
          cout << l << " " << w;
          break;
        }
        if(l == x/2) cout << "-1";
      }
    }
  }
  return 0;
}

Let's say you begin flowing water at position $$$s$$$. Under what conditions on will we be able to water city $$$q$$$?

If $$$q \gt s$$$, then there can't exist $$$s \leq i \lt q$$$ such that $$$h_i \lt h_{i+1}$$$. If $$$s \lt q$$$, then there can't exist $$$q \leq i \lt s$$$ such that $$$h_i \lt h_{i-1}$$$.

If $$$q \gt s$$$ and $$$s$$$ is a valid starting point, then $$$s+1 \leq q$$$ is also a valid starting point. Similarly, if $$$q \lt s$$$ and $$$s$$$ is a valid starting point, then $$$s-1 \geq q$$$ is also a valid starting point.

n, q = map(int, input().split())
q -= 1
a = list(map(int, input().split()))

ans = 1

for i in range(q+1, n):
  if a[i] < a[i-1]:
    break
  ans += 1

for i in range(q-1, -1, -1):
  if a[i] < a[i+1]:
    break
  ans += 1

print(ans)

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

int main() {
  int n, q; cin >> n >> q; q--;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];

  int ans = 1;
  for(int i=q+1; i<n; i++){
    if(a[i] < a[i-1]) break;
    ans++;
  }
  for(int i=q-1; i>=0; i--){
    if(a[i] < a[i+1]) break;
    ans++;
  }

  cout << ans;
  return 0;
}

Try a 4 by 4 grid. Which patterns can generalize to larger grids?

Alternate symbols every row and every other column.

test = int(input())

for tc in range(test):
  n, m = map(int, input().split())

  for i in range(n):
    for j in range(m):
      print((i+j//2)%2, end = "")
    print("")

#include<bits/stdc++.h>
using namespace std;
int main(){
  cin.tie(0)->sync_with_stdio(0);
  int test; 
  cin >> test;

  while(test--){
    int n,m;
    cin >> n >> m;

    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
        cout << (i+j/2)%2;
      }
      cout << "\n";
    }
  }
}

If there are multiple $$$i$$$ such that $$$a_i = i$$$, then which one should we choose?

Process the array backward

test = int(input())

for tc in range(test):
  n = int(input())
  a = map(int, input().split())

  ans = 0
  for i in range(n-1, -1, -1):
    if(a[i] <= i+1):
      ans += (a[i]+ans)//(i+1)
  print(ans)

#include<bits/stdc++.h>
using namespace std;
 
int main(){
  cin.tie(0)->sync_with_stdio(0);
  int test; cin >> test;
  while(test--){
    int n; cin >> n;

    vector<int> a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    long long ans = 0; 
    for(int i=n-1; i>=0; i--){
      if(a[i]<=i+1){
        ans += (a[i]+ans)/(i+1);
      }
    }

    cout << ans << '\n';
  }
  return 0;
}

It is always best to wait as long as possible before using a Golden Maiden, and to give a Golden Maiden all broken tools.

Use two pointers. The first pointer loops through tools as Hephaestus uses them. The second pointer stores which prefix of tool uses have been repaired.

test = int(input())

for tc in range(test):
  n, s = map(int, input().split())
  a = []
  for i in range(n):
    tool, time = map(int, input().split())
    tool -= 1
    a.append((tool, time))

  p, used = 0, 0
  clean = [True] * n
  impossible = False

  for (tool, time) in a:
    if not(clean[tool]):
      used += 1
      while p<n and a[p][1] <= time - s:
        clean[a[p][0]] = True
        p += 1
    if not(clean[tool]):
      impossible = True
    clean[tool] = False 
  
  if impossible:
    print(-1)
  else:
    print(used)

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

int main(){
  cin.tie(0)->sync_with_stdio(0);
  int test; cin >> test;
  while(test--){
    int n, s; cin >> n >> s;
    vector<pair<int,int>> a(n);
    for(int i=0; i<n; i++){
      cin >> a[i].first >> a[i].second;
      a[i].first--;
    }

    int p = 0, used = 0;
    bool impossible = false;
    vector<bool> clean(n, true);

    for(int i=0; i<n; i++){
      if(!clean[a[i].first]){
        used++;
        while(p<n && a[p].second <= a[i].second-s){
          clean[a[p].first] = true;
          p++;
        }
      }
      if(!clean[a[i].first]) impossible = true;
      clean[a[i].first] = false;
    }

    if(impossible) cout << "-1\n";
    else cout << used << "\n";
  }
  return 0;
}

Fix the first element of the subsequence. Then, how can you construct the longest valid subsequence?

An array element $$$a_i$$$ can only be found in $$$d(a_i)$$$ different subsequences where $$$d(x)$$$ is the number of divisors of $$$x$$$.

test = int(input())

for tc in range(test):
  n = int(input())
  a = list(map(int, input().split()))

  occs = {}
  done = {}
  for i in range(n):
    if a[i] not in occs:
      occs[a[i]] = []
      done[a[i]] = False
    occs[a[i]].append(i)

  ans = 0

  for i in range(n):
    if done[a[i]]:
      continue
    done[a[i]] = True
    tot, ind = 1, i

    while a[i]*(tot+1) in occs:
      l, r = -1, len(occs[a[i]*(tot+1)])
      while l+1 < r:
        m = (l+r)//2
        if occs[a[i]*(tot+1)][m] > ind:
          r = m
        else:
          l = m
          
      if(r == len(occs[a[i]*(tot+1)])):
        break
      ind = occs[a[i]*(tot+1)][r]
      tot += 1

    ans = max(ans, tot)
  
  print(ans)

#include<bits/stdc++.h>
using namespace std;
 
int main(){
  cin.tie(0)->sync_with_stdio(0);
  int test; cin >> test;
  while(test--){
    int n; cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin >> a[i];

    map<int, vector<int>> occs;
    for(int i=0; i<n; i++) occs[a[i]].push_back(i);
    map<int, bool> done;
    int ans = 0;
    
    for(int i=0; i<n; i++){
      if(done[a[i]]) continue;
      done[a[i]] = true;
      int tot = 1, ind = i;
      while(lower_bound(occs[a[i]*(tot+1)].begin(), occs[a[i]*(tot+1)].end(), ind) != occs[a[i]*(tot+1)].end()){
        ind = *lower_bound(occs[a[i]*(tot+1)].begin(), occs[a[i]*(tot+1)].end(), ind);
        tot ++;
      }
      ans = max(ans, tot);
    }
    cout << ans << "\n";
  }
  return 0;
}

Imagine holding up the tree by the two heads of the caterpillar, keeping all vertices in between taught, and letting all of the other vertices hang below.

When Azhdaha gets one end of his body to a vertex on the line, then it is always possible for Azhdaha can get to any vertex on the subtree below. Now, just find which vertices on the line that Azhdaha can get to.

Getting a head to a root on the line allows the other head to get to roots on the other side of the line. Those other roots allow the first head to get to more roots and so on.

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

pair<int,int> solvea(vector<int> a){
  int n = (int)a.size();
  int p1 = 0, p2 = n-1;
  int l = a[p2]-1, r = a[p1]-1;
  while((p1 < l && p1<n-1) || (p2 > n-1-r && p2>0)){
    if(p1 < l && p1 < n-1){
      p1++;
      r = max(r, a[p1]-1-p1);
    }
    if(p2 > n-1-r && p2 > 0){
      p2--;
      l = max(l, a[p2]-1-(n-1-p2));
    }
  }
  return make_pair(p1, p2);
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  int test; cin >> test;
  while(test--){
    int n; cin >> n;
    int u,v; cin >> u >> v; u--; v--;
    vector<vector<int>> adj(n);
    for(int i=1; i<=n-1; i++){
      int x,y; cin >> x >> y;
      adj[x-1].push_back(y-1);
      adj[y-1].push_back(x-1); 
    }

    // get path between u and v
    vector<int> path;

    function<bool(int,int)> getpath = [&](int node, int par){
      if(node == v){
        path.push_back(node);
        return true;
      }
      for(int c: adj[node]){
        if(c != par && getpath(c,node)){
          path.push_back(node);
          return true;
        }
      }
      return false;
    }; getpath(u, u);

    vector<bool>inpath(n);
    for(int c: path) inpath[c] = true;

    // get heights and sizes of all nodes on path
    vector<int> height(n), sizes(n);
    function<void(int,int)> dfs = [&](int node, int par){
      for(int c: adj[node]){
        if(c != par && !inpath[c]){
          dfs(c, node);
          height[node] = max(height[node], height[c]);
          sizes[node] += sizes[c];
        }
      }
      height[node] += 1;
      sizes[node] += 1;
    };
    for(int c: path) dfs(c,c);

    // reduce problem to array of heights on path
    int m = (int)path.size();
    vector<int> a;
    for(int c: path) a.push_back(height[c]);

    pair<int,int> ends = solvea(a);
    int ans = 0;
    for(int i=0; i<m; i++){
      if(i<=ends.first || i>=ends.second) ans += sizes[path[i]];
    }
    cout << ans << "\n";
  }
  return 0;
}

When you are in the same position as Xochipilli, it is always optimal to hold the position at least until the move ends.

Let $$$dp_i$$$ be the maximum amount of time you can match with Xochipilli when you are at the start of move $$$i$$$ and in position $$$p_i$$$.

Which cases for transitions can be condensed? You should end up with three general cases.

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

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int test; cin >> test;
  for(int tc=0; tc<test; tc++){
    int n,k; cin >> n >> k;
    vector<pair<int,int>> a(n);
    for(int i=0; i<n; i++){
      cin >> a[i].first >> a[i].second;
      a[i].first--;
    }

    vector<long long> ends(n);
    for(int i=0; i<n; i++){
      if(i>0) ends[i] = ends[i-1];
      ends[i] += a[i].second;
    }

    vector<long long> dp(n), maxdp(n), last(n,-1);
    int pt = n;

    for(int i=n-1; i>=0; i--){
      while(ends[i]+k <= ends[pt-1]) pt--;

      if(last[a[i].first] != -1) dp[i] = max(dp[i], dp[last[a[i].first]]);
      if(pt < n) dp[i] = max(dp[i], dp[pt] - (ends[i]+k - ends[pt-1]));
      if(pt < n-1) dp[i] = max(dp[i], maxdp[pt+1]);
      dp[i] += a[i].second;

      maxdp[i] = dp[i];
      if(i < n-1) maxdp[i] = max(maxdp[i], maxdp[i+1]);
      last[a[i].first] = i;
    }

    long long ans = 0;
    for(int i=0; i<n; i++) ans = max(ans, dp[i]);
    cout << ans << "\n";
  }
  return 0;
}

Process objects in decreasing order of y-coordinate

Call a set of banners a group if they all share a y-coordinate and a wall or rocket to the left and a wall or rocket to the right.

A group of banners blocks out contiguous ranges of x-coordinates below. What data structure can support range updates?

For a group of banners, move all banners as left as possible, and then go from right to left and move each one as far right as possible. Look at the gaps formed by this process. All x-coordinates not part of a gap are blocked out.

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

struct FenwickTree{
  int n;
  vector<int> f;
  void init(int n_){
    n = n_;
    f.resize(n); 
  }
  void add(int i, int v){
    for(; i<n; i=i|(i+1)) f[i] += v;
  }
  int sum(int i){
    int ans = 0;
    for(; i>=0; i=(i&(i+1))-1) ans += f[i];
    return ans;
  }
};

int main(){
  cin.tie(0)->sync_with_stdio(0);
  int test; cin >> test;
  while(test--){
    int n,m,x; cin >> n >> m >> x;

    vector<pair<int,int>> rockets(n);
    for(int i=0; i<n; i++) cin >> rockets[i].first >> rockets[i].second;
    vector<pair<pair<int,int>, int>> banners(m);
    for(int i=0; i<m; i++) cin >> banners[i].first.first >> banners[i].first.second >> banners[i].second;

    // line sweep
    vector<pair<int,pair<int,int>>> events;
    for(int i=0; i<n; i++) events.push_back(make_pair(rockets[i].second, make_pair(1, i)));
    for(int i=0; i<m; i++) events.push_back(make_pair(banners[i].second, make_pair(0, i)));
    sort(events.begin(), events.end(), [&](auto x, auto y){return x>y;});

    FenwickTree ft; ft.init(x+1);
    vector<bool> ans(n);
    set<int> s;
    s.insert(0); s.insert(x);

    int last_height =  -1;
    vector<int> pending;

    for(pair<int,pair<int,int>> event: events){
      int height = event.first, type = event.second.first, index = event.second.second;

      if(height != last_height){
        unordered_map<int,vector<pair<int,int>>> groups;
        for(int c: pending){
          groups[*(s.lower_bound(banners[c].first.first))].push_back(banners[c].first);
        } 
        for(pair<int, vector<pair<int,int>>> group: groups){
          sort(group.second.begin(), group.second.end());
          int rightwall = group.first; 
          int leftwall = *(--s.find(rightwall)); 
          int total_length = 0;
          for(pair<int,int> ban: group.second) total_length += ban.second-ban.first+1;
          int gapsize = rightwall-leftwall-1-total_length;
          if(gapsize == 0){
            ft.add(leftwall+1, 1);
            ft.add(rightwall, -1);
            continue;
          }
          pair<int,int> gap = make_pair(leftwall+1, leftwall+gapsize); 
          for(pair<int,int> ban: group.second){
            pair<int,int> newgap = make_pair(gap.first+ ban.second-ban.first+1, gap.second + ban.second-ban.first+1);
            if(gap.second+1 <= newgap.first-1){
              ft.add(gap.second+1, 1);
              ft.add(newgap.first, -1);
            }
            gap = newgap;
          }
        }
        pending.clear();
      }

      if(type == 1){ // rocket
        if(ft.sum(rockets[index].first) > 0){
          ans[index] = false;
          s.insert(rockets[index].first);
        }
        else ans[index] = true;
      }
      if(type == 0){ // banner
        pending.push_back(index);
      }
      last_height = height;
    }

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

Call an operation of the second type a sprouting and an operation of the first type a manual. Let $$$dp_{i, j}$$$ be the minimum number of manuals to construct the subtree at node $$$i$$$ when using exactly $$$j$$$ sproutings.

Assign sprouting counts of $$$0$$$, $$$1$$$, ... $$$j-1$$$ to $$$j$$$ different children. The other children can get any sprouting count from $$$0$$$ to $$$t$$$.

Use bitmask DP to make these assignments.

Define the type of a subtree to be the maximum number of sproutings that could possibly be applied to the subtree. How many subtrees of each type are there at most? How does this bound the total time complexity?

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

int main(){
  cin.tie(0)->sync_with_stdio(0);
  int test; cin >> test;
  while(test--){
    int n; cin >> n;
    vector<int> par(n); 
    vector<vector<int>> childs(n);
    for(int i=1; i<=n-1; i++){
      cin >> par[i]; par[i]--; 
      childs[par[i]].push_back(i);
    }

    int log = 1;
    while((1<<log) < n) log++;

    vector<vector<int>> dp(n);
    vector<int> type(n);

    function<void(int)> dfs = [&](int node){
      if(childs[node].empty()){
        type[node] = 0;
        dp[node] = {0};
        return;
      }

      // calculate type of node
      vector<int> counts(log);
      for(int c: childs[node]){
        dfs(c);
        counts[type[c]]++;
      }
      int curr = type[node] = (int)childs[node].size();
      for(int i=0; i<log; i++){
        type[node] = min(type[node], curr+i);
        curr -= counts[i];
      }

      // compute pd
      vector<int> pd(1<<(type[node]+1), n);
      pd[0] = 0;

      for(int c: childs[node]){
        vector<int> newpd(1<<(type[node]+1), n);
        for(int mask=0; mask<(1<<(type[node]+1)); mask++){
          for(int j=0; j<=min(type[node], type[c]); j++){
            if((mask>>j)&1){
              newpd[mask] = min(newpd[mask], pd[mask] + dp[c][j]);
              newpd[mask] = min(newpd[mask], pd[mask-(1<<j)] + dp[c][j]);
            }
          }
        }
        pd = newpd;
      }

      // compute dp
      for(int j=0; j<=type[node]; j++){
        dp[node].push_back(min(pd[(1<<j)-1], pd[(1<<(j+1))-1]) + (int)childs[node].size() - j);
      }
    };
    
    dfs(0);

    int ans = n;
    for(int j=0; j<=type[0]; j++) ans = min(ans, dp[0][j] + j);
    cout << ans << "\n";
  }
  return 0;
}

It is never optimal to have an edge between two nodes of the same river.

Adding the edge splits the graph into two independent graphs where each is composed of two paths. How can we solve for the equilibrium cost of one part?

Let $$$\text{best}(i)$$$ be the best city on the Blue Nile to put an edge starting from city $$$i$$$ on the White Nile.

$$$\text{best}(i)$$$ is monotonic on $$$i$$$.

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

#define F first
#define S second

typedef long long ll;
typedef long double ld;

ld single(pair<ld, ld> x, pair<ld, ld> y){
  ld a = x.F, b = x.S, c = y.F, d = y.S;
  if(a+b <= d) return a+b;
  if(c+d <= b) return c+d;
  return a*(c+d-b)/(a+c)+b;
};
 
int main(){
  cin.tie(0)->sync_with_stdio(0);
  int test; cin >> test;
  for(int tc=0; tc<test; tc++){

    // read input
    int n,m; cin >> n >> m;
    vector<pair<ll , ll>> a(n), b(m);
    for(int i=0; i<n; i++) cin >> a[i].F;
    for(int i=0; i<n; i++) cin >> a[i].S;
    for(int i=0; i<m; i++) cin >> b[i].F;
    for(int i=0; i<m; i++) cin >> b[i].S;

    // build prefix sums on each row
    vector<pair<ll, ll>> prefa = a, prefb = b;
    for(int i=1; i<n; i++){
      prefa[i].F += prefa[i-1].F;
      prefa[i].S += prefa[i-1].S;
    }
    for(int i=1; i<m; i++){
      prefb[i].F += prefb[i-1].F;
      prefb[i].S += prefb[i-1].S;
    }
    
    // shortest path if break is at l1 and l2
    function<ld(int,int)>eval = [&](int l1, int l2){
      ld left = single(prefa[l1], prefb[l2]);
      ld right = single(
        make_pair(prefa[n-1].F - prefa[l1].F, prefa[n-1].S - prefa[l1].S),
        make_pair(prefb[m-1].F - prefb[l2].F, prefb[m-1].S - prefb[l2].S));
      return left + right;
    };

    ld ans = 0;

    function<void(int,int,int,int)>consider = [&](int al, int ar, int bl, int br){
      // considers the best matchings for [al, ar] when  you know only [bl, br] is in contention
      if(bl == br){
        for(int i=al; i<=ar; i++) ans = max(ans, eval(i, bl));
        return;
      }

      int am = (al+ar)/2;
      pair<ld, int> best = make_pair(eval(am, bl), bl);
      for(int i=bl; i<=br; i++){
        best = max(best, make_pair(eval(am, i), i));
      }

      ans = max(ans, best.F);
      if(al < am) consider(al, am-1, bl, best.S);
      if(ar > am) consider(am+1, ar, best.S, br);
    };

    consider(0, n-1, 0, m-1);
    cout << setprecision(12) << ans << "\n";
  }
  return 0;
}

What if $$$a_i \gt b_i$$$ for all $$$i$$$? What if $$$a_i \lt b_i$$$ for all $$$i$$$?

Classify messages into two types. Type one is where $$$a_i \lt \leq b_i$$$ and type two is where $$$a_i \gt b_i$$$. Type one messages should go before all type two messages. Within type one messages, sort in increasing order of $$$a_i$$$ and within type two messages, sort in decreasing order of $$$b_i$$$.

How can we condense information about subranges of messages? How do these ranges merge?

Let $$$t$$$ at any given point be the amount of time required to deliver all inscribed-but-undelivered messages. Look at the effect of a message on $$$t$$$ as a function $$$t_{out}(t_{in})$$$.

The function always takes the form $$$t_{out}(x) = max(a, t_{in} + b)$$$. How do those function compose? What does this tell you about subranges of consecutive messages?

What data structure can process moving elements around and merging subarrays?

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

#define mp make_pair
#define F first
#define S second

typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;

mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

struct treap{
  // supports insertion and deletion in O(log n)

  bool compare_times(pi x, pi y){ // returns true if x comes before y
    if((x.F <= x.S) != (y.F <= y.S)) return x.F <= x.S;
    if(x.F <= x.S) return x.F < y.F;
    return x.S > y.S;
  }
 
  struct Node{
    long double priority_key; // heap key
    pi times; // (inscribe time, deliver time time) acts as bst with greedy ordering
    pair<ll,ll> relu; // out_c = max(relu.S, relu.S + c_in - relu.F)
 
    Node *left, *right;
 
    Node(pi times_) :
      priority_key(uniform_real_distribution<long double>(0.0, 1.0)(rng)), 
      times(times_), 
      relu(times_), 
      left(nullptr), 
      right(nullptr) 
    {}
 
    pair<ll,ll> compose_relu(pair<ll,ll> r1, pair<ll,ll> r2){
      if(r1.S < r2.F) return mp(r1.F+r2.F-r1.S, r2.S);
      return mp(r1.F, r2.S+r1.S-r2.F);
    }
 
    void update_relu(){
      if(left == nullptr) relu = times;
      else relu = compose_relu(left->relu, times);
      if(right != nullptr) relu = compose_relu(relu, right->relu);
    }
  };
 
  Node* root = nullptr;
 
  // divide subtree based on whether keys come before val
  pair<Node*, Node*> split(Node* node, pi val){
    if(node == nullptr) return mp(nullptr, nullptr);
    if(compare_times(node->times, val)){ // split right tree
      pair<Node*, Node*> x = split(node->right, val);
      node->right = x.F;
      node->update_relu();
      return mp(node, x.S);
    }
    else{ // split left subtree
      pair<Node*, Node*> x = split(node->left, val);
      node->left = x.S;
      node->update_relu();
      return mp(x.F, node);
    }
  }
 
  // returns root of joined, node1 has all keys less than node2
  Node* join(Node* node1, Node* node2){
    if(node2 == nullptr) return node1;
    if(node1 == nullptr) return node2;
    if(node1->priority_key > node2->priority_key){ // merge node2 into node1's right
      node1->right = join(node1->right, node2);
      node1->update_relu();
      return node1;
    }
    else{ // merge node1 into node2's left
      node2->left = join(node1, node2->left);
      node2->update_relu();
      return node2;
    }
  }
 
  // returns root of inserted
  Node* insert(Node* node, Node* toinsert){
    if(node == nullptr) return toinsert;
    if(toinsert->priority_key > node->priority_key){ // put toinsert here
      pair<Node*, Node*> splits = split(node, toinsert->times);
      toinsert->left = splits.F;
      toinsert->right = splits.S;
      toinsert->update_relu();
      return toinsert;
    }
    else{
      if(compare_times(toinsert->times, node->times)) node->left = insert(node->left, toinsert);
      else node->right = insert(node->right, toinsert);
      node->update_relu();
      return node;
    }
  }
 
  void insert(pi times_){
    Node* toinsert = new Node(times_);
    root = insert(root, toinsert);
  }
 
  Node* find(Node* node, pi times){ 
    if(node == nullptr) return nullptr;
    if(times == node->times) return node;
    if(compare_times(times, node->times)) return find(node->left, times);
    return find(node->right, times);
  }
 
  Node* erase(Node* node, Node*todelete){
    if(node == nullptr) return nullptr;
    if(node == todelete){
      Node* res = join(node->left, node->right);
      delete node;
      return res;
    }
    if(compare_times(todelete->times, node->times)) node->left = erase(node->left, todelete);
    else node->right = erase(node->right, todelete);
    node->update_relu();
    return node;
  }
 
  void erase(pi deletetimes){
    Node* todelete = find(root, deletetimes);
    if(todelete) root = erase(root, todelete);
  }
 
  ll query(pi oldtimes, pi newtimes){
    erase(oldtimes);
    insert(newtimes);
    return (root->relu).S;
  }
};
 
int main(){
  cin.tie(0)->sync_with_stdio(0);
  int test; cin >> test;
  while(test--){
    int n; cin >> n;
    vector<pair<ll, ll>> a(n);
    ll suma = 0;
    treap T;
    for(int i=0; i<n; i++){
      cin >> a[i].F >> a[i].S;
      T.insert(a[i]);
      suma += a[i].F;
    }

    int q; cin >> q;
    for(int qu=0; qu<q; qu++){
      int i; cin >> i; i--;
      pi p; cin >> p.F >> p.S;
      suma += p.F - a[i].F;
      cout << T.query(a[i], p) + suma << "\n";
      a[i] = p;
    }
  }
  return 0;
}

Create the entire triangular lattice within the shape.

What can you say about the orientation of all triangles on the border of a pointy polygon.

What happens when you remove all edges around a unit triangle?

Minimizing added perimeter is the same as maximizing the amount of deleted perimeter.

Make a graph where each triangle is a node and there is an edge between adjacent unit triangles.

The graph is bipartite. We want to find maximum independent set.

#include<bits/stdc++.h>
using namespace std;
 
#define forn(i,n) for(int i=0;(i)<(n);i++)
#define sz(x) (int)x.size()
 
#define mp make_pair
#define F first
#define S second
#define pb push_back

typedef vector<int> vi;
typedef pair<int,int> pi;
 
int MIS(vector<vi> adj){
  // assumes graph is bipartite
  // usies kuhns to find maximum bipartite match then takes complement
  
  int n = sz(adj);
 
  // finds groupings
  vi dist(n,-1);
  queue<int> bfs; 
  forn(i,n){
    if(dist[i]!=-1) continue;
    dist[i] = 0; 
    bfs.push(i);
    while(!bfs.empty()){
      int node = bfs.front(); bfs.pop();
      for(int c: adj[node]){
        if(dist[c]==-1){
          dist[c] = (1+dist[node])%2;
          bfs.push(c);
        }
      }
    }
  }
 
  vi match(n,-1);
  vi augment;
  vector<bool> vis(n);
 
  //returns whether you can find an unsaturated node
  function<bool(int)>dfs = [&](int node){
    if(vis[node]) return false;
    vis[node] = true;
    if(dist[node]==1){
      if(match[node]==-1 || dfs(match[node])){
        augment.pb(node);
        return true;
      }
    }
    else{
      for(int c: adj[node]){
        if(dfs(c)){
          augment.pb(node);
          return true;
        }
      }
    }
    return false;
  };
 
  int ans = 0;
  forn(i,n){
    if(dist[i]==1 || match[i]!=-1) continue;
    vis = vector<bool>(n);
    augment.clear();
    if(dfs(i)){
      ans++;
      for(int x = 0; x<sz(augment); x+=2){
        match[augment[x]] = augment[x+1];
        match[augment[x+1]] = augment[x];
      }
    }
  }
 
  return n - ans;
}
 
int main(){
  cin.tie(0) -> sync_with_stdio(0);
  int test; cin >> test;
  forn(tc,test){
    int n; cin >> n;
    vi a(n);
    forn(i,n){
      cin >> a[i]; // a is an array of [-2, 2]
      a[i] /= 60;
    }
    pi coord = mp(0,0);
    int direction = 0; // 0 is up right, 1 is 
    vector<pi> vertices;
 
    // find vertices and orientation
    forn(i,n){
      direction += a[i];
      if(((direction%6)+6)%6 == 0){
        coord.F += 2;
      }
      if(((direction%6)+6)%6 == 1){
        coord.F += 1;
        coord.S -= 1;
      }
      if(((direction%6)+6)%6 == 2){
        coord.F -= 1;
        coord.S -= 1;
      }
      if(((direction%6)+6)%6 == 3){
        coord.F -= 2;
      }
      if(((direction%6)+6)%6 == 4){
        coord.F -= 1;
        coord.S += 1;
      }
      if(((direction%6)+6)%6 == 5){
        coord.F += 1;
        coord.S += 1;
      }
      vertices.pb(coord);
    }
 
    // wlog vertices in clockwise order, right hand is in shape
    if(direction == -6){
      forn(i,n/2) swap(vertices[i], vertices[n-1-i]);
    }
 
    // get boundary
    vector<pi> boundary;
    map<pi,bool> inboundary;
    unordered_map<int,vi> occ;
    // occ[y] is list of all x-coordinates that mark insides of that y-value
    forn(i,n){
      pi x = vertices[i], y = vertices[(i+1)%n]; 
      if(y.F==x.F+2 && y.S==x.S){
        if(!inboundary[mp(x.F+1, x.S-1)]){
          boundary.pb(mp(x.F+1, x.S-1));
        }
        inboundary[mp(x.F+1, x.S-1)] = true;
      }
      if(y.F==x.F+1 && y.S==x.S-1){
        if(!inboundary[(mp(x.F, x.S-1))]){
          boundary.pb(mp(x.F, x.S-1));
        }
        inboundary[(mp(x.F, x.S-1))] = true;
        occ[x.S-1].pb(x.F);
      }
      if(y.F==x.F-1 && y.S==x.S-1){
        if(!inboundary[(mp(x.F-1, x.S-1))]){
          boundary.pb(mp(x.F-1, x.S-1));
        }
        inboundary[(mp(x.F-1, x.S-1))] = true;
        occ[x.S-1].pb(x.F-1);
      }
      if(y.F==x.F-2 && y.S==x.S){
        if(!inboundary[(mp(x.F-1, x.S))]){
          boundary.pb(mp(x.F-1, x.S));
        }
        inboundary[(mp(x.F-1, x.S))] = true;
      }
      if(y.F==x.F-1 && y.S==x.S+1){
        if(!inboundary[(mp(x.F, x.S))]){
          boundary.pb(mp(x.F, x.S));
        }
        inboundary[(mp(x.F, x.S))] = true;
        occ[x.S].pb(x.F);
      }
      if(y.F==x.F+1 && y.S==x.S+1){
        if(!inboundary[(mp(x.F+1, x.S))]){
          boundary.pb(mp(x.F+1, x.S));
        }
        inboundary[(mp(x.F+1, x.S))] = true;
        occ[x.S].pb(x.F+1);
      }
    }
 
    vector<pi> interior;
    map<pi, int> index;
 
    for(pair<int,vi> p: occ){
      sort(p.S.begin(), p.S.end());
      for(int i = 0; i<sz(p.S); i+=2){
        for(int j=p.S[i]; j<=p.S[i+1]; j++){
          interior.pb(mp(j,p.F));
        }
      }
    }
 
    // nodes in triangles - boundary are graph
    vector<pi> graph;
    for(pi p: interior){
      if(!inboundary[p]){
        index[p] = sz(graph);
        graph.pb(p);
      }
    }
 
    // construct graph
    int N = sz(graph);
    vector<vi> adj(N);
 
    forn(i,N){
      int x = graph[i].F, y = graph[i].S;
      if(!inboundary[mp(x-1,y)]){
        adj[i].pb(index[mp(x-1,y)]);
      }
      if(!inboundary[mp(x+1,y)]){
        adj[i].pb(index[mp(x+1,y)]);
      }
      if(((x+y)%2+2)%2 == 0){ // pointed down
        if(!inboundary[mp(x, y+1)]){
          adj[i].pb(index[mp(x,y+1)]);
        }
      }
      else{ // pointed up
        if(!inboundary[mp(x, y-1)]){
          adj[i].pb(index[mp(x,y-1)]);
        }
      }
    }
 
    int mis = MIS(adj);
    cout << (3*sz(interior)+n)/2 - 3*mis - n << "\n";
  }
  return 0;
}

All of the input possibilities are names of Greek Gods (specifically Olympians).

Google the name of each Olympian.

s = input()
if s == "Hephaestus" or s == "Ares":
  print("Hera")
elif s == "Apollo" or s == "Artemis":
  print("Leto")
else:
  print("Rhea")

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

int main() {
  string s; cin >> s;

  if(s == "Hephaestus" || s == "Ares") cout << "Hera";
  else if(s == "Apollo" || s == "Artemis") cout << "Leto";
  else cout << "Rhea";

  return 0;
}

The output suggests that this is some kind of hand game.

If you don't know the game, you can search up "Slide, Slide, Slippery Slide clap missing 5". In general, just try cramming every clue in the problem into one google query.

n = int(input())
for i in range(1, n+1):
  if not('5' in str(i)):
    print("Clap", i)

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

int main() {
  int n; cin >> n;

  for(int i=1; i<=n; i++){
    if(to_string(i).find('5') == string::npos) cout << "Clap " << i << "\n";
  }

  return 0;
}

Note everything that the limerick references: turtle, python, counting, program, pen.

The problem is loosely about the Python turtle module.

Aak is the mayan word for turtle

The problem is about mayan numerals

def read_cell():
  res = 0
  rows = int(input())
  for row in range(rows):
    inp = input().split()
    for i in range(len(inp)):
      if inp[i] == "down":
        if inp[i+1] == "up":
          res += 1
        else:
          res += 5
  return res

ans = 0
cells = int(input())
for cell in range(cells):
  ans *= 20
  ans += read_cell()

print(ans)

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

int read_cell() {
  int res = 0;
  int rows; cin >> rows;
  cin.ignore(); 

  for (int r = 0; r < rows; ++r) {
    string line;
    getline(cin, line);
    stringstream ss(line);
    vector<string> inp;
    string word;

    while (ss >> word)  inp.push_back(word);

    for (int i = 0; i < (int)inp.size(); ++i) {
      if (inp[i] == "down") {
        if (inp[i + 1] == "up") res += 1;
        else res += 5;
      }
    }
  }

  return res;
}

int main() {
  int ans = 0;
  int cells; cin >> cells;

  for (int cell = 0; cell < cells; ++cell) {
    ans *= 20;
    ans += read_cell();
  }

  cout << ans << endl;
  return 0;
}