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

Автор RAD, 12 лет назад, перевод, По-русски

263A - Красивая матрица

Если единственная единица стоит на пересечении r-ой строки и c-го столбца (в 1-индексации), то ответ: |3 - r| + |3 - c|.

263B - Квадраты

Если k > n, решения нет. Иначе отсортируем квадраты по убыванию размеров. Теперь нам подходит любая точка, которая принадлежит k-ому квадрату, и не принадлежит k + 1-ому. Например, можно вывести координаты (ak, 0).

263C - Круг чисел

Первым делом проверим, что каждое число встречается во входных данных 4 раза. Если это не так, то решения точно нет. Иначе попытаемся восстановить круг. Так как циклический сдвиг не имеет значения, пусть 1 будет первым числом. Второе и третье число должны быть соединены с 1 и между собой, поэтому вариантов мало, их все можно перебрать. Зная эти 3 первых числа, оставшаяся часть круга однозначно восстанавливается за линейное время. Возьмем последние 2 числа из круга, далее найдем число, которое соединено с ними, но еще не входит в ответ, и добавим его в конец. Если такое число нашлось, то продолжим процесс. Если в результате получилось добавить все числа в круг, то это и есть ответ.

263D - Цикл в графе

Рассмотрим такой простой путь v1, v2, ..., vr, что его нельзя продолжить добавлением вершины в конец, к vr. Это значит, что все соседи vr уже содержатся в пути. Найдем первую вершину в пути (vl), которая соединена с vr. Понятно, что vl, vl + 1, ..., vr — цикл, и он содержит всех соседей vr. По условию задачи, каждая вершина имеет хотя бы k соседей. Значит длина цикла не менее k + 1 ( + 1 получается за счет самой вершины vr).

263E - Ромб

Разделим ромб на 4 прямоугольных треугольника, как показано на рисунке ниже. В результате получится 1 треугольник размера k, 2 — размера k - 1, 1 — размера k - 2.

Разобьем задачу на 4 подзадачи. Самый удобный способ сделать это — 4 раза повернуть исходный массив на 90 градусов, и каждый раз запускать одну и ту же функцию, которая решает для одного треугольника. Функция будет возвращать 2-мерный массив, каждая ячейка которого будет содержать ответ для треугольника с вершиной в этой ячейке. Несложно понять, как совместить 4 таких массива, чтобы получить ответ для исходного ромба.

Основная идея решения для треугольника в том, что, зная ответ для одной клетки, мы можем "подвинуть" треугольник на единицу в любую сторону (вправо, вниз, влево или вверх) и пересчитать ответ за константное время. Вообще говоря, важны только 2 направления: вправо и вниз. А ответ для верхней левой клетки можно посчитать за O(k2) двумя вложенными циклами.

Определим следующие 5 функций:

  1. Сумма на диагональном отрезке из k элементов:

  2. Сумма на вертикальном отрезке из k элементов:

  3. Взвешенная сумма на вертикальном отрезке из k элементов:

  4. Сумма на треугольнике:

  5. Взвешенная сумма на треугольнике:

Посчитать первые 3 функции за O(nm) в сумме совсем просто. Остальные функции можно быстро считать так:

triangle(x, y + 1) = triangle(x, y) - diagonal(x, y - k + 1) + vertical(x, y + 1)

triangleWeighted(x, y + 1) = triangleWeighted(x, y) - triangle(x, y) + verticalWeighted(x, y + 1)

Формулы для перемещения треугольника в другие стороны почти ничем не отличаются.

Разбор задач Codeforces Round 161 (Div. 2)
  • Проголосовать: нравится
  • +58
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You also need to mention that, for 263C - Circle of Numbers, how: - N=5 is trivial (any combination works) - N=6 there are 12/(6C2=)15 possible pairs, so ensure that the missing 3 pairs are not neighbours - N>6 probably your approach will work (N>=10 would be safest)

and also, please clarify what you mean by ..., there are only few possibilities. So let's try them all... For example, for N=1, say i discover that 1 is neighbours to 6 and 3, and 6 and 3 are neighbours to each other, it could be '1 (either 3 or 6) (either 3 or 6) ...' or '(either 3 or 6) 1 (either 3 or 6)...' What are you trying to say? maybe illustrate with a link to a AC submission, please.

much appreciated.

  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Let's consider the number of the common neighbours of 1 and 3(say,t1) and the number of the common neighbours of 1 and 6(say,t2).

    If t1=2 and t2=1, then it should be 1 3 6.

    If t1=1 and t2=2, then it should be 1 6 3.

    If t1=2 and t2=2, then it should be 3 1 6.

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

[deleted]

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

+1 for the tutorial! I hope that all next contests will have a similar one! And nice contest by the way :)

»
12 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

My solution to problem C is quite different from the tutorial:

  1. for n == 5, any combination will work;
  2. for n == 6, try all permutations;
  3. for n >= 7, scan every edge and see how many "triangles" can it construct; if it is two, then this edge should be a "side edge", i.e. two vertices are neighbors.

Triangle means: for an edge(u, v), there exists k that both edge(u, k) && edge(k, v) exist.

Special cases should be noted: the given graph may not be connected!

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I don't get it, why N = 6 is special case, can someone point it out please?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Actually I make use of this property: If N >= 7, then for three consecutive vertices (a, b, c), a will be connected with (d, e) and c will be connected with (f, g), and (d, e, f, g) will be distinct vertices. For N == 6, this property does not hold.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For N>=7, nodes X and Y are next to each other in the circle iff their adjacency lists look like this:

    X(A,B,Y,E1) Y(A,B,X,E2)

    where E1 != E2.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    for special case, if each point is exactly connected to 4 other points and there're 2*n nodes, the whole graph must be connected

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Do you mean 2n edges? Consider this case: put two valid n=5 cases together to get an n=10 case, this graph is disconnected but all nodes is connected with 4 other nodes.

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

It was really unfair not to rejudge problem D as many clearly wrong solutions passed(see this thread) and thus decreased the point of the problem. My solution may fail too in rejudge but fair result should be ensured.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    take vertex = 1 + ( n * m + ( n ^ m ) + ( n & m ) + ( n | m ) ) % n; find max distance to all its neighbour, get accepted what is logic to solve it?

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does anybody have an idea for the problem E ?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

В E с данными ограничениями достаточно было вначале посчитать частичные суммы на диагоналях, и для каждой клетки как для центра ромба считать за константное время сумму на клетках каждого уровня ромба, а потом домножать эту сумму на нужный коэффициент. Вот пруф, что операций будет мало: http://www.wolframalpha.com/input/?i=Maximum[k*%281000-2k%29*%281000-2k%29].

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I have wrote a solution in Chinese, anyone can view it. here is my blog

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here is my approach for case N = 6 in problem C:

Because each node connects to exactly 4 others, there're always 3 pairs of nodes which are not neighbors. Find these 3 pairs and put them into the circle. Place node a of pair (a, b) in any position i from 1 to 3 (make sure it's still available), then place node b in position i + 3.

»
12 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Я решал Е немного иначе. Я поворачивал матрицу на 45 градусов и искал сумму на квадратах, а не на треугольниках.

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Я прочитал разбор D трижды, но ничего не понял. Можно подробнее, что там происходит?

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I wonder why I got TLE in Div1.C by not checking if all numbers are repeated 4 times... It doesn't change the order, does it?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone please explain me that why we use |3-x| + |3 — y| in beautiful matrix

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The problem asks to move the only '1' to the center of the matrix, which is located as (3, 3). For any position with (x, y), we need |x-3| + |y-3| steps to move it to the center. You may refer to Manhattan Distance for more details, and if you still have questions, welcome to discuss.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i am getting tle my code is for beautiful matrix question``

include include using namespace std;

int main() { int arr [5][5]; int x,y =0; for (int i = 1; i <=5; i++) { for (int j = 1; j <= 5; j++) { cin>>arr[i][j]; if (arr[i][j]== 1) { x =i ; y =j ;

} } } cout<<(abs(3-x)+abs(3-y)); return 0; } please help me out

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If you use arr[5][5], then both i and j should not exceed 4. In other words, when i=5 or j=5, it leads to out of bound. You may use arr[6][6] instead.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      why be have to take arr[6][6] as when we have to define an array we define it by its size ie is 5x5

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        The index in general starts from 0, and thus for arr[5], we could only use arr[0], arr[1],...,arr[4]

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A pretty neat trick for Problem A.

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define dbg(x) cout<<#x<<" "<<x<<endl;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef vector<string> vs;

void solve() {
    int r=0,c=0;
    for(int i=1; i<=25; i++) {
        int tmp;
        cin>>tmp;
        if(tmp==1) {
            // dbg(i);
            r=(i-1)/5;
            c=(i-1)%5;
            break;
        }
    }
    // dbg(r);
    // dbg(c);
    cout<<abs(r-2)+abs(c-2)<<endl;
}

int main() {
    fastio;
    // int t;
    // cin>>t;
    // while(t--) {
        solve();
    // }
    return 0;
}