HomeCompetitionTasks

 Tasks

The complete list of the tasks

National Round

Task 1 - PALINDROMES



Emilian is a very smart boy who loves palindromes. Radu knows this fact so he gifted his friend a set of n integers, some being palindromes and other not. Emilian was very happy so he asked himself more questions and he will apriciate if you help him answering one of them. What is the sum of all palindrome integers from the set received from Radu?

Task

Given a set of n integers calculate the sum of the palindrome integers.

Input Format

The first line contains the integer n and the second line contains nintegers.

Output Format

The first line contains only one integer representing the sum of all palindrome integers.

Constraints

  • 1 ≤ n ≤ 1,000,000
  • All integers from the set are less than 1,000,000,000
  • Subtasks

    Subtask Score Restrictions
    1 15 points All integers from the set are palindromes
    2 Another 20 points All integers from the set are < 100
    3 Another 30 points All integers from the set are < 1000
    4 Another 35 points Normal restrictions


Sample Input

  5
  1  13  22  121  45


Sample Output

   144

Maximum time of execution: 0.6 sec/test.
Maximum available memory: 64 MB

Task 2 - NORELA



Adrian the 3rd  is a wizard prince. On International Wizard’s Day (4th  of November) he wanted to impress Norela, his dream girl. He has n playing cards, which are initially put with the face down on a table. Adrian can use m spells, a spell has the format: q a1 a2 … aq . If Adrian uses a spell, the playing cards with the indices a1 a2 … aq will be turned in order. (Integers a1 a2 … aq are all different). The card will be turn face up if it is face down and will be turned face down if it is face up and all spells can be used no more than one time. Help Adrian impress Norela before his nemesis Manea Long Eyebrow does it!

Task

Find the minimum number of spells that have to be used to turn all n cards face up, also determinate the indices of the used spells. If there are more solutions, print the minimum lexicographical answer.

Input Format

The first line contains two integers n and m. The next m lines contain the description of every spell q a1 a2 … aq, where q is the number of cards that will be turned by that spell and a1 a2 … aq are the indices of those cards.

Output Format

The first line will contain only one integer representing the minimum number of used spells and the second line will contain the indices of those spells. If there are more solutions with minimum number of used spells, there will be printed the minimum lexicographical answer.

Subtasks

  • A set of integers a1 a2 … an is lexicographically smaller than other set b1 b2 … bn if there is a k between 1 and n so that a1=b1 , a2=b2 ,.. , ak-1 = bk-1 si ak < bk.

Subtasks

Subtask Score Restrictions
1 20 points n  ≤ 40 m  ≤ 18
2 Another 30 points n  ≤ 50 m  ≤ 21
3 Another 25 points n  ≤ 60 m  ≤ 22
4 Another 30 points n  ≤ 60 m  ≤ 24


Sample Input

  5 6
  3 1 3 4
  2 3 5
  2 2 3
  3 1 2 5
  1 1
  4 1 2 3 4 


Sample Output

  3
  1 2 3

Using the spells with indices 1,2 and 3 (1 3 4, 3 5 and 2 3) will turn all cards face up. It can be observed that another solution that turns all cards face up is 1,4 and 5, but this one is lexicographically bigger.


Maximum time of execution: 0.6 seconds/test.

Maximum available memory: 512 MB

Task 3 - SHELL



Florin is again in Drobeta-Turnu Severin. Unfortunately, he did not get rid off the pickpockets that bother him so much! They followed him even in this beautiful city! But Florin is very smart and figured out how to get rid of them. Drobeta-Turnu Severin is a city that is represented by a directed acyclic graph with n vertices and m edges. To finally get rid of those annoying pickpockets, Florin(who is initially in vertex 1) has to reach vertex n using a certain path. He managed to obtain a list of p vertices. In his way from vertex 1 to vertex n he has to cross all these p nodes in the given order, or else he will not get rid of the pickpockets and our hero will be very upset.

Task

Find the number of possible paths from vertex 1 to vertex n that cross all p vertices in the given order from the list. Because the result can be very big you have to print the answer modulo 1.000.000.007.

Input Format

The first line contains three integers n, m and p.

The second line contains the p vertices that have to be crossed by Florin in the given order.

The next m lines contain the edges from the graph, represented by two integers x and y, meaning there is an edge from vertex x to vertex y.

Output Format

The first line will contain only one integer representing the number of paths modulo 1.000.000.007.

SUBTASKS

WARNING!!! There can be more edges between the same 2 vertices !!!!

WARNING!!! It can be observed that at subtask 3, m is bigger than at the subtask.

YOU HAVE TO PRINT THE ANSWER MODULO 1.000.000.007.

WE HAD NO GOOD REASON TO NAME THIS PROBLEM SHELL

Subtasks

Subtask Score Restrictions
1 10 points n ≤ 20,  m ≤ 190,  p ≤ 11
2 Another 45 points n ≤ 1000,  m ≤ 30000,  p ≤ 1000
3 Another 20 points n ≤ 1500,  p ≤ 1500 and there is an unique edge from any vertex x to any vertex y with x ≤ y
4 Another 25 points n , m , p ≤ 1000000


Sample Input

6 9 3
3 5 6
1 3
1 3
1 2
2 3
2 4
3 4
3 5
4 5
5 6


Sample Output

   6


Explanation

The 6 paths are:
1-3-5-6
1-3-4-5-6
1-3-5-6
1-3-4-5-6
1-2-3-5-6
1-2-3-4-5-6

It can be observed that 1-3-4-5-6 appears 2 times, this is because there are 2 edges from 1 to 3. One of the paths use an edge, the second one uses the other edge. The same situation is for 1-3-5-6.

Maximum time of execution: 0.8 seconds/test.
Maximum available memory: 512 MB

Task 4 - THE GRADE



AlekuKebap is in his math class. While he tries to figure out why 1+1=2, his teacher was writing on the board a slightly more complicated problem. There are given Q queries and a list S with P elemnts equal with 0. Let A be initially an empty set. The querries can be:

  • 0 x (insert value x in set A)
  • 1 x (erase the value x from set A, it is guaranteed that the value x exists in set A)
It is guaranteed that A will never be empty after a query. After every query, the teacher asks Aleku the following question: can I arrange in list S all elements from the set A (not necessary in the order from the A) so that:
  • Elements form A will be put on distinct standings, the rest being occupied by P elements equal with 0
  • Let S[i] be a positive element from S and S[j] the closest positive element from S that is located to the left of S[i], then the following condition mus be respected: i-j ≥ S[i].
  • Let f be the first positive element from the left of S, then f ≥ S[f].

Task

Help AlekuKebap to answer correctly to all teacher’s questions to recive a 10 grade.

HIS AVERAGE DEPENDS ON THIS GRADE!!

Input Format

The first line contains two integers Q and P.

The next Q lines contain the description of every query.

Output Format

Every line will contain the answer to every question from the Q questions.

SUBTASKS

  • YOU HAVE TO PRINT THE ANSWER MODULO 1.000.000.007.
  • All numbers that will be added in the set are ≤ 1.000.000.
  • WARNING!!! If the answer for a query is no, print -1 !!!
  • WARNING !!!Alecu is not a kebap, he is a human being but this is his name. He is actually a captain…THE CAPTAIN.

Subtask Score Restrictions
1 10 Q ≤ 22, P ≤ 22
2 Another 10 points Q ≤ 100.000, P ≤ 3000
and all the values that will be at the same time in A will be equal
3 Another 10 points Q ≤ 100.000, P ≤ 3000
and all the values that will be at the same time in A will be different
4 Another 20 points Q ≤ 100.000, P ≤ 3000
5 Another 15 points Q ≤ 100.000, P ≤ 100.000
and all the values that will be at the same time in A will be equal
6 Another 15 points Q ≤ 100.000, P ≤ 100.000
and all the values that will be at the same time in A will be different
7 Another 20 points Q ≤ 100.000, P ≤ 100.000


Sample Input

9 8
0 3
0 3
0 2
1 2
0 1
0 1
0 1
1 3
1 1


Sample Output

6
6
3
6
12
6
-1
60
60

Maximum time of execution: 0.5seconds/test.

Maximum available memory: 512 MB

Task 5 - CAMBRIDGE



The admission interview at the prestigious University of Cambridge consist of N tasks, numbered from 1 to N. Alex is there right now, waiting to attend the interview. Takahiro Wong, who has just finished his interview, solved all the tasks. More precisely, he solved the i-th problem after Di seconds from the beginning of the interview.

Knowing the fact that he can solve the i-th problem in Ti seconds, Alex asks himself M questions: x y. For every question, Alex will consider only the tasks from the interval [x;y] and he wants to know whether he can solve each of these tasks before Takahiro Wong. (Alex can solve the tasks from the interval [x;y] in any order).

For example, let’s consider that Alex has to solve the tasks a and b (in this order). He will finish task a after Ta seconds, and task b after Ta + Tb seconds. Alex will solve both problems before Takahiro Wong if Ta < Da and Ta + Tb < Db.

Both Takahiro Wong and Alex will start their interviews at second 0.
Help Alex answer correctly to all M questions.

Standard Input

  • The first line of the standard input will contain N and M.
    N - the number of tasks, M - the number of questions.
  • On the following N lines, there will be Ti and Di.
    Ti - the time needed for Alex to solve the i-th problem
    Di - the time (from the beginning of his interview) after Takahiro Wong will solve
    the i-th problem.
  • On the following M lines, there will be x and y, representing the interval [x; y].

Standard Output

The standard output will contain M lines, the answers to the M questions.
The i-th line will contain:

  • 1, if Alex cand solve all the tasks from the interval [x;y] before Takahiro Wond
  • 0, otherwise.

Restrictions and SUbtasks

  • 1 ≤ Ti < Di ≤ 109
  • The Di values are not distinct (there can be a value that appears multiple times)
  • Alex can’t solve 2 tasks in the same time, but Takahiro Wong can (The Di values are not distinct).

Subtasks

Subtask Points Restrictions
1 15 points 1 ≤ N, M ≤ 10
2 25 points 1 ≤ N * M ≤ 105
3 15 points 1 ≤ N ≤ 103
1 ≤ M ≤ 105
4 45 points 1 ≤ N , M ≤ 105


Standard Input

4 3
1 10
14 18
2 7
10 12
3 4
2 4
1 3


Standard Output

0
0
1


Explanation

The 3rd question refers to the interval [1;3]:

  • There are 6 ways Alex can solve the tasks: (1,2,3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).
  • If he solves the tasks in the order (1, 3, 2), we have to fulfill the following
    relations:
    T1 < D1, T1 + T3 < D3 si T1 + T3 + T2 < D2. We can see that all of them are true.
  • Because Alex found at least one way to solve all the problems before Takahiro Wong, the answer is 1 for the third question.

Maximum time of execution: 1.0seconds/test.

Maximum available memory: 256 MB

International Round

Task 1 - MAXCOMP



For a matrix, let’s call a subset of cells, S, connected if there is a path between any two cells of S which consists only of cells from S. A path is a sequence of cells u1, u2, ..., uk where ui and ui+1 are adjacent for any i = 1,k-1

Given a matrix A with N rows and M columns, we define the following formula for a connected subset S of A:

weight(S) = max{A(s)|s∈S}-|S|.
where |*| represents the cardinality of a set and A(s) represents the value of the cell s in A.

INPUT

The first line of input contains two number N and M representing the dimensions of the matrix A.

The following N lines describe the matrix. The i-th line contains M integers where the j-th value represents A(i,j).

OUTPUT

Print the maximum value of weight(S) between all connected components S of the given matrix.

General constraints

  • 0 ≤ A(i,j) ≤ 109
  • 1 ≤ N , M ≤ 103

SUBTASKS

  • For 15 points: 1 ≤ N*M ≤ 20
  • For other 15 points: N = 1
  • For other 30 points: N,M ≤ 20

Example

STANDARD INPUT
2 3
2 4 3
5 7 5
STANDARD OUTPUT
2

Explanation

One of the optimal connected subsets is {(1,1),(1,2),(2,2)}. {(1,1),(2,2)} is not a solution because there is no path between (1,1) and (2,2).


Time limit : 0.5seconds
Memory limit : 256MiB

Task 2 - DEL13



The bipolar monster strikes again! And the peaceful Line city is his target. As the name suggests, Line city consists of 𝑁 neighborhoods numbered 1, 2, 3, … , 𝑁 arranged from left to right in a line.


The bipolar monster makes bipolar operations on the town. An operation consists of choosing a neighborhood X that is not destroyed yet and that is not the leftmost nor the rightmost with this property, with the purpose of destroying it. However, as the monster is bipolar, right after choosing 𝑋, he decides to destroy the 2 yet undestroyed neighborhoods immediate to the left and to the right of 𝑋.


In other words, let’s assume that at some point, the neighborhoods that are not destroyed yet are, in order from left to right 1 ≤ 𝑖1 < 𝑖2 < 𝑖3 < ⋯ < 𝑖𝐾 ≤ 𝑁. X should be one of these neighborhoods, but not the leftmost nor the rightmost. Therefore, 𝑋 = 𝑖𝑗 for 𝑗 with 1 < 𝑗 < 𝐾. For this choice of 𝑗, the monster will destroy the neighborhoods indexed 𝑖𝑗−1 and 𝑖𝑗+1


Our monster is not that much of a monster as you’d think – the 2 of its personalities don’t want to destroy neighborhoods just for fun, they want to make their father proud. The monster knows what exact final configuration of neighborhoods his father would like to see, and so he’d like to make his choices of 𝑋 in such a way that the final configuration of neighborhoods left undestroyed will please his father. His father’s favorite configuration is also a subsequence of the N cities 1 ≤ 𝑝1 < 𝑝2 < 𝑝3 < ⋯ < 𝑝𝑄 ≤ 𝑁.


Sometimes, parents’ expectations are a bit unrealistic, and so can be the case with monsters! It is not even guaranteed that with the given operation (which is the only way the monster can destroy cities, given his bipolarity) the desired subsequence of neighborhoods can be achieved. That’s why the monster would like to know if he can make a proper choice of his moves so that he will achieve the given subsequence. Not only that, but, as you probably guessed, he wants to know a way of doing so, if possible.


You want to help the monster to make his father proud because he’s already been through enough (it’s hard to be a bipolar monster). He will give you a list of several cities similar to Line city and of the configurations his father wants to achieve for each such city (both the configuration and the value of 𝑁 may differ from a city to another). For each city, you need to tell the monster if he can carry out his plan and, if so, how it can do that.


Input

On the first line of the input there will be a number 𝑇 – the number of cities the monster is considering altering in order to make his father proud. The next 2𝑇 lines contain the description of the cities and monster’s father’s desired final configuration of the cities, in the following format:
𝑁 𝑄
𝑝1, 𝑝2, … , 𝑝q

Read more

Task 3 - HIDDEN SEQUENCE



This is a communication (interactive) problem!

You did it! You have finally made it to the X spot of the treasure map, but, to open the treasure chest, you first need to break the code. On the label attached to the chest, the rules of the game are written: the code is a binary sequence of length 𝑁, and in order to find this sequence you’re allowed to ask questions of the following type: “is S a subsequence of the hidden sequence?”


A binary sequence 𝑆, with values 𝑆1, 𝑆2, … , 𝑆𝐾 is considered to be a subsequence of the code 𝐶, with values 𝐶1, 𝐶2, … , 𝐶𝑁, if and only if 𝑆 can be obtained by deleting some of the values of 𝐶.

Read more

Task 4 - BALANCED TREE



A D-Balanced Tree (D being a positive integer) is a tree that satisfies the following conditions:

  • Each node is either black or white.
  • For every black node, there is at least one other black node at distance at most D
  • For every white node, there is at least one other white node at distance at most D.


You are given a tree that may not have the colour of every node decided yet. You have to choose the colour of all remaining nodes in order to minimize the value of D. However, there may be no valid positive integer D such that the tree is D-Balanced (see example).
Full score will be given only if you found a valid coloring that leads to your answer. However, partial score may be given otherwise. It will be required to solve the problem for several trees.

Read more