HomeCompetitionTasks

 Tasks

The complete list of the tasks

National Round

Task 1 - MONSTERS



The 2017 International Congress of Monsters gathers N monsters coming from all over the world. Their chairman has to solve the following problem: if the i th monster ( 1 ≤ i ≤ N ) has k i   fingers, indexed from 0 to k i - 1 , so he can lift j of those fingers ( 0 ≤ j ≤ k i ), obtaining a certain number, in the following way: if a certain finger is lifted, 2 finger index  is added to the current number. As a result, the i th monster can count on his fingers nri distinct numbers. Therefore, the demanded result is nr1 + nr2 + ... + nr nr modulo 10 9 + 7

Task

Compute the required sum, modulo 10 9 + 7

Input Format

The first line of the input file, monsters.in contains the number N.
The second line contains N positive integers, k1, k2,  . . ., kn , representing the numbers of fingers of each monster.

Output Format

The output file, monsters.out, must contain a single positive integer, the requested sum, modulo 10 9 + 7

Constraints

  • N ≤ 200,000
  • k i ≤1,000,000,000
  • The fingers are indexed from 0.
  • Subtasks

    Subtask Score Additional input constraints
    1 40 N ≤ 1.000,  k i ≤ 10.000
    2 100 N ≤ 200.000,  k i ≤ 1.000.000.000


Sample Input

  2
  3  7


Sample Output

   136


Explanation

The first monster can obtain 8 numbers:

  0 - no finger was lifted;
  1 - the index of the lifted finger is 0;
  2 - the index of the lifted finger is 1;
  3 - the indexes of the lifted fingers are 0 and 1;
  4 - the index of the lifted finger is 2;
  5 - the indexes of the lifted fingers are 0 and 2;
  6 - the indexes of the lifted fingers are 1 and 2;
  7 - the indexes of the lifted fingers are 0, 1 and 2;


The second monster can obtain 128 numbers

Task 2 - DNA



It is known that the human DNA is represented by an integer number. On a microscopical level, the DNA consists of numerous genes. Considering the binary representation of the corresponding number of the DNA, we notice the following rule: digit 1 on the i th  position indicates the presence of the i th gene, whereas digit 0 indicates its absence (i  is a positive integer ). Moreover, it was observed that any two distinct adults can give birth to a child whose DNA only contains the i th  gene if and only if the DNAs of both of the adults contain that gene.

Task

Generate an array of 2000 non-negative integers representing the DNAs of a group of adults so that the total number of children with distinct DNAs that can be born from adults belonging to this group is as big as possible. (as big as possible doesn’t mean optimum). The scoring will respect the table below.

Constraints

  • ATTENTION! This problem is "output-only". You are expected to upload a   .txt file
  • The demanded array must contain non-negative integers from the range [ 0 , 2 20-1 ].
  • All children must come from different adults, meaning that any 2 children must have at least one different parent.
  • The two parents of a child must be distinct.

Score

Score NR - the number of children with distinct DNAs
1 37 200,000 ≤ NR  ≤ 549,999
2 74 550,000 ≤ NR  ≤ 600,000
3 74 + 1,5 * ( ( X - 600,001 ) * 1 ⁄ 40000 + 1 ) 600,001 ≤ NR  ≤ 999,999
4 100 1,000,000 ≤ NR


Example

Considering that the adults have the following DNAs: 1, 5, 3, 6, 9, 12, the distinct DNAs of the children will be: 1, 0, 4, 2, 8.

Task 3 - PROMOTION



Gigel wants to test his cooking abilities and goes to the market to get some supplies. At the market, there are M types of objects sold as promotional packages for a period of N days. On the i th  day, Gigel has two options: he either buys the promotional package available on that day or not. The promotional package is represented by a non-empty subset of the set of the M types of objects and it has a certain price.

Task

Knowing M, N, the price and the composition of each of the N promotional packages, find the minimal price that Gigel should pay in order to buy at least one object of each of the M types.

Input Format

The first line of the input file, promotion.in contains 2 numbers, M and N.

The next N lines describe the N promotional packages in this way: the ( 1 + i ) th line (1 ≤ i ≤ N ) contains NR and P, which stand for the number of objects in the promotional package from that day and its price. Then, on the same line, there are given NR numbers which represent the indexes of the objects that belong to that package.

Output Format

In the output file, promotion.outprint a positive integer number equal to the minimal price that should be paid in order to buy at least one object of every type.

Constraints

  • 1 ≤ M ≤ 17, 1 ≤ N ≤ 1,000 , 1 ≤ P ≤ 1,000,000
  • All numbers found in the input file are positive integers.
  • A promotional package shall be bought only completely
  • The indexes of the objects that describe a certain package have values from the following set: {1 , 2 , … , M}.
  • It is guaranteed that there is a solution for all test cases.

Subtasks

Subtask Score Additional input constraints
1 50 M ≤ 10,  N ≤ 100
2 80 M ≤ 15,  N ≤ 1.000
3 100 M ≤ 17,  N ≤ 1.000


Sample Input

  5   4
  3  10   1  3  2
  2  8  1  4
  3  11  5  4  3
  5  27  1  4  2  3  5


Sample Output

   21


Explanation

The chosen packages are the first and the third ones, thus obtaining a minimal cost of 10+11 = 21. Note that Gigel buys one object of type 1, one object of type 2, two objects of type 3, one object of type 4 and one object of type 5.

Task 4 - COMEBACK



After going to a public garden, Antonio returns home, where he finds a string of N non-negative integers and a number X. Feeling bored, he decides to invent a game with this array in N steps. Therefore, at each step, Antonio performs 2 actions:

  1. He determines all the subsequences of the array whose sums are smaller or equal to X and calculates the arithmetic mean of the sums of such subsequences and their number.
  2. He circularly permutes the array to the left with one position.

Task

Determine the values kept in mind by Antonio at each step.

Input Format

The first line of the input file, comeback.in contains numbers N and X.

On the second line of this file there are N space-separated elements corresponding to the array.

Output Format

The output file, comeback.out   has N lines:
The i th line contains two integers separated by a space, the sum of the sums of valid subsequences at step i   and their number.

Constraints

  • N ≤ 100,000, X ≤ 1,000,000,000
  • The elements of the array are between 0 and 106.
  • A subsequence of the given array consists of elements found on consecutive positions.

Subtasks

Subtask Score Additional input constraints
1 40 N ≤ 1.000
2 100 N ≤ 100.000


Sample Input

  3   5
  1  2   3  


Sample Output

   14    5
  15   5
  13   5


Explanation

Stage 1. The sum of the sums of valid subsequences: 1 + 2 + 3 + (1 + 2) + (2 + 3)=14
There are 5 valid subsequences.
The array becomes 2, 3, 1.

Stage 2. The sum of the sums of valid subsequences: 2 + 3 + 1 + (2 + 3) + (3 + 1)=15
There are 5 valid subsequences.
The array becomes 3, 1, 2.

Stage 3. The sum of the sums of valid subsequences: 3 + 1 + 2 + (3 + 1) + (1 + 2)=13.
There are 5 valid subsequences.
The array becomes 1, 2, 3.

Task 5 - WALK



One morning, Răzvăran decided to invite his two friends, Matthew and Peter, to go for a walk in a well-known public garden. This garden has the shape of a tree with N nodes (indexed from 1 to N) and between N-1 pairs of nodes there are paths which measure 10 meters. In each i  node, there is an i  spring. The friends only accept the invitation if the walk respects the following rules: Matthew, a pretentious young man, wants to get to all of the springs walking as few meters as possible and Peter, wanting to rise up to the challenge, says that he wants to visit M springs in a pre-established order: P 1 , P 2 , … , P m. Răzvăran now wonders in how many ways they can walk, knowing that both the entrance and the exit are at the first spring, which is at the same time the root of the tree.

Task

Determine the number of ways in which the three friends can walk. This number must be printed modulo 10 9+7

Input Format

The first line of the input file, walk.in  there are two positive integers, N and M, which represent the number of springs of the public garden and the number of springs Peter wants to visit.
The next line contains N-1 numbers T 2 , T 3 , … , T n representing the parent array corresponding to the tree. On the next line there are M distinct numbers P 1 , P 2 , … , P m.

Output Format

On the first line of the output file, walk.out  you shall print the required number.

Constraints

  • 2 ≤ M ≤ N ≤ 400,000
  • It is guaranteed that the shape of the public garden is a tree (an acyclic, connected and undirected graph).

Subtasks

Subtask Score Additional input constraints
1 20 1 ≤ M ≤ N ≤ 10
2 60 1 ≤ M ≤ N ≤ 4.000
3 100 1 ≤ M ≤ N ≤ 400.000


Sample Input

  7   3
  1  1   2  2  2  3
  5  4  7


Sample Output

   3 . 4


Explanation

The correct ways the three friends can walk are:
1  2  5  2  4  2  6  2  1  3  7  3  1 
1  2  6  2  5  2  4  2  1  3  7  3  1 
1  2  5  2  6  2  4  2  1  3  7  3  1 

Moreover, three invalid walks are :
1  2  5  2  4  2  1  3  7  3  1  (the 6th spring is not visited)
1  2  4  2  5  2  6  2  1  3  7  3  1  (they visit the 4th spring before the 5th one)
1  2  4  2  5  2  6  2  4  2  1  3  7  3  1  (the length of the walk is not minimal)

International Round

Task 1 - EASTER EGGS



This is a communication (interactive) problem!

Antonio is known in his city, Barlad, for being the winner of the last edition of JBOI, a contest for juniors only. As he is a senior from now on, he wants to show his best friend, Zetul, that he can solve harder problems too.

In order to do this, Zetul hid an Easter Egg in the Public Garden, a beautiful park in their hometown. The Public Garden contains N islands, connected by N-1 bridges, so that the set of the N islands is beautiful.

Now, Antonio should find the Easter Egg asking Zetul several questions: Antonio will give Zetul a set of islands and Zetul will tell him whether or not, among the set, there is the island where the Easter Egg is hidden. The only condition Zetul is asking for is the set of islands to be beautiful. A set of islands is beautiful if any two islands are connected by some bridges . More precisely, there is a path of bridges between any two islands from the set.

You should help Antonio find the Easter Egg, using as few questions as you can, to show Zetul that Antonio can solve senior problems too!

In a test case, there will be at least one Easter Egg hidden, so make sure your program supports multiple Easter Eggs findings. There will be maximum 60 findEgg calls in a test case, the time limit is for all these calls.

Task

You need to implement a function findEgg that determines the island where the Easter Egg is hidden.

  • findEgg (N, bridges)
  • N: the number of islands.
  • bridges: vector of length N-1; it contains N-1 pairs of islands, so that for every pair there is a bridge connecting the two islands.

You can call a function query to help you find the Easter Egg. This function will return 1, if the egg is found on the islands from the query and 0 if not.

  • query (islands)
  • islands: vector of integers; the set of islands Antonio is giving to Zetul (don’t forget that set of islands must be beautiful).

Subtask N Points Percentage
1 N ≤ 16 30 100%, 0 ≤ Q ≤ 4
80%, 5 ≤ Q ≤ 6
66%, 7 ≤ Q ≤ 10
40%, 11 ≤ Q ≤ 14
25%, Q = 15
15%, Q = 16
2 N ≤ 500 40 100% 0 ≤ Q ≤ 9
85%, 10≤ Q ≤11
66%, 12≤ Q ≤ 45
3 N = 512 30 100% 0 ≤ Q ≤ 9
75%, 10≤ Q ≤11
66%, 12≤ Q ≤ 45

Implementation Details

You have to submit exactly one cpp file. This file implements findEgg as described above using the following signature: (There will not be a main)

int findEgg(int N, vector < pair < int, int > > bridges);

The signature of query is as follows:

int query(vector < int > islands);

Example

For N = 5, and bridges: (1, 2), (1, 3), (2,4), (4,5)
The set {1, 2, 3} is beautiful. The set {1, 2, 4, 5} is beautiful. The set {1, 2, 3, 5} is NOT beautiful(The islands are 1-indexed).

Task 2 - XORSUM



You are given an array V, consisting of N integers V1,  V2 ... VN.
Your task is to find the result of XOR (1 ≤ i ≤ j ≤ N) (Vi  + Vj )

Input Format

The first line contains integer N - the size of the array.
The second linde contains N space-separated integers V1  V2,   ...,   VN.

Output Format

The first line contains the required answer.

Subtasks

Subtask Constraints Scoring
1 1 ≤ N ≤ 4*103,   1 ≤ Vi  ≤ 5 * 108 7 points
2 1 ≤ N ≤ 106,   1 ≤ Vi  ≤ 4 * 103 11 points
3 1 ≤ N ≤ 106,   1 ≤ Vi  ≤ 106 21 points
4 1 ≤ N ≤ 105,   1 ≤ Vi  ≤ 5 * 108 38 points
5 1 ≤ N ≤ 106,   1 ≤ Vi  ≤ 5 * 108 23 points


Sample Input

  4
  3  9   6  6


Sample Output

   20


Note:

(1, 1) : 3 + 3 = 6
(1, 2) : 3 + 9 = 12
(1, 3) : 3 + 6 = 9
(1, 4) : 3 + 6 = 9
(2, 2) : 9 + 9 = 18
(2, 3) : 9 + 6 = 15
(2, 4) : 9 + 6 = 15
(3, 3) : 6 + 6 = 12
(3, 4) : 6 + 6 = 12
(4, 4) : 6 + 6 = 12

6 ^ 12 ^ 9 ^ 9 ^ ^18 ^ 15 ^ 15 ^ 12 ^ 12 ^ 12 = 20

Task 3 - BINARY SUBSEQUENCES



The scientific committee is in deep trouble: they could come up with a nice task, but they are not sure they can build the test data for it. The problem statement sounds like this:
“Being given a string containing only 0s and 1s, compute the number of distinct non-empty subsequences that appear in it”

Here, by subsequence of a string, we understand a string that can be obtained from the initial string by erasing some of its characters (possibly none). Two subsequences are considered different if and only if they differ in at least one place or they have different lengths. For example, string “101” has 6 different non-empty subsequences: “0”, “1”, “10”, “01”, “101” and “11”.

Now, the committee could, of course, generate the tests randomly and compute the answer for each of them with the official source, but this idea doesn’t satisfy the author. They want to have full control over the output. They want to know, for each value K in a given file, how many binary strings have exactly K different non-empty subsequences and what is the shortest such string. If there are more strings meeting the requirements, the committee will be pleased with any such string. As the answer to the first request might be very big, they want to know just the number modulo 1.000.000.007.

Input Format

On the first line of the input file, there will be a number T representing the number of values K that follow. On the next T lines there’ll be the values of K for which you need to answer to the 2 queries described in the statement

Output Format

For each value K in the input file, you’ll have to print 2 lines:

On the first line, you should print the number of binary strings that have exactly K different non-empty subsequences modulo 1.000.000.007, or, if you want to skip this query -1. If you print any number different from -1, we’ll consider that you’ve tried to answer the question.

On the second line, you should print -1 if you want to skip the query. Otherwise, you should print L binary digits separated by spaces, digits that should form one of the binary strings of minimal length that have exactly K different non-empty subsequences.

Subtasks

There will be 3 subtasks for this problem. You can skip queries only in the first subtask by printing -1s as explained in the Output section.

Subtask Constraints Scoring
1 T = 2000 and K takes all the values from 1 to 2000 in order In order to get a non-zero score, each of your answers must be either correct, either skipped. Let A be the number of correct answers to the first requirement and B the number of correct answers to the second one. You’ll get:
43 * ( 0.3 * A + 0.7 * B) * 1 / 2000 points
2 T ≤ 10, K ≤ 100.000 39 points
3 T ≤ 10, K ≤ 1.000.000 18 points


Sample Input

  3
  2
  3
  8


Sample Output

   2
  0   0
  4
  1   0
  -1
  1  1  0  0


Explanation:

For K = 2, we have exactly 2 strings that with 2 different non-empty subsequences: “00” (with subsequences “0” and “00”) and “11” (with subsequences “1” and “11”). To be noted that string “11” has the minimum length too and it would be accepted by the grader as a correct answer.

For K = 3, we have 4 strings fulfilling the requirement: “10” (with subsequences “0”, “1” and “10”), “01” (with subsequences “0”, “1” and “01”), “000” (with subsequences “0”, “00” and “000”), “111” (with subsequences “1”, “11” and “111”)

We skipped the first query for K = 8 and “1100” has exactly 8 different non-empty subsequences: “0”, “00”, “1” “11”, “110”, “1100”, “10” and “100”.

This is just an example to clarify the information in the statement. As you can see, T is not 2000, so this couldn’t be a test from subtask 1, which means that by skipping a query, we get 0 points.

Task 4 - PERMUTATION RECOVERY



Ghiţă is a guy really keen on competitive programming. His favourite activities are playing with permutations and spending time with his wife, Ana. At their 10thanniversary, Ana gave him a very beautiful permutation as she knew this is the best present Ghiţă could receive.Let Pj be the j thelement of the permutation for every j with 1 ≤ j ≤ N.
Ghiţă was so excited by his present that he began computing the value Qifor each i with 1 ≤ i ≤ N. Qi is defined as the number of increasing subsequences that he could find in the prefix of length i of his permutation.

More formally, for each i with 1 ≤ i ≤ N, Qi is the number of integer arrays j1, j2  ... jk   so that 1 ≤ j1 < j2 < ... < jk-1 < jk ≤ i and Pj1 < Pj2 < ... < Pjk.

He thought that Q, even though it wasn’t a permutation, was pretty nice too. That’s why he saved it near the permutation P.

Everything was ok until Lică Sămădăul came. He wanted to use Ghiţă’s surveillance system for immoral purposes and Ghiţa, being a fair man, didn’t help him. Enraged by Ghiţă’s answer, Lică Sămădăul hired Buză Spartă to help him steal Ghiţă’s most valuable assets: his permutation and his wife. And so he did.

The next day Ghiţă found out that P was missing and now, the only solution for Ghiţă to recover the permutation is by using the array Q that he still has. You can guess that your job is to help Ghiţă recover array P being provided with array Q.

Input Format

On the first line of the input there is N, the length of the permutation. On the second line, separated by spaces, there are Q1, Q2,  ... ,QN.

Output Format

On the first and only line of the output, you should print the array P representing the stolen permutation.

Constraints

  • It is guaranteed that there is exactly one possible answer (only one P has the given Q).
  • N ≤ 70.000
  • The input size is less than 111 MB.
  • We advise you to independently check the running time and the usage of memory of the reading part of your program in order to make sure that the eventual inefficiency of your program is not due to this part, as the reading of the input is not intended to be an impediment in solving this task.

Scoring

Subtask Restriction T = Number of digits of Q(N) Maximum input size Score
1 N ≤ 9 - - 10 points
2 N ≤ 400 T ≤ 18 - 15 points
3 N ≤ 700 - - 18 points
4 N ≤ 40.000 T ≤ 171 4.5 MB 17 points
5 N ≤ 70.000 T ≤ 258 10 MB 11 points
6 N ≤ 70.000 T ≤ 314 16 MB 7 points
7 N ≤ 70.000 - 85 MB 16 points
8 N ≤ 70.000 - 111 MB 6 points


Sample Input 1

  4
  1   2   5   6


Sample Output 1

  3  2  4  1


Sample Input 2

  6
  1   3   5   9   11   21


Sample Output 2

  1  6  3  4  2  5


Explanation:

In the first example, N = 4 and P = {3, 2, 4, 1}
Q1 = 1 because {3} is the only increasing subsequence of {3}
Q2 = 2 because {3} and {2} are the only increasing subsequences of {3, 2}
Q3 = 5 because {3}, {3, 4}, {2}, {2, 4} and {4} are the only increasing subsequences of {3, 2, 4}
Q4 = 6 because {3}, {3, 4}, {2}, {2, 4}, {4} and {1} are the only increasing subsequences of {3, 2, 4, 1}.