А719б

17/06/2015 by Іванов Вячеслав Володимирович

Условие

Симметричные квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex] заданы последовательностями из [latex]\frac{n(n+1)}{2}[/latex] чисел аналогично правым треугольным матрицам. Получить в аналогичном виде матрицу [latex]A^{2}-B^{2}[/latex].

Решение

Безусловно, по входным данным можно восстановить матрицы, тривиальным образом их перемножить и вывести результат в заданном виде. Как пример плохого стиля программирования: наивный алгоритм приводит к почти двукратному перерасходу потребляемой памяти и существенно уступает в производительности. Существует другое решение, прийти к которому можно путем последовательного приспособления стандартных матричных операций к формату входных данных.

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

Замечание 1

Подпространство симметричных матриц незамкнуто относительно умножения: произведением двух симметричных матриц может быть несимметричная матрица.

Пример

[latex] \left(\begin{array}{ccc} 1 & 1 & 3 \\ 1 & 4 & 5 \\ 3 & 5 & 0\end{array} \right) \cdot \left( \begin{array}{ccc} 4 & 0 & 0 \\ 0 & 4 & 3 \\ 0 & 3 & 2 \end{array} \right) = \left( \begin{array}{ccc} 4 & 13 & 9 \\ 4 & 31 & 22 \\ 12 & 20 & 15 \end{array} \right)[/latex]

Замечание 2

Степень симметрической матрицы также является симметрической матрицей. Доказательство основано на представлении матрицы как представления линейного оператора и на свойствах эрмитовых операторов.

Во всех дальнейших выкладках подразумевается, что матрица представлена линейным массивом из [latex]\frac{n(n+1)}{2}[/latex] элементов.

Для начала, заметим, что элемент [latex]c_{i,j}[/latex] матрицы [latex]C=A^{2}[/latex], равен скалярному произведению (как векторов в стандартном базисе) [latex]i[/latex]-ой строки матрицы [latex]A[/latex] на [latex]j[/latex]-ую её строку (в силу того, что в симметричной матрице [latex]j[/latex]-ая строка совпадает с [latex]j[/latex]-м столбцом). Следовательно, для возведения в степень симметричной матрицы необходимо и достаточно реализовать операцию скалярного перемножения двух её строк.

Тогда следует понять, как по данному представлению матрицы получить её [latex]i[/latex]-ую строку. Для удобства, выпишем имеющиеся элементы в виде полной матрицы. Заметим, что первым элементом [latex]i[/latex]-ой строки будет [latex]i[/latex]-ый элемент первой строки, и обобщим это наблюдение. Обозначим позицию текущего интересующего нас элемента [latex]i[/latex]-ой строки как [latex]j[/latex]. Если [latex]j < i[/latex], то следует выбрать [latex]i[/latex]-ый элемент [latex]j[/latex]-ой строки, иначе следует выбрать все элементы [latex]j[/latex]-ой строки, лежащие правее данного. Графически можно интерпретировать алгоритм таким образом: начиная с [latex]i[/latex]-го элемента первой строки, спускаться вертикально вниз по матрице до тех пор, пока не будет достигнута [latex]i[/latex]-ая строка, далее — двигаться вправо до конца строки. Наглядность алгоритма позволяет легко воплотить его программно.
Следует только пронаблюдать, как изменяются расстояния между элементами, лежащими один под другим, при движении вниз по строкам матрицы, что позволит легко перенести алгоритм на линейное представление верхней треугольной матрицы. Предлагаем читателю самому проделать это несложное, но наглядное упражнение, для лучшего понимания алгоритма.

Теперь можно перейти непосредственно к реализации.

Тесты

[latex]n[/latex]	[latex]A[/latex]	[latex]B[/latex]	[latex]A^{2}-B^{2}[/latex]
2	1 2 5	7 4 8	-60 -48 -51
4	1 7 3 -2 3 1 9 2 8 11	4 5 11 -3 4 -7 22 1 4 0	-108 116 -8 -79 -434 -10 75 -109 290 -239

Реализация

ideone: http://ideone.com/Dyte8l

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

//Симметричная квадратная матрица порядка n задана линейным набором из
//n(n+1)/2 элементов. Все методы класса оперируют только с таким представлением.

template <typename T>
class symmetric_matrix{
private:
    T* data;
    int data_size;
   
public:
    //Конструкторы.
    symmetric_matrix(){}
    symmetric_matrix(int n){
        data = new T[(n*(n+1))/2];
        data_size = n;
    }
    symmetric_matrix(int n, int value){
        data = new T[(n*(n+1))/2];
        for(int i = 0; i < (n*(n+1))/2; i++)
            data[i] = value;
        data_size = n;
    }
    //Методы.
    int size(){ return data_size; }
    T get(int pos){ return data[pos]; }
    void set(int pos, T value){ data[pos] = value; }
    //Подпространство симметричных квадратные матриц заданного порядка
    //не замкнутно относительно операции матричного умножения.
    //Тем не менее, при возведение матрицы в степень замкнутость не
    //нарушается, в связи с чем операция умножения реализована для него.
    symmetric_matrix<T> operator *(symmetric_matrix<T> B){
        int n = data_size;
        symmetric_matrix<T> C(n);
        int curr = 0;
        for(int row = 0; row < n; row++){			//row
            for(int col = row; col < n; col++){		//col
                int rpos = row, cpos = col;	        //(row, col)
                int rstep = n-1, cstep = n-1;	    //row, col step
                for(int i = 0; i < n; i++){
                    C.set(curr, C[curr] + data[rpos]*B[cpos]);
                    rpos += (rstep >= n-row)*(rstep - 1) + 1;
                    cpos += (cstep >= n-col)*(cstep - 1) + 1;
                    rstep--, cstep--;
                }
                curr++;
            }
        }
        return C;
    }

    //Операторы.
    T operator [](int pos){return data[pos];}
    symmetric_matrix<T> operator +(symmetric_matrix<T> B){
        int n = B.size();
        symmetric_matrix<T> C(n);
        for(int i = 0; i < (n*(n+1))/2; i++)
            C.set(i, data[i] + B[i]);
        return C;
    };
    symmetric_matrix<T> operator -(symmetric_matrix<T> B){
        int n = B.size();
        symmetric_matrix<T> C(n);
        for(int i = 0; i < (n*(n+1))/2; i++)
            C.set(i, data[i] - B[i]);
        return C;
    };
};

//Бинарный алгоритм возведения матрицы в степень.
template <typename T>
symmetric_matrix<T> power(symmetric_matrix<T> A, int n){
    symmetric_matrix<T> result(A.size());
    //Изначально result - нейтральный элемент относительно умножения
    //т.е. единичная матрица.
    for(int i = 0, diag = 0; i < A.size(); i++){
        result.set(diag, 1);
        diag += A.size()-i;
    }
    while(n){
        if(n & 1)
            result = result * A;
        A = A * A;
        n >>= 1;
    }
    return result;
}


int main(){
	int n; cin >> n;
	symmetric_matrix<int> A(n), B(n), C(n);
	//Считывание данных
	for(int i = 0; i < (n*(n+1))/2; i++){
        int value; cin >> value;
        A.set(i, value);
    }
    for(int i = 0; i < (n*(n+1))/2; i++){
        int value; cin >> value;
        B.set(i, value);
    }

    C = power(A, 2) - power(B, 2);
    for(int i = 0; i < (n*(n+1))/2; i++){
        cout << C.get(i) << " ";
    }
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

#include <bits/stdc++.h>

using namespace std;

//Симметричная квадратная матрица порядка n задана линейным набором из

//n(n+1)/2 элементов. Все методы класса оперируют только с таким представлением.

template <typename T>

class symmetric_matrix{

private:

T* data;

int data_size;

public:

//Конструкторы.

symmetric_matrix(){}

symmetric_matrix(int n){

data = new T[(n*(n+1))/2];

data_size = n;

}

symmetric_matrix(int n, int value){

data = new T[(n*(n+1))/2];

for(int i = 0; i < (n*(n+1))/2; i++)

data[i] = value;

data_size = n;

}

//Методы.

int size(){ return data_size; }

T get(int pos){ return data[pos]; }

void set(int pos, T value){ data[pos] = value; }

//Подпространство симметричных квадратные матриц заданного порядка

//не замкнутно относительно операции матричного умножения.

//Тем не менее, при возведение матрицы в степень замкнутость не

//нарушается, в связи с чем операция умножения реализована для него.

symmetric_matrix<T> operator *(symmetric_matrix<T> B){

int n = data_size;

symmetric_matrix<T> C(n);

int curr = 0;

for(int row = 0; row < n; row++){ //row

for(int col = row; col < n; col++){ //col

int rpos = row, cpos = col; //(row, col)

int rstep = n-1, cstep = n-1; //row, col step

for(int i = 0; i < n; i++){

C.set(curr, C[curr] + data[rpos]*B[cpos]);

rpos += (rstep >= n-row)*(rstep - 1) + 1;

cpos += (cstep >= n-col)*(cstep - 1) + 1;

rstep--, cstep--;

}

curr++;

}

return C;

}

//Операторы.

T operator [](int pos){return data[pos];}

symmetric_matrix<T> operator +(symmetric_matrix<T> B){

int n = B.size();

symmetric_matrix<T> C(n);

for(int i = 0; i < (n*(n+1))/2; i++)

C.set(i, data[i] + B[i]);

return C;

};

symmetric_matrix<T> operator -(symmetric_matrix<T> B){

int n = B.size();

symmetric_matrix<T> C(n);

for(int i = 0; i < (n*(n+1))/2; i++)

C.set(i, data[i] - B[i]);

return C;

};

//Бинарный алгоритм возведения матрицы в степень.

template <typename T>

symmetric_matrix<T> power(symmetric_matrix<T> A, int n){

symmetric_matrix<T> result(A.size());

//Изначально result - нейтральный элемент относительно умножения

//т.е. единичная матрица.

for(int i = 0, diag = 0; i < A.size(); i++){

result.set(diag, 1);

diag += A.size()-i;

}

while(n){

if(n & 1)

result = result * A;

A = A * A;

n >>= 1;

}

return result;

}

int main(){

int n; cin >> n;

symmetric_matrix<int> A(n), B(n), C(n);

//Считывание данных

for(int i = 0; i < (n*(n+1))/2; i++){

int value; cin >> value;

A.set(i, value);

}

for(int i = 0; i < (n*(n+1))/2; i++){

int value; cin >> value;

B.set(i, value);

}

C = power(A, 2) - power(B, 2);

for(int i = 0; i < (n*(n+1))/2; i++){

cout << C.get(i) << " ";

}

return 0;

}

Тесты

Детали реализации

Задачи раздела носят обучающий характер, так что при реализации были произведены определенные обобщения, что делает решение более универсальным.

Формулировка задачи не оговаривает тип элементов матрицы, так что класс [latex]symmetric\_matrix[/latex] является шаблоном, пригодным для типов данных, поддерживающих операции сложения, вычитания и умножения (соответствующие операторы определены внутри класса).
Алгоритм бинарного возведения матрицы в степень полезен при решении более широкого круга задач, в связи с чем также реализован. При необходимости, программа легко обобщается на большие степени матрицы.
Предусмотрены три типа конструкторов: конструктор по умолчанию и два параметрических конструктора, один из которых позволяет заполнить матрицу некоторым наперед заданным значением.
Для удобства работы с заданным представлением данных, добавлен синтаксический сахар: перегружен оператор [latex][][/latex], осуществляющий доступ к заданному элементу матрицы в линейном её представлении.

Related Images:

e-olimp 4650. Граф-Турнир

08/05/2015 by Іванов Вячеслав Володимирович

Граф-турнир.

Постановка задачи

Построить на n вершинах турнир, расстояние между любой парой вершин в котором не превышает двух рёбер.

Алгоритм решения

Условию удовлетворяет любая тройка вершин, принадлежащих циклу длины три, следовательно, искомый граф сильно связен. Уместно взять за основу полный неориентированный граф [latex]K_n[/latex] (не ограничивая общности рассуждений, будем представлять граф на плоскости как правильный [latex]n[/latex]-угольник) и задать на нём ориентацию рёбер согласно набору правил:

Контур графа (рёбра вида [latex](k, k+1)[/latex]) ориентирован по часовой стрелке.
В дальнейших построениях будем отталкиваться от контура: каждая вершина графа должна находиться в хотя бы в одном цикле длины три с данной. Опишем процедуру построения такого орграфа: начиная с вершины под номером 1 будем просматривать все остальные вершины. Если на некотором шаге ребро, связывающее вершины, не ориентировано, то ориентируем его образом, противоположным ориентации ребра, соединяющего текущую вершину-исток и предыдущую по номеру вершину в обходе. Более конструктивно процедура формулируется так: обойти все вершины в порядке их следования в контуре. Пусть номер стартовой вершины для исходной итерации — [latex]V_{i}[/latex], рассматриваемой на данном шаге — [latex]V_{k}[/latex] Если ребро [latex]\left(V_{i}, V_{k}\right)[/latex] не ориентировано, и номера обеих вершин (не)чётны — задать ориентацию [latex]\left[V_{i}, V_{k}\right][/latex], иначе — [latex]\left[V_{k}, V_{i}\right][/latex].

Исключение — граф [latex]K_4[/latex]: степень каждой вершины равна трём, следовательно, одно ребро каждой вершины не принадлежит контуру. Но таких рёбер всего два, следовательно, невозможно задать чередование ориентаций рёбер и получить четыре цикла длины 3. Для всех графов на большем числе вершин построение всегда возможно.

Реализация

ideone: http://ideone.com/XwY7fX
Засчитанное решение: http://codeforces.ru/contest/323/submission/10850799
Для решения задачи достаточно хранить граф в форме матрицы смежности.

#include <cstdio>
unsigned G[1000][1000];
int main()
{
    unsigned n; scanf("%u", &n);
    if(n == 4){
        puts("-1");
    }
    else{
	    for(size_t i = 0; i < n; i++){
	        G[i][(i+1)%n] = 1;
	    }
	    for(size_t i = 0; i < n; i++){
	        for(size_t j = 0; j < n; j++){
	            if(G[i][j] + G[j][i] == 0 && i != j){
	                if(i % 2 == j % 2)
	                    G[i][j] = 1;
	                else
	                    G[j][i] = 1;
	            }
	        }
	    }
	    for(size_t i = 0; i < n; i++){
	        for(size_t j = 0; j < n-1; j++){
	            printf("%u ", G[i][j]);
	        }
	        printf("%u\n", G[i][n-1]);
	    }
    }
    return 0;
}

#include <cstdio>

unsigned G[1000][1000];

int main()

{

unsigned n; scanf("%u", &n);

if(n == 4){

puts("-1");

}

else{

for(size_t i = 0; i < n; i++){

G[i][(i+1)%n] = 1;

}

for(size_t i = 0; i < n; i++){

for(size_t j = 0; j < n; j++){

if(G[i][j] + G[j][i] == 0 && i != j){

if(i % 2 == j % 2)

G[i][j] = 1;

else

G[j][i] = 1;

}

for(size_t i = 0; i < n; i++){

for(size_t j = 0; j < n-1; j++){

printf("%u ", G[i][j]);

}

printf("%u\n", G[i][n-1]);

}

return 0;

}

ideone: http://ideone.com/eBcMcY

import java.util.*;
import java.io.*;
import java.math.*;
 
class Solver {	
    public static void main(String args[]) throws IOException{
    	new Solver().run();
	}

	StreamTokenizer in;
	PrintWriter out;

	int nextInt() throws IOException{
		in.nextToken();
		return (int)in.nval;
	}
	void run() throws IOException{
		in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		out = new PrintWriter(new OutputStreamWriter(System.out));
		solve();
		out.flush();
	}
	void solve() throws IOException{
		int n = nextInt();
    	int[][] G = new int[n][n];
    	if(n == 4)
    		out.println("-1");
    	else{
    		for(int i = 0; i < n; i++)
    			G[i][(i+1)%n] = 1;
    		for(int y = 0; y < n; y++){
    			for(int x = 0; x < n; x++){
    				if(G[y][x] + G[x][y] == 0 && x != y){
    					if(y % 2 == x % 2) G[y][x] = 1;
    					else G[x][y] = 1;
    				}
    			}
    		}
    		for(int y = 0; y < n; y++){
    			for(int x = 0; x < n-1; x++){
    				out.print(G[y][x]);
    				out.print(" ");
    			}
    			out.println(G[y][n-1]);
    		}
    	}
	}
}

import java.util.*;

import java.io.*;

import java.math.*;

class Solver {

public static void main(String args[]) throws IOException{

new Solver().run();

}

StreamTokenizer in;

PrintWriter out;

int nextInt() throws IOException{

in.nextToken();

return (int)in.nval;

}

void run() throws IOException{

in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

out = new PrintWriter(new OutputStreamWriter(System.out));

solve();

out.flush();

}

void solve() throws IOException{

int n = nextInt();

int[][] G = new int[n][n];

if(n == 4)

out.println("-1");

else{

for(int i = 0; i < n; i++)

G[i][(i+1)%n] = 1;

for(int y = 0; y < n; y++){

for(int x = 0; x < n; x++){

if(G[y][x] + G[x][y] == 0 && x != y){

if(y % 2 == x % 2) G[y][x] = 1;

else G[x][y] = 1;

}

for(int y = 0; y < n; y++){

for(int x = 0; x < n-1; x++){

out.print(G[y][x]);

out.print(" ");

}

out.println(G[y][n-1]);

}

Related Images:

I. Новорічні іграшки

29/04/2015 by Іванов Вячеслав Володимирович

Задача с SEERC 2015, [latex]\frac {1}{8}[/latex] финала.

Формулировка

«У кожного свята є один недолік – рано чи пізно, але воно закінчується. Ось і новорічні свята завершились і малому Дмитрику необхідно скласти іграшки у коробки. Частину іграшок він склав у одну коробку, а частину у іншу. Старший брат Дмитрика Петрик навчається в математичному класі. І його цікавить чи можна перекласти всі іграшки у одну з коробок (кожна коробка вміщує усі іграшки), якщо з одної коробки у іншу можна перекладати стільки іграшок, скільки у іншій коробці.

Вхідні дані:
Два числа N і M — кількість іграшок у першій та другій коробці (1 ≤ N, М ≤ 2000000000).
Вихідні дані:
Bиведіть 1 – якщо можна перекласти іграшки у одну коробку, або 0 – якщо такої можливості немає.»

Алгоритм

Ограничение на входные данные.
Предположим, что при некоторых [latex]N[/latex], [latex]M[/latex] ответ положительный. Пусть [latex]c = N + M[/latex].
Будем выстраивать последовательность шагов от конца к началу. Стартовая позиция — [latex]\left(c \quad 0 \right)[/latex](подарков в коробках). Очевидно, что прийти в неё можно только из [latex]\left( \frac {c}{2} \quad \frac {c}{2} \right)[/latex]. Определим вид предыдущей позиции: [latex]\begin{cases} a+b=c, \\ a-b=\frac { c }{ 2 } ; \end{cases}\sim \begin{cases} 2a=c+\frac { c }{ 4 } , \\ b=a-\frac { c }{ 2 } ; \end{cases}\sim \begin{cases} a=\frac { 3c }{ 4 } , \\ b=\frac { c }{ 4 } ; \end{cases}[/latex]. Принципиально важно, что показатель знаменателя на каждом шаге монотонно возрастает. В силу конечности [latex]c[/latex], процесс конечен. Меньший член пары имеет общий вид [latex]\frac {c}{2^{n}}[/latex], следовательно, [latex]c = N + M = 2k[/latex] (здесь и далее предполагается, что все переменные — некоторые натуральные числа).
Заметим, что постоянный множитель [latex]k[/latex] не влияет на сходимость. Следовательно, на него можно сократить и суммы [latex]N + M[/latex]. Максимальный из таких [latex]k[/latex] будет [latex]gcd \left(N, M \right)[/latex].
Полученный результат позволяет сформулировать необходимое условие: если решение есть, то сумма чисел [latex]N[/latex] и [latex]M[/latex] равна некоторой степени двойки с точностью до НОД([latex]N, M[/latex]).
Достаточно условие сходимости.
Пусть [latex]N, M[/latex] — некоторые числа, удовлетворяющие необходимому условию. Тогда [latex]\exists n: N=2^{ n }-M[/latex].
Рассмотрим следующий шаг, предполагая, что [latex]N \ge M[/latex]: [latex]\left(2N \quad 2^{n}-2N\right) \sim \left(N \quad 2^{n-1}-N \right)[/latex]) — задачу удалось свести к подзадаче. Повторяя аналогичную процедуру, на [latex]n[/latex]-м шаге придём в позицию, эквивалентную [latex]\left(1 \quad 2^{0}-1 \right) \sim \left(1 \quad 0 \right)[/latex], т.е. последнему шагу. Следовательно, для любого набора данных, удовлетворяющих необходимому условию, решение существует. Следовательно, условие является необходимым и достаточным, с поправкой на тривиальный случай [latex]N = M[/latex].

Реализация

ideone: http://ideone.com/OxWVLi

#include <cstdio>
inline int gcd(int a, int b){
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}
int main()
{
    int a, b, c;
    scanf("%d %d", &a, &b);
    c = (a + b)/gcd(a, b);
    printf("%d\n", (a == b || c == (c & (-c))));
    return 0;
}

#include <cstdio>

inline int gcd(int a, int b){

while(b) b ^= a ^= b ^= a %= b;

return a;

}

int main()

{

int a, b, c;

scanf("%d %d", &a, &b);

c = (a + b)/gcd(a, b);

printf("%d\n", (a == b || c == (c & (-c))));

return 0;

}

ideone: http://ideone.com/Xnupjz

import java.util.*;
import java.io.*;
import java.math.*;
 
class Ideone { 
    public static int gcd(int a, int b){
        while(b != 0) b ^= a ^= b ^= a %= b;
        return a;
    }
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt(); int b = in.nextInt();
        int c = (a + b)/gcd(a, b);
        System.out.println((a == b || c == (c & (-c))) ? 1 : 0);
    }
}

import java.util.*;

import java.io.*;

import java.math.*;

class Ideone {

public static int gcd(int a, int b){

while(b != 0) b ^= a ^= b ^= a %= b;

return a;

}

public static void main(String args[]) {

Scanner in = new Scanner(System.in);

int a = in.nextInt(); int b = in.nextInt();

int c = (a + b)/gcd(a, b);

System.out.println((a == b || c == (c & (-c))) ? 1 : 0);

}

Детали реализации

Задачи тура подразумевали лаконичные реализации решений. Использование битовых операций позволяет легко ответить на вопрос, является ли сумма чисел некоторой степенью двойки, а также вычислить НОД двух чисел методом приведения в смятение, для чего используется, на мой взгляд, весьма красивое наблюдение о свойствах функции XOR.