KirillLykov

Problem: Given a binary tree, we install cameras on the nodes of the tree. Each camera at a node can monitor its parent, itself, and its immediate children. Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Solution: The basis of the induction is that leafs (if it is not trivial case) has no camera. This is the key in this greedy approach. The elegant way to express this, introduced by lee215, is by coloring not existing nodes by COVERED.

KirillLykov

// https://atcoder.jp/contests/abc125/tasks/abc125_c
// There are N integers,, written on the blackboard.
// You will choose one of them and replace it with an integer of your choice between 1 and 10^9 (inclusive), 
// possibly the same as the integer originally written.
// Find the maximum possible greatest common divisor of the  N integers on the blackboard after your move.

// Interesting prolem on precomputing prefix/suffix function
// In this case it is gcd which is associative as we know
#include <bits/stdc++.h>
using namespace std;

KirillLykov

1. Let A is array, find maximum sum of subarray in A. Empty subarray is also valid.

int res = -1e9;
int dp0 = 0;
for (int i = 0; i < n; ++i) {
  dp0 = max(0, dp0 + A[i]);
  res = max(res, dp0);
}
return res;

KirillLykov

// https://codeforces.com/contest/1146/problem/C
// To find diameter of a tree in non-interactive problem
// it would be enought to:
// 1. take a random vertex v
// 2. find the most distant from v vertex u
// 3. find the distance to the most distance from u vertex,
// this would be the answer
//
// Now, in interactive problem we want to find the most distant
// vertex from randomly chosen vertex 1.

KirillLykov

// Count number of unique subsequencies of DNA sequence
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

// only 4 letters
int char2int(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    if (c == 'G') return 2;

KirillLykov

Problem 1

Given array and length of sliding window return array of maximum in each position for sliding window. leetcode

Solution

The algorithm outlook is the following:

1. Precompute array containing for each value nums[i] index of the following value less than nums[i]

KirillLykov

Problem 1: Add elements on segments

You are given list of requests you need to execute. Eeach request is a triple (l,r,x), which means that to all the elements with indixes in the range [l,r) you need to add x. You are to print all the values in the array Input: n - size of the array (<10^5), m - the number of requests.

Example: Input: [0 2]

KirillLykov

// http://codeforces.com/problemset/problem/543/B
// delete edges such that there is path between dist(si, ti) < li, i < 2
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(NULL);

    int n, m;
    cin >> n >> m;

KirillLykov

#include <cassert>
#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>

using namespace std;
using namespace __gnu_pbds;

// A PATRICIA trie with a prefix-search node-updator type. Note that

KirillLykov

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

class disjoint_sets
{
    vector<int> parent;
    vector<int> rank;
    vector<int> count;
public:
    disjoint_sets(size_t sz)