This post is based on this leetcode problem.

1
2
3
4
5
6
7
8
9

# preludes
# from collections import *
class Solution:
    def mostFrequentEven(self, nums: List[int]) -> int:
        try:
            return max(Counter([i for i in nums if not i % 2]).items(), key=lambda x:(x[1], -x[0]))[0]
        except:
            return -1
        

In this problem, we are trying to get the most frequent even number in a sequence, if there's multiple most frequent answers, we take the smallest one. E.g. for a sequence of number , the smallest of most frequent numbers is .

We first use a list comprehension to get the even values followed by putting them on the init values of Counter() class from the collections module to get a counter for the list of numbers. Then use .items() method to convert the Counter object, which is actually a dict, to a list to tuples that looks like (number, frequency). We then use a max function we a key argument to get the most frequent element and the smallest one. What we do here is to create a tuple for each key, x[1] means we want the most frequent ones first, -x[0] means we want the smallest number first. Putting them in a tuple means we want the one that fulfils both conditions but the first one has a higher priority. We then ask for the first item in the sorted list and return that value. Finally, we wrap the whole line with a try and except block because if there's no even number, the length of the list comprehension will be zero, and max function will raise an error.

Original Problem: https://leetcode.com/contest/weekly-contest-311/problems/sum-of-prefix-scores-of-strings/

For a string , we need to find all its prefixes and all strings with the same prefix. We can achieve this goal by using a trie tree with a meta tag in each node to record the time for a specific prefix to happen in all strings.

Time complexity: Space complexity:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    
    def sumPrefixScores(self, words: List[str]) -> List[int]:
        tree = {}
        # build tree
        for word in words:
            cur = tree
            for i in word:
                if cur.get(i):
                    cur = cur[i]
                    cur['meta'] += 1
                else:
                    cur[i] = {}
                    cur = cur[i]
                    cur['meta'] = 1
        
        # calculate
        ans = []
        for word in words:
            t = 0
            cur = tree
            for i in word:
                cur = cur[i]
                t += cur['meta']
            ans.append(t)
        
        return ans

DP Problemss I've met

LC22

Note: BFS-Like Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution
{
public:
    vector<string> generateParenthesis(int n)
    {
        deque<pair<string, pair<int, int>>> dq;
        vector<string> res;
        dq.push_back({"(", {1, 0}});
        while (!dq.empty())
        {
            auto tt = dq.front();
            string t = tt.first;
            auto l = tt.second.first, r = tt.second.second;
            dq.pop_front();

            if (t.length() == n * 2)
                res.push_back(t);
            else
            {
                if (l < n)
                    dq.push_back({t + "(", {l + 1, r}});

                if (r < l)
                    dq.push_back({t + ")", {l, r + 1}});
            }
        }
        return res;
    }
};

Educational Codeforces Round 130

Origin Problem set can be fine here

A. Parkway Walk

If the amount of energy is capable of allowing us to travel without a rest, return . Else return the energy needed to be recover.

Code:

1
2
3
4
5
6
7
8
9
10

fn slove(sc: &mut Scanner, wr: &mut Writer) {
    let n = sc.nextInt();
    let m = sc.nextInt();
    let mut s = 0;
    for _ in 0..n {
        let tmp = sc.nextInt();
        s += tmp;
    }
    wr.println(max(&(s - m), &0));
}

B. Promo

After getting all of the input, sort the array reversely and calculate prefix sum of it. For each pair of and , the maximum value of free item would be .

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

fn slove(sc: &mut Scanner, wr: &mut Writer) {
    let n = sc.nextUsize();
    let m = sc.nextInt();
    let mut v: Vec<i32> = (0..n).map(|_| sc.nextInt()).collect();
    v.sort_unstable();
    v.reverse();
    let mut s: Vec<u64> = vec![0; n + 1];
    for i in 1..n + 1 {
        s[i] = s[i - 1] + v[i - 1] as u64;
    }
    for _ in 0..m {
        let (x, y) = (sc.nextUsize(), sc.nextUsize());
        wr.println(&(s[x] - s[x-y]));
    }
}

C. awoo's Favorite Problem

First, the count of a, b and c must be the same. A c must come after a a in order for them to be exchanged. At any position , .

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

fn slove(sc: &mut Scanner, _wr: &mut Writer) -> bool {
    let n = sc.nextUsize();
    let s: Vec<_> = sc.nextLine().chars().collect();
    let t: Vec<_> = sc.nextLine().chars().collect();
    let mut x = vec![];
    let mut y = vec![];
    for i in 0..n {
        if s[i] == 'c' {
            x.push((2, i));
        } else if s[i] == 'a' {
            x.push((0, i));
        }
        if t[i] == 'c' {
            y.push((2, i));
        } else if t[i] == 'a' {
            y.push((0, i));
        }
    }
 
    if x.len() != y.len() {
        return false;
    }
 
    x.iter().zip(y.iter()).all(|(&(t1, p1), &(t2, p2))| {
        if t1 != t2 {
            return false;
        }
        if t1 == 0 {
            return p1 <= p2;
        }
        return p1 >= p2;
    })
})}

D. Guess The String

For character at a index , check where . If result of q2 equals to the unique letters in the range, the letter at must equal to the letter on position`. We can then use a binary search to improve this algorithm to decrease the amount of query for each letter to . If there is no such result even when , the letter must be a new letter. Use q1 on it.

Total Number of query2 would be O(nlog(n)).

Unoptimized Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

char q1(int pos)
{
    string s;
    cout << "? 1 " << pos + 1 << endl
         << flush;
    cin >> s;
    return s[0];
}
 
int q2(int pos1, int pos2)
{
    int ans;
    cout << "? 2 " << pos1 + 1 << ' ' << pos2 + 1 << endl
         << flush;
    cin >> ans;
    return ans;
}
 
void solve()
{
    int len;
    cin >> len;
    vector<char> res(len, '?');
 
    res[0] = q1(0);
    for (int i = 1; i < len; i++)
    {
        set<char> st;
        bool f = false;
        for (int j = i - 1; j >= 0; j--)
        {
            st.insert(res[j]);
            if (q2(j, i) == int(st.size()))
            {
                res[i] = res[j];
                f = true;
                break;
            }
        }
 
        if (!f)
            res[i] = q1(i);
 
    }
 
    cout << "! ";
    for (auto &a : res)
        cout << a;
    cout << endl
         << flush;
}

Original Problem can be found here.

For number and , we can found that ones in plus ones in , equals to the ones in plus ones in .

E.g. for and , their binary formats are and , (3 & 2).bit_count() equals to 1, (3 | 2).bit_count() equals to 2.

Thus, for this problem, we need to find any pair of numbers where the sum of their bit_count() is greater or equal than . We can use a binary search algorithm to achieve this.

Time Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

import bisect

class Solution:
    def countExcellentPairs(self, nums: List[int], k: int) -> int:
        res = 0
        nums = set(nums)

        def bitcount(x: int):
            c = 0
            while x:
                c += x & 1
                x >>= 1
            return c

        length = len(nums)
        binl = sorted([bitcount(i) for i in nums])
        for ii, i in enumerate(binl):
            pos = bisect.bisect_left(binl, k - i)
            t = length - pos
            res += t
        
        return res

Published here Easy to use. This site is built with this tool

A Tool that allows you to build your blog using Github Pages

THIS IS A DEPRECATED PROJECT, SOME FUNCTIONS MAYNOT WORK AS INTENDED.

Usage

Press Use This template

Create your content in the content/ folder

Write the following in your commandline

1

./x.py push

Demo

My personal blog: https://sbihere.github.io/

Markdown Latex Template QuickNote

Original Project Site: https://github.com/Wandmalfarbe/pandoc-latex-template

Usage

1

pandoc example.md -o example.pdf --from markdown --template eisvogel --listings

On top of document write

1
2
3
4
5
6
7
8

---
title: "The Document Title"
author: [Example Author, Another Author]
date: "2017-02-20"
keywords: [Markdown, Example]
...

Here is the actual document text...

Minimum Template

This is the minimum template that only implements BufferedReader and BufferedWriter. Unlike std::io::BufReader, you can simply use sc.nextInt() to get next int.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_imports)]

fn slove(sc: &mut Scanner, wr: &mut Writer){
	// Your code starts here.
}

fn main() {
    let mut sc = Scanner::new();
    let mut wr = Writer::new();

    let T = sc.nextUsize();
    for _ in 0..T {
        slove(&mut sc, &mut wr);
    }
}

use std::{
    array,
    cmp::*,
    collections::{HashMap, LinkedList, VecDeque},
    hash::Hash,
    io::{stdin, stdout, BufRead, BufReader, BufWriter, Stdin, Stdout, Write},
};

struct Scanner {
    buf: LinkedList<String>,
    reader: BufReader<Stdin>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            buf: LinkedList::new(),
            reader: BufReader::new(stdin()),
        }
    }

    fn read<T: std::str::FromStr>(&mut self) -> T {
        match self.buf.pop_front() {
            Some(s) => s.parse().ok().expect("failed while parsing"),
            None => {
                self.buf = self
                    .nextLine()
                    .split_whitespace()
                    .map(String::from)
                    .collect();
                self.read()
            }
        }
    }

    fn nextUsize(&mut self) -> usize {
        self.read()
    }

    fn nextInt(&mut self) -> i32 {
        self.read()
    }

    fn nextFloat(&mut self) -> f32 {
        self.read()
    }

    fn nextLine(&mut self) -> String {
        let mut buffer = String::new();
        self.reader.read_line(&mut buffer).ok();
        String::from(buffer.trim())
    }
}

struct Writer {
    writer: BufWriter<Stdout>,
}

impl Writer {
    fn new() -> Writer {
        Writer {
            writer: BufWriter::new(stdout()),
        }
    }

    fn print<T: ToString>(&mut self, s: &T) {
        self.writer.write(s.to_string().as_bytes()).ok();
    }

    fn println<T: ToString>(&mut self, s: &T) {
        self.print(s);
        self.print(&'\n');
    }
}

Simple Shortlink service

Find Source Code and deploy instruction here

A free solution for building your own shortlink service.

Usage

1. Install Deta CLI and login.
2. Run the following commands in your terminal

   1 2 3 4

   git clone https://github.com/spihere/shortlink-py-deta deta new -p shortlink-py-deta cd shortlink-py-deta deta deploy

3. The deta new command returns a json formatted string that contains the URL for your instance.
4. use [your-instance-url]/link to access a short link, [url]/new?src=[alias]&to=[target] to create a shortlink, [url]/del?src=[alias]to delete a shortlink.

Example

Create an alias

1

[url]/new?src=google&target=https://www.google.com

Accessing the alias

1

[url]/google

Deleting the alias

1

[url]/del?src=google

Demo

Due to abuse, I won't provide a Demo.

Contributing

By adding DBConnections implementation in the db folder, this application can support other databases. You can do it by creating a new file in db folder and implements a class that inherits DBCOnnection abstract class. You can then change the database variable in main.py to anything you want.

Codeforces #797 (Div.3) Simple Solution

Original Problems: https://codeforces.com/contest/1690

A

Try split the problem into three situations: , , . Then it can be solved easily.

Code:

1
2
3
4
5
6
7
8
9
10
11

void solve()
{
    int n;
    cin >> n;
    if (n % 3 == 0)
        cout << n / 3 << ' ' << n / 3 + 1 << ' ' << n / 3 - 1 << endl;
    else if (n % 3 == 1)
        cout << n / 3 << ' ' << n / 3 + 2 << ' ' << n / 3 - 1 << endl;
    else
        cout << (n + 1) / 3 << ' ' << (n + 1) / 3 + 1 << ' ' << n / 3 - 1 << endl;
}

B

For each pair of pair and , if b equals to zero. have to be subtracted at least b times, but have no limit on how high it goes. If is not zero, but be greater or equal than , also must be equal to the on other pairs where is not zero.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

typedef vector<int> vi;
#define yesnosolve cout << (solve() ? "NO" : "YES") << endl

int solve()
{
    int n;
    cin >> n;
    vi a(n), b(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];

    int m = -1;

    for (int i = 0; i < n; i++)
        m = max(a[i] - b[i], m);

    for (int i = 0; i < n; i++)
    {
        if (b[i] == 0)
        {
            if (a[i] > m)
                return 1;
        }
        else
        {
            if (a[i] < b[i] || a[i] - b[i] < m)
                return 1;
        }
    }

    return 0;
}

C

For the first end time , duration is . For other end time , duration is

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

typedef vector<int> vi;

void solve()
{
    int n;
    cin >> n;
    vi s(n), f(n);
    for (int i = 0; i < n; i++)
        cin >> s[i];
    for (int i = 0; i < n; i++)
        cin >> f[i];

    cout << f[0] - s[0] << ' ';
    for (int i = 1; i < n; i++)
    {
        cout << f[i] - max(s[i], f[i - 1]) << ' ';
    }
    cout << endl;
}

D

Use prefix sum algorithm to determine black strips in a certain region. Iterate through the array and find the minimum value of

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

const int INF = 2e9;
typedef vector<int> vi;

void solve()
{
    string s;
    int n, m;
    cin >> n >> m;
    cin >> s;
    s = ' ' + s;
    vi p(n + 10), a(n + 10);
    for (int i = 1; i <= n; i++)
        if (s[i] == 'B')
            p[i]++;

    for (int i = 1; i <= n + 1; i++)
        a[i] = a[i - 1] + p[i];

    int mi = INF;
    for (int i = 1; i + m <= n + 1; i++)
        mi = min(mi, m - a[i + m - 1] + a[i - 1]);
    cout << mi << endl;
}

E

1. Sum the value of each where is integer division for each goods to a value .
2. Create a new array using the remainder of the last step.
3. Sort the array and use binary search to find the minimun where .
4. Add one to and erase both elements and continue.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

typedef unsigned long long ull;
typedef vector<int> vi;

void solve()
{
    int n, k;
    cin >> n >> k;
    vi g(n);
    for (int i = 0; i < n; i++)
        cin >> g[i];

    multiset<int> st;

    ull ans = 0;
    for (auto& a : g)
        ans += a / k, st.insert(a % k);

    while (!st.empty())
    {
        auto t = *st.begin();
        st.erase(st.begin());

        auto it = st.lower_bound(k - t);
        if (it != st.end())
            ans++, st.erase(it);
    }

    cout << ans << endl;
}