ABBYY Cup 2.0 - Easy - virtual participation

A2. Good Matrix Elements

http://www.codeforces.com/contest/177/problem/A2

You are given a \(N\) x \(N\) matrix, where \(N\) is an odd number. A good element of the matrix is defined as follow:

(1) Element of the main diagonal.
(2) Element of the secondary diagonal.
(3) Element of the "middle" row (\(\frac{n}{2}\) row).
(4) Element of the "middle" column (\(\frac{n}{2}\) column).

Your task is to count the number of good elements in the matrix.

The solution of this problem is pretty straightforward, we just need to add up the elements which has one or more of the following properties:

B2. Rectangular Game

http://www.codeforces.com/contest/177/problem/B2

You are playing the following game, initially you have \(n\) pebbles, at each step you arranges them in such way that each row has the same amount of pebbles. Once you have arranges the pebbles, you take back any of the resulting rows (that is, b pebbles) and discards all other pebbles. Keep playing until you end up with exactly one pebble. Your task is to print the maximum possible result of the game.

The first thing to note here is that if you want to distribute certain number \(n\) into \(a\) rows with \(b\) pebbles each, then necessarily \(a | n\) and \(b | n\). Clearly, we going to be dealing with divisors of \(n\) in this problem.

Based on the previous claim the main idea of this problem is keep dividing the number of \(n\) until we reach some point we cannot do it anymore. This reasoning lead us to the question of how to divide in order to maximize the final result.

Le'ts look an example with the number 6, the asterisk represent the pebbles :

The divisors of the number 6 are \(\{1, 2, 3, 6\}\), we can distribute the pebble in four possible ways:

(1) one row of six pebbles  

\(6 / 1 = 6\)

******

(2) two rows of three pebbles  

\(6 / 2 = 3\)

***

*** 

(3) three row of two pebbles  

\(6 / 3 = 2 \)

**

**

**

(4) six rows of one pebble

\(6 / 6 = 1\)

*

*

*

*

*

* 

Looking at this example it seems obvious that we should take the lowest available divisor greater than one at each step. 

To implement this idea we simply iterate over all the factors of \(n\), and for each one of them add up \(\frac{n}{d}\) to the solution. The overall time complexity of this solution is \(O(\sqrt{n})\).

C2. Party

http://www.codeforces.com/contest/177/problem/C2

You are organizing a party, from all of your acquaintances some of them are friends and some of them dislike each other. To make the party a success you came up with the idea of only inviting people that share a friendship relationship. Given the relationship between the acquaintances, your task is to return the maximum number of people that you can invite to the party.

This is a typical graph connectivity problem, it can be solved with DFS, BFS or Disjoint Sets. I solved using Disjoint Set data structure.

The Disjoint Set data structure helps us to divide each of the acquaintances in groups according to their direct or indirect friendship relationship. Initially every person belongs to its own group, using the \(union\_set(u, v)\) operation we unite the people who share a relationship of mutual friendship in a common group. We keep track of the number of people in each of the groups. 

The final step is to check which of those groups has people that dislike each other. Having the Disjoint Set this is a straightforward task, for each pair of people that dislike each other let's called it \((u,v)\) we check if \(find\_set(u) = find\_set(v)\). This means that, if the pair \((u,v)\) belongs to the same group we can not invite any of the people in that group.