KirillLykov

inline std::size_t hash_combine(std::size_t hash1, std::size_t hash2) {
    return hash1 ^ (hash2 * 0x9e3779b9 + (hash1 << 6) + (hash1 >> 2));
}

struct Hasher2 {
  size_t operator() (const tuple<int,int>& val) const {
      return hash_combine(hash<int>{}(get<0>(val)), hash<int>{}(get<1>(val)));
  } 
};

KirillLykov

codeforces

Quite interesing problem. We need to minize function of sum_l sum_r f(l,r), where f(l,r) = sum_i ai * bi, i<-[l,r]. So first of all forget about the fact we have two vectors, try to rewrite sum of all the sum of subarrys in one sum. Should have a form sum_i ai * coef(i, n).

How many subarrays are in the array of length n? The same is how many ordered pairs <i,j>? For each i there (n - i) subarrays starting at this i. The total number is S(n) = sum_i (n - i) = n^2 - n(n-1)/2 = n(n+1)/2.

KirillLykov

The solution is split into two parts:

1. Check if there are loops
2. Return ordered vertices indices

Check for the loops is done with recursion and without just as an exercise.

A more interesting thing is to compute the order. So we actually solve a different problem -- for each vertex tell what is the earliest moment we can start it.

Easy to see that:

KirillLykov

Given 2 arrays, find if it is possible to make the first to be strictly increasing by replace some of it's elements with those from array2. Solution using memoization and dfs. It got TLE, I guess due to memory allocation because if I use static it worked, whatever.

LC

class Solution {
public:
    vector<vector<int>> mem;

KirillLykov

// further readings: http://forskning.diku.dk/PATH05/GoldbergSlides.pdf
// problem itself https://leetcode.com/problems/minimum-moves-to-move-a-box-to-their-target-location/
class Solution {
public:
    using State = tuple<int,int,int,int>; // xbox, ybox, xme, yme
    static constexpr int x[] = {1,-1,0,0};
    static constexpr int y[] = {0,0, 1, -1};
    
    bool impossible(vector<vector<char>>& grid, const pair<int,int>& pos) {
        if (pos.first < 0 || pos.first >= grid.size() || 

KirillLykov

// The problem is to find sum_i sum_j {max(segment[i,j]) - min(segment[i,j]}
// The main observation is that sum(i,j) of max - min = sum(i,j) max - sum(i,j) min
// To find sum of all the maximums we find how many time each number might be maximum by using standard 
// technique of looking forward/backward
// https://codeforces.com/contest/817/problem/D
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

// For a given index i, finds and saves index of 

KirillLykov

Useful facts

• E - is linear operator, eg E(x + y) = Ex + Ey and we don't care about independence of the events
• If the problems is like find expectation of the maximum value in N tries you can use the following fact:

P(outcome == k) = P(outcome is at most k) - P(outcome is at most k-1)
P(outcome is at most k) = (k/m)^n

For instance, if the problem "You roll a 6-sided die twice. Find EV of the bigger of two scores.":

KirillLykov

Performance tips & tricks

Perf tool [1]

# general statistics
perf stat ./main

# per function statistics with graph call
# -fno-omit-frame-pointer fals must be used to see proper call stack!!!

KirillLykov

System Design Cheatsheet

Picking the right architecture = Picking the right battles + Managing trade-offs

Basic Steps

1. Clarify and agree on the scope of the system

• User cases (description of sequences of events that, taken together, lead to a system doing something useful)
  • Who is going to use it?
  • How are they going to use it?

KirillLykov

// https://leetcode.com/problems/number-of-matching-subsequences/submissions/
class Solution {
public:
    int getCode(char c) {
        return c - 'a';
    }
    
    bool recognized(vector< array<int,26> > const& dfa, string const& w) {
        int cur = 0;
        for (char c : w) {