Analysis of the tasks of the second qualification round of RCC 2016 / Mail.ru Group blog

On May 29, the second qualifying round of the Russian Code Cup 2016 championship was held, which was first held in English. This time, the participants again had to solve five problems within two hours. In the second qualifying round, 3891 people fought, and the 200 best received the right to participate in the qualifying round, which will be held on June 19. And today we suggest you familiarize yourself with the solutions to the proposed problems.

1. Petya and the textbook
2. Gregory and the Bank
3. Name Generators
4. T-shirts
5. Bridge testing

Problem A. Petya and the textbook

Condition

Time limit 2 seconds
Memory limit 256 megabytes

While cleaning the room today, Petya found his old Russian language textbook. Since he does not like this subject since childhood, he began to tear out pages from it.

In the textbook, there are n pages numbered from 1 to n that are bound together so that i and n  -  i   + 1 pages are connected to each other - if one of them is torn out, the second also drops out of the textbook. Petya really likes the process of tearing pages out of a textbook, but he still wants to control it, and it is at some points in time that he is interested to know what number p has1st in order of the remaining pages. Help him with this task.

Input format

Input data contains several test suites. The first line contains the number of tests t (1 ≤  t  ≤ 1000).

Each of the following t tests is described as follows: the first line of the test description contains two numbers n , q (2 ≤  n  ≤ 100, n is even; 1 ≤  q  ≤ 100) - the number of pages in the textbook and the number of requests, respectively. The following q lines contain two types of queries:

• - i - Petya pulls out the page with number i ;
• ? p - Petya wants to find out which number has the pth in order from the remaining pages.

It is guaranteed that in the first type request the deleted page exists, and in the second type request the current number of pages is not less than p .

Output format

For each request of the second type in a separate line print the number of the page you are looking for.

Examples

Input
2
4 4
? 3
- 2
? 2
? 1
6 5
- 3
? 3
- 1
? 2
? 1

Output
3
4
1
5
5
2

Solution

In this task, you just had to write what you are asking. It is enough to store an isDeleted array of size n, where isDeleted [i] means whether page number i has already been torn out . To process the first request, it is enough to set isDeleted [i] and isDeleted [ n  -  i  + 1] to false, and to process the second request, find the index p- th true in the isDeleted array .

Asymptotic behavior of the solution: O (t • q • n) .

Problem V. Gregory and the Bank

Condition

Time limit 2 seconds
Memory limit 256 megabytes

Gregory works in accounting at one large enterprise. He receives bank transfers from buyers and transfers money to sellers.

Gregory receives and sends all transfers through the only accessible branch of the bank, in which his company is serviced. The work of this department is rather strange. Every day, the bank works in one of two ways: it allows customers to either send or only accept money transfers. At the same time, Gregory can perform no more than one operation: receive one transfer or make one transfer, depending on the type of operation allowed on that day. You can choose a counterparty at your discretion. At the same time, the head of Gregory makes him necessarily go to the bank and send or receive transfers every day, otherwise he will decide that Gregory is not working and will fire him.

Gregory must process n requests for receiving money from buyers and mrequests to send money to sellers. Gregory knows the schedule of the bank, and can also agree with each buyer and seller about when the money will be transferred.

At the initial moment, there is no money on the account managed by Gregory. Then he comes to the bank every day and either receives money in the account or sends it from him. At the same time, he understands that it may turn out that he will not be able to pay off some sellers. Gregory will not be able to pay if, on the agreed day of payment, he has less money on his account than is required to pay for the services of the seller. In this case, money from the account is not transferred, and Gregory receives a reprimand from his superiors. The offended seller refuses to deliver the goods and no longer interacts with the company of Gregory.

Gregory wants to agree on the days of settlements with sellers and buyers so that sellers with whom he will not be able to pay are as few as possible. Help him do it!

Input format

Input data contains several test suites. The first line contains the number of tests t (1 ≤  t  ≤ 1000).

Each of the tests is described as follows: the first line of the test description contains the numbers n and m (1 ≤  n ,  m  ≤ 100) - the number of buyers and sellers, respectively. The second line contains n numbers a _i (1 ≤  a _i ≤ 1000) - the amount that the i- th buyer must transfer . The third line contains m numbers b _j (1 ≤  b _j  ≤ 1000) - the amount to be transferred to the jth seller. The last line of the test description contains the string s (the length s is n  +  m , s contains n + characters and m characters -). s [k] is +, if on the k- th day the bank only accepts money transfers, and if the bank works only to send transfers, then s [k] is -.

Output format

For each test, in a separate line print the answer to it - the minimum possible number of sellers that Grigory will not be able to pay.

Examples

Input
3
2 1
1 5
4
+ - +
1 3
1
2 2 2
- + -
2 2
2 2
3 3
+ - + -

Output
0
3
1

Solution

The idea to solve this problem is based on greedy. Consider a random arrangement of buyers and sellers.

Suppose we have a pair of buyers a _i and a _j , i  < j and a _i  <  a _j . i and j are the positions in the selected random arrangement. If you swap them, it is obvious that the answer will not worsen, since the amount of money in Gregory’s account will increase in the interval from i to j . Therefore, it is advantageous for buyers to transfer money in descending order of a _i .

Similarly, we can prove that if there are two sellers with whom you can pay, it is more profitable to put them in ascending order of b _j .

The only subtle point is the presence of sellers with whom it is impossible to pay. Obviously, if Gregory cannot pay with x sellers, then it is more profitable that they are the most expensive.

Based on the foregoing, we obtain a solution to the problem. We sort the sequences a _i and b _j , after which we simulate the process, maintaining the current balance of Gregory.

Problem C. Name Generators

Condition

Time limit 2 seconds
Memory limit of 256 megabytes of

the greatest writers of all time Henk Morbuks already figured out what he was going to write the next bestseller, but has not yet decided on the names k their characters. As for previous books, he will receive names by dividing a specially invented string into k different and non-empty parts. Help Henk understand if it is possible to split a given string into k different names.

Input format

The first line of the file contains the number of tests t (1 ≤  t  ≤ 1000).

Each test is described in two lines. The first line of the test description contains a string of length not exceeding 100, consisting of lowercase English letters. The second line contains one positive number k (1 ≤  k  ≤ 5) - by how many different lines you need to divide the given one.

Output Format

The result of each test should be displayed in the format described below.

If you can split the source line in the described way, then the output file must contain k  + 1 lines. The first line should contain YES. The ( i  + 1) th line should contain the i- th name. The original string should be obtained by concatenating the strings in the output order.

If it is impossible to split the source line in the described way, the output file should contain one line NO.

Examples

Input
3
aaa
2
aaa
3
abc
3

Output
YES
a
aa
NO
YES
a
b
c

Solution

First of all, we note that for any k all strings of length greater than or equal to k ( k  + 1) / 2 can be divided into k distinct. To do this, we take substrings of length 1, 2, ..., k  - 1 and n  -  k ( k - 1) / 2. Since k  ≤ 5, we learned to split all the lines with a length of at least 15. And for lines of length less than 15, we start iterating over all k  - 1 positions where we split it, and check if all the lines in the resulting split are true various.

Task D. T-Shirts

Condition

Time limit 2 seconds
Memory limit 256 megabytes

Ilya, Vanya and Vlad have long been involved in team programming competitions. This year there were n team competitions, in each of which the guys received a T-shirt. We assume that the types of T-shirts are numbered from 1 to n , in accordance with the competitions at which they were awarded.

Every boy has a favorite T-shirt, a little less favorite, and so on. Namely, each boy has a permutation of numbers from 1 to n - the number of T-shirts, the first of which is the most favorite, and the last is the most unloved.

Now the guys are in the competition. They want to wear the same t-shirts for every contest. But their t-shirt preferences may differ, so before the contest they wrote out numbers from 1 to n on a piece of paper and cross out one number in turn. The t-shirt, the number of which remains the last, the guys put on this time.

The guys always cross out optimally, that is, everyone is trying to make sure that in the end there is a t-shirt that he likes the most. Therefore, the guys decided to ask you to write a program that will find the number of T-shirts, which will remain in the end.

Input format The input

contains several test cases. The first line contains one number t (1 ≤  t ≤ 50) - the number of tests. The following are descriptions of the tests.

Each test is defined as follows: the first line contains one natural number n (1 ≤  n  ≤ 13) - the number of competitions in which the guys participated.

The next line contains a permutation from 1 to n - Ilya's t-shirt preferences.

The next line contains a permutation from 1 to n - preferences for Vani's t-shirts.

The next line contains a permutation from 1 to n - Vlad's t-shirt preferences.

The guys go in the following order: Ilya, Vanya, Vlad.

Output format

For each test case print a single number - the number of the T-shirt, which will remain in the end.

Examples

Input
3
4
1 3 2 4
4 1 2 3
1 2 3 4
5
1 3 2 4 5
5 3 2 1 4
1 3 2 4 5
3
1 2 3
1 2 3
1 2 3

Output
1
3
1

Solution

For To solve this problem, we use dynamic subset programming. Denoted by dp [i] [mask] the optimal number of T-shirts, which can achieve the i -th participant, if he makes a move and he was available to T-shirts, the corresponding set bits in the number of mask. To recount, we’ll sort out which T-shirt he will cross out and find out which T-shirt he will get using the value dp [( i  + 1)% 3] [ mask 1], where mask 1 is obtained from mask by zeroing the corresponding bit.

Task E. Bridge Testing

Condition

Time limit 4 seconds
Memory limit 256 megabytes

A small country located on the islands is developing its transport system. Some of the islands are connected by bridges in such a way that between any two islands there is only one way along the bridges, in other words, the bridge system forms a tree. Bridges can have different lengths.

Before opening these bridges for everyone, it is necessary to check their reliability. To do this, within q days, two workers will travel at a fixed speed of 1 along some path from one island to another. Each of them will travel its own way, possibly starting at different points in time. The bridge is considered tested in iday, if that day both workers rode along it for a certain non-zero period of time. For each of the q test days, determine if at least one bridge was tested that day.

Input data format

The first line contains two numbers n and q (1 ≤  n ,  q  ≤ 10 ⁵ ,  n  ≥ 2) - the number of islands and test days, respectively. The following n  - 1 lines describe the bridges in the format u _i v _i l _i (1 ≤  u _i ,  v _i  ≤  n, 1 ≤  l _i  ≤ 10 ⁹ ) - the ends of the bridge and its length. Each of the following q lines contains descriptions of the two working paths. Each path is given by three numbers b _i ,  e _i ,  s _i (1 ≤  b _i ,  e _i  ≤  n , 1 ≤  s _i  ≤ 10 ⁹ ,  b _i  ≠  e _i ) - the initial and final vertex of the path, as well as the time, in which worker will begin to move.

Output Format

Output qlines with answers to requests. In the i- th line print YES if at least one bridge was tested on the i- th day, and NO otherwise.

Examples

Input
8 6
1 2 3
1 3 1
1 4 2
2 5 5
2 6 1
5 7 2
5 8 4
5 3 2 7 4 2
8 6 1 1 7 6
4 5 1 4 5 10
7 8 3 3 4 5
6 7 6 5 1 2
2 1 10 8 3 3

Output
YES
YES
NO
NO
NO
YES

Solution

We will solve all the requests independently from each other, online. To begin with, we find the intersection of two paths and leave only this intersection from each of the paths.

How to find the intersection of two paths? To do this, "project" each of the ends of the second path to the first path. The projection of a vertex u onto a path s → t is a vertex lying on the path s → t , which is the closest to u by distance in the tree. This vertex can be one of the following vertices:

• s or t ;
• LCA ( s ,  t );
• LCA ( s ,  u ) if it lies on the path s → t ;
• LCA ( t ,  u ) if it lies on the path s → t .

The path between the projections of each of the vertices of the second path onto the first will be the desired intersection, we denote it by s ' → t' .

After this, two cases should be considered:

• The paths go along this intersection in different directions. In this case, you can find the point in time when both workers will be at the same point (do not forget that it can be half-integral). After this, it remains to verify that this moment of time corresponds to the edge, and not the top.
• The paths go in the same direction. In this case, it can be shown that if both workers at one point in time were on one edge, then this is also true for an edge with a maximum length on the path s ' → t' . If the maximum edge length on s ' → t' is M , then the answer is YES if and only if | t ₁  -  t ₂ | <  M , where t ₁ and t ₂ - time of the beginning of movement.

In the solution described above, LCA search was used, the search for the maximum edge on the path and the distance between two vertices. All this can be realized, for example, using the binary ups technique in O (( n  +  q ) log n ) time and O ( n log n ) memory.

***
The Russian Code Cup Championship is one of the Mail.Ru Group initiatives aimed at developing the Russian IT industry and united by the IT.Mail.Ru resource. The IT.Mail.Ru platform was created for those who are interested in IT and strive to develop professionally in this field. The project unites the championships of the Russian Ai Cup, Russian Code Cup and Russian Developers Cup, educational projects of the Technopark at MSTU. Bauman, Technosphere at Moscow State University M.V. Lomonosov and Technotrek at MIPT. In addition, at IT.Mail.Ru you can use the tests to test your knowledge of popular programming languages, learn important news from the IT world, visit or watch broadcasts from relevant events and lectures on IT topics.