Записи в блоге

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Блог пользователя netman

Разбор раунда Codeforces Round #390 (Div. 2)

Автор netman, история, 8 лет назад, По-русски

Tutorial is loading...

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	vector<int> a(n);
	long long sum = 0;
	for (int & x : a) {
		scanf("%d", &x);
		sum += x;
	}
	if (sum != 0) {
		puts("YES");
		puts("1");
		printf("%d %d\n", 1, n);
		exit(0);
	}
	sum = 0;
	for (int i = 0; i < n; i++) {
		sum += a[i];
		if (sum != 0) {
			puts("YES");
			puts("2");
			printf("%d %d\n", 1, i + 1);
			printf("%d %d\n", i + 2, n);
			exit(0);
		}
	}
	puts("NO");
}

Tutorial is loading...

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
	char str[4][4 + 1];
	// cells are '.', 'o', 'x'
	for (int i = 0; i < 4; i++) {
		cin >> str[i];
	}

	auto check = [&]() {
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				for (int dx = -1; dx <= 1; dx++) {
					for (int dy = -1; dy <= 1; dy++) {
						if (dx == 0 && dy == 0) continue;
						if (i + dx * 3 > 4 || j + dy * 3 > 4 || i + dx * 3 < -1 || j + dy * 3 < -1) continue;
						bool ok = true;
						for (int p = 0; p < 3; p++) {
							ok &= str[i + p * dx][j + p * dy] == 'x';
						}
						if (ok) return true;
					}
				}
			}
		}
		return false;
	};

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (str[i][j] == '.') {
				str[i][j] = 'x';
				if (check()) {
					puts("YES");
					exit(0);
				}
				str[i][j] = '.';
			}
		}
	}
	puts("NO");
}

Tutorial is loading...

Code

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()

void solve() {
	int n;
	cin >> n;
	vector<string> names(n);
	for (string& name : names) {
		cin >> name;
	}
	sort(all(names));

	auto getIdx = [&](const string& s) {
		int pos = lower_bound(all(names), s) - names.begin();
		if (pos == (int)names.size() || names[pos] != s) return -1;
		return pos;
	};

	auto splitIntoUserMessage = [](const string& s) {
		size_t pos = s.find(':');
		assert(pos != string::npos);
		return make_pair(s.substr(0, pos), s.substr(pos + 1));
	};

	auto splitIntoTokensOfLatinLetters = [](const string& s) {
		vector<string> result;
		string token;
		for (char c : s) {
			if (isalpha(c) || isdigit(c)) {
				token += c;
			}
			else {
				if (!token.empty()) {
					result.push_back(token);
				}
				token.clear();
			}
		}
		if (!token.empty()) {
			result.push_back(token);
		}
		return result;
	};

	int m;
	cin >> m;
	vector<int> who(m);
	vector<vector<char>> can(m, vector<char>(n, true));

	vector<string> messages(m);

	string tmp;
	getline(cin, tmp);

	for (int i = 0; i < m; i++) {
		string cur;
		getline(cin, cur);
		pair<string, string> p = splitIntoUserMessage(cur);
		const string& user = p.first;
		const string& message = p.second;
		who[i] = getIdx(user);
		if (who[i] != -1) {
			fill(all(can[i]), false);
			can[i][who[i]] = true;
		}
		messages[i] = message;
		vector<string> tokens = splitIntoTokensOfLatinLetters(message);
		for (const string& z : tokens) {
			int idx = getIdx(z);
			if (idx != -1) {
				can[i][idx] = false;
			}
		}
	}

	vector<vector<int>> par(m, vector<int>(n, -1));
	for (int i = 0; i < n; i++) {
		if (can[0][i]) par[0][i] = 0;
	}
	for (int msg = 0; msg + 1 < m; msg++) {
		for (int i = 0; i < n; i++) {
			if (par[msg][i] == -1) continue;
			for (int j = 0; j < n; j++) {
				if (i == j) continue;
				if (can[msg + 1][j]) {
					par[msg + 1][j] = i;
				}
			}
		}
	}
	int msg = m - 1, pos = -1;
	for (int i = 0; i < n; i++) {
		if (par[msg][i] != -1) {
			pos = i;
			break;
		}
	}
	if (pos == -1) {
		cout << "Impossible\n";
		return;
	}
	while (msg >= 0) {
		who[msg] = pos;
		pos = par[msg][pos];
		msg--;
	}
	for (int i = 0; i < m; i++) {
		cout << names[who[i]] << ":" << messages[i] << "\n";
	}
	return;
}

int main() {
	//freopen("input.txt", "r", stdin);
	int t;
	cin >> t; // number of tests

	while (t--) {
		solve();
	}
}

Tutorial is loading...

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int nextInt() {
	int x = 0, p = 1;
	char c;
	do {
		c = getchar();
	} while (c <= 32);
	if (c == '-') {
		p = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * p;
}

#define all(x) (x).begin(), (x).end()

const int N = (int)3e5 + 5;
const int MAX_VAL = (int)1e9;

int n;
ll l[N], r[N];

struct event {
	ll x;
	int c;
	event() {}
	event(ll x, int c) : x(x), c(c) {}
};

pair<ll, int> check(ll len) {
	if (len == 0) return make_pair(0LL, n);
	static vector<event> evs;
	evs.resize(0);
	for (int i = 1; i <= n; i++) {
		if (r[i] - len > l[i]) {
			evs.push_back(event(l[i], 1));
			evs.push_back(event(r[i] - len, -1));
		}
	}
	sort(all(evs), [](const event & a, const event & b) { return a.x < b.x; });
	reverse(all(evs));
	int cnt = 0, maxiCnt = 0;
	ll bestPos = 0;
	while (evs.size() > 0) {
		ll x = evs.back().x;
		while (evs.size() > 0 && evs.back().x == x) {
			cnt += evs.back().c;
			evs.pop_back();
		}
		if (cnt > maxiCnt) {
			maxiCnt = cnt;
			bestPos = x;
		}
	}
	return make_pair(bestPos, maxiCnt);
}

vector<int> getAns(ll len) {
	if (len == 0) {
		vector<int> res(n);
		iota(all(res), 1);
		return res;
	}
	ll pos = check(len).first;
	vector<int> res;
	for (int i = 1; i <= n; i++) {
		if (pos >= l[i] && pos < r[i] - len) {
			res.push_back(i);
		}
	}
	return res;
}

int main() {
	n = nextInt();
	int k = nextInt();
	for (int i = 1; i <= n; i++) {
		l[i] = nextInt();
		r[i] = nextInt() + 2;
	}
	ll l = 0, r = MAX_VAL + MAX_VAL + 5;
	while (r - l > 1) {
		ll mid = (l + r) >> 1;
		if (check(mid).second >= k) l = mid;
		else r = mid;
	}

	vector<int> ans = getAns(l);

	cout << l << endl;
	assert((int)ans.size() >= k);
	ans.resize(k);
	for (int i : ans) {
		printf("%d ", i);
	}
	puts("");
}

Tutorial is loading...

C++ code

#include <bits/stdc++.h>

using namespace std;

const int N = (int)404;
const int ALPHA = 26;

bitset<N> b[ALPHA][N];
char patt[N][N];
bitset<N> result[N];

bitset<N> getShifted(const bitset<N>& b, int len, int shift) {
	assert(0 <= shift && shift < len);
	return (b >> shift) | (b << (len - shift));
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int n, m, r, c;
	scanf("%d%d", &n, &m);

	for (int i = 0; i < n; i++) {
		static char str[N];
		scanf("%s", str);
		for (int j = 0; j < m; j++) {
			b[(int)(str[j] - 'a')][i][j] = true;
		}
	}
	
	scanf("%d%d", &r, &c);

	for (int i = 0; i < n; i++) {
		result[i] = ~result[i];
	}

	for (int i = 0; i < r; i++) {
		scanf("%s", patt[i]);
		for (int j = 0; j < c; j++) {
			if (patt[i][j] == '?') continue;
			int c = patt[i][j] - 'a';
			int shiftByX = (((-i) % n) + n) % n;
			int shiftByY = (((j) % m) + m) % m;
			for (int x = 0; x < n; x++) {
				int nx = (x + shiftByX);
				if (nx >= n) nx -= n;
				result[nx] &= getShifted(b[c][x], m, shiftByY);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			putchar(result[i][j] ? '1' : '0');
		}
		puts("");
	}
}

Java code

import java.io.*;
import java.util.*;

public class Main {

    static class InputReader {
        BufferedReader bufferedReader;
        StringTokenizer stringTokenizer;
        InputReader(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream), 32768);
            stringTokenizer = null;
        }
        String next() {
            while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException ex) {
                    ex.printStackTrace();
                    throw new RuntimeException(ex);
                }
            }
            return stringTokenizer.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    static int[] newBitSet(int n) {
        return new int[(n + 31) / 32];
    }

    static void setBit(int[] a, int pos) {
        a[pos >>> 5] |= (1 << (pos & 31));
    }

    static boolean getBit(int[] a, int pos) {
        return ((a[pos >>> 5]) & (1 << (pos & 31))) != 0;
    }

    static void setAll(int[] a) {
        for (int i = 0; i < a.length; i++) {
            a[i] = ~0;
        }
    }

    static void resetAll(int[] a) {
        for (int i = 0; i < a.length; i++) {
            a[i] = 0;
        }
    }

    static void andXYtoX(int[] x, int[] y) {
        for (int i = 0; i < x.length; i++) {
            x[i] &= y[i];
        }
    }

    static void leftShiftAndOr(int ch, int shift, int x, int[][][][] shl, int[] to) {
        int[] z = shl[ch][shift & 31][x];
        int delta = (shift >>> 5);
        for (int i = delta; i < to.length; i++) {
            to[i - delta] |= z[i];
        }
    }

    static void rightShiftAndOr(int ch, int shift, int x, int[][][][] shr, int[] to) {
        int[] z = shr[ch][shift & 31][x];
        int delta = (shift >>> 5);
        for (int i = 0; i + delta < to.length; i++) {
            to[i + delta] |= z[i];
        }
    }

    static void printBitset(int a[], int l, int r) {
        for (int i = l; i <= r; i++) {
            System.err.print(getBit(a, i) ? '1' : '0');
        }
        System.err.println();
    }

    static final int ALPHA = 26;

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int m = in.nextInt();

        int[][][][] shl = new int[ALPHA][32][n][];
        int[][][][] shr = new int[ALPHA][32][n][];

        for (int c = 0; c < ALPHA; c++) {
            for (int sh = 0; sh < 32; sh++) {
                for (int i = 0; i < n; i++) {
                    shl[c][sh][i] = newBitSet(m);
                    shr[c][sh][i] = newBitSet(m);
                }
            }
        }

        String[] s = new String[n];

        for (int i = 0; i < n; i++) {
            s[i] = in.next();
            for (int j = 0; j < m; j++) {
                int c = s[i].charAt(j) - 'a';
                for (int sh = 0; sh < 32; sh++) {
                    if (j - sh >= 0) {
                        setBit(shl[c][sh][i], j - sh);
                    }
                    if (j + sh < m) {
                        setBit(shr[c][sh][i], j + sh);
                    }
                }
            }
        }

        int r = in.nextInt();
        int c = in.nextInt();

        String[] patt = new String[r];

        int[][] res = new int[n][];

        for (int i = 0; i < n; i++) {
            res[i] = newBitSet(m);
            setAll(res[i]);
        }

        int[] tmp = newBitSet(m);

        for (int i = 0; i < r; i++) {
            patt[i] = in.next();
            for (int j = 0; j < c; j++) {
                if (patt[i].charAt(j) == '?') continue;
                int cur = patt[i].charAt(j) - 'a';
                int shiftByX = (((-i) % n) + n) % n;
                int shiftByY = (((j) % m) + m) % m;

                for (int x = 0; x < n; x++) {
                    int nx = x + shiftByX;
                    if (nx >= n) nx -= n;
                    resetAll(tmp);
                    leftShiftAndOr(cur, shiftByY, x, shl, tmp);
                    rightShiftAndOr(cur, m - shiftByY, x, shr, tmp);
                    andXYtoX(res[nx], tmp);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                out.print(getBit(res[i], j) ? '1' : '0');
            }
            out.println();
        }

        out.close();
    }
}

Полный текст и комментарии »

Разбор задач Codeforces Round 390 (Div. 2)

разбор, 390

+108

netman
8 лет назад
54

Codeforces Round #390 (Div. 2)

Автор netman, история, 8 лет назад, По-русски

Привет, Codeforces!

Рад сообщить, что сегодня в 17:35 MSK состоится первый в новом году раунд Codeforces Round #390 для второго дивизиона. Традиционно, участники из первого дивизиона смогут принять участие вне конкурса.

Подготовкой раунда занимался я, Алексей netman Вистяж.

Выражаю благодарность Николаю KAN Калинину за помощь в подготовке задач и Михаилу MikeMirzayanov Мирзаянову за платформы Codeforces и Polygon.

Участникам будет предложено пять задач и два часа на их решение.

Разбалловка будет объявлена к началу раунда.

UPD: Разбалловка 500 — 1000 — 1500 — 2000 — 2500

UPD2:

Во время контеста было несколько проблем — в задаче C первый претест не совпадал с первым тестом из условия, и, к сожалению, эта задача была решена намного хуже, чем мы ожидали. Я сделал выводы и в следующий раз я буду оценивать сложности задач более ответственно.

Поздравляем победителей!

Div 2:

Div 1:

UPD3:

Разбор опубликован!

Полный текст и комментарии »

Анонс Codeforces Round 390 (Div. 2)

codeforces, round, 390

+252

netman
8 лет назад
210

Codeforces Round #260 — Разбор

Автор netman, 10 лет назад, По-русски

456A - Ноутбуки

Решение: 7407613;

В этой задаче надо было проверить существования таких i и j, что i ≠ j, a[i] < a[j], b[i] > b[j]. Если существуют такие i и j, то Леша рад.

Для этой задачи есть очень простое решение. Просто проверить, что для всех i верно, что a[i] = b[i]. Если это так, то Леша не рад.

Доказательство очень простое. Давайте отсортируем массивы a и b, как пары чисел, по возрастанию. Можно увидеть что Лёша рад, если есть хотя бы одна инверсия в массиве b, то есть существуют такие i и j, что b[i] > b[j] и i < j ( $\text{[math]}$ , так как числа в массиве a идут в возрастающем порядке). То есть это значит, что массив b не отсортирован, и это значит, что a ≠ b.

456B - Федя и математика

Решения: 7407625, 7407631;

В этой задаче надо было вычислить то, что просили в условии. Правда в лоб это не легко сделать.

Но если посмотреть на формулу, то можно сделать следующее:

$\text{[math]}$

Эта формула верна, потому что 5 — простое число и оно взаимнопросто с 1, 2, 3, 4.

φ(5) = 4

Чтобы применить это решение, нужно уметь брать остаток от деления на 4 длинного числа и уметь вычислять выражение для маленького n.

Асимптотика — $\text{[math]}$ .

Можно было писать другое решение. Более лобовое. Можно было использовать быстрое возведение в степень, но не бинарное. Идея та же, что и у бинарного возведения. Пусть мы возводим число x в степень n по модулю P. Мы должны двигаться по длинному числу n с конца и хранить два значения: Result — текущий результат и K — число x возведенное в 10ⁱ, где i — номер разряда на котором мы стоим (разряды нумеруются с конца начиная с нуля). Чтобы обновить ответ надо сделать следующее: $\text{[math]}$ , c[i] — i-ая цифра числа n с конца.

Асимптотика — $\text{[math]}$ .

456C - Скука / 455A - Скука

Решения: 7407649, 7407655;

В этой задаче вам надо было максимизировать сумму набранных очков. Давайте подсчитаем количество всех чисел в массиве a, то есть заведем массив cnt, где cnt[x] — количество чисел x в массиве a. Теперь очень просто считать ДП. Оно имеет такой вид:

f(i) = max(f(i - 1), f(i - 2) + cnt[i]·i), 2 ≤ i ≤ n;

f(1) = cnt[1];

f(0) = 0;

Ответ будет содержаться в f(n).

Асимптотика — O(n).

456D - Много игр / 455B - Много игр

Решения: 7407663, 7407670;

Давайте научимся определять, может ли игрок выиграть и может ли проиграть в одной игре. Для этого нам понадобится префиксное дерево(бор), сформированние из всех строк набора. Будем считать два ДП — win[v], lose[v]. Если v — лист бора, то win[v] = false;lose[v] = true.

Иначе win[v] = (win[v] or (not win[i])); lose[v] = (lose[v] or (not lose[i])), по всем i — детям вершины v.

Теперь осталось рассмотреть пару случаев:

Если win[v] = false, то выигрывает второй игрок (то есть первый игрок будет все k игр проигрывать и начинать заново новую игру, так как он проиграл в прошлой игре).

Если win[v] = true и lose[v] = true, то выигрывает первый игрок (тут первый игрок может в первой игре изменить ход событий в свою пользу).

Иначе у нас остается только один случай — win[v] = true и lose[v] = false, то тут исход игры зависит от четности k, если k mod 2 = 1, то выигрывает первый игрок, иначе второй (в этом случае игроки будут по очереди выигрывать и всё зависит от чётности k).

Асимптотика — $\text{[math]}$ .

456E - Цивилизация / 455C - Цивилизация

Решения: 7407681, 7407683;

Во-первых можно было заметить, что наша система дорог всегда будет оставаться лесом деревьев. Для эффективного хранения компонент следует использовать СНМ (система непересекающихся множеств). Вначале нужно построить начальную систему дорог. В каждой компоненте начальной системы дорог нужно найти диаметр компоненты. Это можно сделать обходом в ширину или глубину. Пусть a — произвольная вершина. Тогда b — самая далекая вершина от вершины a. И c — самая далекая вершина от вершины b. Расстояние от вершины b до вершины c — диаметр. Все эти утверждения верны только для дерева. Теперь для каждого множества в СНМ мы знаем его диаметр. Теперь очень легко отвечать на запрос первого типа: Узнать в каком множестве лежит вершина x и вывести диаметр этого множества. Запрос второго типа тоже легко обработать: Пусть u — номер множества в котором лежит вершина x, v — номер множества в котором лежит вершина y. Теперь если u ≠ v, то можно объеденять эти два множества в новое множество. Диаметр нового множетсва вычисляется так:

$\text{[math]}$

Асимптотика — O(n·A^- 1(n)), где A^- 1(n) — обратная функция Аккермана.

455D - Серега и веселье

Решения: 7407693, 7407699, 7407703;

Давайте сведем запрос 1-го типа к двум более простым более простым запросам:

Удалить число из массива на r-ой позиции. Вставить это же число в массив на l-ую позицию, то есть после (l - 1)-ой позиции.

Теперь давайте хранить наш массив, как $\text{[math]}$ блоков. В каждом блоке будем хранить сами числа в таком порядке, как в массиве a и будем хранить массив cnt. cnt[x] — количество чисел x в блоке. Всё это будет требовать $\text{[math]}$ памяти.

Теперь легко быстро выполнять запрос 1-го типа. Удалить число с r-ой позиции мы можем за $\text{[math]}$ операций. А потом уже вставить это же число тоже можем за $\text{[math]}$ операций. За O(1) мы так же можем обновлять массив cnt. Асимптотика выполнения первого запроса — $\text{[math]}$ .

Так же легко быстро выполнять запрос 2-го типа. Нужно пройтись всего по $\text{[math]}$ блокам, которые полностью попадают под границы запроса. И нужно пройтись по $\text{[math]}$ числам, которые лежат в блоках, которые частично попали в запрос.

Чтобы сохранять размеры блоков близкими к $\text{[math]}$ , нужно каждые $\text{[math]}$ запросов 1-го вида перестраивать наши блоки. Перестройка делается за O(n).

Итоговая асимптотика — $\text{[math]}$ .

455E - Функция

Решения: 7407711, 7452418;

В этой задаче нужно было быстро уметь считать описанную в условии функцию.

Можно свести задачу нахождения значения функции f(x, y) к более простой задаче:

Пройти по массиву a, начиная от позиции y, сделав (x - 1) шаг. Шаг может быть таким: либо пойти влево, либо остаться на месте.

Значение функции $\text{[math]}$ , где k_i — сколько раз мы посетили i-ый элемент массива a.

Для фиксированного l понятно, выгоднее всего, чтобы минимум на отрезке [l, y] был посещен (x - (y - l)) раз, а все остальные числа по одному разу. Ещё можно заметить, что нам выгодно, чтобы a[l] был минимумом.

Из всего этого можно сделать вывод, что для фиксированного l ответом будет — sum[y] - sum[l] + a[l]·(x - (y - l)), где sum — массив префиксных сумм массива a.

Формулу выше можно расписать так:

sum[y] - sum[l] + a[l]·(x - (y - l)) = sum[y] - sum[l] + a[l]·(x - y + l) = sum[y] - sum[l] + a[l]·l + a[l]·(x - y) = sum[y] + (a[l]·(x - y) + a[l]·l - sum[l])

Можно заметить, что в скобках вышло что-то похожее на уравнение прямой — K·X + B. В скобках вышло: a[l]·(x - y) + a[l]·l - sum[l], где K = a[l], X = (x - y), B = a[l]·l - sum[l].

Теперь нам осталось научиться для всех подходящих l научиться искать минимум на всех прямых при фиксированном X = (x - y).

Прямых у нас будет n. То есть для каждого элемента массива a своя прямая. Теперь ответ на запрос будет равен:

$\text{[math]}$ , где (K_i, B_i) — i-ая прямая. K_i = a[i], B_i = a[i]·i - sum[i].

Чтобы вычислять ответ на запрос быстрее, чем простой проход по прямым, нужно ипользовать Convex Hull Trick на дереве отрезков. То есть в каждой вершине дерева отрезков мы храним все прямые, за которые отвечает эта вершина. Итого у нас будет израсходовано $\text{[math]}$ памяти. А запрос будет выполняться за $\text{[math]}$ операций. Так как мы посетим $\text{[math]}$ вершин и в каждой вершине выполним $\text{[math]}$ операций. Подробнее познакомиться с Convex Hull Trick вы можете тут.

Асимптотика — $\text{[math]}$ .

Полный текст и комментарии »

Разбор задач Codeforces Round 260 (Div. 1)

Разбор задач Codeforces Round 260 (Div. 2)

разбор, 260, editorial

netman
10 лет назад
175

SPOJ COT2

Автор netman, 11 лет назад, По-русски

Всем привет!

Не так давно я решил задачу COT2.

В этой задаче нам дано дерево. Каждому дереву соответствует число. Нужно быстро отвечать на запрос x y — кол-во различных чисел на пути от вершины x до вершины y.

Сначала я написал на неё, как мне казалось верное решение, но оно было не верным, но оно зашло.

Вот это решение — http://pastie.org/8667428.

Идея его была такова:

Обойдем дерево dfs'ом и сохраним все вершины в порядке обхода. Обход назовем v[]. Потом чуть переделаем наши запросы:

Вместо (x,y) будет (l,r), где l и r позиции вершин x и y в нашем обходе v[]. Если l>r, то поменяем l и r местами.

Теперь применим корневую эвристику к запросам, то есть отсортируем запросы по паре (l/block,r), где block ~ sqrt(n).

Теперь будем обрабатывать наши запросы в отсортированном порядке.

То есть, если мы сейчас на пути v[old_l]->v[old_r] и нам надо перейти на путь v[l]->v[r], то мы просто двигаемся по дереву от вершины old_l до вершины l и от вершины old_r до вершины r. При этом, каждый раз посещая какую-нибудь вершину, мы проверяем: лежит ли она на пути v[l]->v[r], если лежит, то проверяем ложили ли мы число этой вершины в ответ, если нет, то ложим(ложить будем числа за O(1) применяя обычный массив меток).

Это есть мое первое решение. Оно зашло, хоть оно неверное. Так как для него есть хороший контр-тест, который дает асимптотику O(N*M).

Этот тест будет таким:

    1
   /|\
  / 2 \
 |     |
 |     |
 .     .
 .     .
 .     .
(n/2) (n)

А запросы будут такого вида:

(n/2,n/2+1), (2,n/2+2), (n/2,n/2+3), ..., (2,n)

Это будет худшим случаем для данного решения, так как мы построим такой обход:

v[]={ 1, 3, 4, 5, ..., n/2, 2, n/2+1, n/2+2, ..., n }

И вершины n/2 и 2 будут находиться рядом, но вот расстояние между ними будет O(N), и если мы будем обрабатывать запросы, в которых мы должны будем переходить на такое расстояние, то будет сложность решения O(N*M).

Но чуть позже я придумал верное решение. Оно отличается от первого решения совсем немного.

Вот код этого решения — http://pastie.org/8667490.

Мы должны поменять обход, чтобы расстояние между соседними вершинами в обходе было O(1). То есть dist(v[i],v[i+1])=O(1).

Делать будем его так:

Почти так же, как и обычный обход.

Будем ходить dfs'ом по дереву, когда заходим в вершину, то добавляем её в обход, если она на четной глубине. Когда выходим из вершины, то добавляем её в обход, если она на нечетной глубине.

Из этого видно что расстояние между соседними вершинами будет примерно 3-4, то есть dist(v[i],v[i+1])=O(1).

И мы получаем честное решение за O(M sqrt N).

Можете рассматривать эту мини-статейку, как разбор к этой задаче :)

Но у меня есть вопрос: Можно ли решить эту задачу с более лучшей асимптотикой, например O(M log N) или O(M log^2 N)? Если да, то как её решить с более лучшей асимптотикой?

Полный текст и комментарии »

cot2, problem, spoj, judge, task

netman
11 лет назад
10

Выбор ноутбука для спортивного программирования

Автор netman, 11 лет назад, По-русски

Собираюсь купить себе ноутбук для спортивного программирования(до 600$), только не знаю какой выбрать.

Нужны примерно такие характеристики:

Видеокарта: не нужна;
Процессор: можно i3;
Экран: вот тут я не знаю что выбрать(13.3" или 15.6");
Оперативная память: 3-4GB думаю хватит;
Жесткий диск: хватит 320GB;
Клавиатура: нужна удобная, чтобы печатать было быстро и удобно;
Батарея: нужно чтобы держала в кодерском режиме 3-4 часа;

Пожалуйста помогите выбрать ноутбук под мои нужды.

Не минусуйте пожалуйста :)

UPD:

Я подобрал пару моделей. Но какая из них лучше, надежнее и удобнее для кодинга?

Lenovo IdeaPad Z580 (Lenovo все хвалят из-за качества, посматриваю на этот ноут)
Acer Aspire V3-571 (Acer'ы наоборот многие не любят за плохое качество, но эта модель хороша)
ASUS K55A (этот ноутбук тоже неплох, может стоит его выбрать?)

Полный текст и комментарии »

ноутбук, программирование

netman
11 лет назад
28