kirill lykov KirillLykov

Interesting problem on dynamic programming from atcoder. Given a string in the format "(|?)+" find how many number can be formed such that the reminder of the division of each of this numbers by 13 gives exactly 5.

So lets define function dp[x][y] to be count of such numbers for prefix of length x and reminder y. For example, for 1?2 dp[2][5] will mean the count of such numbers for substring 1? and the reminder 5.

The interesting part is the transition. It uses implicit difinition.

for (all prevReminder)
  dp[i+1][ (prevReminder * 10 + curDigit)%13 ] += dp[i][prevReminder]

Problem 1

Given an array with coins and target amount x. Find number of ways this sum can be formed if you can use each coin main times. lc

Hint

Define function dp[len][x] - answer for subarray [0:len] for amount x.
Find the recurent function.

The problem is to find all rectangular of minimal area spanned on 4 points from the given set. See lc.

The brute force solution is to have a cache of already tackled points and for each current point and for each point in cache we are looking in the cache if necessary 2 other points existed. Beside of fast search, the cache of seen points also allows to avoid considering dublicates.

    struct Hash {
        size_t operator()(const pair<int,int>&x)const{
            return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));

Interesting problem on sliding window: lc

The idea of solution is to solve a simpler problem - count subarrays with at most K distinct characters. This one is similar to longest substr without repeating characters

class Solution {
public:

Data structure itself. We don't store the data itself - only max.

    class MaxQueue {
        deque< pair<int,size_t> > dq; // first is value, second is how many 
        // time this value is used beside itself
        // for example, for  [7,3,4,5] 5 will be used 2 times, 7 0 times
      public:
        void push(int x) {
            size_t cnt = 0;

Problem 0

A sorted array was cyclicly shifted by unknown offset. Find min element. lc

Solution

    int findMin(vector<int>& nums) {
        if (nums.size() == 0) return 0;

Solution for https://leetcode.com/problems/shortest-palindrome/submissions/

everyone is writing KMP and Manacher, I would just write a simple hashing algorithm:

    const int p = 31;
    const int M = 1e9 + 7; // I prefer always use mod prime even if we don't need to 
	// find a reverse element. Just for consistancy, it is faster to write one standard way
	// every time instead of creating something ad hoc
    string shortestPalindrome(string s) {
        const int n = s.size();

The firsrt hashing function is a standard string hashing together coupled with sorting of the string elements to get rid of ambiguity: we want our hash to return the same value independently on the order of the characters in the string. This approach essentially requires copying of the string because we cannot mutate the original strings since we need them later to construct the output.

The second approach is hasing based on prime numbers. Basically, we encode each unique char with a prime number. This approach does not require sorting and, hence, sorting of the string.

class Solution {
public:

	// https://codeforces.com/contest/242/problem/C
	// You are given lines where king can move (row and column start/finish
	// You need to find min number of moves. The grid is too large to use standard bfs 10^9*10^9
	// Important - add to visited when add to queue!!! (line 60)
	#include <bits/stdc++.h>
	using namespace std;

	struct hasher {
	size_t operator() (const pair<int,int>& p) const {
	return (((size_t)p.first)<<31)^(p.second);

	// Given bollean expression with only one variable (x, note that X := !x),
	// find the minimum number of symbols editing to make it independent on the variable
	// value. For example, (x&0) does not depend on x.
	//
	// The idea is that we can always achieve this by changing the root operation in AST
	// So we just find out if the output of the expression (represented as vector 0xAB, where A,B <- {0,1})
	// is either 0x11 or 0x00.
	// Otherwise, there is exactly one modification to achieve what is needed (change root operation).
	#include <bits/stdc++.h>
	using namespace std;