Codeforces Round #616 (Div.

2)

A. Even But Not Even In the first test case of the example, 1227 is already an ebne number (as
1 + 2 + 2 + 7 = 12 , 12 is divisible by 2, while in the same time, 1227 is
1 second, 256 megabytes not divisible by 2) so we don't need to delete any digits. Answers such as
127 and 17 will also be accepted.
Let's define a number ebne (even but not even) if and only if its sum of
digits is divisible by 2 but the number itself is not divisible by 2. For In the second test case of the example, it is clearly impossible to create
example, 13 , 1227 , 185217 are ebne numbers, while 12 , 2, 177013, an ebne number from the given number.
265918 are not. If you're still unsure what ebne numbers are, you can
In the third test case of the example, there are many ebne numbers we
look at the sample notes for more clarification.
can obtain by deleting, for example, 1 digit such as 17703 , 77013 or
You are given a non-negative integer 𝑠, consisting of 𝑛 digits. You can 17013 . Answers such as 1701 or 770 will not be accepted as they are

delete some digits (they are not necessary consecutive/successive) to not ebne numbers. Answer 013 will not be accepted as it contains
make the given number ebne. You cannot change the order of the digits, leading zeroes.
that is, after deleting the digits the remaining digits collapse. The resulting
Explanation:
number shouldn't contain leading zeros. You can delete any number of
digits between 0 (do not delete any digits at all) and 𝑛 − 1 . 1 + 7 + 7 + 0 + 3 = 18 . As 18 is divisible by 2 while 17703 is not
For example, if you are given 𝑠 =222373204424185217171912 divisible by 2, we can see that 17703 is an ebne number. Same with
then one of possible ways to make it ebne is: 77013 and 17013 ;

222373204424185217171912 → 2237344218521717191. The 1 + 7 + 0 + 1 = 9 . Because 9 is not divisible by 2, 1701 is not an

sum of digits of 2237344218521717191 is equal to 70 and is ebne number;
divisible by 2, but number itself is not divisible by 2: it means that the 7 + 7 + 0 = 14 . This time, 14 is divisible by 2 but 770 is also
resulting number is ebne. divisible by 2, therefore, 770 is not an ebne number.
Find any resulting number that is ebne. If it's impossible to create an In the last test case of the example, one of many other possible answers
ebne number from the given number report about it.
is given. Another possible answer is: 222373204424185217171912
→ 22237320442418521717191 (delete the last digit).
Input
The input consists of multiple test cases. The first line contains a single
integer 𝑡 (1 ≤ 𝑡 ≤ 1000)  — the number of test cases. The description of
the test cases follows.
B. Array Sharpening
1 second, 256 megabytes
The first line of each test case contains a single integer 𝑛 (1 ≤ 𝑛 ≤ 3000 )
 — the number of digits in the original number. You're given an array 𝑎1 , … , 𝑎𝑛 of 𝑛 non-negative integers.
The second line of each test case contains a non-negative integer Let's call it sharpened if and only if there exists an integer 1 ≤ 𝑘 ≤ 𝑛
number 𝑠, consisting of 𝑛 digits. such that 𝑎1 < 𝑎2 < … < 𝑎𝑘 and 𝑎𝑘 > 𝑎𝑘+1 > … > 𝑎𝑛 . In particular,
any strictly increasing or strictly decreasing array is sharpened. For
It is guaranteed that 𝑠 does not contain leading zeros and the sum of 𝑛
over all test cases does not exceed 3000 . example:

Output The arrays [4] , [0, 1], [12, 10, 8] and [3, 11, 15, 9, 7, 4] are
For each test case given in the input print the answer in the following sharpened;
format: The arrays [2, 8, 2, 8, 6, 5] , [0, 1, 1, 0] and [2, 5, 6, 9, 8, 8] are not
sharpened.
If it is impossible to create an ebne number, print "-1" (without
quotes); You can do the following operation as many times as you want: choose
Otherwise, print the resulting number after deleting some, possibly any strictly positive element of the array, and decrease it by one.
zero, but not all digits. This number should be ebne. If there are Formally, you can choose any 𝑖 (1 ≤ 𝑖 ≤ 𝑛) such that 𝑎𝑖 > 0 and assign
𝑎𝑖 := 𝑎𝑖 − 1.
multiple answers, you can print any of them. Note that answers with
leading zeros or empty strings are not accepted. It's not necessary Tell if it's possible to make the given array sharpened using some number
to minimize or maximize the number of deleted digits. (possibly zero) of these operations.

Input
input The input consists of multiple test cases. The first line contains a single
4 integer 𝑡 (1 ≤ 𝑡 ≤ 15 000 )  — the number of test cases. The description
4
of the test cases follows.
1227
1
The first line of each test case contains a single integer 𝑛 (
0
1 ≤ 𝑛 ≤ 3 ⋅ 10 ).
5
6
177013
24 The second line of each test case contains a sequence of 𝑛 non-negative
222373204424185217171912 integers 𝑎1 , … , 𝑎𝑛 (0 ≤ 𝑎𝑖 ≤ 109 ).
output It is guaranteed that the sum of 𝑛 over all test cases does not exceed
1227 3 ⋅ 10 .
5

-1
17703 Output
2237344218521717191

/
For each test case, output a single line containing "Yes" (without quotes) Please note that the friends you don't control may do their choice
if it's possible to make the given array sharpened using the described arbitrarily, and they will not necessarily take the biggest element
operations, or "No" (without quotes) otherwise. available.

input Input
The input consists of multiple test cases. The first line contains a single
10 integer 𝑡 (1 ≤ 𝑡 ≤ 1000)  — the number of test cases. The description of
1
248618 the test cases follows.
3
12 10 8
The first line of each test case contains three space-separated integers 𝑛,
6 𝑚 and 𝑘 (1 ≤ 𝑚 ≤ 𝑛 ≤ 3500 , 0 ≤ 𝑘 ≤ 𝑛 − 1 )  — the number of

100 11 15 9 7 8 elements in the array, your position in line and the number of people
4 whose choices you can fix.
0 1 1 0
2 The second line of each test case contains 𝑛 positive integers
0 0
𝑎1 , 𝑎2 , … , 𝑎𝑛 (1 ≤ 𝑎𝑖 ≤ 10 )  — elements of the array.
9

2
0 1
2 It is guaranteed that the sum of 𝑛 over all test cases does not exceed
1 0 3500 .

2
1 1 Output
3 For each test case, print the largest integer 𝑥 such that you can
0 1 0
guarantee to obtain at least 𝑥.
3
1 0 1
input
output
4
Yes 6 4 2
Yes 2 9 2 3 8 5
Yes 4 4 1
No 2 13 60 4
No 4 1 3
Yes 1 2 2 1
Yes 2 2 0
Yes 1 2
Yes
No output
8
In the first and the second test case of the first test, the given array is 4
already sharpened. 1
1
In the third test case of the first test, we can transform the array into
[3, 11, 15, 9, 7, 4] (decrease the first element 97 times and decrease the In the first test case, an optimal strategy is to force the first person to
last element 4 times). It is sharpened because 3 < 11 < 15 and take the last element and the second person to take the first element.
15 > 9 > 7 > 4 .

the first person will take the last element (5) because he or she was
In the fourth test case of the first test, it's impossible to make the given
forced by you to take the last element. After this turn the remaining
array sharpened.
array will be [2, 9, 2, 3, 8] ;
the second person will take the first element (2) because he or she
C. Mind Control was forced by you to take the first element. After this turn the
1 second, 256 megabytes remaining array will be [9, 2, 3, 8] ;
if the third person will choose to take the first element (9), at your turn
You and your 𝑛 − 1 friends have found an array of integers the remaining array will be [2, 3, 8] and you will take 8 (the last
𝑎1 , 𝑎2 , … , 𝑎𝑛 . You have decided to share it in the following way: All 𝑛 of
element);
you stand in a line in a particular order. Each minute, the person at the
if the third person will choose to take the last element (8), at your turn
front of the line chooses either the first or the last element of the array,
the remaining array will be [9, 2, 3] and you will take 9 (the first
removes it, and keeps it for himself. He then gets out of line, and the next
element).
person in line continues the process.

You are standing in the 𝑚 -th position in the line. Before the process Thus, this strategy guarantees to end up with at least 8. We can prove
starts, you may choose up to 𝑘 different people in the line, and persuade that there is no strategy that guarantees to end up with at least 9. Hence,
them to always take either the first or the last element in the array on their the answer is 8.
turn (for each person his own choice, not necessarily equal for all people), In the second test case, an optimal strategy is to force the first person to
no matter what the elements themselves are. Once the process starts, take the first element. Then, in the worst case, both the second and the
you cannot persuade any more people, and you cannot change the third person will take the first element: you will end up with 4.
choices for the people you already persuaded.

Suppose that you're doing your choices optimally. What is the greatest D. Irreducible Anagrams
integer 𝑥 such that, no matter what are the choices of the friends you
didn't choose to control, the element you will take from the array will be 2 seconds, 256 megabytes
greater than or equal to 𝑥?
Let's call two strings 𝑠 and 𝑡 anagrams of each other if it is possible to
rearrange symbols in the string 𝑠 to get a string, equal to 𝑡.

/
Let's consider two strings 𝑠 and 𝑡 which are anagrams of each other. output
We say that 𝑡 is a reducible anagram of 𝑠 if there exists an integer 𝑘 ≥ 2
No
and 2𝑘 non-empty strings 𝑠1 , 𝑡1 , 𝑠2 , 𝑡2 , … , 𝑠𝑘 , 𝑡𝑘 that satisfy the Yes
following conditions: Yes
Yes
1. If we write the strings 𝑠1 , 𝑠2 , … , 𝑠𝑘 in order, the resulting string will No
No
be equal to 𝑠;
2. If we write the strings 𝑡1 , 𝑡2 , … , 𝑡𝑘 in order, the resulting string will be In the first sample, in the first and third queries, the substring is "a",
equal to 𝑡; which has itself as an irreducible anagram since two or more non-empty
3. For all integers 𝑖 between 1 and 𝑘 inclusive, 𝑠𝑖 and 𝑡𝑖 are anagrams strings cannot be put together to obtain "a". On the other hand, in the
of each other. second query, the substring is "aaa", which has no irreducible anagrams:
its only anagram is itself, and we may choose 𝑠1 = "a", 𝑠2 = "aa", 𝑡1 =
If such strings don't exist, then 𝑡 is said to be an irreducible anagram of 𝑠.
"a", 𝑡2 = "aa" to show that it is a reducible anagram.
Note that these notions are only defined when 𝑠 and 𝑡 are anagrams
of each other. In the second query of the second sample, the substring is "abb", which
has, for example, "bba" as an irreducible anagram.
For example, consider the string 𝑠 = "gamegame". Then the string 𝑡 =
"megamage" is a reducible anagram of 𝑠, we may choose for example
𝑠1 = "game", 𝑠2 = "gam", 𝑠3 = "e" and 𝑡1 = "mega", 𝑡2 = "mag", E. Prefix Enlightenment
𝑡3 = "e":
3 seconds, 256 megabytes

On the other hand, we can prove that 𝑡 = "memegaga" is an irreducible There are 𝑛 lamps on a line, numbered from 1 to 𝑛. Each one has an
anagram of 𝑠. initial state off (0) or on (1).

You will be given a string 𝑠 and 𝑞 queries, represented by two integers You're given 𝑘 subsets 𝐴1 , … , 𝐴𝑘 of {1, 2, … , 𝑛} , such that the
1 ≤ 𝑙 ≤ 𝑟 ≤ |𝑠| (where |𝑠| is equal to the length of the string 𝑠). For
intersection of any three subsets is empty. In other words, for all
1 ≤ 𝑖1 < 𝑖2 < 𝑖3 ≤ 𝑘 , 𝐴𝑖 ∩ 𝐴𝑖 ∩ 𝐴𝑖 = ∅ .
each query, you should find if the substring of 𝑠 formed by characters 1 2 3

from the 𝑙-th to the 𝑟 -th has at least one irreducible anagram. In one operation, you can choose one of these 𝑘 subsets and switch the
state of all lamps in it. It is guaranteed that, with the given subsets, it's
Input
possible to make all lamps be simultaneously on using this type of
The first line contains a string 𝑠, consisting of lowercase English
operation.
characters (1 ).
5
≤ |𝑠| ≤ 2 ⋅ 10

Let 𝑚𝑖 be the minimum number of operations you have to do in order to

The second line contains a single integer 𝑞 (1 )  — the number
5
≤ 𝑞 ≤ 10
make the 𝑖 first lamps be simultaneously on. Note that there is no
of queries.
condition upon the state of other lamps (between 𝑖 + 1 and 𝑛), they can
Each of the following 𝑞 lines contain two integers 𝑙 and 𝑟 ( be either off or on.
1 ≤ 𝑙 ≤ 𝑟 ≤ |𝑠| ), representing a query for the substring of 𝑠 formed by
You have to compute 𝑚𝑖 for all 1 ≤ 𝑖 ≤ 𝑛 .
characters from the 𝑙-th to the 𝑟 -th.
Input
Output
The first line contains two integers 𝑛 and 𝑘 (1 ).
5
≤ 𝑛, 𝑘 ≤ 3 ⋅ 10
For each query, print a single line containing "Yes" (without quotes) if the
corresponding substring has at least one irreducible anagram, and a The second line contains a binary string of length 𝑛, representing the
single line containing "No" (without quotes) otherwise. initial state of each lamp (the lamp 𝑖 is off if 𝑠𝑖 = 0 , on if 𝑠𝑖 = 1 ).

The description of each one of the 𝑘 subsets follows, in the following

input
format:
aaaaa
3 The first line of the description contains a single integer 𝑐 (1 ≤ 𝑐 ≤ 𝑛 )  —
1 1 the number of elements in the subset.
2 4
5 5 The second line of the description contains 𝑐 distinct integers 𝑥1 , … , 𝑥𝑐 (
1 ≤ 𝑥𝑖 ≤ 𝑛 )  — the elements of the subset.
output
Yes It is guaranteed that:
No
Yes The intersection of any three subsets is empty;
It's possible to make all lamps be simultaneously on using some
input operations.
aabbbbbbc
6 Output
1 2 You must output 𝑛 lines. The 𝑖-th line should contain a single integer 𝑚𝑖
2 4
 — the minimum number of operations required to make the lamps 1 to 𝑖
2 2
1 9 be simultaneously on.
5 7
3 5

/
input output
7 3 0
0011100 1
3 1
1 4 6 1
3 2
3 4 7 2
2 2
2 3 3
3
output 3
3
1
4
2
4
3
4
3
4
3
4
3
4
3
4
5
input
In the first example:
8 6
00110011
3 For 𝑖 = 1, we can just apply one operation on 𝐴1 , the final states will
1 3 8 be 1010110 ;
5
For 𝑖 = 2, we can apply operations on 𝐴1 and 𝐴3 , the final states
1 2 5 6 7
2 will be 1100110 ;
6 8 For 𝑖 ≥ 3, we can apply operations on 𝐴1 , 𝐴2 and 𝐴3 , the final
2
3 5 states will be 1111111 .
2
4 7 In the second example:
1
2 For 𝑖 ≤ 6, we can just apply one operation on 𝐴2 , the final states will
output be 11111101;
1 For 𝑖 ≥ 7, we can apply operations on 𝐴1 , 𝐴3 , 𝐴4 , 𝐴6 , the final
1 states will be 11111111.
1
1
1
1
F. Coffee Varieties (easy version)
4 1 second, 256 megabytes
4
This is the easy version of the problem. You can find the hard version in
input the Div. 1 contest. Both versions only differ in the number of times you
5 3 can ask your friend to taste coffee.
00011
3 This is an interactive problem.
1 2 3
1 You're considering moving to another city, where one of your friends
4 already lives. There are 𝑛 cafés in this city, where 𝑛 is a power of two. The
3 𝑖-th café produces a single variety of coffee 𝑎𝑖 .
3 4 5
As you're a coffee-lover, before deciding to move or not, you want to
output
know the number 𝑑 of distinct varieties of coffees produced in this
1 city.
1
1 You don't know the values 𝑎1 , … , 𝑎𝑛 . Fortunately, your friend has a
1
1 memory of size 𝑘, where 𝑘 is a power of two.

Once per day, you can ask him to taste a cup of coffee produced by the
input café 𝑐 , and he will tell you if he tasted a similar coffee during the last 𝑘
19 5 days.
1001001001100000110
2 You can also ask him to take a medication that will reset his memory. He
2 3 will forget all previous cups of coffee tasted. You can reset his memory at
2 most 30 000 times.
5 6
2 More formally, the memory of your friend is a queue 𝑆 . Doing a query on
8 9
café 𝑐 will:
5
12 13 14 15 16
1 Tell you if 𝑎𝑐 is in 𝑆 ;
19 Add 𝑎𝑐 at the back of 𝑆 ;
If |𝑆 | > 𝑘, pop the front element of 𝑆 .

Doing a reset request will pop all elements out of 𝑆 .

/
 2𝑛
2
The second line should contain two integers 𝑛 and 𝑘, separated by space
Your friend can taste at most cups of coffee in total. Find the (1 ≤ 𝑘 ≤ 𝑛 ≤ 1024, 𝑘 and 𝑛 are powers of two).
𝑘
diversity 𝑑 (number of distinct values in the array 𝑎). 2
2𝑛
It must hold that ≤ 20 000 .
Note that asking your friend to reset his memory does not count towards 𝑘
the number of times you ask your friend to taste a cup of coffee.
The third line should contain 𝑛 integers 𝑎1 , 𝑎2 , … , 𝑎𝑛 , separated by
In some test cases the behavior of the interactor is adaptive. It means spaces (1 ≤ 𝑎𝑖 ≤ 𝑛 ).
that the array 𝑎 may be not fixed before the start of the interaction and
may depend on your queries. It is guaranteed that at any moment of the input
interaction, there is at least one array 𝑎 consistent with all the answers 4 2
given so far. N
N
Y
Input N
The first line contains two integers 𝑛 and 𝑘 (1 ≤ 𝑘 ≤ 𝑛 ≤ 1024 𝑘 , and 𝑛 N
are powers of two). N
N
2
2𝑛
It is guaranteed that ≤ 20 000 . output
𝑘
? 1
Interaction ? 2
You begin the interaction by reading 𝑛 and 𝑘. ? 3
? 4
To ask your friend to taste a cup of coffee produced by the café 𝑐 , in R
? 4
a separate line output ? 1
? 𝑐 ? 2
! 3
Where 𝑐 must satisfy 1 ≤ 𝑐 ≤ 𝑛 . Don't forget to flush, to get the
answer. input
In response, you will receive a single letter Y (yes) or N (no), telling 8 8
you if variety 𝑎𝑐 is one of the last 𝑘 varieties of coffee in his memory. N
N
To reset the memory of your friend, in a separate line output the N
N
single letter R in upper case. You can do this operation at most Y
30 000 times. Y
When you determine the number 𝑑 of different coffee varieties, output
output ? 2
! 𝑑 ? 6
? 4
2
? 5
In case your query is invalid, you asked more than 2𝑛
queries of type ?
𝑘 ? 2
or you asked more than 30 000 queries of type R, the program will print ? 5
the letter E and will finish interaction. You will receive a Wrong Answer ! 6
verdict. Make sure to exit immediately to avoid getting other verdicts.
In the first example, the array is 𝑎 = [1, 4, 1, 3] . The city produces 3
After printing a query do not forget to output end of line and flush the different varieties of coffee (1, 3 and 4).
output. Otherwise, you will get Idleness limit exceeded. To do this, use:
The successive varieties of coffee tasted by your friend are
1, 4, 1, 3, 3, 1, 4 (bold answers correspond to Y answers). Note that
fflush(stdout) or cout.flush() in C++;
between the two ? 4 asks, there is a reset memory request R, so the
System.out.flush() in Java;
answer to the second ? 4 ask is N. Had there been no reset memory
flush(output) in Pascal;
request, the answer to the second ? 4 ask is Y.
stdout.flush() in Python;
see documentation for other languages. In the second example, the array is 𝑎 = [1, 2, 3, 4, 5, 6, 6, 6] . The city
produces 6 different varieties of coffee.
Hack format
The successive varieties of coffee tasted by your friend are
The first line should contain the word fixed 2, 6, 4, 5, 2, 5 .

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform