Hello CodeForces community!

Recently I've recalled one interesting C++ problem. In short: is it possible to write functions action and cond in such a way, so that the following code snippets work differently:

// Snippet #1:
action();
while (cond()) {
    action();
}

// Snippet #2:
do {
    action();
} while (cond());

More formally: suppose you're given the following three files:

#include <iostream>

bool cond() {}

void action() {
    std::cout << "Action" << std::endl;
}

#include "common.h"

int main() {
    action();
    while (cond()) {
        action();
    }
    return 0;
}

#include "common.h"

int main() {
    do {
        action();
    } while (cond());
    return 0;
}

You're only allowed to modify common.h. You have to do that in such a way, so that Action word is printed different amount of times by execution of main_while.cpp and main_do_while.cpp.

One of the possible solutions (try to think yourself before opening the spoiler!):

#include <iostream>

bool cond() {
    #define do if(true)
    static int attempt = 0;
    attempt++;
    return attempt % 2 != 0;
}

void action() {
    std::cout << "Action" << std::endl;
}

Share your solutions in the comments and don't forget to hide them under the spoilers! It would be interesting to see something smarter (e.g. solution which will work in any language with analogues of while and do-while)

Hello community, Happy New Year!

I came up with interesting macro which allows sort objects by some field. The code is laconic but requires C++11. Macro itself:

#define by(T, x) [](const T& a, const T& b) { return a.x < b.x; }

Usage:

struct Item {
    int a, b;
};

sort(arr, arr + N, by(Item, a));

Full example: http://pastebin.com/Cp5ZkwE4.

Happy New Year!

UPD: It was pointed out (in Russian discussion) that C++14 allows shorter version:

#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; }
sort(arr, arr + N, by(a));

Hello, CodeForces!

From time to time some people ask questions related to center, radius and diameter of graph (I could google only about tree). In this topic you can find their definitions and algorithms for finding them.

Problem: you are given graph G = (V, E), where V is set of nodes and E is set of edges. You have to find its center, radius and diameter.

Let's denote d_i, j as shortest distance between nodes . Then diameter of graph is denoted as the greatest possible among all possible shortest distances between two nodes:

Also we can define eccentricity of node as maximal distance from that node to other:

Having values of eccentricity of all nodes, we can define radius of graph as minimal one among them:

Also we can observe that diameter of graph is maximal eccentricity of node:

Center of graph is set of nodes with eccentricity equal to the radius of graph:

After these basic definitions we can find radius, diameter and center of graph using Floyd-Warshall's algorithm:

const int   N = ...; // Number of nodes in graph
const int   INF = ...; // Infinity
int         d[N][N]; // Distances between nodes
int         e[N]; // Eccentricity of nodes
set <int>   c; // Center of graph
int         rad = INF; // Radius of graph
int         diam; // Diamater of graph

// Floyd-Warshall's algorithm
for (int k = 0; k < N; k++) {
    for (int j = 0; j < N; j++) {
        for (int i = 0; i < N; i++) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

// Counting values of eccentricity
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        e[i] = max(e[i], d[i][j]);
    }
}

for (int i = 0; i < n; i++) {
    rad = min(rad, e[i]);
    diam = max(diam, e[i]);
}

for (int i = 0; i < n; i++) {
    if (e[i] == rad) {
        c.insert(i);
    }
}

Now let's try to change problem statement: suppose that G is a tree. There is one interesting fact about trees: number of nodes in the center of tree is equal to one or two.

Possible algorithm for finding center of tree is the following: using BFS from any node (denote it as v1) find the farthest from v1 node (denote as v2), then run BFS from v2, choose the farthest node from v2 (call it v3). Nodes in the middle of the path between v2 and v3 are center of graph, distance between them is diameter. Radius of graph is half of diameter rounded up: (diam(G) + 1) / 2. I will not provide implementation of that algorithm because it look quiet bulky. Instead, I will show another algorithm which is much easier to implement.

Theorem: Let L be set of leaves of G. If |V| ≤ 2 then L is center of G, otherwice center of graph remains the same after removing of L:

This theorem brings us to the following algorithm: remove leaves, level by level, until there are  ≤ 2 nodes. These nodes will be center of graph. Implementation of this algorithm is similar to BFS:

const int   N = ...; // Number of nodes in graph
int         maxlevel = 0; // Level of center of graph
int         level[N]; // Level of node
int         degree[N]; // Degree of node
int         g[N][N]; // Adjacency matrix
set <int>   c; // Center of graph
queue <int> q; // Queue for algo

// Start from leaves
for (int i = 0; i < N; i++) {
    if (degree[i] == 1) {
        q.push(i);
    }
}

while (!q.empty()) {
    int v = q.front();
    q.pop();

    // Remove leaf and try to add its parent
    for (int i = 0; i < N; i++) {
        if (g[v][i]) {
            degree[i]--;
            
            if (degree[i] == 1) {
                q.push(i);
                level[i] = level[v] + 1;
                maxlevel = max(maxlevel, level[i]);
            }
        }
    }
}

for (int i = 0; i < N; i++) {
    if (level[i] == maxlevel) {
        c.insert(i);
    }
}

It's not so hard to prove that after running of this algo center of graph will be in c, и rad(G) = (diam(G) + 1) / 2.

I could not fin appropriate problems to solve, feel free to post them in comments.

Problems to solve:

• IOI2013 Dreaming
• 456E - Civilization
• 592D - Super M
• Problem F from this contest

Thank you for attention, you can write about typos to private messages.

519A - A and B and Chess

Author: BekzhanKassenov

This problem asked to determine whose chess position is better.

Solution: Iterate over the board and count scores of both player. Then just output the answer.

Complexity: O(n²), where n is the length of the side of the board (8 here)

Code: 10083191

519B - A and B and Compilation Errors

Author: ADJA

In this problem you were given three arrays. Second array is the same as the first array without one element, third array is the same as second array without first element. You were asked to find deleted elements.

Solution: I'll describe easiest solution for this problem: Let's denote a as sum of all elements of first array, b as sum of all elements of second array and c as sum of all elements of third array. Then answer is a - b and b - c

There are also some other solutions for this problem which use map, xor, etc.

Complexity: O(N)

Code: 10083248

519C - A and B and Team Training

Author: ADJA

In this problem we should split n experienced participants and m newbies into teams.

Solution: Let's denote number teams with 2 experienced partisipants and 1 new participant as type1 and teams with 1 experienced participant and 2 new participants as type2. Let's fix number of teams of type1 and denote it as i. Their amount is not grater than m. Then number of teams of type2 is min(m - 2 * i, n - i). Check all possible i' and update answer.

Complexity: O(N)

Code: 10083265

519D - A and B and Interesting Substrings

Author: ADJA

In this problem you were asked to find number of substrings of given string, such that each substring starts and finishes with one and the same letter and sum of weight of letters of that substring without first and last letter is zero.

Solution: Let's denote sum[i] as sum of weights of first i letters. Create 26 map < longlong, int > 's, 1 for each letter. Suppose we are on position number i and current character's map is m. Then add m[sum[i - 1]] to the answer and add sum[i] to the m.

Complexity: O(NlogN), where N — the length of input string.

Code: 10083293

519E - A and B and Lecture Rooms

Author: BekzhanKassenov

In this problem we have to answer to the following queries on tree: for given pairs of vertices your program should output number of eqidistand vertices from them.

Let's denote:

dist(a, b) as distance between vertices a and b.

LCA(a, b) as lowest common ancestor of vertices a and b.

depth[a] as distance between root of the tree and vertex a.

size[a] as size of subtree of vertex a.

On each picture green nodes are equidistant nodes, blue nodes — nodes from query.

Preprocessing: Read edges of tree and build data structure for LCA (it is more convenient to use binary raise, becase we will use it further for other purposes).

Complexity: O(NlogN)

Queries:

We have to consider several cases for each query:

1) a = b. In that case answer is n.

2) dist(a, b) is odd. Then answer is 0.

3) dist(a, l) = dist(b, l), where l = LCA(a, b).

Find children of l, which are ancestors of a and b (let's denote them as aa and bb). Answer will be n - size[aa] - size[bb].

4) All other cases.

Assume that depth[a] > depth[b]. Then using binary raise find dist(a, b) / 2-th ancestor of a (let's denote it as p1), dist(a, b) / 2 - 1-th ancestor of vertex a (denote it as p2). Answer will be size[p1] - size[p2].

Complexity: O(logN) for each query, O(MlogN) for all queries.

Resulting complexity:: O(MlogN + NlogN)

Code: 10083310

Hello everyone!

Topcoder SRM 634 will take today at 21.00 EDT.

Good luck and have fun!

P.S Still cannot find decription of the match using their new site. Can anyone help me? I got it using clist.by

Hello everyone!

Topcoder SRM 606 will take place 30 January, at 6.00 MSK.

Let's discuss problems here after the contest.

GL & HF

Hello, Codeforces community!

Open Ural FU Championship 2013 will take place today tomorrow at this time on timus.

Let's discuss problems in comments after the contest.

GL & HF

Hello, Codeforces community!

Ural Championship 2013 will take place 3 august at this time on timus.

Let's discuss problems in comments after the contest.

GL & HF

Hello everyone!

Topcoder SRM 586 will take place today, at 12.00 EDT.

Let's discuss problems here after the contest.

GL & HF

Open Ural FU Personal Contest 2013 will take place 22 june at 11.00 MSK. The contest will be held on timus — link to the contest.

Let's discuss problems here after the contest.

P.S. Look at this post's number :)

P.P.S Sorry for my poor English.

That's problem:

Given 2 integer number a and b, and the equation (a / x) + (b / y) = 1. You have to find the number of integer solutions of equation. |a|, |b| <= 10^14.

Here is archive of contest.

Здравствуй, Сообщество Codeforces! Я довольно-таки часто сталкиваюсь с проблемой: ловлю СЕ, когда на компе все нормально. Этот СЕ связан с СТЛ, а точнее с algorithm. Я не знаю как, но когда я подключаю string или vector некоторые функции (sort, reverse) включаются автоматически. Использую я Far + mingw. Ну естественно, без алгоритма у меня все компилится, я отправляю, а на сервере — СЕ. То есть потеря времени. Кто знает как решить эту проблему (м.б. какие-нибудь параметря компилятору надо передавать?). Я начал использовать заготовки, куда все инклудил, но иногда кажется проще без них. Заранее благодарен всем, кто ответит.