Thanks for participating, hope you enjoyed the problems! Implementations for the problems are chosen randomly among testers, and I made some changes to their codes (for example, deleted meaningless comment lines). Please do not hesitate to provide feedback in the comments, so I can improve in setting problems next time.

**UPD**: Sorry but there is a checker bug in problem E. All submissions of problem E will be rejudged soon.

**UPD2:** Rejudge done, the round remains rated.

**Statistics**

Number of FST for rated participants:

Problem A: $$$29$$$

Problem B: $$$90$$$

Problem C: $$$12$$$

Problem D1: $$$4$$$

Problem D2: $$$0$$$

Problem E: $$$6$$$

Number of AK: $$$22$$$

Number of clarifications: $$$85$$$

**Hint**

When is the lexicographically smallest permutation of $$$S$$$ (i.e. the sorted string) not the answer?

**Solution**

If there are no occurrences of `a`

, `b`

or `c`

in $$$S$$$, sort $$$S$$$ and output it.

Else, if $$$T \ne$$$ `abc`

, sort $$$S$$$ and output it.

Else, output all `a`

, then all `c`

, then all `b`

, then the rest of the string sorted.

**Implementation (C++, I_Love_YrNameCouldBeHere)**

```
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
int main() {
int T;
cin >> T;
while(T--) {
string s, t;
cin >> s >> t;
sort(all(s));
vector<int> cnt(26, 0);
for(auto x: s)cnt[x - 'a']++;
if(t != "abc" || !cnt[0] || !cnt[1] || !cnt[2])cout << s << "\n";
else{
while(cnt[0]--)cout<<"a";
while(cnt[2]--)cout<<"c";
while(cnt[1]--)cout<<"b";
for(int i = 3;i < 26; ++i){
while(cnt[i]--)cout<<char('a' + i);
}
cout << "\n";
}
}
}
```

**Fun fact**

Originally, the author and two testers' solutions are all wrong, but we didn't notice until the third tester submitted the real correct solution.

**Hint**

There must exist a solution for $$$c=1$$$ under the given constraints.

**Solution**

Key observation: there always exists a solution with $$$c = 1$$$ under the given constraints. We set $$$n \ge 10$$$ because there is no solution when $$$1 \le n \le 5$$$ or $$$n = 7$$$.

Solution 1: Brute force from $$$a = 2, 3, 4, \dots$$$ and calculate the value of $$$b$$$ ($$$b = n - a - 1$$$), then check whether $$$gcd(a, b) = 1$$$. It works, because you will find a prime number $$$p \le 29$$$ such that $$$n-1$$$ does not divide $$$p$$$.

Solution 2: Randomly choose $$$a$$$ and calculate $$$b$$$ ($$$b = n - a - 1$$$). Repeating that for enough times will eventually get you a pair of ($$$a, b$$$) such that $$$gcd(a, b) = 1$$$.

Solution 3: Constructive solution.

When $$$n \equiv 0 \pmod 2$$$, output ($$$n-3, 2, 1$$$).

When $$$n \equiv 1 \pmod 4$$$, output ($$$\left \lfloor \frac{n}{2} \right \rfloor -1, \left \lfloor \frac{n}{2} \right \rfloor +1, 1$$$).

When $$$n \equiv 3 \pmod 4$$$, output ($$$\left \lfloor \frac{n}{2} \right \rfloor -2, \left \lfloor \frac{n}{2} \right \rfloor +2, 1$$$).

**Implementation (Solution 1, Java, SecondThread)**

```
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.Scanner;
public class B {
public static void main(String[] args) {
Scanner fs = new Scanner(System.in);
int T=fs.nextInt();
for (int tt=0; tt<T; tt++) {
int n=fs.nextInt();
for (int target=2; true; target++) {
if (gcd(n-1-target, target)!=1)
continue;
System.out.println(n-1-target+" "+target+" "+1);
if (n-1-target<=1) throw null;
break;
}
}
}
static int gcd(int a, int b) {
return b==0?a:gcd(b, a%b);
}
static void sort(int[] a) {
ArrayList<Integer> l=new ArrayList<>();
for (int i:a) l.add(i);
Collections.sort(l);
for (int i=0; i<a.length; i++) a[i]=l.get(i);
}
}
```

**Implementation (Solution 2, C++, dbsic211)**

```
#include <bits/stdc++.h>
using namespace std;
mt19937 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
void solve(int tc) {
int n;
cin >> n;
while(1) {
int k = uniform_int_distribution<int>(2, n-2)(rng);
int l = n-k-1;
if(k != l && k != 1 && l != 1 && gcd(k, l) == 1) {
cout << k << ' ' << l << ' ' << 1 << endl;
break;
}
}
}
int main() {
int t;
cin >> t;
for(int i=1; i<=t; i++) {
solve(i);
}
}
```

**Implementation (Solution 3, C++, anthony123)**

```
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n;
cin>>n;
if (n%2==0) cout<<"2 "<<(n-1)-2<<" 1\n";
else {
int cur=(n-1)/2;
if (cur%2==0) cout<<cur-1<<" "<<cur+1<<" "<<1<<endl;
else cout<<cur-2<<" "<<cur+2<<" "<<1<<endl;
}
}
signed main(){
int t;
cin>>t;
while (t--) solve();
}
```

1617C - Paprika and Permutation

**Hint 1**

For any two positive integers $$$x$$$, $$$y$$$ that satisfy $$$x \ge y$$$, what is the maximum value of $$$x \bmod y$$$?

**Hint 2**

Consider the following input: $$$n = 4$$$, $$$a = [3, 3, 10, 10]$$$. Sometimes, we don't need to do anything to some $$$a_i$$$. When do we have to make operations, and when do we not have to?

**Solution**

Key observation: $$$x \bmod y < \frac{x}{2}$$$ if $$$x \ge y$$$, and $$$x \bmod y = x$$$ if $$$x < y$$$.

Notice that the bigger the $$$x$$$, the bigger the range of values that can be obtained after one $$$\bmod$$$ operation. So, intuitively, we want to assign smaller $$$a_i$$$ to smaller numbers in the resulting permutation.

However, if $$$a_i$$$ satisfies $$$1 \le a_i \le n$$$, we can just leave it there and use it in the resulting permutation (if multiple $$$a_i$$$ satisfy $$$1 \le a_i \le n$$$ and have the same value, just choose one). Let's suppose in the optimal solution, we change $$$x$$$ to $$$y$$$ and change $$$z$$$ to $$$x$$$ for some $$$z > x > y$$$ ($$$x$$$, $$$y$$$, $$$z$$$ are values, not indices). Then changing $$$x$$$ to $$$x$$$ (i.e. doing nothing) and changing $$$z$$$ to $$$y$$$ uses $$$1$$$ less operation. And, if it is possible to change $$$z$$$ to $$$x$$$, then it must be possible to change $$$z$$$ to $$$y$$$. However, if it is not possible to change $$$z$$$ to $$$x$$$, it might still be possible to change $$$z$$$ to $$$y$$$.

Therefore, the solution is as follows: Sort the array. For each element $$$i$$$ in the sorted array:

If $$$1 \le a_i \le n$$$ and it is the first occurrence of element with value $$$a_i$$$, leave it there.

Else, let the current least unassigned value in the resulting permutation be $$$m$$$, if $$$m < \frac{a_i}{2}$$$, we can assign the current element to value $$$m$$$ and add the number of operations by $$$1$$$. Else, output $$$-1$$$ directly.

The solution works in $$$O(n \log n)$$$.

**Implementation (C++, physics0523)**

```
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t>0){
t--;
int n;
cin >> n;
set<int> st;
for(int i=1;i<=n;i++){st.insert(i);}
vector<int> rem;
for(int i=0;i<n;i++){
int v;
cin >> v;
if(st.find(v)!=st.end()){st.erase(v);}
else{rem.push_back(v);}
}
sort(rem.begin(),rem.end());
reverse(rem.begin(),rem.end());
int pt=0;
bool err=false;
for(auto &nx : rem){
auto it=st.end();
it--;
int ctg=(*it);
if(ctg>(nx-1)/2){err=true;break;}
st.erase(it);
}
if(err){cout << "-1\n";}
else{cout << rem.size() << '\n';}
}
return 0;
}
```

1617D1 - Too Many Impostors (easy version)

**Hint 1**

The weird constraint, $$$\frac{n}{3} < k < \frac{2n}{3}$$$, is crucial.

**Hint 2**

If you know the index of one crewmate and one impostor, how to find the roles of other $$$n-2$$$ players in exactly $$$n-2$$$ queries?

**Hint 3**

Query players ($$$1, 2, 3$$$), ($$$2, 3, 4$$$), $$$\dots$$$, ($$$n-1, n, 1$$$), ($$$n, 1, 2$$$). After that, you can surely find out the index of one crewmate and one impostor. Try to find out how.

**Solution**

Key observation: if result of query ($$$a, b, c$$$) $$$\ne$$$ result of query ($$$b, c, d$$$), since $$$b$$$ and $$$c$$$ are common, players $$$a$$$ and $$$d$$$ have different roles. Additionally, if result of query ($$$a, b, c$$$) = $$$1$$$ then player $$$a$$$ is a crewmate (and player $$$d$$$ is an impostor), vice versa.

The first step is to query players ($$$1, 2, 3$$$), ($$$2, 3, 4$$$), $$$\dots$$$, ($$$n-1, n, 1$$$), ($$$n, 1, 2$$$).

If the results of any two adjacent queries (or queries ($$$1, 2, 3$$$) and ($$$n, 1, 2$$$)) are different, we instantly know the roles of the two players that are only included in one query — one is a crewmate, one is an impostor. Since the number of impostors $$$k$$$ and crewmates $$$n-k$$$ satisfy $$$k > \frac{n}{3}$$$ and $$$n - k > \frac{n}{3}$$$, there must be one pair of adjacent queries that are different.

After we know one crewmate and one impostor (let's call them $$$a$$$, $$$d$$$), we can query these two players with each one of the rest of the players. If a query ($$$a, d, x$$$) ($$$1 \le x \le n$$$, $$$x \ne a$$$ and $$$x \ne d$$$) returns $$$0$$$, player $$$x$$$ is an impostor, else player $$$x$$$ is a crewmate.

In total, $$$2n-2$$$ queries are used.

**Implementation (C++, dbsic211)**

```
#include <bits/stdc++.h>
using namespace std;
void solve() {
int N;
cin >> N;
int res[N];
for(int i=0; i<N; i++) {
cout << "? " << i + 1 << " " << (i+1) % N + 1 << " " << (i+2) % N + 1 << endl;
cin >> res[i];
}
vector<int> imp;
for(int i=0; i<N; i++) {
if(res[i] != res[(i+1) % N]) {
if(res[i] == 0) imp.push_back(i + 1);
else imp.push_back((i+3) % N + 1);
for(int j=0; j<N; j++) {
if(j != i && j != (i+3) % N) {
cout << "? " << i + 1 << " " << (i+3) % N + 1 << " " << j + 1 << endl;
int r;
cin >> r;
if(r == 0) imp.push_back(j + 1);
}
}
break;
}
}
cout << "! " << imp.size();
for(int x : imp) cout << " " << x;
cout << endl;
}
int main() {
int T;
cin >> T;
for(int i=1; i<=T; i++) {
solve();
}
}
```

1617D2 - Too Many Impostors (hard version)

Thanks must be given to arvindf232 and generic_placeholder_name for the solution.

**Hint 1**

Aim to find an impostor and a crewmate's index in $$$\frac{n}{3} + c$$$ queries, with $$$c$$$ being a small constant.

**Hint 2**

Consider splitting the $$$n$$$ players into groups of $$$3$$$ (and query each group) in order to reach the goal in Hint 1. What is special about the results of the $$$\frac{n}{3}$$$ queries?

**Solution (Step 1)**

Firstly query ($$$1, 2, 3$$$), ($$$4, 5, 6$$$), $$$\dots$$$, ($$$n-2, n-1, n$$$). Due to the constraint $$$\frac{n}{3} < k < \frac{2n}{3}$$$, among the results of these $$$\frac{n}{3}$$$ queries, there must be at least one $$$0$$$ and one $$$1$$$. Now, let's call a tuple ($$$a, b, c$$$) that returns $$$0$$$ a $$$0$$$-majority tuple, and vice versa.

From the easy version, notice that finding one crewmate and one impostor is very helpful in determining the roles of the remaining players. Let's make use of the above observation, and pick one adjacent $$$0$$$-majority tuple and $$$1$$$-majority tuple.

Let's say we picked ($$$i, i+1, i+2$$$) and ($$$i+3, i+4, i+5$$$). Then, we query ($$$i+1, i+2, i+3$$$) and ($$$i+2, i+3, i+4$$$). Among the four queries ($$$i, i+1, i+2$$$), ($$$i+1, i+2, i+3$$$), ($$$i+2, i+3, i+4$$$), ($$$i+3, i+4, i+5$$$), there must be a pair of adjacent queries with different results. From the easy version, we can directly find the index of an impostor and a crewmate.

In all the above cases, we end up knowing an impostor and a crewmate using $$$\frac{n}{3} + 2$$$ queries, including the first step.

**Hint 3**

You have the index of an impostor and a crewmate now, and around $$$\frac{2n}{3}$$$ queries left.

Consider using at most $$$2$$$ queries to find out roles of each player in each group of $$$3$$$ from Step 1, which should add up to $$$\frac{2n}{3}$$$ queries.

Make use of the information you know about each group (whether it is $$$0$$$-majority or $$$1$$$-majority).

**Hint 4**

Assume a tuple (group of $$$3$$$) is $$$0$$$-majority. There are $$$4$$$ possibilities of roles of the $$$3$$$ players in the tuple, which are:

impostor, impostor, impostor

crewmate, impostor, impostor (and its permutations)

In each query, reduce half of the possibilities.

**Solution (Step 2)**

It remains to figure out how we can find the roles of the remaining players using $$$\frac{2n}{3}$$$ queries. For each tuple ($$$i, i+1, i+2$$$) queried in the first step, let's assume the tuple is $$$0$$$-majority (because the other case can be solved similarly). Then, there are only four possibilities:

All players $$$i$$$, $$$i+1$$$, $$$i+2$$$ are impostors.

Player $$$i$$$ is a crewmate, players $$$i+1$$$, $$$i+2$$$ are impostors.

Player $$$i+1$$$ is a crewmate, players $$$i$$$, $$$i+2$$$ are impostors.

Player $$$i+2$$$ is a crewmate, players $$$i$$$, $$$i+1$$$ are impostors.

Earlier, we found the index of a crewmate and an impostor, let the index of the crewmate be $$$a$$$ and the impostor be $$$b$$$.

If the tuple ($$$i, i+1, a$$$) is $$$1$$$-majority, either player $$$i$$$ or player $$$i+1$$$ is a crewmate. So, we reduced the number of possibilities to $$$2$$$. To check which player is the crewmate, query it with $$$a$$$ and $$$b$$$ like we did in the easy version.

Else, either there are no crewmates or player $$$i+2$$$ is a crewmate. So, we reduced the number of possibilities to $$$2$$$. To check the role of player $$$i+2$$$, query it with $$$a$$$ and $$$b$$$ like we did in the easy version.

In both cases, we use $$$2$$$ queries for each initial tuple ($$$i, i+1, i+2$$$). So, we used $$$n + 2$$$ queries in total, but we gave you a bit more, in case you used some more queries to find a crewmate and an impostor.

There is one corner case we should handle: if the tuple ($$$i, i+1, i+2$$$) contains $$$a$$$ or $$$b$$$, we can just naively query for each unknown role in the tuple, since we won't use more than $$$2$$$ queries anyway.

**Implementation (C++, dbsic211)**

```
#include <bits/stdc++.h>
using namespace std;
int query(int a, int b, int c) {
cout << "? " << a << ' ' << b << ' ' << c << endl;
int r; cin >> r;
return r;
}
void solve(int tc) {
int n; cin >> n;
int a[n+1], role[n+1];
for(int i=1; i+2<=n; i+=3) a[i] = query(i, i+1, i+2);
int imp, crew;
for(int i=1; i<=n; i++) role[i] = -1;
for(int i=1; i+5<=n; i+=3) {
if(a[i] != a[i+3]) {
a[i+1] = query(i+1, i+2, i+3), a[i+2] = query(i+2, i+3, i+4);
for(int j=i; j<i+3; j++) {
if(a[j] != a[j+1]) {
if(a[j] == 0) {
imp = j, crew = j+3;
role[j] = 0, role[j+3] = 1;
}
else {
imp = j+3, crew = j;
role[j+3] = 0, role[j] = 1;
}
}
}
break;
}
}
for(int i=1; i+2<=n; i+=3) {
if(i == imp || i+1 == imp || i+2 == imp || i == crew || i+1 == crew || i+2 == crew) {
for(int j=i; j<i+3; j++) {
if(role[j] == -1) {
role[j] = query(imp, crew, j);
}
}
}
else if(a[i] == 0) {
if(query(i, i+1, crew) == 1) {
if(query(i, imp, crew) == 0) role[i] = 0, role[i+1] = 1;
else role[i] = 1, role[i+1] = 0;
role[i+2] = 0;
}
else {
role[i] = role[i+1] = 0;
role[i+2] = query(i+2, imp, crew);
}
}
else {
if(query(i, i+1, imp) == 0) {
if(query(i, imp, crew) == 0) role[i] = 0, role[i+1] = 1;
else role[i] = 1, role[i+1] = 0;
role[i+2] = 1;
}
else {
role[i] = role[i+1] = 1;
role[i+2] = query(i+2, imp, crew);
}
}
}
cout << "! ";
queue<int> q;
for(int i=1; i<=n; i++) if(role[i] == 0) q.push(i);
cout << q.size();
while(q.size()) {
cout << " " << q.front();
q.pop();
}
cout << endl;
}
int main() {
int T; cin >> T;
for(int i=1; i<=T; i++) solve(i);
}
```

**Hint 1**

Translate the problem into a graph problem. What feature of the graph is it asking about?

**Hint 2**

Draw out the graph, for $$$a_i \le 10$$$. What special property does the graph have?

**Hint 3**

Any specific algorithm to solve the problem (in Hint 1)?

**Solution (Step 1)**

In graph terms, the problem is as follows: in a graph with infinite nodes, two nodes $$$x$$$ and $$$y$$$ are connected if $$$x + y = 2^k$$$ for some $$$k \ge 0$$$. Among $$$n$$$ special nodes, find the pair of nodes ($$$i, j$$$) with maximum shortest distance.

Here comes the key observation: For any $$$i \ge 1$$$, there exists only one $$$j$$$ ($$$0 \le j < i$$$) such that $$$i + j = 2^k$$$ for some $$$k \ge 0$$$.

The proof is as follows: let's say that $$$0 \le j_1, j_2 < i$$$, $$$j_1 \ge j_2$$$, $$$i + j_1 = 2^{k_1}$$$, $$$i + j_2 = 2^{k_2}$$$. Then, $$$j_1 - j_2 = 2^{k_2} \cdot (2^{k_1-k_2} - 1)$$$. So, $$$j_1 \equiv j_2 \pmod {2^{k_2}}$$$. Since $$$i \le 2^{k_2}$$$, $$$j_1 = j_2$$$.

Then, we realize we can build a graph as follows: add an edge between $$$x$$$ and $$$y$$$ ($$$x, y \ge 0$$$) if $$$x + y = 2^k$$$ for some $$$k \ge 0$$$. Because of the first key observation, the graph must be **a tree**. We can root the tree at node $$$0$$$.

Our problem is equivalent to finding the pair of nodes which have maximum distance in a tree, which can be solved using the diameter of tree algorithm.

**Hint 4**

We can't build the entire tree as it has $$$10^9 + 1$$$ nodes. Try to notice something about the depth of the tree, then think of how this could help us solve the problem (by building the tree, or otherwise).

**Solution (Step 2)**

Since $$$0 \le a_i \le 10^9$$$, it is impossible to build the entire tree. A final observation is that: Consider any node $$$v$$$ with degree $$$\ge 2$$$ in the tree, then $$$v > p_v$$$ and $$$p_v > p_{p_v}$$$, therefore $$$v + p_v > p_v + p_{p_v}$$$ ($$$p_x$$$ denotes the parent of node $$$x$$$ in the tree).

Hence the depth of the tree is $$$\lceil \log(max(a_i)) \rceil = 30$$$, since there are only $$$\lceil \log(max(a_i)) \rceil$$$ possible $$$k$$$ ($$$0 \le k < 30$$$) for the sum of two nodes connected by an edge.

So, there are two ways to do it: the first way is to build parts of the tree: only the $$$n$$$ given nodes and the ancestors of the $$$n$$$ nodes. There will be at most $$$O(n \log max(a_i))$$$ nodes, which should fit into the memory limit. The second way is to not build the tree at all, and calculate the LCA (Lowest Common Ancestor) of two nodes to find their distance. Since the depth of the tree is $$$30$$$, LCA of two nodes can be computed by simply checking every ancestor of both nodes.

In both ways, the time complexity is $$$O(n \log max(a_i))$$$.

**Implementation (C++, physics0523)**

```
#include<bits/stdc++.h>
using namespace std;
int f(int x){
for(int i=0;;i++){
if((1<<i)>=x){
return (1<<i)-x;
}
}
}
using pi=pair<int,int>;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
map<int,pair<pi,pi>> mp;
priority_queue<int> pq;
for(int i=0;i<n;i++){
int v;
cin >> v;
pq.push(v);
mp[v].first=make_pair(0,i+1);
}
while(!pq.empty()){
int od=pq.top();pq.pop();
if((!pq.empty()) && od==pq.top()){continue;}
if(od!=1){
int nx=f(od);
pq.push(nx);
pi send=mp[od].first;
send.first++;
if(mp[nx].first<send){
mp[nx].second=mp[nx].first;
mp[nx].first=send;
}
else if(mp[nx].second<send){mp[nx].second=send;}
}
}
int ra=0,rb=0,rc=-1;
for(auto &nx : mp){
pair<pi,pi> tg=nx.second;
if(tg.first.second==0 || tg.second.second==0){continue;}
if(rc<tg.first.first+tg.second.first){
rc=tg.first.first+tg.second.first;
ra=tg.first.second;
rb=tg.second.second;
}
}
cout << ra << ' ' << rb << ' ' << rc << '\n';
return 0;
}
```

ooh fast editorial :)

dbsic211 orz

Wow it's amazingly fast editorial :D.

anthony123 orz

omg fast editorial

As lck, I am offended by your template :(

Bad Kevin, I will throw you into River Cam when u arrive at Cambridge

Today B screwed me.

It was easy but very observational, if you can observe quick it's pretty easy otherwise it screws.

There must exist a solution for c=1 under the given constraints.

I still don't exactly see why that is the case....

Assume $$$c = 1$$$, you are left with $$$n - 1$$$ which must be divided in two groups, $$$a$$$ and $$$b$$$.

Dividing by $$$2$$$ will either equally distribute the amount or it won't.

In the second case, one value will always be $$$+1$$$ than the other and $$$gcd$$$ of two consecutive numbers is $$$1$$$.

In the first case, both numbers will either be odd or even. If both numbers are even then simply subtract $$$1$$$ from one value and add it to the second value, by doing this both numbers will be odd now with a difference of $$$2$$$, hence $$$gcd = 1$$$. If both numbers are odd, subtract $$$2$$$ from one value and add it to the other value. By doing this you will have two odd numbers with a difference of $$$4$$$, hence $$$gcd = 1$$$

Maybe this is a complicated way to think about it but that's how I did it

How to prove two odd numbers are mutually prime with a difference of 4 between them ?

if the difference between the two numbers is 4,their gcd cannot be greater than 4.now since the numbers are odd 2 and 4 won't divide them.so now we are left with 1 and 3.let's say the gcd is 3 so it divides the smaller number x the next numbers it will divide will be x+3,x+6 but our second number is x+4. so 1 is their gcd.

gcd(x+4, x) = gcd(x+4-x, x) = gcd(4, x) but x is odd => gcd(4, x) = 1

Nice, thanks for the explanation!

When it comes to proving that there exists a pair $$$(a, b)$$$ for $$$c=1$$$ which solves the problem one can use Goldbach's conjecture (which was shown to work for numbers $$$\leq 10^{18}$$$). If $$$n-1$$$ is odd then it's easy to see that we can choose $$$a=x$$$ and $$$b=x+1$$$ where $$$x=\frac{n}{2}-1$$$, but when $$$n-1$$$ is even GC gives us that there exist 2 primes $$$p, q$$$ such that $$$p+q=n-1$$$.

Thanks your explanation was lucid and simple .I was able to frame the solution and am sure it will be helpful in upcoming problems. May God bless you with more ratings

Great contest! I especially enjoyed solving problem D, thanks :)

In D1, the difference between "<=,>=" and "<,>" changes everything...

Great contest! Great problems! Great editorial! Sad orange can’t play._.

Lightening fast editorial :)

Time complexity of editorial: O(1)

In the solution of problem C, the observation will be $$$x$$$ $$$mod$$$ $$$y$$$ $$$< \lceil \frac{x}{2} \rceil$$$ if $$$x$$$ $$$>=$$$ $$$y$$$

Problems were good and so the quality of the editorial. All editorials should have hint spoilers.

I like how the author split the editorial into hints, solutions, and code snippets, and had them spoilered separately, which would be helpful for beginners who are learning cp;) (But it’s also extra effort, so I wouldn’t go as far as to ask for having this in particular, rather, I’ll just treat it as a bonus)

As a tester, I have some fun facts about problem D:

Originally, D had only one version, which is the current D1. Then I tested D and came up with a $$$\frac{4n}{3} + O(1)$$$ query solution. (Actually, originally, $$$n \bmod 3 = 0$$$ wasn't a thing, and the lower bound was $$$4$$$, so getting that to AC was a lot of pain :v) That solution became D2 — except that later, arvindf232 came up with the $$$n + 2$$$ query solution. Then we had a problem, which was that we couldn't decide which of $$$2n$$$, $$$\frac{4n}{3}$$$, or $$$n$$$ should be the official D1/D2. In the end we decided that $$$2n$$$ for D1 and $$$n + O(1)$$$ for D2 would be best for balance.

We (or at least I) thought that D2 was more difficult than it ended up being. We had the idea of changing the distribution to 1750-1250-2500, but it never came to pass. In my opinion, the original distribution turned out to be better. :v

I'm curious, how many participants actually proved their solution of B?

EDIT: I'm not looking for proofs of this solution or that solution. I'm more interested in the ratio of "guessed/hoped" vs "solved". Actually in some sense it's more interesting to hear from people who didn't prove their solution.

Ya, i have prrof for my solution. By choosing c = 1, the problem can be proved by checking even or odd of number and its half. submission: https://codeforces.com/contest/1617/submission/139495888

The 3-case people probably proved their solution, but probably most other solutions didn't :v My "proof" was a vague understanding of probability and a heavy dose of inshallah :)

Me. I used the approach of finding the first prime that does not divide n — 1, which must exist within the first 10 primes since n is at most 1e9.

if n-1 is odd then answer is some consecutive number but if it is even, by goldbach's conjecture it follows that it can be written as a sum of two primes.

I proved it but I think it's hackable. Solution Link

I did the same thing.

You can check it here

Ummm Yes, I can prove my solution

It took me 44 mins on B just to prove that a brute force soln works and in the end i coded the entire proof lol .When i was a newbie i used to solve these type of questions pretty fast but as my experience increased i started proving things haha.Anyways i liked the contest very much

i assumed the gcd is 1 because otherwise the complexity would be exponential then i made a program that told me how many numbers can be obtained from x%y with 1<=y<x and those were all from 1 to (x-1)/2 so i kind of proved it

139546379 I don't know why I get TLE on D2, I think my time complexity is $$$O(n)$$$.

Edit: I know where was wrong. I didn't handle the case when query return -1

Thank you so much!!!

Can we do D2 in $$$\leq n$$$ queries?

It can be done is $$$n + 1$$$ by reducing $$$1$$$ query from the editorial's solution using the fact that the two people between the impostor and crewmate we detected, are of opposite type, so we can just ask for one of them.

I don’t think $$$< n$$$ is possible, but exactly $$$n$$$ queries is possible (tho idk how)

There are around $$$2^n$$$ possible answers, and each queries gives a binary answer. So the theoretical lower bound is $$$\log_2(2^n)=n$$$ queries.

(nevermind, I was wrong here.)

I don't think this works in all cases. If the different 3-tuples occur somewhere in between, we will need $$$n+1$$$ queries still.

Yes, with this way it is mathematically impossible to get exactly $$$n$$$ queries. If there is a $$$n$$$ query solution it won't be this one.

Nice problems great editorial with hints. overall great contest!!! Well done dbsic211.

Was totally confused at C. Luckily understood the meaning of k range to solve D1 and that saved my rating for this contest or else whoooooosh it would have gone

Problem D in n+1 queries: 139550123

Can you explain your solution :)

How to think the solution of problem B during the contest....

Actually, first observation is gcd(a,b)=c so a=cx and b=cy where x and y are mutually prime. So the given equation becomes c*(x+y+1)=n . so c is a factor of n. Now you think that if n is a prime number, then it's only factors are 1 and the number itself. if c=the prime number itself, then x+y+1=1 ===> x+y=0 which is not possible according to the given problem. So c=1 for prime numbers. On the other hand the equation will be holding for composite numbers as well so, you can proceed with c=1. therefore the equation becomes x+y+1=n or x+y=n-1. Now, we have already said that x and y are mutually prime. So the immediate thing that should come to mind is that two consecutive numbers are equal . if n-1 is odd, then you should know that an odd number can be written always as a sum of two consecutive numbers (if x is odd, then x=x/2+x/2+1 ...x unrelated to the explanation above) . otherwise,n-1 is even, so a possibility is x=(n-1)/2 and y=(n-1)/2 . But x and y are coprime, so probably, we can go one step forward for y and one step backward for x .Then x=(n-1)/2 -1 and y=(n-1)/2+1 .Now if originally x and y were even numbers, then the new x and y must be odd numbers. These two odd numbers with a difference of one will always be coprime. Otherwise,if both new x and y are even, then decrease x one more time and increase y one more time .Again we end up with two odd numbers and these two with a difference of 4 will always be mutually prime .

Great problems, fast editorial with hints, I hope more of these contests will be held :)

Thanks dbsic211

Superfast editorial!

What's more, with hints!

I enjoy the contest very much, the problems are fabulous, thank you!

For anyone looking for video editorial you can check mine out

It's only up to D1 tho

Problems were nice, although I could try only up to D1.

Hoping to see you in another round :)

borked checker rejudge time

Can anyone tell me, for problem D1 why I am getting the

wrong answer verdicton Test Case 1?Any help would be appreciable. Thank you :)

Submission

You are only printing the elements of ans. You also need to print the size of ans before you print it's elements.

Thanks, buddy! Now my code is asking too many queries so can you or anyone tell me any optimal way to solve this question.

I spent too many queries just to find one crewmate and one imposter to get the answer so is there is any optimal way to find them?

You can read the editorial. It tells you how to find one crewmate and one imposter in exactly n queries.

SIUUU!

In problem B , why Brute force solution is working

Because there are only limited divisors of $$$n - 1$$$, which means that

eventuallythere are going to be two coprime numbers. There's some math that proves this, but ehh, nobody cares enough to prove it.because the gap of two prime number at most 300 in the range 10^12. so,when you picked up a big prime ,the other side is lower than prime.so there gcd is 1. for example, n=34,if we pick a prime 29,then the other side is (34-29)-1=4 so a=29,b=4 and gcd(29,4)=1.

My more complicated, less elegant solution to D1:

So in the worse path, we use (2n/3-1) + (n/3-1) + 2 + (n-4) = 2n queries.

Very nice trick to solve D2

can anyone help me with this code :

139558441

a lot of thanks to anyone who can help me

Try this test case:

Expected output is

`2`

, while your code produces`-1`

.my code produces 2 not -1

pic...

It's because you're not handling multiple test cases correctly. Just wrap this testcase with another one, and you can spot the error.

For example, on the input

your code produces

`-1 -1`

while the intended output is`-1 2`

.I understand now what's wrong with my code

SpoilerThanks a lot for the help

can someone please tell why this is giving me RTE on the first test case? it is working fine on my compiler https://codeforces.com/contest/1617/submission/139558421

I like the A question which made me an orgasm

can anyone please explain this? in problem B solution 3

`if (n%2==0) cout<<"2 "<<(n-1)-2<<" 1\n";`

It's just $$$a = 2, b = n-3, c = 1$$$. $$$n$$$ is even, so $$$n-3$$$ is odd, so it's coprime with $$$2$$$.

ohh got it

If you are interested in video solutions, here are the solutions for the first

4problems.Whyyyyy.... your mistake on E checker cost me 140 rating :(

-1000 social rating bad very bad :((((

.

5%4==1 5%3==2 9%6==3 14%10==4 5 is already left thus we can make a permutation in 4 moves. Hope this helps

I tried to hack my solution but I got "Unexpected verdict". Is there a problem with the solution to that problem?

The test is

2

7 9

The particular thing about that test is that the diameter of the tree shouldn’t consider the node 0, (just nodes 7 and 9 in this case) my solution didn’t consider that and that is the reason of the wrong answer. This happens when all the nodes in the input lie in the same path from the root to the farthest node. Please consider adding a similar test.

I've implemented the idea of D2 on D1(6 queries), but wasn't aware that same way I can solve D2. And i also missed the simple idea of D1!!

Nice Contest dbsic211

Fast editorial! Thanks!

Problem E is really nice, good job!

Is there anyone can solve D2 in n queries? I can just solve it in (n+1) queries!

I used Trie to solve E. Submission link

(I know it's overkill but the logic is somewhat different from the one in editorial)

Hey! Can you please explain what is the idea behind your solution?

for Problem D1,why we need query $$$(n-1,n,1)$$$ and $$$(n,1,2)$$$ ?

It seems that query $$$(1,2,3)$$$ to $$$(n-2,n-1,n)$$$ can find one pair of crewmate and impostor.

can give me a counter-example？= ^ =

Not needed, I coded without that query.

Can you help me see why my code got WA?139605367

Your code seems to count imposters twice.

Like this

15

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

I understand now what's wrong with my code

Thanks a lot for the help！

Could someone please tell me whats wrong with my d2 solution? I am getting the same output as testcase 1, but its showing "Incorrect set of impostors"?

Here's my code

`Since the number of impostors k and crewmates n-k satisfy k>n/3 and n−k>n/3, there must be one pair of adjacent queries that are different.`

Can someone explain why?

You know that n is divisible by 3. So you can split it into x intervals of 3 each, such that x*3=n. So assume x=n/3.

Now, k>n/3 =>k>x and k<2*x. so k belongs to [x+1,2*x).

Applying pigeon hole principle, you have x intervals and a minimum of x+1 impostors to fill, so at least one interval will have 2(or more) impostors.

With this, it wont be difficult to see that ~~~~~ for any n and k, that satisfy the constraints, the number of impostors k and crewmates n-k satisfy k>n/3 and n−k>n/3, there must be one pair of adjacent queries that are different. ~~~~~

According to the pigeon hole principle, As long as one adjacent 0-majority tuple and 1-majority tuple exists, there is exactly 4 cases of one kind of tuple.

0-major -> {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {1, 0, 0}; 1-major -> {1, 1, 1}, {1, 1, 0}, {1, 0, 1}, {0, 1, 1}.

for the {0-major} + {1-major} and {1-major} + {0-major} cases, brutally select each tuple, pair them up, try all 2 * (4 * 4) = 32 cases, we can see there will always be at least one 4-consecutive indices {id, id + 1, id + 2, id + 3} from all 6 places for each case, for which query {id, id + 1, id + 2} and query{id + 1, id + 2, id + 3} differs.

For example check 2 tuples {0 1 1} + {0 0 0}, start with the second index, {1 1 0 0} meets our need.

The method may be kind of tedious, I wonder if other elegant proofs exist.

In problem D, I wonder what "The jury is adaptive" means. Why there are still feedbacks of "wrong set of impostors"?

Problem D is pretty amazing. Loved to upsolve it.

Can anyone explain me the meaning of "FST","AK"?

failed on system test

solve all the problems in a contest

I have a solution to problem E which does not involve graphs in any way.

At the beginning, our array values fit in range $$$[0, 2^{30}]$$$. Let's now divide the array into two parts $$$L$$$ and $$$R$$$, where $$$L$$$ will contain all values $$$\le 2^{29}$$$ and $$$R$$$ will contain all larger values.

Now suppose $$$(x, y)$$$ is the optimal pair we are searching for. Here comes a crucial observation. If both $$$(x, y)$$$ are in $$$R$$$ they are both larger than $$$2^{29}$$$ so we cannot use any $$$k \le 29$$$ operation on them. The only way to continue is to use $$$k = 30$$$ and make them both less than $$$2^{29}$$$.

Also suppose $$$x \le 2^{29}$$$ and $$$y > 2^{29}$$$. In this case we have to transfer one value to the other side by using $$$k = 30$$$, but transferring $$$x$$$ is never optimal. Let's prove it.

Case $$$x = 2^{29}$$$ is trivial. Otherwise $$$x < 2^{29}$$$ so $$$2^{30} - x > 2^{29}$$$ and since also $$$y > 2^{29}$$$ we arrive at the previous state when we are forced to decrease both of them using $$$k = 30$$$. This means that it is always better to do an operation on $$$y$$$, again reducing it to some value $$$< 2^{29}$$$ and continue from there.

All the reasoning above means that all values $$$R$$$ have to be reduced in one operation to become less than $$$2^{29}$$$ and after that we can merge those values with $$$L$$$ and repeat our algorithm again with a threshold $$$2^{29}$$$.

We can repeat this process until we arrive at a simple case when all values are in range $$$[0, 1]$$$. Here we can just consider a transition $$$0 \rightarrow 1$$$ and we are done.

This solution can be implemented in various ways. One I can think of is to store $$$L$$$ and $$$R$$$ as sorted vectors and merge them using two pointers. But I personally think that maps are the most simple and elegant way. Maps introduce an additional $$$\log n$$$ factor, resulting in a $$$O(n \log n \log 10^9)$$$ solution overall which is still fast enough considering a very generous time limit.

Here is my submission: https://codeforces.com/contest/1617/submission/139683868

[My Submission](https://codeforces.com/contest/1617/submission/139840155

Can someone tell me why my code to Problem D1 is getting Idleness limit exceeded even though I flushed wherever required. Thanks in advance.

You are flushing after cin , flush after cout. Tip : Use endl.

Sorry if it's obvious, but why is the graph formed in E connected? I see that there are no cycles but how do we know that we can get from any $$$x$$$ to any $$$y$$$?

Any number can reach 0, and 0 can reach any number.

I think this is not the intended solution for 1617B - GCD Problem...

Link : 141021665

can someone tell me why i am getting WA on testcase 2 in this solution : https://codeforces.com/contest/1617/submission/141883310

Can anyone tell me what's wrong with my code? I've coded differently, but the approach is same as given for problem C.

142936588

Solution with TC O(N):142954118

In Problem C, According to Editorial Solution I found

-1as output when I providearray = {1, 2, 7, 8}as Input. But here the output should be2. Like forarray[3] = 7we can choosex = 3and7 % 3i.e. 4lies in[1, n],similarly forarray[4] = 8we can choosex = 5and8 % 5 i.e. 3 lies in [1, n].hence we can obtain the permutation as{1, 2, 4, 3}which should be acceptable. May be I am wrong if anyone found the proper solution please reply ASAP.$$$7 \% 3$$$ is $$$1$$$ not $$$4$$$, since the remainder when $$$7$$$ is divided by $$$3$$$ is $$$1$$$.

Really, Great Editorial :)

There exists a completely different and overcomplicated reasoning for the solution of problem E:

Notations:

Firstly, let's visualize the effects of an operation $$$x = 2^k - x$$$ on the binary representation of integer $$$x$$$.

the operation is essentially equivalent to flipping the bits in the range $$$[k + 1, lsb(x))$$$ of the binary representation of $$$x$$$.ObservationsObservation 1: $$$lsb(x)$$$ changes only in the trivial case or when $$$x = 0$$$. $$$\therefore$$$ For some sequence of operations $$$S$$$, which converts $$$x$$$ to $$$x'$$$ such that $$$lsb(x) \neq lsb(x')$$$, $$$x$$$ must become equal to $$$0$$$ after some operation in $$$S$$$.Now, in the binary representation of any integer $$$x$$$, observe the positions $$$i > lsb(x)$$$ such that $$$bit_i \neq bit_{i + 1}$$$. Let's call these positions "special positions" (green links):

Observation 2: Any operation on an integer $$$x$$$ with $$$2^k$$$ (except the trivial case where $$$x = 2^k$$$), corresponds to either removing the leftmost special position, or introducing a new special position to the left of the current leftmost special position.Basically, the special positions can be viewed as a stack, you can either add an element on top which is less than the current top element, or pop the top element.Observation 3: The minimum number of moves to reduce any integer $$$x$$$ to $$$0$$$ is equal to ($$$1$$$ + the number of special positions in its binary representation).Proof0 doesn't contain any special positions. The minimum number of moves to make a stack empty is = the size of the stack. Finally, we require one more move as $$$lsb(x)$$$ will still be set after we remove all the special positions.

Observation 4: The minimum number of moves to convert $$$x \rightarrow y$$$ is equal to the minimum number of moves to convert $$$y \rightarrow x$$$.ProofWe can simply perform all operations in a reversed manner.

Optimal strategy for making two arbitrary integers equalNow, let's try and come up with an optimal strategy for making two arbitrary integers $$$x$$$ and $$$y$$$ equal. Assume WLOG that $$$x < y$$$:

Case 1$$$(lsb(x) \neq lsb(y))$$$ :Claim: It is never sub-optimal to convert both $$$x$$$ and $$$y$$$ to $$$0$$$.ProofLet's assume there exists another final integer $$$z$$$ such that converting ($$$x \rightarrow z$$$ and $$$y \rightarrow z$$$) is more optimal than ($$$x \rightarrow 0$$$ and $$$y \rightarrow 0$$$)

Thus the minimum number of operations = (1 + number of special positions of x) + (1 + number of special positions of y).Case 2($$$lsb(x) = lsb(y)$$$): Finding the minimum number of moves to make both $$$x$$$ and $$$y$$$ equal is equivalent to the minimum number of push/pop operations to make two stacks equal (because performing operations $$$x = 2^k - x$$$ is equivalent to performing push/pop operations on a stack of their special positions). It is easy to see that the optimal way to do so is pop only those elements from the stacks which lie outside their common prefix.Thus the minimum number of operations = (number of special positions of x) + (number of special positions of y) — 2 * (longest common prefix in a list of their special positions).Finding the two integers which require the maximum number of moves to equalizeFor an integer $$$x$$$, among all integers $$$y$$$ with $$$(lsb(x) \neq lsb(y))$$$ it's always optimal to choose $$$y$$$ with the maximum number of special positions. So, we can simply maintain the integer with maximum number of special positions for each $$$lsb$$$, and simply check all of these, in $$$O(log{n})$$$ time for each $$$x$$$.

For an integer $$$x$$$, among all integers $$$y$$$ with $$$(lsb(x) = lsb(y))$$$ it's always optimal to choose $$$y$$$ with maximum value of ((number of special positions of $$$y$$$) — $$$2$$$ * (longest common prefix in a list of special positions of $$$x$$$ and $$$y$$$)). This can be easily done with the help of a trie. Note that this trie might not fit into the memory limit of 512 mb as it will require almost $$$O(n\log^2{n})$$$ memory. So, we can instead not build the trie at all, and just perform a dfs on it virtually.

Implementation: link