Codeforces Global Round 16

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
1566 Codeforces Global Round 16 FINISHED False 9000 105722662 Sept. 12, 2021, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 130 ) H Xor-quiz PROGRAMMING constructive algorithms dp interactive math number theory

B"This is an interactive problem. You are given two integers c and n . The jury has a randomly generated set A of distinct positive integers not greater than c (it is generated from all such possible sets with equal probability). The size of A is equal to n . Your task is to guess the set A . In order to guess it, you can ask at most lceil 0.65 cdot c rceil queries. In each query, you choose a single integer 1 <= x <= c . As the answer to this query you will be given the bitwise xor sum of all y , such that y in A and gcd(x, y) = 1 (i.e. x and y are coprime). If there is no such y this xor sum is equal to 0 . You can ask all queries at the beginning and you will receive the answers to all your queries. After that, you won't have the possibility to ask queries. You should find any set A' , such that |A'| = n and A' and A have the same answers for all c possible queries. Firstly you are given two integers c and n ( 100 <= c <= 10^6 , 0 <= n <= c ). In the first line you should print an integer q (0 <= q <= lceil 0.65 cdot c rceil) -- the number of queries you want to ask. After that in the same line print q integers x_1, x_2, ldots, x_q (1 <= x_i <= c) -- the queries. For these queries you should read q integers, i -th of them is the answer to the described query for x = x_i . After that you should print n distinct integers A'_1, A'_2, ldots, A'_n -- the set A' you found. If there are different sets A' that have the same answers for all possible queries, print any of them. If you will ask more than lceil 0.65 cdot c rceil queries or if the queries will be invalid, the interactor will terminate immediately and your program will receive verdict Wrong Answer. After printing the queries and answers do not forget to output en"...

Tutorials

Codeforces Global Round 16 Editorial

Submissions

No solutions yet.