ABBYY Cup 2.0 - Easy

Solutions for ABBYY Cup 2.0 - Easy (contest 177). 10/11 problems verified against sample I/O. Difficulty range: 800-2600.

11 items

ABBYY Cup 2.0 - Easy

Type: Special | Problems: 11 | Verified: 10/11 | Rating range: 800-2600 | Time: 24m 43s

Problem	Name	Rating	Tags	Solve Time	Verified
A1	Good Matrix Elements	800	implementation	1m 37s	✗
A2	Good Matrix Elements	800	implementation	3m 13s	✓
B1	Rectangular Game	1000	number-theory	1m 36s	✓
B2	Rectangular Game	1200	number-theory	2m 20s	✓
C1	Party	1500	dfs-and-similar, dsu, graphs	3m 2s	✓
C2	Party	1500	brute-force, dfs-and-similar, dsu	1m 32s	✓
D1	Encrypting Messages	1200	brute-force	1m 47s	✓
E1	Space Voyage	1700	binary-search	3m 38s	✓
F1	Script Generation	1800	-	48s	✓
G1	Fibonacci Strings	2400	strings	3m 11s	✓
G2	Fibonacci Strings	2600	matrices, strings	1m 59s	✓

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177A1 - Good Matrix Elements

We are given a square matrix of size n × n, where n is guaranteed to be an odd number. Each element of the matrix is a non-negative integer.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177A2 - Good Matrix Elements

We are given a square matrix of size n×n, where n is guaranteed to be odd. Each cell of the matrix contains a non-negative integer. The task is to sum the "good" elements of this matrix.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177B1 - Rectangular Game

The game starts with n pebbles. In one move, we split the current number of pebbles into a equal rows of size b, where a 1 and a b = current. After forming the rows, we keep exactly one row and throw away the others.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177B2 - Rectangular Game

The problem describes a game played by a beaver with n pebbles. On each turn, the beaver arranges all remaining pebbles into a rectangle with more than one row and some number of columns. He then selects a single row and discards the rest.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177C1 - Party

The problem asks us to choose the largest possible set of people to invite to a party, subject to two conditions. First, if a person is invited, all their friends must also be invited. Second, no two people in the invited set may dislike each other.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177C2 - Party

We are given a social graph of people. Some pairs are friends, and some pairs dislike each other. Friendship and dislike are both undirected relations. The Beaver wants to invite a set of people satisfying three conditions at the same time.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177D1 - Encrypting Messages

We have an array representing the message and another smaller array representing the encryption key. The encryption process slides the key across the message from left to right.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177E1 - Space Voyage

Each planet receives exactly a[i] suitcases, and every suitcase contains the same number x of presents. That means planet i starts with a[i] x presents. The Beaver always spends the first day on a planet without giving anything away.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177F1 - Script Generation

The problem asks us to enumerate all possible ways to pair up a set of n men with n women using a given list of k possible marriages. Each marriage has a happiness score, and each man or woman can appear in at most one marriage in a set.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177G1 - Fibonacci Strings

The problem asks us to count occurrences of query strings inside Fibonacci strings. Fibonacci strings are defined recursively: the first string is "a", the second is "b", and each subsequent string is the concatenation of the previous string followed by the one before that.

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177G2 - Fibonacci Strings

We build strings using the Fibonacci recurrence, except concatenation replaces addition. The first two strings are: Every later string is formed by concatenating the previous string with the one before it: The beginning looks like this: For each query string s, we must count…